Web3D引擎中三維圖形對象拾取的算法與實現

陳 煜 ， 林 瑋

（1.南京工業職業技術學院，江蘇 南京210046；2.南京航空航天大學，江蘇 南京 210016；3.南京樂游游軟件科技有限公司，江蘇 南京 210000）

近年來虛擬現實技術的迅猛發展，以及計算機計算能力的提高，使3D技術得到了很大的發展，已經出現了幾十種之多，常見的有：cult3D，Pulse3D，ShockWave3D等[1-3]。這些引擎具有三維效果逼真的優點，然而應用于Web時，會出現下載速度慢以及需要額外下載插件等問題。idx3D，3DzzD等開源引擎采用JAVA技術，此類引擎具有不需要特殊硬件實現3D效果，用戶在使用時也不需額外下載插件等優越性。由于在互聯網上要實現三維圖形的展示以及漫游等功能，三維圖形對象的拾取功能必不可少。但是，目前這些引擎均未實現對特定對象的拾取功能，這就大大限制了人機交互的實現。

本文提出了射線分層次求交算法，首先采用包圍盒算法來實現對選擇對象的快速拾取，然后，為解決包圍盒求交時過分拾取的問題，采用三角形算法來實現對對象的準確拾取。在提出算法的基礎上，實現了用JAVA語言，在開源Web3D引擎 idx3D上對所選圖形對象的拾取功能的開發。

1 圖形的三維顯示和拾取的基本原理

1.1 圖形在屏幕上的三維顯示

要將現實世界的物體以立體的視覺效果在計算機顯示器上顯示出來，需要進行渲染管線的處理[4-6]。通常需要先建立3D場景以及設置虛擬攝像機，根據攝像機所能看到的圖形效果，將整個場景轉換成2D的圖像顯示在顯示器上，這個過程就是渲染管線。其流程如圖1所示。本地空間可以方便各物體的建模，在建模后，需要將各物體的自身坐標變換成統一的世界空間下的世界坐標。將虛擬攝像機移至世界坐標的原點時，則形成了視圖空間，此時各物體的坐標也需變換形成視圖空間坐標，這個過程為視圖空間變換。在視圖空間中把3D場景轉化為2D圖像，這一過程被稱為投影。投影可分為平行投影和透視投影[4]，而透視投影又可分為一點透視，二點透視和三點透視，在圖形學中一點透視投影被廣泛使用。將投影空間中通過透視形成的視錐體或稱平頭截體，進行規格化，也就是簡化成立方體，則形成圖像空間。在此，為了簡化問題，將圖像空間并入投影空間。視口是屏幕上一個矩形區域，視口變換就是把投影窗口變換為視口。3D物體的模型是由若干個三角形堆砌而成，將這些三角形的每個頂點轉換到屏幕上就形成了2D圖像，這個過程被稱為光柵化。

1.2 拾取的基本原理

無論是在虛擬現實、動漫制作還是工業設計等領域，拾取的過程可以看成是渲染的逆運算。比較通用的基本原理[5-10]大多可以歸納為如下步驟：

圖1 三維圖形的顯示過程

（1）將屏幕上鼠標點擊點的二維坐標，轉化為投影空間內的三維坐標。

（2）再將此三維坐標進行轉換至視圖空間，設這個點為P1。從虛擬攝像機的所在位置，即視圖空間的原點到 P1就是視圖空間下的射線，此時的P1表示有方向的向量。

（3）然后，再將視圖空間中的射線，變換到世界空間中，射線可表示為P (t ) = P0+ tP1。該變換由視圖變換的逆運算來完成。

（4）將各對象由包圍體包圍起來，射線與包圍體求交，若相交則表示該圖形被拾取。

2 拾取算法

在1.2節中介紹的方法基礎上，本文結合Web3D引擎的特點，提出并實現了射線的分層次求交算法來提高拾取的效率。在 Web3D中三維圖形的模型是用三角形網格來描述的[7]，也就是說一個三維圖形的模型是由若干個三角形堆砌而成的。所謂的分層次求交算法的思想是：第一步，先以盡量少的計算量確定可能的拾取對象，本文提出射線與包圍盒求交法以快速確定拾取范圍。由于各三維圖形的形狀往往并不規則，在包圍盒的范圍內，有些點并不屬于圖形對象，作者稱這種現象為過度拾取。為了解決過度拾取的問題，第二步，在包圍盒的范圍內，遍歷三角形，將射線與三角形求交，以此來精確拾取圖形。

2.1 獲得射線的矢量

要進行拾取，首先要獲得射線的矢量。圖2是相同的點在不同空間中的示意圖。左圖中的鼠標點擊點M (x, y)，在投影空間中所對應的點為中圖內的點 proj, 該點在視圖空間中對應的點為view, view為在近裁剪面上的點。視圖空間中的原點，和屏幕空間上鼠標點在視圖空間內的對應點構成視圖空間下的射線，為實現拾取功能，還需將射線變換至世界空間下。要獲得射線要進行以下的一系列變換：

圖2 鼠標點在各空間中的對應示意圖

（1）屏幕上鼠標點的坐標轉換至投影空間的坐標

具體方法為：將鼠標點的坐標轉換為投影窗口也就是投影空間中近裁剪面上的坐標，再確定表示深度的Z軸的值，為計算方便取Z軸的值為0，如圖2的中圖所示。

屏幕的原點在左下角，而近裁剪面的原點在中心位置，又因為近裁剪面也就是投影窗口的范圍為min=(-1, -1)和max=(1, 1)。根據解析幾何的計算，易得變換公式為

（2）計算投影窗口上的點在視圖空間的坐標。將該點與視圖空間的原點相連，則可以確定視圖空間內的射線。

投影窗口上的點在視圖空間的坐標，是通過透視投影將平截頭體轉換到視圖空間的逆運算。因此，需要了解透視投影以及投影空間和視圖空間的變換關系。圖3描述了平截頭體從視圖空間至投影空間的變換關系。投影空間中原點為平截頭體規格化的立方體的前平面的中心。左圖為視圖空間，右圖為投影空間。

式(2)是投影變換矩陣[11]，其中各變量的含義如式(3)所示。Zn和fov的含義如圖4所示，Zn是原點至近裁剪面的距離，fov表示視圖空間中原點與近裁剪面高度的夾角。screenWidth和screenHeight分別為屏幕的寬度和高度，Zf為原點至遠裁剪面的距離。

圖3 視圖空間至投影空間的變換關系

圖4 平截頭體在視圖空間中的投影示意圖

根據投影空間和視圖空間的變換，易得投影空間中的點proj和視圖空間中的點view有下式的關系

其中 proj_x, proj_ y, proj_z分別為點proj在x, y和z軸上的坐標，同理view_x , view_ y, view_z分別為點view在x, y和z軸上的坐標。在此采用齊次坐標表示法來表示投影空間中的點和視圖空間中的點的對應關系。所謂齊次坐標表示法[6]是指用n+1維向量來表示n維向量的方法。這種方法便于表達平移，旋轉以及縮放等變換。

由式(4)可得下式

（3）計算視圖空間中這條射線的方向矢量，該方向矢量用view_dir表示。

參照圖4，由式(5)，易得射線方向矢量的各分量計算公式如下

（4）計算射線在世界空間下的向量。對世界空間轉換到視圖空間的矩陣求逆，可得視圖空間轉換到世界空間的矩陣

Vworldspace為世界空間下的向量，Vviewspace為視圖空間下的向量，為視圖空間轉換到世界空間的矩陣。

根據式(6)可以分別計算射線頂點和方向在世界空間下的向量。

2.2 射線與包圍盒求交的算法

包圍體的類型主要有軸對齊包圍盒（Axis-Aligned Bounding Box，簡稱AABB），包圍球(Sphere)，方向包圍盒（Oriented Bounding Box，簡稱 OBB）等[12]。作者采用了 AABB包圍盒。AABB包圍盒的建立以及射線與包圍盒求交的算法如下：

（1）從三維圖形的模型得到在x, y, z軸各方向的最大絕對值，以此來確定包圍盒的8個頂點的本地空間坐標。

（2）將包圍盒的本地空間坐標轉換到世界空間，得到包圍盒各頂點的世界坐標。

（3）將射線轉換到世界坐標。

（4）射線分別對包圍盒的6個面求交，射線的點落在包圍盒的某一個面的范圍內時，判斷射線與包圍盒相交。為了提高計算的速度，在6個面中，計算出任意一個面相交后就可以停止計算。

在確定了相交的包圍盒后，進入到下一個階段：射線與包圍盒中三維圖形模型的各三角形求交的計算。如果沒有與射線相交的包圍盒，則沒有要拾取的對象。

2.3 射線與三角形求交的算法

Web3D中的各三維圖形的模型都是由三角形堆砌而成的，對射線與三角形求交可以精準地拾取目標圖形。如果射線落在某一個三角形內則可以確定該三角形所在的圖形為拾取的對象，示意圖如圖5所示。這是一個三角形線性插值的問題，具體的演算如下：

設射線原點為P0，射線方向為Dir；三角形三個頂點為 V0，V1，V2；t ，u ，v分別為標量。假設射線與三角形相交，則交點為

這是一個齊次線性方程組，若有解則行列式[-Dir，V1-V0，V2-V0]不為0。根據t，u，v的含義，易得，當t >0, 0< u <1, 0< v <1, 0< u +v <1時該交點在三角形內部，根據線性代數中的克萊姆法則，可知：射線原點到相交點的距離 t，以及交點的坐標( u，v)。

圖5 射線與三角形相交的示意圖

3 拾取的實現

3.1 idx3D引擎簡介

idx3D是一款開源的Web3D引擎，基本實現了渲染管線，也就是將3D模型轉換成屏幕上的有立體視覺的2D圖形的基本流程。由于該引擎是由JAVA語言編寫的，利用其開發的系統有如下優點：

（1）在Web瀏覽器上運行時，用戶不需下載特殊插件；

（2）不依賴于硬件也就是顯卡可以實現3D效果。

由于這種基于JAVA開發的Web3D引擎對于Web3D技術的實用化和普及化具有積極的意義，有必要探討其功能的擴展。idx3D具有簡單的3D渲染框架，有利于將精力集中在拾取功能的實現上，非常適合于將所研究的算法在此引擎上實現。

3.2 具體實現

3.2.1 拾取的流程

拾取算法的流程圖如圖6所示，實現拾取的過程如下：首先，在圖形程序窗口，設鼠標點擊點為 posMouse(x, y)，該點為平面上的點。得到該點的坐標后，將該鼠標點逐步轉換為投影空間中的三維坐標，再轉換為視圖空間坐標，至此可以得到視圖空間中的射線，然后將射線轉換至世界空間中。接下來進入對拾取目標的判斷。一個三維圖形對應一個包圍盒，此處為一個循環結構，boxCnt為包圍盒的個數。射線對包圍盒逐個求交，直至得到相交的包圍盒，或者找不到相交包圍盒而結束循環。對包圍盒求交的方法是，計算射線與一個包圍盒的各個面是否相交，也就是計算射線是否在包圍盒的某一個面的范圍內，SURCNT為包圍盒的面的個數即6。當確定了與射線相交的包圍盒后，由于包圍盒的范圍內有一部分是不屬于對象圖形的，也就是產生了過度拾取的問題。這時，需要對包圍盒內圖元的各個三角形與射線求交，此處也是一個循環結構，如果計算出與射線相交的三角形，則可以確定該三角形所屬的圖形即為所要拾取的圖形，否則對任何圖形不做拾取處理，triCnt為三角形的個數。

3.2.2 代碼的實現

為實現拾取功能，在idx3D引擎的基礎上，主要建立了以下各類，并在相應類中定義了實現算法的屬性和方法。實現拾取的類圖見圖7。

（1）拾取器Picker類的建立主要定義了以下各拾取方法：

1）定義了拾取對象的方法：ObjectPicking-Result類型的 pickObject (Scene scene, Vector mousePos, Object model, boolean returnAt1stTime)方法。

2）定義了拾取對象包圍盒的方法：AABBPickingResult 類型的 pickAABB(Camera camera, Vector mousePos, Vector min, Vector max)方法。

3）定義了拾取對象三角形的方法：TrianglePickingResult 類 型 的 pickTriangle(Camera camera, Vector mousePos, Vector v0,Vector v1, Vector v2)方法。

（2）計算屏幕上的點到視圖空間中的點的轉換過程，并由此生成射線，再將射線轉換至世界空間坐標下。

在Camera.java中定義了getScreenToWorldRay(Vector screenPos)方法進行如下計算：

1）計算屏幕上鼠標點在標準投影空間中近裁剪面上的坐標；

2）調用getProjectionMatrix( )方法獲得投影變換矩陣，計算投影點在視圖空間下的坐標；

3）計算視圖空間下射線的方向；

4）調用getViewMatrix( )方法獲得世界空間至視圖空間的轉換矩陣，再求逆矩陣。計算世界空間中的射線。

（3）射線Ray類的建立

1）定義射線是一個有起點和方向的三維空間中的向量；

2）定義了拾取對象包圍盒的方法：IntersectionResult類型的 intersects(AABB box )方法。由于包圍盒在碰撞，場景管理以及特效等方面都需要用到，因此與射線求交的方法定義在Ray類中，以方便后續功能的擴展。

（4）包圍盒AABB類的建立

用min和max兩個三維向量來表示圖形對象包圍盒的范圍。這兩個點分別是在本地空間中的左下前點和右上后點，前者的x, y, z軸的坐標均為最小值，后者的x, y, z軸的坐標均為最大值。其他各頂點的坐標值均可以通過min和max兩點坐標值的正負計算而獲得。

定義了對該包圍盒進行變換的方法。包圍盒是對象圖形在本地空間中建立起來的，需要對其進行相應的至其他空間的變換。

圖6 拾取算法流程圖

圖7 實現拾取的類圖

3.3 案 例

采用實現了圖形拾取功能的 Web3D引擎，開發出如圖8和圖9所示的演示案例。圖中的茶壺為可旋轉、縮放的三維圖形，當光標在茶壺以外的位置時，如圖8所示，鼠標的標記為小箭頭，茶壺的顏色不變，也就是圖形沒有被拾取。當光標移至茶壺上時，如圖9所示，鼠標的標記變為小手形狀，茶壺變為紅色，表明該對象被拾取。

該案例開發的流程如下：

（1）采用3DSMax為茶壺建模；

（2）構造場景；

（3）加入材質和燈光；

（4）將模型文件導入程序中；

（5）重構場景，以及場景規格化；

（6）初始化渲染狀態；

（7）設置旋轉矩陣，實現整體平移，縮放和旋轉，以及單體平移，縮放和旋轉；

（8）進行渲染得到有三維效果的圖形；

（9）在MouseMove（）中調用拾取功能實現圖9所顯示的拾取全過程。

圖8 未拾取的運行結果

圖9 拾取的運行結果

4 結 論

本文根據 Web3D引擎的特點在射線拾取的基礎上，提出了分層次射線求交算法，并在實際的 Web3D引擎上實現了該算法。通過實際案例驗證了可以高效地實現對三維圖形的拾取功能。在程序中實現的射線，AABB包圍盒以及三角形等部分，為后續的碰撞檢測算法的實現奠定了基礎。

[1]羅立宏, 譚夏梅. 幾種 Web3D技術及比較[J]. 甘肅科技, 2007, (5): 60-63.

[2]朱珊虹, 李 彥. 幾種 Web3D 技術的比較研究[J].內江科技, 2010, (4): 117.

[3]羅立宏, 譚夏梅. 基于ShockWave3D的Web虛擬現實技術研究[J]. 科技資訊, 2007, (4): 101-102.

[4]李春雨, 等. 計算機圖形學及實用編程技術[M]. 北京: 北京航空航天大學出版社, 2009: 73-94.

[5]姚繼權, 李曉豁. 計算機圖形學人機交互中三維拾取方法的研究[J]. 工程設計學報, 2006, (2):116-120.

[6]孫家廣, 等. 計算機圖形學(第3版)[M]. 北京: 清華大學出版社, 1998: 358-390.

[7][美]Steve Cunningham. 計算機圖形學[M]. 石教英,潘志庚譯. 北京: 機械工業出版社, 2008: 83-85.

[8]王 劍, 陸國棟, 譚建榮. 三維場景中圖形對象的拾取方法[J]. 機械, 2004, (7): 29-32.

[9]張嘉華, 等. GPU 三維圖元拾取[J]. 工程圖學學報,2009, 30(1): 46-52.

[10]郭艷霞, 侯彤璞, 杜園園. 基于 DirectX 的三維場景實體的拾取[J]. 遼寧石油化工大學學報, 2009,29(3): 77-84.

[11]Transforms變換[Z]. http://www.gesoftfactory.com/developer/Transform.htm#_世界變換

[12]王曉榮, 王 萌, 李春貴. 基于AABB包圍盒的碰撞檢測算法的研究[J]. 計算機工程與科學, 2010,32(4): 59-61.