鄒 昆， 沃 焱， 李文生

(1. 電子科技大學(xué)中山學(xué)院計算機(jī)學(xué)院，廣東 中山 528402；2. 華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006)

一種基于位置關(guān)系判定的GPU三維幾何圖元拾取方法

鄒 昆1， 沃 焱2， 李文生1

(1. 電子科技大學(xué)中山學(xué)院計算機(jī)學(xué)院，廣東 中山 528402；2. 華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006)

針對交互式圖形應(yīng)用對拾取在效率、適用范圍和拾取信息方面的需求，提出一種新的基于GPU的三維幾何圖元拾取方法。在進(jìn)行拾取繪制時關(guān)閉光柵化，將鼠標(biāo)位置信息和圖元頂點(diǎn)坐標(biāo)變換到規(guī)范化設(shè)備坐標(biāo)系，通過在幾何處理器中判斷投影后的二維圖元與鼠標(biāo)或選擇框的位置關(guān)系進(jìn)行命中判定，并利用變換反饋將拾取信息返回應(yīng)用程序。在提出方法的基礎(chǔ)上，介紹了單體拾取和塊拾取的OpenGL實現(xiàn)。實驗表明，該方法的單體拾取效率較基于GPU的射線相交法有約10%的提升，同時能支持高效塊拾取。

計算機(jī)應(yīng)用；幾何圖元拾??；GPU；三維交互

圖形拾取技術(shù)是交互式圖形應(yīng)用的關(guān)鍵技術(shù)之一，在CAD軟件、游戲、圖形用戶界面等方面有著廣泛應(yīng)用。隨著圖形技術(shù)和圖形硬件的快速發(fā)展，交互式圖形應(yīng)用中三維場景的復(fù)雜度越來越高，這對拾取方法的高效性提出了更高的要求。此外，在功能方面圖形應(yīng)用對拾取的需求是多樣化的：有的只需要單體拾取，而有的還需要支持塊拾取；有的只需要獲取到拾取對象的ID，而有的還需要獲取拾取到的三角形的頂點(diǎn)坐標(biāo)、拾取點(diǎn)的深度信息等等。這要求拾取方法適用范圍廣，拾取信息豐富。

隨著現(xiàn)代GPU的迅速發(fā)展，GPU的并行處理能力以超摩爾定律的速度發(fā)展著，在并行處理方面較CPU有著絕對優(yōu)勢，同時GPU的可編程能力越來越強(qiáng)，靈活性越來越高。ShaderModel4.0的GPU上已可進(jìn)行3個階段(vertexShader、geometryShader和fragmentShader)的GPU編程。編程能力的增強(qiáng)使得可以實時實現(xiàn)更多的圖形特效，同時也能利用GPU進(jìn)行更廣泛的通用計算。

針對交互式圖形應(yīng)用中對拾取在效率、適用范圍和拾取信息方面的需求，通過將 GPU用于通用計算目的而非渲染目的，充分利用現(xiàn)代 GPU的并行處理能力、可編程性及靈活性，提出一種可在大量幾何圖元中快速拾取目標(biāo)圖元或圖元集合，并能獲取豐富拾取信息的方法。該方法通過在幾何處理器(geometryShader)中判斷投影后的二維圖元與鼠標(biāo)位置或選擇框的關(guān)系進(jìn)行命中判定，并利用變換反饋(transform feedback)將拾取結(jié)果返回應(yīng)用程序。實驗表明，該方法既適用于單體拾取，也適用于塊拾取，并可獲取到豐富的拾取信息，且過程高效。

1 相關(guān)方法

目前常見的三維幾何圖元拾取方法有以下3種：(1) 老版本OpenGL提供的拾取方法?；诠潭魉€的老版本OpenGL(OpenGL 1.0-3.0)提供了一種基于名稱堆棧和拾取矩陣的拾取方法[1-2]。其主要步驟為：設(shè)置名稱緩存，進(jìn)入選擇模式，初始化名稱堆棧，設(shè)置拾取矩陣，進(jìn)行拾取繪制，返回常規(guī)模式，處理命中記錄。拾取的原理是利用拾取矩陣修改投影變換，將視域體限制在以鼠標(biāo)位置為中心的拾取塊內(nèi)，繪制時，如果圖形對象未被完全裁減掉，則根據(jù)當(dāng)前名稱堆棧中的名稱信息在名稱緩存中記錄一條命中信息。該方法需要為不同的圖形對象設(shè)置不同的ID，并在繪制相應(yīng)對象前更新名稱堆棧(進(jìn)行名稱的壓入與彈出操作)。

該方法的缺點(diǎn)是：①頻繁的堆棧壓入與彈出操作會嚴(yán)重影響拾取效率[3]；②當(dāng)場景中含有大量幾何圖元時名稱堆棧容易溢出[3]；③得不到命中圖元的頂點(diǎn)坐標(biāo)等信息。

(2) 射線相交測試法。射線相交測試法[2,4-7]將鼠標(biāo)點(diǎn)從屏幕坐標(biāo)系逆變換到世界坐標(biāo)系得到投影點(diǎn)，然后將從視點(diǎn)指向投影點(diǎn)的射線與場景中的各幾何圖元在世界坐標(biāo)系下進(jìn)行相交測試，找出被選中的物體。其步驟如下[7]：①獲得屏幕上鼠標(biāo)點(diǎn)擊的點(diǎn)，找到其對應(yīng)的投影窗口上的點(diǎn)p；②計算拾取射線，即一條從原點(diǎn)出發(fā)穿過點(diǎn)p的射線；③將射線乘以投影矩陣和觀察矩陣級聯(lián)后矩陣的轉(zhuǎn)置逆矩陣，變換到和模型相同的坐標(biāo)系中；④判定射線和物體是否相交，如相交則該物體有被拾取到，對于有多個物體與射線相交的情況，可根據(jù)深度信息判定拾取到的物體。

當(dāng)場景中含有大量圖元時，逐三角形求交效率較低。王劍等[4]和郭艷霞等[5]采用將射線與包圍盒求交的方法提高效率。陳煜和林瑋[6]采用了分層求交的思想，先用包圍盒求交實現(xiàn)快速拾取，再用三角形求交提高拾取精度。張嘉華等[7]則利用GPU的幾何處理器對射線相交拾取進(jìn)行提速。

射線相交測試法能夠得到更精確的拾取信息，但用于塊拾取時，需要用多條射線進(jìn)行相交測試，計算量太大[3]。

(3) 基于離屏渲染的拾取方法。此類方法[3,7-8]將圖形對象ID等信息編碼為顏色，在進(jìn)行拾取時將不同對象以不同顏色繪制到離屏緩存中，繪制完成后根據(jù)鼠標(biāo)位置讀取離屏緩存中相應(yīng)位置像素的顏色值，進(jìn)行解碼從而獲得拾取到的物體信息。

此方法有以下缺點(diǎn)：①需要額外進(jìn)行一次完整的繪制，速度較GPU上實現(xiàn)的射線相交法要慢[7]；②信息編碼容量受到離屏緩存位深的限制；③只能拾取到位于最前方的對象，獲取到的拾取信息也非常有限。

除上述3種常見方法外，何健鷹等[9]提出了一種不同的拾取方法：將三角形圖元變換到屏幕坐標(biāo)系后，通過判斷鼠標(biāo)點(diǎn)和三角形的位置關(guān)系來進(jìn)行拾取。此方法與本文提出的方法有一定相似性，但該方法面向的是三維地形圖上的任意點(diǎn)拾取，且未討論塊拾取，也并未利用GPU實現(xiàn)。

2 基于GPU的拾取框架

本文方法需要ShaderModel4.0或以上版本GPU的支持。圖1為支持ShaderModel4.0的GPU圖形流水線示意圖，其中頂點(diǎn)處理器、幾何處理器和片元處理器為可編程的。頂點(diǎn)處理器處理的對象是頂點(diǎn)，主要用于決定裁剪坐標(biāo)系下的頂點(diǎn)坐標(biāo)；幾何處理器的處理對象是圖元，在此處理器中可獲取到頂點(diǎn)處理器傳遞過來的圖元各頂點(diǎn)信息，由于本文方法對圖元進(jìn)行拾取需要圖元的完整信息，因此主要判定過程在此處理器中完成，變換反饋可將幾何處理器輸出的圖元頂點(diǎn)屬性輸出到回饋緩存中，從而將拾取信息返回給應(yīng)用程序；片元處理器的處理對象是片元，主要用于決定片元的顏色等屬性，由于片元數(shù)遠(yuǎn)大于頂點(diǎn)數(shù)，其工作量通常遠(yuǎn)大于頂點(diǎn)處理，本文方法在進(jìn)行拾取繪制時禁用了無需用到的光柵化及其后續(xù)的片元處理等流水線階段，有助于提高效率。

圖1 支持ShaderModel4.0的GPU圖形流水線示意圖

拾取方法的基本思想是，在拾取時進(jìn)行一次額外的繪制，將鼠標(biāo)位置信息和圖元頂點(diǎn)坐標(biāo)變換到規(guī)范化設(shè)備坐標(biāo)系，利用幾何處理器判斷投影后的二維圖元與鼠標(biāo)位置或選擇框的關(guān)系，并利用變換反饋將拾取信息返回應(yīng)用程序。

圖2 拾取繪制流程示意圖

圖2給出了拾取繪制流程的示意圖。在拾取時禁用了光柵化，因此在圖中未出現(xiàn)光柵化、片元處理等流水線階段。拾取對象的頂點(diǎn)數(shù)據(jù)存放在GPU端的頂點(diǎn)緩存中，以利于繪制時能高速訪問。頂點(diǎn)處理器負(fù)責(zé)對輸入頂點(diǎn)進(jìn)行模型變換、觀察變換和投影變換，變換到裁剪坐標(biāo)系下，如果需要獲取所拾取到圖元的世界坐標(biāo)系或模型坐標(biāo)系下坐標(biāo)，則在頂點(diǎn)處理器中計算相應(yīng)坐標(biāo)系下頂點(diǎn)坐標(biāo)并傳給幾何處理器。幾何處理器主要負(fù)責(zé)判斷當(dāng)前圖元是否被拾取到，是則輸出拾取信息到回饋緩存，否則遺棄當(dāng)前圖元，具體步驟見圖3。應(yīng)用程序端負(fù)責(zé)場景的組織、繪制順序的控制以及為頂點(diǎn)處理器和幾何處理器提供拾取需要的屬性參數(shù)。

下面分別針對單體拾取和塊拾取對拾取方法進(jìn)行詳細(xì)描述，并介紹其OpenGL實現(xiàn)。

3 拾取方法及實現(xiàn)

3.1 單體拾取

在進(jìn)行單體拾取時，應(yīng)用程序端的步驟如下：

(1) 將鼠標(biāo)位置由窗口設(shè)備坐標(biāo)系轉(zhuǎn)換到規(guī)范化設(shè)備坐標(biāo)系并傳入幾何處理器，方法如下：

其中，ptX和ptY是轉(zhuǎn)換后的鼠標(biāo)位置，x和y是窗口設(shè)備坐標(biāo)系下的鼠標(biāo)位置，viewportX和viewportY是窗口坐標(biāo)系下視口左下角位置，viewportWidth和 viewportHeight為視口的寬度和高度。

(2) 關(guān)閉光柵化(OpenGL中通過 glEnable (GL_RASTERIZER_DISCARD))，開啟變換反饋。

(3) 繪制各拾取對象。對于復(fù)雜場景，可按照深度順序繪制各拾取對象，以簡化拾取信息的處理，并可利用場景分割和提前裁剪進(jìn)一步提高拾取繪制的效率。在繪制各拾取對象前：①設(shè)置對象的變換矩陣并傳進(jìn)頂點(diǎn)處理器，這些變換矩陣與常規(guī)繪制時一致，以保證拾取繪制時各對象的位置不變；②將各對象的ID傳進(jìn)幾何處理器，也可根據(jù)需要將其父對象ID等信息傳進(jìn)幾何處理器。

(4) 關(guān)閉變換反饋，查詢反饋結(jié)果，處理和獲取拾取信息。處理工作比如從回饋緩存中搜索深度值最小的圖元從而拾取到最前方的圖元，如果在繪制時已經(jīng)是按照深度順序進(jìn)行繪制的，則無需此處理。

在進(jìn)行拾取時，幾何處理器的程序流程如圖3所示，具體闡述如下：

圖3 用于拾取繪制的幾何處理器程序流程

(1) 絕大多數(shù)應(yīng)用中圖元為三角形，因此輸入圖元類型設(shè)置為三角形；每個命中圖元只產(chǎn)生一套拾取信息輸出，因此輸出圖元類型設(shè)為點(diǎn)。

(2) 輸入變量包括鼠標(biāo)位置信息、遠(yuǎn)近裁剪面到視點(diǎn)的距離(判斷圖元是否在視域體外時用到)、表示當(dāng)前投影類型的布爾變量，以及根據(jù)所需拾取信息設(shè)置的輸入變量(例如對象ID、父對象ID、模型坐標(biāo)系頂點(diǎn)坐標(biāo)等等)；輸出變量即輸出到回饋緩存的屬性，一般要有圖元所屬對象的ID，根據(jù)需要還可包括父對象ID、鼠標(biāo)對應(yīng)位置深度、拾取到圖元的頂點(diǎn)坐標(biāo)等等。

(3) 判斷圖元是否在視域體內(nèi)可以快速排除一些圖元，避免進(jìn)行后續(xù)計算，在透視投影情況下也可保證后續(xù)的透視除法不會除以0或接近0的數(shù)而產(chǎn)生較大誤差。如果當(dāng)前圖元至少有一個頂點(diǎn)在視域體內(nèi)，則進(jìn)行后續(xù)處理。

對于透視投影，判斷頂點(diǎn)是否在視域體內(nèi)方法如下：

其中，near和far分別是近、遠(yuǎn)裁剪面到視點(diǎn)的距離，abs為求絕對值函數(shù)，A是一圖元頂點(diǎn)在裁剪坐標(biāo)系下的坐標(biāo)，而A.w實際上等于觀察坐標(biāo)系下的–A.z，即A.w代表的是A所在的與觀察坐標(biāo)系z軸垂直的平面到視點(diǎn)的距離。如果AIn為true，則A在視域體內(nèi)，否則在視域體外。

對于正交投影，視域體的6個面正好是裁剪坐標(biāo)系下的x = ±1，y = ±1和z = ±1，而頂點(diǎn)的w坐標(biāo)為1，因此判斷方法更加簡單：

(4) 通過透視除法即可將頂點(diǎn)坐標(biāo)從裁剪坐標(biāo)系轉(zhuǎn)換到規(guī)范化設(shè)備坐標(biāo)系(坐標(biāo)范圍在–1到1之間)：A = A / A.w。

(5) 對投影平面上的二維圖元進(jìn)行命中判定是幾何處理器程序的核心。對于單體拾取，目標(biāo)是判斷拾取點(diǎn)(鼠標(biāo)位置)是否位于當(dāng)前圖元內(nèi)部，此時只用到圖元頂點(diǎn)的x、y坐標(biāo)。具體方法是：沿逆時針繞向訪問圖元各頂點(diǎn)，針對每一頂點(diǎn)計算從當(dāng)前頂點(diǎn)指向下一頂點(diǎn)的邊向量及從當(dāng)前頂點(diǎn)指向拾取點(diǎn)的向量，通過判斷此二向量的叉乘結(jié)果的z坐標(biāo)符號可知拾取點(diǎn)在邊的左邊(z≥0)還是右邊(z < 0)，如果拾取點(diǎn)在3條邊向量的左邊即可判定拾取點(diǎn)在三角形內(nèi)部，否則即在外部。對應(yīng)GLSL源碼如下(圖4給出了三角形頂點(diǎn)、拾取點(diǎn)及相關(guān)向量的示意圖)：

圖4 三角形圖元、拾取點(diǎn)及相關(guān)向量示意圖

(6) 在為輸出屬性賦值時，所屬對象ID及其父對象ID、圖元頂點(diǎn)坐標(biāo)等直接由輸入變量得到，而拾取點(diǎn)M的深度可根據(jù)三個頂點(diǎn)A、B、C的深度值進(jìn)行線性插值得到，插值系數(shù)分別為三角形MBC、MCA、MAB的面積占三角形ABC面積的比重，三角形的面積可以利用叉乘得到，相應(yīng)的GLSL源碼如下：

其中，CrossA、CrossB、CrossC的值之前進(jìn)行命中判定時已得到，dot為求點(diǎn)積函數(shù)，深度值depth為規(guī)范化坐標(biāo)系下的深度值。

(7) 在輸出拾取屬性到回饋緩存(使用EmitVertex())前，為了確保拾取點(diǎn)在視域體內(nèi)，還需對拾取點(diǎn)的深度值depth進(jìn)行一次判定：如果其值在–1到1之間則進(jìn)行輸出。這是因為前面只確保了有一個圖元頂點(diǎn)在視域體內(nèi)，而命中判定只確保了拾取點(diǎn)的投影在視域體內(nèi)，有可能出現(xiàn)拾取點(diǎn)在深度方向上偏離出視域體的情況。

如果在拾取繪制時不是按照深度順序進(jìn)行繪制的，繪制完后在應(yīng)用程序端還需從回饋緩存中搜索深度值最小的圖元從而拾取到最前方的圖元。如果拾取繪制和常規(guī)繪制的場景完全一樣，也可在拾取繪制前讀取鼠標(biāo)位置的深度值，并傳入幾何處理器，在算出拾取點(diǎn)M的深度后，與傳入的深度值進(jìn)行比較來判定M是否被遮擋，這樣對于復(fù)雜場景的拾取，可降低后期拾取信息處理的復(fù)雜度。

3.2 塊拾取

在進(jìn)行塊拾取時，使用鼠標(biāo)等定位設(shè)備確定一個選擇框，投影后位于該選擇框內(nèi)的圖元判定為命中。最常見的是矩形選擇框，但也有應(yīng)用需要任意形狀選擇框。而命中判定通常有2種方式：①整個圖元位于選擇框內(nèi)則判定為命中；②圖元有部分位于選擇框內(nèi)則判定為命中。本文方法可為采用第①種命中判定方式的塊拾取提供方便高效的實現(xiàn)，下面對其進(jìn)行詳細(xì)介紹，而對于采用第②種命中判定方式的塊拾取在后面給出拓展思路。

采用矩形選擇框和第①種命中判定方式的塊拾取方法與前面的點(diǎn)拾取非常相似。應(yīng)用程序端的工作與單體拾取基本一致，只是傳入幾何處理器的不再是鼠標(biāo)位置，而是選擇框的坐標(biāo)信息，同樣是轉(zhuǎn)換到規(guī)范化設(shè)備坐標(biāo)系。幾何處理器的程序流程同樣如圖3所示，但有以下不同：

(1) 判斷圖元是否在視域體外時，判斷頂點(diǎn)是否在視域體內(nèi)的方法與單體拾取相同，但只有當(dāng)圖元所有頂點(diǎn)都在視域體內(nèi)時，才進(jìn)行后續(xù)處理。

(2) 在對投影平面上的二維圖元進(jìn)行命中判定時更加簡單，如果圖元的所有頂點(diǎn)都在矩形框內(nèi)則判定為命中。

(3) 在為輸出屬性賦值時，深度值可輸出3個頂點(diǎn)的深度值，或是輸出頂點(diǎn)平均深度值，不再需要進(jìn)行插值。

(4) 在輸出拾取屬性到回饋緩存前，不再需要對深度值進(jìn)行判定，因為前面已確保整個圖元在視域體內(nèi)。

如果需要僅拾取未被遮擋的圖元，可以在進(jìn)行拾取繪制前讀取矩形選擇框區(qū)域的深度值，保存為深度紋理，然后在進(jìn)行拾取繪制時，在幾何處理器中，在判定頂點(diǎn)均位于選擇框內(nèi)后，根據(jù)頂點(diǎn)相對于選擇框的x、y坐標(biāo)確定紋理坐標(biāo)，從深度紋理采樣，將采樣得到的深度值與頂點(diǎn)深度值進(jìn)行比較，如果全部頂點(diǎn)均被遮擋則判定為未命中，否則判定為命中。

此外，也可對命中判定進(jìn)行修改，使能夠支持任意形狀選擇框下的塊拾取，其思想與單體拾取時的命中判定相似：如果沿逆時針方向訪問任意形狀選擇框的各邊，頂點(diǎn)A始終在各邊的左邊，則該頂點(diǎn)在選擇框內(nèi)，如果3個頂點(diǎn)都在選擇框內(nèi)，則該圖元判定為命中。

對于第②種命中判定方式：圖元有部分位于選擇框內(nèi)則判定為命中，可利用多邊形裁剪算法(例如Sutherland-Hodgman多邊形裁剪算法[10])判定圖元與選擇框是否相交，但由于目標(biāo)是相交判斷而不是獲得裁剪后的多邊形，可以對算法進(jìn)行相應(yīng)的優(yōu)化，具體實現(xiàn)留待后續(xù)工作完成。

4 實驗結(jié)果及分析

在Microsoft VisualStudio 2010環(huán)境下使用OpenGL4.3和FreeGLUT庫實現(xiàn)了上述拾取方法，塊拾取采用了矩形選擇框和第①種命中判定方式：整個圖元位于選擇框內(nèi)則判定為命中。實驗使用了一個3D場景漫游程序，場景中包含地面、天空球、圓環(huán)及多個隨機(jī)分布的球。實驗硬件為 CPU i5-2430M(2.40 GHz雙核)、4 G內(nèi)存、顯卡NVIDIA GeForce GT 550M(2 G顯存)的筆記本。

圖5給出了單體拾取的示例，在鼠標(biāo)點(diǎn)擊進(jìn)行單體拾取操作后將拾取到的對象用紅色線框包裹顯示，并在控制臺輸出拾取信息，包括拾取到的三角形數(shù)量、三角形頂點(diǎn)模型坐標(biāo)系坐標(biāo)、拾取對象ID(這里拾取到第140號小球)以及鼠標(biāo)拾取位置的深度值(規(guī)范化設(shè)備坐標(biāo)系)。塊拾取時使用鼠標(biāo)按下拖動形成的矩形框來框選圖元，圖6給出了塊拾取的示例，其中拾取到的8個地面三角形用紅色線框突出顯示。

圖5 單體拾取示例

圖6 塊拾取示例

效率測試仍然使用上述場景，通過控制球的數(shù)量來調(diào)節(jié)場景的圖元總數(shù)。在測試塊拾取時，使用隨機(jī)位置和大小的選擇框。此外用OpenGL實現(xiàn)了在拾取速度方面具有代表性的文獻(xiàn)[7]中基于 GPU的射線相交測試方法，進(jìn)行單體拾取的對比。實驗中拾取繪制時均未采取場景分割、提前裁剪等措施，也未按照深度順序進(jìn)行繪制。拾取時間取 10次拾取用時的平均值。

表1給出了實驗的時間數(shù)據(jù)，從中可以看到相對于基于 GPU的射線相交法，本文單體拾取方法有約10%的性能提升，這得益于其更高效的判定過程(在幾何處理器中判定一個三角形是否命中僅需3次透視除法和3次叉乘，如需計算拾取點(diǎn)深度再加上1次點(diǎn)乘和1次除法)。對于塊拾取本文方法同樣可以高效地完成，而射線相交法無法為塊拾取提供有效的支持，如果從選擇框內(nèi)每一像素引發(fā)一條射線，一方面效率低，另一方面有限的射線數(shù)量會降低拾取精度，有可能造成漏拾取的情況。相對于單體拾取，本文塊拾取的速度稍慢，這是因為塊拾取時命中的圖元數(shù)要更多，實驗發(fā)現(xiàn)，選擇框越大，拾取時間越長。本文方法拾取時間主要耗時不在拾取時的繪制，而在從回饋緩存獲取拾取結(jié)果，例如對于 6 755 700個圖元的情況，單體拾取平均耗時102.44Ms，其中拾取繪制平均耗時才6.69Ms。

表1 拾取時間數(shù)據(jù)

5 結(jié) 論

本文提出了一種基于 GPU的三維幾何圖元拾取方法，通過在 GPU幾何處理器中判斷投影后的二維圖元與鼠標(biāo)或選擇框的位置關(guān)系進(jìn)行命中判定。該方法既適用于單體拾取，也適用于塊拾取，單體拾取相對基于GPU的射線相交法有約10%的效率提升，并且可獲取到豐富的拾取信息，能較好地滿足各種三維交互式圖形應(yīng)用的需要。

[1]SegalM, Akeley K. The OpenGL graphicsSystem: aSpecification (version 1.0) [S]. USA：Silicon Graphics Inc, 1994.

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

[3] 李 勝, 汪國平. 一種在圖形處理器上拾取三維幾何圖元的方法[P]. 中國, 200810103054.5. 2008-09-24.

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

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

[6] 陳 煜, 林 瑋. Web3D引擎中三維圖形對象拾取的算法與實現(xiàn)[J]. 工程圖學(xué)學(xué)報, 2011, 32(6): 82-88.

[7] 張嘉華, 梁 成, 李桂清. GPU三維圖元拾取[J]. 工程圖學(xué)學(xué)報, 2009, 30(1):46-52.

[8] 王亞平, 余 柯, 羅 堃. 在OpenGL中一種新的拾取方法及其應(yīng)用—基于對象緩沖區(qū)的選擇拾取方法[J].工程圖學(xué)學(xué)報, 2003, 24(2): 60-65.

[9] 何健鷹, 徐強(qiáng)華, 游 佳. 基于OpenGL的一種三維拾取方法[J]. 計算機(jī)工程與科學(xué), 2006, 28(1):45-46, 70.

[10]Sutherland I E, Hodgman G W. Reentrant polygon clipping [J]. Communications of the ACM, 1974, 17(1): 32-42.

A 3D Geometric Primitive PickingMethod on GPU by Positional Relation Judgment

Zou Kun1, Wo Yan2, Li Wensheng1
(1.School of Computer Engineering, Zhongshan Institute, University of ElectronicScience and Technology of China, Zhongshan Guangdong 528402, China; 2.School of ComputerScience and Technology,South China University of Technology, Guangzhou Guangdong 510006, China)

3D geometry primitive picking is a key technique for 3D interactive graphics applications which is required to be highly efficient, widely applicable and able to obtain rich information. In order toSatisfy these requirements, a novel GPU-based 3D geometric primitive pickingMethod is proposed. The drawing for picking is conducted as follows: rasterization is first turned off, then theMouse position and coordinates of primitive vertexes are transformed to the normalized equipment coordinateSystem, and hit test isMade on the geometry processor by judging the positional relation between the 2D projected primitive and theMouse position orSelection box, at last picking results are returned to the application by utilization of transform feedback. Based on thisMethod, the OpenGL implementation ofSingle-object picking and block picking are both discussed. ExperimentsShow that the proposedMethod is about 10% faster than GPU-based ray intersectionMethod in terms ofSingle-object picking, and it canSupport efficient block picking.

computer application; geometric primitive picking; GPU; 3D interaction

TP 391.41

A

2095-302X(2015)02-0262-06

2014-07-03；定稿日期：2014-10-04

國家自然科學(xué)基金資助項目(61300095)；廣東省自然科學(xué)基金資助項目(S2013010012307，S2012010010508)；廣東省高等學(xué)校優(yōu)秀青年教師培養(yǎng)計劃資助項目(Yq2013206)；電子科技大學(xué)中山學(xué)院科研團(tuán)隊培育資助項目(412YT01)

鄒 昆(1980–)，男，湖北鄖西人，副教授，博士。主要研究方向為圖形圖像處理。E-mail：cszoukun@foxmail.com