鄒 昆， 沃 焱， 李文生

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

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

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

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

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

計算機應用；幾何圖元拾??；GPU；三維交互

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

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

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

1 相關方法

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

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

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

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

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

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

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

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

2 基于GPU的拾取框架

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

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

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

圖2 拾取繪制流程示意圖

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

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

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

3.1 單體拾取

在進行單體拾取時，應用程序端的步驟如下：

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

其中，ptX和ptY是轉換后的鼠標位置，x和y是窗口設備坐標系下的鼠標位置，viewportX和viewportY是窗口坐標系下視口左下角位置，viewportWidth和 viewportHeight為視口的寬度和高度。

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

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

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

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

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

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

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

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

對于透視投影，判斷頂點是否在視域體內方法如下：

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

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

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

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

圖4 三角形圖元、拾取點及相關向量示意圖

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

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

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

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

3.2 塊拾取

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

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

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

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

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

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

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

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

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

4 實驗結果及分析

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

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

圖5 單體拾取示例

圖6 塊拾取示例

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

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

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

5 結 論

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

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

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

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

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

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

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

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

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

[9] 何健鷹, 徐強華, 游 佳. 基于OpenGL的一種三維拾取方法[J]. 計算機工程與科學, 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

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

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