熊宇龍，李維詩

一種針對復雜曲面的快速自由交互拾取算法

熊宇龍，李維詩

(合肥工業(yè)大學儀器科學與光電工程學院測量理論與精密儀器安徽省重點實驗室，安徽 合肥 230009)

三維模型的交互拾取作為最直觀的人機交互方式，在各個領域都有廣泛地應用，如幾何建模、3D游戲和有限元分析等。針對目前含有復雜曲面模型的拾取效率和拾取自由度低等問題，提出了一種對復雜曲面的快速自由交互拾取算法。首先采用一種類似畫刷的工具，對畫刷在屏幕中移動的路徑進行離散，接著對每一個離散點應用基于BVH結(jié)構(gòu)的單點拾取法來拾取復雜曲面，然后用2個哈希結(jié)構(gòu)降低算法的響應時間，最后對該算法進行了驗證。

圖形交互；交互拾?。粡碗s曲面

三維模型的交互拾取作為最直觀的人機交互方式，在各個領域都有廣泛地應用，如幾何制圖、3D游戲和有限元分析等。隨著圖形技術和圖形硬件的快速發(fā)展，交互式圖形應用中三維場景的復雜度越來越高，在圖形交互領域中，能快速、準確地提取到目標模型對其后續(xù)進行分析、修改、增刪等操作具有非常重要的意義。

在現(xiàn)有的研究中，對于三維模型進行鼠標交互拾取的算法主要有以下幾種：

(1) 射線拾取法(ray-casting)[1-5]。該方法將屏幕二維坐標轉(zhuǎn)化為三維環(huán)境中的射線，通過射線與圖元求交的方法來檢測三維環(huán)境中散落的圖元，最終根據(jù)深度信息確定拾取到的圖元。該方法拾取的準確度高，但針對復雜模型，該方法的效率較低；

(2) 基于緩沖區(qū)的拾取方法[6-7]。該方法在需要進行鼠標拾取時，將所有的三維圖形重新渲染到緩沖區(qū)，并在緩沖區(qū)中給每個圖元一個特定的索引號，將鼠標點擊的屏幕二維坐標作為索引值，在緩沖區(qū)中拾取對應的圖元。由于在拾取時需對圖形進行重新渲染，導致該方法拾取速率不及射線拾取法；

(3) 基于視口空間的拾取法[8]。該算法根據(jù)視口變換將所有三維環(huán)境中的圖形包圍盒投影到二維空間，在二維空間中進行拾取。該方法的缺陷和基于緩沖區(qū)的方法一樣，在拾取時，三維環(huán)境向二維空間中投影的時間隨著模型的復雜度呈線性增長，導致拾取速率低。

針對交互拾取效率較低的問題，文獻[1]首先計算模型的包圍球，然后用包圍球和射線進行求交，一定程度上提升了拾取的效率，但該方法有可能造成圖形的誤拾??；文獻[2]采用分層次求交的形式，先將射線與包圍盒求交，再對包圍盒內(nèi)的三角形求交，一定程度上解決了網(wǎng)格模型拾取效率問題，但對于大型復雜曲面模型，用該方法所生成的包圍盒較多，拾取效率得不到保障；文獻[5]通過Three.js中自帶的組合功能來合并已有的幾何體，從而達到單次拾取多個幾何體的目的；文獻[3,9-11]將拾取、渲染等計算過程放到GPU上，與使用CPU計算的方法相比，拾取效率有一定程度上的提升，但僅限于鼠標的單點拾取，對于復雜曲面的拾取效率仍較低。

為了解決上述問題，本文首先介紹一種基于表面積啟發(fā)式(surface area heuristic，SAH)方法的結(jié)構(gòu)單點拾取算法(bounding volume hierarchy，BVH)；然后在單點拾取算法的基礎上，提出了一種類似畫刷工具的快速自由拾取算法；最后，驗證了該算法的自由性和低延時性。

1 鼠標單點拾取算法

1.1 射線拾取原理

將三維環(huán)境中的幾何模型需要經(jīng)過視點變換、投影變換、透視變換、視口變換4個步驟被投影到二維屏幕上，并將原模型所在的物體坐標系轉(zhuǎn)換到屏幕所在的窗口坐標系上，如圖1(a)所示。上述過程可由一個變換矩陣來表示，稱作相機綜合變換矩陣(viewing-modeling-projection-viewport transformation，MVPW)。因此從屏幕拾取目標實體的過程可以看作是上述過程的逆過程，即通過MVPW的逆變換，將屏幕上的二維坐標點轉(zhuǎn)換為物體坐標系中的一條射線，然后通過射線與三維空間中自由曲面求交的方式來確定具體拾取的曲面。如圖2所示，鼠標所拾取的曲面為4。

圖1 坐標系變換((a)物體坐標系到窗口坐標系；(b)窗口坐標系到物體坐標系)

圖2 射線拾取原理

雖然采用該方法能準確地拾取到自由曲面，但隨著三維空間中曲面數(shù)量的增加，射線和曲面作相交測試所花費的時間呈線性增長，其時間復雜度為()，對于大型復雜曲面的交互拾取延遲高、響應時間慢，因此亟需一種快速、自由的拾取方法來解決大型復雜曲面的拾取問題。

通常使用基于包圍體的數(shù)據(jù)結(jié)構(gòu)和層次空間分解(hierarchical spatial decomposition，HSD)技術來解決上述難題。這些結(jié)構(gòu)包含k-d樹[12]、基于球的分割樹[13]、軸對齊包圍盒(axis aligned bounding box，AABB)樹[14]、k-點樹[15]、方向包圍盒(oriented bounding box，OBB)樹[16]等。上述結(jié)構(gòu)可將算法的時間復雜度優(yōu)化為(logN)，其中為樹節(jié)點的分支數(shù)。為了達到系統(tǒng)所需求的響應時間，并盡可能簡化數(shù)據(jù)結(jié)構(gòu)，本文采用基于SAH方法的BVH結(jié)構(gòu)，該結(jié)構(gòu)在模型導入預處理階段時建立，不會隨場景、視點的變化而重新構(gòu)建，且時間復雜度為(log2)，符合本文所需的實時性要求。

1.2 基于BVH結(jié)構(gòu)的射線拾取法

BVH數(shù)據(jù)結(jié)構(gòu)實際上是一棵二叉樹，每個節(jié)點最多包含2個子節(jié)點。該結(jié)構(gòu)中，所有的節(jié)點只可能是以下2種類型：葉子結(jié)點(leaf node)或內(nèi)部節(jié)點(internal node)。其中葉子結(jié)點保存的是唯一的幾何元素及包圍盒且該節(jié)點不再有子節(jié)點；內(nèi)部節(jié)點有的包圍盒能將其所有子樹中的幾何體包圍起來，并按照特定劃分方式劃分出2個子節(jié)點，如圖3所示。

圖3 BVH結(jié)構(gòu)示意圖

根據(jù)上述性質(zhì)，可得BVH結(jié)構(gòu)的節(jié)點定義如下：

其中，leftChild和rightChild為該節(jié)點的左右子節(jié)點，若該節(jié)點為葉子節(jié)點，則上述2項值為空(Null)；bx為當前節(jié)點的包圍盒；nPrimitives為當前節(jié)點所包含的幾何元素數(shù)量，當該節(jié)點為葉子節(jié)點時，該值為1；s為具體的幾何體，只有當該節(jié)點為葉子節(jié)點時才有具體的值，其他情況均為空(Null)。

BVH結(jié)構(gòu)包含構(gòu)建和遍歷2個階段。

構(gòu)建工作考慮的是如何構(gòu)造一顆有效描述當前場景信息的二叉樹。該過程的關鍵問題是如何將毫無規(guī)律分布在場景中的曲面進行劃分，即決定左子樹與右子樹上包含哪些曲面。由于是在三維空間中對曲面進行劃分，為了將問題簡化，可以采用分而治之的方法，即決定在哪個坐標軸上進行劃分。該方法與場景中曲面片在各個軸上分布的“散度”有關，即若某個軸上，曲面分布的跨度最大，則沿該軸進行劃分。

確定了劃分原則后，還需選用適當?shù)膭澐址椒ǎ拍馨l(fā)揮該結(jié)構(gòu)最大的作用。本文中選用的劃分方法為表面啟發(fā)式算法。該算法根據(jù)物體在劃分軸分布的跨度，將該軸平分為個區(qū)域，根據(jù)代價公式計算出每一個塊分割的代價，并選擇代價最低的塊進行分割及迭代，直到每一個曲面片都被劃分到唯一的一個BVH葉子結(jié)點中[17]。代價公式為

其中，為當前節(jié)點；和分別為左右子節(jié)點；()為節(jié)點的包圍盒面積；N為節(jié)點的物體數(shù)量；K和K分別為遍歷和單次相交測試的代價。在構(gòu)建數(shù)據(jù)結(jié)構(gòu)的過程中，通過最大限度地降低劃分代價來實現(xiàn)高渲染效果。SAH算法不能完全做到曲面片不重疊或劃分后絕對均勻，但其每一次劃分都是選取當前情形下的最優(yōu)方案，因此性能遠高于中點劃分法和等量劃分法。圖4為SAH算法的劃分示意圖，圖中矩形代表節(jié)點包圍盒的大小，最佳的分割位置如圖所示。

圖4 基于SAH方法的物體劃分示意圖

Fig. 4 Object segmentation based on SAH

BVH結(jié)構(gòu)的遍歷與普通二叉樹的遍歷一樣，采用深度優(yōu)先遍歷法，即通過射線與左右節(jié)點進行相交測試，最終找到的葉子節(jié)點即為所要拾取的曲面片。由于遍歷與二叉樹的遍歷方法相同，所以時間復雜度為(log2)，其中為樹的節(jié)點數(shù)量。單點拾取算法的具體流程圖如圖5所示。

基于單點拾取算法的拾取原理，可將其引申為OpenGL中的拾取方法，即在需要拾取的區(qū)域左上角按下鼠標左鍵，將鼠標拖動到目標區(qū)域的右下角松開左鍵，記錄這2個點并以此生成一個矩形框，落在框內(nèi)的物體即為拾取到的物體。按照圖1(b)的轉(zhuǎn)換流程，屏幕上的矩形經(jīng)MVPW逆變換后會生成一個截錐，錐體的生長方向由當前的視點決定。用該截錐與BVH結(jié)構(gòu)中的各曲面包圍盒求交，有交集的即為拾取到的曲面。拾取過程如圖6所示。

圖5 單點拾取算法流程圖

圖6 矩形拾取示意圖

2 鼠標快速拾取算法

鼠標單點拾取算法，適用于含有少數(shù)曲面模型的低延時性交互拾取。但對于大型復雜模型，如飛機的機翼(約3 705個曲面)、汽車的車門(約20 735個曲面)等，若用鼠標逐個單擊拾取，其效率較為低下；矩形拾取的效率較高，但是自由度較低。因此需要一種快速、自由拾取多個曲面的方法，提升對復雜曲面拾取效率與自由度。

2.1 畫刷拾取原理

為了滿足自由拾取的需求，可將需要拾取區(qū)域的屏幕二維點集擬合成一條光滑的曲線，曲線經(jīng)過的部分即為需要拾取的部分。由此聯(lián)想到Windows系統(tǒng)下的畫刷工具，首先對畫刷工具的寬度進行設置，然后鼠標按下后在屏幕上繪制的軌跡與曲面相交的部分即為需要拾取的部分。圖7中被拾取到的曲面為4～9。

圖7 畫刷拾取示意圖

與單點拾取和矩形拾取不同，畫刷在屏幕上繪制的拾取軌跡可為任意圖形，若要將該圖形經(jīng)過MVPW逆矩陣投影到三維空間中會比較復雜且耗時較長。因此，不能單純沿用圖1(b)所示的轉(zhuǎn)換方式。

孫鑫在《VC++深入詳解》中介紹了一種在MFC框架中實現(xiàn)畫圖功能的方法，其利用MFC對消息的響應機制，將繪圖過程的程序?qū)懺陧憫瘮?shù)OnMouseMove中，根據(jù)個人電腦配置的不同，該函數(shù)在鼠標移動的過程中每隔一定時間響應一次。因此，對于復雜軌跡的繪制可離散成一些小段直線首尾相接連成的組合線，給出畫刷的寬度后，相當于繪制一系列以鼠標軌跡為中心，畫刷寬度為半徑的圓。

本文利用上述方法并結(jié)合單點拾取方法，先將每一小段直線根據(jù)指定的離散度離散成一些列點，再對每一個離散點運用單點拾取原理，即可實現(xiàn)畫刷拾取。畫刷的寬度和離散度相關系數(shù)如圖8所示。

圖8 畫刷寬度和離散度

2.2 畫刷拾取算法優(yōu)化

由于單點拾取可將拾取到的曲面壓入到拾取隊列中，若將所有離散點所對應的曲面拾取到拾取隊列之中，將導致隊列中包含多個重復曲面，其不僅消耗大量的系統(tǒng)內(nèi)存，還給后續(xù)拓撲關系的建立、曲面分析等帶來困難。

為解決上述問題，本文引入了三維實體的哈希表，用來記錄已拾取過的幾何實體。因此在二維點所對應的曲面片進入拾取隊列之前，先通過哈希表判斷該曲面是否已存在于隊列中。若存在，則略過該點；反之，將其對應的曲面片壓入拾取隊列中。

為了提升程序的性能，還引入了儲存屏幕像素坐標點的哈希表，在鼠標軌跡反復經(jīng)過同一片區(qū)域時，程序不進行任何操作，可節(jié)省大量單點拾取的時間。在當前場景經(jīng)過平移、旋轉(zhuǎn)和縮放等操作后，將該哈希表清空。圖9為畫刷拾取的流程圖。

圖9 畫刷拾取流程圖

3 曲面拾取結(jié)果

本文在配置CPU：Intel(R) Xeon(R) CPU E5-1650 v4及GPU：NVIDIA Quadro M2000的電腦上，基于Visual Studio 2013的平臺環(huán)境以及采用MFC架構(gòu)和C++語言進行編程，實現(xiàn)上述的拾取算法。圖10(a)為單點拾取的結(jié)果，其中藍色網(wǎng)格部分為拾取到的曲面；圖10(b)為采用單點拾取算法拾取50次曲面的單點響應時間，圖中橙色直線為50次拾取的算法平均響應時間(ms)，由此可知該算法滿足低延時性拾取的需求。

圖11(a)為矩形拾取結(jié)果，從圖中可知矩形拾取算法能一次性拾取到大量的自由曲面；圖11(b)為矩形拾取曲面數(shù)與其響應時間之間的關系。由圖可知，隨著矩形拾取框選的曲面數(shù)量增加，算法所需的響應時間呈線性增長趨勢，這主要是由截錐和BVH結(jié)構(gòu)中包圍盒求交的次數(shù)增多所導致的。

圖10 單點拾取算法驗證((a)拾取結(jié)果；(b)算法響應時間)

圖11 矩形拾取算法驗證((a)拾取結(jié)果；(b)算法響應時間)

圖12(a)為畫刷拾取結(jié)果，從圖中可知，與矩形拾取相比，畫刷拾取具有更大的自由度，但拾取效率不如矩形拾??；圖12(b)為畫刷拾取曲面數(shù)與其響應時間之間的關系，與矩形拾取相比，畫刷拾取隨拾取曲面數(shù)量的增加，響應時間上升的趨勢不明顯，主要是因為畫刷拾取是分時段進行的，但由于需對畫刷拾取的路徑進行離散，所以在所拾取曲面較少的情況下，其響應時間與矩形拾取相比沒有優(yōu)勢。

圖12 畫刷拾取算法驗證((a)拾取結(jié)果；(b)算法響應時間)

4 總 結(jié)

本文介紹了一種采用基于SAH方法的BVH結(jié)構(gòu)的鼠標單點快速拾取算法，并在此基礎上提出了畫刷拾取方法。該方法與OpenGL中的矩形拾取方法相比，在同一時間內(nèi)拾取的曲面數(shù)量較少，且不支持拾取點云數(shù)據(jù)，但該方法的拾取自由度高，可由用戶設置畫刷的寬度和拾取路徑的離散密度，對畫刷在屏幕上任意掃掠路徑下的曲面進行拾取。經(jīng)驗證，該畫刷拾取方法滿足復雜曲面拾取的自由性和低延時性。

References)

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

YAO J Q, LI X H. Research on 3-dimension pick-up of human-computer interaction in computer graphics[J]. Journal of Engineering Design, 2006, 13(2): 116-120 (in Chinese).

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

CHEN Y, LIN W. The algorithm and implementation of picking 3D figure by Web3D engine[J]. Journal of Engineering Graphics, 2011, 32(6): 82-88 (in Chinese).

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

ZHANG J H, LIANG C, LI G Q. 3D primitive picking on GPU[J]. Journal of Engineering Graphics, 2009, 30(1): 46-52 (in Chinese).

[4] LEE A, JANG I. Mouse picking with ray casting for 3D spatial information open-platform[C]//2018 International Conference on Information and Communication Technology Convergence (ICTC). New York: IEEE Press, 2018: 649-651.

[5] 余莉. 基于Three.js的拾取方法的研究[J]. 計算機時代, 2020(6): 61-63, 66.

YU L. Research on Three.js based pick-up method[J]. Computer Era, 2020(6): 61-63, 66 (in Chinese).

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

WANG Y P, YU K, LUO K. A new method of pick object in OpenGL and application—the method of pick object based on object-buffer[J]. Journal of Engineering Graphics, 2003, 24(2): 60-65 (in Chinese).

[7] 馬梓翔, 周順, 李青元, 等. 基于虛擬倒序繪制-像素著色檢測的圖形要素拾取方法[J]. 計算機應用, 2014, 34(S2): 243-245, 252.

MA Z X, ZHOU S, LI Q Y, et al. Generic graphical object picking method based on virtual reverse order drawing and pixel colored detection[J]. Journal of Computer Applications, 2014, 34(S2): 243-245, 252 (in Chinese).

[8] 朱明亮, 董冰, 王祎, 等. 三維場景中基于視口空間的拾取算法[J]. 工程圖學學報, 2008, 29(2): 94-97.

ZHU M L, DONG B, WANG Y, et al. Algorithm for picking in 3D scenes based on viewport space[J]. Journal of Engineering Graphics, 2008, 29(2): 94-97 (in Chinese).

[9] 葉美芬, 鄭貴洲. 三維點云數(shù)據(jù)拾取與可視化技術[J]. 測繪與空間地理信息, 2019, 42(7): 134-137.

YE M F, ZHENG G Z. Technology of 3D point cloud data picking and visualization[J]. Geomatics & Spatial Information Technology, 2019, 42(7): 134-137 (in Chinese).

[10] ZHAO H L, JIN X G, SHEN J B, et al. Fast and reliable mouse picking using graphics hardware[J]. International Journal of Computer Games Technology, 2009, 2009: 1-7.

[11] GU G, KIM D. Accurate and efficient GPU ray-casting algorithm for volume rendering of unstructured grid data[J]. ETRI Journal, 2020, 42(4): 608-618.

[12] DE BOI I, RIBBENS B, JORISSEN P, et al. Feasibility of kd-trees in Gaussian process regression to partition test points in high resolution input space[J]. Algorithms, 2020, 13(12): 327.

[13] BENITEZ A, DEL CARMEN RAMIREZ M, VALLEJO D. Collision detection using sphere-tree construction[C]//The 15th International Conference on Electronics, Communications and Computers (CONIELECOMP’05). New York: IEEE Press, 2005: 286-291.

[14] 鄧峻生, 毛世峰, 劉旭峰, 等. 基于AABB樹的聚變堆形變部件碰撞檢測算法[J]. 計算機系統(tǒng)應用, 2018, 27(11): 161-167.

DENG J S, MAO S F, LIU X F, et al. Collision detecting algorithm for deformable components in fusion reactor based on AABB tree[J]. Computer Systems & Applications, 2018, 27(11): 161-167 (in Chinese).

[15] WU H Y, SHU Z M, LIU Y G. Study based on hybrid bounding volume hierarchy for collision detection in the virtual manipulator[J]. Applied Mechanics and Materials, 2013, 454: 74-77.

[16] TANG L, SONG W G, HOU T C, et al. Collision detection of virtual plant based on bounding volume hierarchy: a case study on virtual wheat[J]. Journal of Integrative Agriculture, 2018, 17(2): 306-314.

[17] DMITRY S, DENIS B, DANILA U. Real-Time SAH BVH construction for ray tracing dynamic scenes[EB/OL]. [2021-01-26]. http://graphicon.ru/html/2011/conference/gc2011Sopin.pdf.

A fast and free interactive picking method for complex surfaces

XIONG Yu-long, LI Wei-shi

(Anhui Province Key Laboratory of Measuring Theory and Precision Instrument, School of Instrument Science and Opto-Electronics Engineering, Hefei University of Technology, Hefei Anhui 230009, China)

As an intuitive way for human-computer interaction, the interactive picking of 3D models is widely used in various fields, such as geometric modeling, 3D games, and finite element analysis.To address the problems of low picking efficiency and low degree of picking freedom of complex surface models, a fast and free interactive picking method for complex surface model was proposed. This method employed a brush-like tool to discretize the moving path of the brush in the screen, applied the single point picking method based on BVH structure to pick up the complex surface for each discrete point, and then utilized two hash structures to reduce the response time of the algorithm, and finally the algorithm was verified.

graphic interaction; interactive picking; complex surface

TP 391

10.11996/JG.j.2095-302X.2021060957

A

2095-302X(2021)06-0957-06

2021-04-21；

2021-06-17

國家自然科學基金(51927811)

熊宇龍(1995-)，男，湖南常德人，碩士研究生。主要研究方向為復雜曲面與大尺寸測量技術。E-mail：xyl147033@163.com

李維詩(1970–)，男，山東煙臺人，教授，博士，博士生導師。主要研究方向為反求工程、復雜外形自動檢測中的幾何建模與計算等。E-mail：weishili@hfut.edu.cn

21 April，2021；

17 June，2021

National Natural Science Foundation of China (51927811)

XIONG Yu-long (1995–), male, master student. His main research interests cover geometric modeling and calculation in automatic detection of complex surface. E-mail：xyl147033@163.com

LI Wei-shi (1970-), male, professor，Ph.D,. His main research interests cover reverse engineering, geometric modeling and computing in automatic inspection of complex shapes, etc. E-mail：weishili@hfut.edu.cn