Web3D引擎中三維圖形對(duì)象拾取的算法與實(shí)現(xiàn)

陳 煜 ， 林 瑋

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

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

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

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

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

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

1.2 拾取的基本原理

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

圖1 三維圖形的顯示過(guò)程

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

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

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

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

2 拾取算法

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

2.1 獲得射線的矢量

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

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

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

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

屏幕的原點(diǎn)在左下角，而近裁剪面的原點(diǎn)在中心位置，又因?yàn)榻眉裘嬉簿褪峭队按翱诘姆秶鸀閙in=(-1, -1)和max=(1, 1)。根據(jù)解析幾何的計(jì)算，易得變換公式為

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

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

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

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

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

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

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

由式(4)可得下式

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

參照?qǐng)D4，由式(5)，易得射線方向矢量的各分量計(jì)算公式如下

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)射線原點(diǎn)為P0，射線方向?yàn)镈ir；三角形三個(gè)頂點(diǎn)為 V0，V1，V2；t ，u ，v分別為標(biāo)量。假設(shè)射線與三角形相交，則交點(diǎn)為

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

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

3 拾取的實(shí)現(xiàn)

3.1 idx3D引擎簡(jiǎn)介

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

（1）在Web瀏覽器上運(yùn)行時(shí)，用戶不需下載特殊插件；

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

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

3.2 具體實(shí)現(xiàn)

3.2.1 拾取的流程

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

3.2.2 代碼的實(shí)現(xiàn)

為實(shí)現(xiàn)拾取功能，在idx3D引擎的基礎(chǔ)上，主要建立了以下各類，并在相應(yīng)類中定義了實(shí)現(xiàn)算法的屬性和方法。實(shí)現(xiàn)拾取的類圖見(jiàn)圖7。

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

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

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

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

（2）計(jì)算屏幕上的點(diǎn)到視圖空間中的點(diǎn)的轉(zhuǎn)換過(guò)程，并由此生成射線，再將射線轉(zhuǎn)換至世界空間坐標(biāo)下。

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

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

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

3）計(jì)算視圖空間下射線的方向；

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

（3）射線Ray類的建立

1）定義射線是一個(gè)有起點(diǎn)和方向的三維空間中的向量；

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

（4）包圍盒AABB類的建立

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

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

圖6 拾取算法流程圖

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

3.3 案 例

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

本文根據(jù) Web3D引擎的特點(diǎn)在射線拾取的基礎(chǔ)上，提出了分層次射線求交算法，并在實(shí)際的 Web3D引擎上實(shí)現(xiàn)了該算法。通過(guò)實(shí)際案例驗(yàn)證了可以高效地實(shí)現(xiàn)對(duì)三維圖形的拾取功能。在程序中實(shí)現(xiàn)的射線，AABB包圍盒以及三角形等部分，為后續(xù)的碰撞檢測(cè)算法的實(shí)現(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í)技術(shù)研究[J]. 科技資訊, 2007, (4): 101-102.

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

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

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

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

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

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

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

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

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