陳 煜 ， 林 瑋

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

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

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

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

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

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

1.2 拾取的基本原理

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

圖1 三維圖形的顯示過程

（1）將屏幕上鼠標(biāo)點擊點的二維坐標(biāo)，轉(zhuǎn)化為投影空間內(nèi)的三維坐標(biāo)。

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

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

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

2 拾取算法

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

2.1 獲得射線的矢量

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

圖2 鼠標(biāo)點在各空間中的對應(yīng)示意圖

（1）屏幕上鼠標(biāo)點的坐標(biāo)轉(zhuǎn)換至投影空間的坐標(biāo)

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

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

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

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

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

圖3 視圖空間至投影空間的變換關(guān)系

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

根據(jù)投影空間和視圖空間的變換，易得投影空間中的點proj和視圖空間中的點view有下式的關(guān)系

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

由式(4)可得下式

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

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

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

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

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

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

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

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

（2）將包圍盒的本地空間坐標(biāo)轉(zhuǎn)換到世界空間，得到包圍盒各頂點的世界坐標(biāo)。

（3）將射線轉(zhuǎn)換到世界坐標(biāo)。

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

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

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

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

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

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

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

3 拾取的實現(xiàn)

3.1 idx3D引擎簡介

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

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

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

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

3.2 具體實現(xiàn)

3.2.1 拾取的流程

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

3.2.2 代碼的實現(xiàn)

為實現(xiàn)拾取功能，在idx3D引擎的基礎(chǔ)上，主要建立了以下各類，并在相應(yīng)類中定義了實現(xiàn)算法的屬性和方法。實現(xiàn)拾取的類圖見圖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）計算屏幕上的點到視圖空間中的點的轉(zhuǎn)換過程，并由此生成射線，再將射線轉(zhuǎn)換至世界空間坐標(biāo)下。

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

1）計算屏幕上鼠標(biāo)點在標(biāo)準(zhǔn)投影空間中近裁剪面上的坐標(biāo)；

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

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

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

（3）射線Ray類的建立

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

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

（4）包圍盒AABB類的建立

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

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

圖6 拾取算法流程圖

圖7 實現(xiàn)拾取的類圖

3.3 案 例

采用實現(xiàn)了圖形拾取功能的 Web3D引擎，開發(fā)出如圖8和圖9所示的演示案例。圖中的茶壺為可旋轉(zhuǎn)、縮放的三維圖形，當(dāng)光標(biāo)在茶壺以外的位置時，如圖8所示，鼠標(biāo)的標(biāo)記為小箭頭，茶壺的顏色不變，也就是圖形沒有被拾取。當(dāng)光標(biāo)移至茶壺上時，如圖9所示，鼠標(biāo)的標(biāo)記變?yōu)樾∈中螤?，茶壺變?yōu)榧t色，表明該對象被拾取。

該案例開發(fā)的流程如下：

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

（2）構(gòu)造場景；

（3）加入材質(zhì)和燈光；

（4）將模型文件導(dǎo)入程序中；

（5）重構(gòu)場景，以及場景規(guī)格化；

（6）初始化渲染狀態(tài)；

（7）設(shè)置旋轉(zhuǎn)矩陣，實現(xiàn)整體平移，縮放和旋轉(zhuǎn)，以及單體平移，縮放和旋轉(zhuǎn)；

（8）進(jìn)行渲染得到有三維效果的圖形；

（9）在MouseMove（）中調(diào)用拾取功能實現(xiàn)圖9所顯示的拾取全過程。

圖8 未拾取的運行結(jié)果

圖9 拾取的運行結(jié)果

4 結(jié) 論

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

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

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

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

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

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

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

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

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

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

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

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

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