一種針對(duì)復(fù)雜曲面的快速自由交互拾取算法

熊宇龍，李維詩(shī)

一種針對(duì)復(fù)雜曲面的快速自由交互拾取算法

熊宇龍，李維詩(shī)

(合肥工業(yè)大學(xué)儀器科學(xué)與光電工程學(xué)院測(cè)量理論與精密儀器安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009)

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

圖形交互；交互拾取；復(fù)雜曲面

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

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

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

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

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

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

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

1 鼠標(biāo)單點(diǎn)拾取算法

1.1 射線拾取原理

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

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

圖2 射線拾取原理

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

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

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

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

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

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

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

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

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

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

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

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

Fig. 4 Object segmentation based on SAH

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

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

圖5 單點(diǎn)拾取算法流程圖

圖6 矩形拾取示意圖

2 鼠標(biāo)快速拾取算法

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

2.1 畫(huà)刷拾取原理

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

圖7 畫(huà)刷拾取示意圖

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

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

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

圖8 畫(huà)刷寬度和離散度

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

由于單點(diǎn)拾取可將拾取到的曲面壓入到拾取隊(duì)列中，若將所有離散點(diǎn)所對(duì)應(yīng)的曲面拾取到拾取隊(duì)列之中，將導(dǎo)致隊(duì)列中包含多個(gè)重復(fù)曲面，其不僅消耗大量的系統(tǒng)內(nèi)存，還給后續(xù)拓?fù)潢P(guān)系的建立、曲面分析等帶來(lái)困難。

為解決上述問(wèn)題，本文引入了三維實(shí)體的哈希表，用來(lái)記錄已拾取過(guò)的幾何實(shí)體。因此在二維點(diǎn)所對(duì)應(yīng)的曲面片進(jìn)入拾取隊(duì)列之前，先通過(guò)哈希表判斷該曲面是否已存在于隊(duì)列中。若存在，則略過(guò)該點(diǎn)；反之，將其對(duì)應(yīng)的曲面片壓入拾取隊(duì)列中。

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

圖9 畫(huà)刷拾取流程圖

3 曲面拾取結(jié)果

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

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

圖10 單點(diǎn)拾取算法驗(yàn)證((a)拾取結(jié)果；(b)算法響應(yīng)時(shí)間)

圖11 矩形拾取算法驗(yàn)證((a)拾取結(jié)果；(b)算法響應(yīng)時(shí)間)

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

圖12 畫(huà)刷拾取算法驗(yàn)證((a)拾取結(jié)果；(b)算法響應(yīng)時(shí)間)

4 總 結(jié)

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

References)

[1] 姚繼權(quán), 李曉豁. 計(jì)算機(jī)圖形學(xué)人機(jī)交互中三維拾取方法的研究[J]. 工程設(shè)計(jì)學(xué)報(bào), 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引擎中三維圖形對(duì)象拾取的算法與實(shí)現(xiàn)[J]. 工程圖學(xué)學(xué)報(bào), 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]. 工程圖學(xué)學(xué)報(bào), 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]. 計(jì)算機(jī)時(shí)代, 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中一種新的拾取方法及其應(yīng)用: 基于對(duì)象緩沖區(qū)的選擇拾取方法[J]. 工程圖學(xué)學(xué)報(bào), 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] 馬梓翔, 周順, 李青元, 等. 基于虛擬倒序繪制-像素著色檢測(cè)的圖形要素拾取方法[J]. 計(jì)算機(jī)應(yīng)用, 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] 朱明亮, 董冰, 王祎, 等. 三維場(chǎng)景中基于視口空間的拾取算法[J]. 工程圖學(xué)學(xué)報(bào), 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] 葉美芬, 鄭貴洲. 三維點(diǎn)云數(shù)據(jù)拾取與可視化技術(shù)[J]. 測(cè)繪與空間地理信息, 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樹(shù)的聚變堆形變部件碰撞檢測(cè)算法[J]. 計(jì)算機(jī)系統(tǒng)應(yī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

國(guó)家自然科學(xué)基金(51927811)

熊宇龍(1995-)，男，湖南常德人，碩士研究生。主要研究方向?yàn)閺?fù)雜曲面與大尺寸測(cè)量技術(shù)。E-mail：xyl147033@163.com

李維詩(shī)(1970–)，男，山東煙臺(tái)人，教授，博士，博士生導(dǎo)師。主要研究方向?yàn)榉辞蠊こ獭?fù)雜外形自動(dòng)檢測(cè)中的幾何建模與計(jì)算等。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