角度約束路徑法的網(wǎng)格曲面興趣區(qū)域邊界快速交互選取

舒孝陽，劉斌

（華僑大學(xué) 數(shù)字化視覺測量廈門市重點(diǎn)實(shí)驗(yàn)室，福建 廈門361021）

興趣區(qū)域（ROI），是指曲面上用戶交互指定的一塊操作區(qū)域.曲面上興趣區(qū)域的交互選取廣泛應(yīng)用于網(wǎng)格融合［1］、網(wǎng)格分割［2］、網(wǎng)格建模［3］、特征重用［4］等領(lǐng)域.解決該問題的目標(biāo)是快速、簡單、有效地得到所需的興趣區(qū)域邊界.對(duì)興趣區(qū)域的交互選取研究，主要有3種典型的方法.1）基于Dijkstra最短路徑［5］的方法［6-7］.這類方法的時(shí)間復(fù)雜度至少為O（nlogn），n為三角網(wǎng)格模型頂點(diǎn)數(shù).2）基于割集分割策略的方法［8-9］.由于該方法需要判斷切平面Tp和網(wǎng)格模型上所有三角面片的距離是否小于給定閾值，該方法的時(shí)間效率與網(wǎng)格模型的規(guī)模呈負(fù)相關(guān)，即網(wǎng)格規(guī)模越大，時(shí)間效率越低.3）基于智能剪切（intelligent scissoring）操作的方法［10-11］.該方法可將網(wǎng)格剪切成用戶可感知的部分，然而該方法涉及到曲率計(jì)算，算法效率不高.因此，為了快速、有效地交互選取用戶所需的興趣區(qū)域邊界，本文提出角度約束路徑法，用于快速尋找網(wǎng)格曲面上兩點(diǎn)間的一條路徑.

圖1 三角網(wǎng)格曲面興趣區(qū)域邊界選取實(shí)例Fig.1 Selected example of interest region boundary on triangular mesh surface

1 角度約束路徑法

三角網(wǎng)格曲面興趣區(qū)域邊界選取實(shí)例，如圖1所示.其中，黑色線為該算法生成的邊界實(shí)例.由圖1可以看到：用戶通過鼠標(biāo)在屏幕上交互選定一系列二維點(diǎn)；然后，將這些二維點(diǎn)轉(zhuǎn)化成三角網(wǎng)格曲面上的頂點(diǎn)（黑色點(diǎn)）；最后，采用角度約束路徑法分別找出相鄰兩頂點(diǎn)間的路徑，得到的總路徑便是網(wǎng)格曲面上選取區(qū)域的邊界.

1.1 算法的實(shí)現(xiàn)

角度約束路徑法是一個(gè)從起始點(diǎn)S開始不斷向前傳播的過程.算法分為當(dāng)前點(diǎn)判斷和當(dāng)前點(diǎn)更新兩部分.該算法的偽代碼為

輸入：網(wǎng)格曲面M、起始點(diǎn)S、目標(biāo)點(diǎn)T；

輸出：兩點(diǎn)間的路徑點(diǎn)集Path＝｛Pti｜i＝0，1，…，n｝；

1）當(dāng)前點(diǎn)Pti←S；

2）將點(diǎn)S存入點(diǎn)集Path中；

3）While當(dāng)前點(diǎn)Pti不在T附近；

4）更新當(dāng)前點(diǎn)Pti；

5）將Pti存入點(diǎn)集Path中；

6）結(jié)束 While；

7）算法結(jié)束.

其中，當(dāng)前點(diǎn)判斷用以判斷Pti是否為目標(biāo)點(diǎn)T，若Pti為目標(biāo)點(diǎn)T，則算法停止.當(dāng)前點(diǎn)更新的目的是在當(dāng)前點(diǎn)Pti的1-ring鄰域頂點(diǎn)中，尋找一個(gè)偏離實(shí)際測地線方向（文中算法采用Pti和目標(biāo)點(diǎn)T之間的連線方向代替）最小的點(diǎn).算法執(zhí)行如圖2所示，具體為3個(gè)步驟.

圖2 算法執(zhí)行示意圖Fig.2 Schematic of algorithm execution

1）設(shè)Path傳播到當(dāng)前點(diǎn)Pti處，尋找點(diǎn)Pti的1-ring鄰域上的頂點(diǎn)Aj（設(shè)頂點(diǎn)的個(gè)數(shù)為m，則j＝0，1，…，m，下同），計(jì)算Pti點(diǎn)處的法矢為n，并建立Pti點(diǎn)的切平面Tp.

2）分別將所有向量PtiAj與向量PtiT分別投影到切平面Tp上，并且單位化上述向量，得到對(duì)應(yīng)的投影向量PtiA′j，PtiT′.

3）分別計(jì)算cosθj，θj為PtiA′j，PtiT′之間的夾角.保存當(dāng)cosθj為最大值（cosθj）max時(shí)，所在的頂點(diǎn)為B1和δ1＝（cosθj）1max，并計(jì)算余下頂點(diǎn)的ωk值.其中：ωk＝（cosθj）max-cosθk，k＝0，1，…，m-1.此時(shí)，根據(jù)ωk值的不同進(jìn)行不同的處理，設(shè)ζ為給定的閾值.

然后，判斷Pti＝T是否為真.若為真，算法停止，點(diǎn)集Path便為所求路徑上的所有頂點(diǎn)；否則，返回步驟1），繼續(xù)循環(huán).

Ⅱ）直接取Pti＝B1，并將點(diǎn)B1存入點(diǎn)集Path中，判斷Pti＝T是否為真.若為真，則算法停止，點(diǎn)集Path便為所求路徑上的所有頂點(diǎn)；否則，返回步驟1），繼續(xù)循環(huán).

由于該算法僅與S，T兩頂點(diǎn)間的局部區(qū)域有關(guān)，算法的時(shí)間復(fù)雜度小于O（n），n為網(wǎng)格模型頂點(diǎn)的個(gè)數(shù).因此，可用于快速交互選擇三角網(wǎng)格曲面上的興趣區(qū)域.

1.2 算法的改進(jìn)

在算法的實(shí)際執(zhí)行過程中發(fā)現(xiàn)，當(dāng)兩點(diǎn)間的曲面區(qū)域較平坦時(shí)，采用上述方法，能得到較直的一條路徑；然而，當(dāng)兩點(diǎn)間的曲面區(qū)域較陡峭時(shí)，獲得的路徑效果較差，如圖3（a）所示.這是由于角度約束路徑法是基于兩點(diǎn)間連線方向進(jìn)行角度約束，當(dāng)兩點(diǎn)間的曲面區(qū)域較陡峭時(shí)，兩點(diǎn)間連線方向和實(shí)際測地線方向相差較大.因此，文中對(duì)該算法進(jìn)行了改進(jìn)，即在兩點(diǎn)間插入1個(gè)過渡點(diǎn)，使兩點(diǎn)間的曲面區(qū)域趨于平坦，如圖3（b）所示.

設(shè)網(wǎng)格曲面M上的頂點(diǎn)集合為V，兩點(diǎn)為p，q.對(duì)于過渡點(diǎn)的確定，首先，以頂點(diǎn)集合建立K-D樹；然后，采用沿給定方向向量搜索距離該方向向量最近的頂點(diǎn).方向向量dir的確定，如圖4所示.設(shè)np，nq分別為p，q兩點(diǎn)的法矢，則將pq沿著nq×np軸逆時(shí)針旋轉(zhuǎn)90°得到的向量便是dir.

圖3 角度約束路徑法存在的問題及其改進(jìn)示意圖Fig.3 Schematic diagram of existing problems and improvement results of angular constraint path method

2 興趣區(qū)域邊界獲取

基于角度約束路徑法可實(shí)現(xiàn)網(wǎng)格曲面上興趣區(qū)域邊界的快速獲取，具體步驟為

1）用戶根據(jù)自己的需要，交互選取一些二維點(diǎn)，并保存之；

2）將上述二維點(diǎn)投影到網(wǎng)格曲面上，得到距離各投影點(diǎn)最近的網(wǎng)格頂點(diǎn)，并保存之；

3）采用角度約束路徑法得到任意相鄰兩點(diǎn)間的一條路徑，保存路徑上的頂點(diǎn).此外，還需要得到首末位置頂點(diǎn)間的一條路徑，取出路徑上的重復(fù)點(diǎn)，最終得到一條封閉的興趣區(qū)域邊界，如圖5所示.

圖4 方向向量dir的確定Fig.4 Determination of the direction vector dir

圖5 三角網(wǎng)格曲面興趣區(qū)域邊界選取實(shí)例Fig.5 Selected example of interest region boundary on triangular mesh surface

3 實(shí)驗(yàn)驗(yàn)證

文中算法是基于Microsoft Visual Studio 2008開發(fā)工具和OpenGL函數(shù)庫編寫的.為了驗(yàn)證角度約束路徑算法的有效性和時(shí)間效率，在CPU為2.26 GHz AMD Athlon（tm）ⅡX2 240 Processor，內(nèi)存為2.0 GB的PC機(jī)上運(yùn)行該算法.

由上述可知：該算法的時(shí)間復(fù)雜度小于O（n）.因此，本算法的時(shí)間效率應(yīng)優(yōu)于Dijkstra最短路徑法（時(shí)間復(fù)雜度為O（nlogn））.為了驗(yàn)證文中算法的時(shí)間效率，分別采用角度約束路徑法和Dijkstra最短路徑法測試鞋楦模型、斯坦福兔子模型和頭像模型上選定的路徑點(diǎn)，2種算法頂點(diǎn)位置選擇相同，得到的實(shí)驗(yàn)數(shù)據(jù)如表1所示.由表1可知：角度約束法具有運(yùn)算速度快的特點(diǎn)，適用于交互選取三角網(wǎng)格曲面上的興趣區(qū)域邊界.

表1 角度約束路徑法和Dijkstra最短路徑法時(shí)間效率對(duì)比Tab.1 Comparison of time efficiency between angular constraint path method and Dijkstra shortest path method

4 結(jié)束語

文中提出角度約束路徑法，用以實(shí)現(xiàn)三角網(wǎng)格曲面興趣區(qū)域邊界的快速交互選取.然而，在算法的實(shí)際執(zhí)行過程中發(fā)現(xiàn)，當(dāng)相鄰兩點(diǎn)間曲面區(qū)域較陡峭時(shí)，得到的路徑效果較差.針對(duì)這一問題，采用在兩點(diǎn)間插入一個(gè)過渡點(diǎn)的方法，從而使相鄰兩點(diǎn)間的曲面重新趨于平坦.試驗(yàn)結(jié)果表明：改進(jìn)后的角度約束路徑法獲取的路徑效果好.不僅如此，對(duì)比Dijkstra最短路徑法，該方法具有算法執(zhí)行快速快的特點(diǎn)，適用于興趣區(qū)域的快速交互選取.

［1］ JUNGE K，BINNEB?SEL M，ROSCH R，et al.Impact of proinflammatory cytokine knockout on mesh integration［J］.Investigative Surgery，2009，22（4）：256-262.

［2］ 孫曉鵬，李華.三維網(wǎng)格模型的分割及應(yīng)用技術(shù)綜述［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（8）：1647-1655.

［3］ KOBBELT L，CAMPAGNA S，VORSATZ J，et al.Interactive multi-resolution modeling on arbitrary meshes［C］∥Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM，1998：105-114.

［4］ SCHMIDT R，SINGH K.Drag，drop，and clone：An interactive interface for surface composition［R］.Toronto：University of Toronto，2010：1-10.

［5］ DIJKSTRA E W.A note on two problems in connexion with graphs［J］.Numerische Mathematik，1959，1（1）：269-271.

［6］ SCH MIDT R，SINGH K.Sketch-based procedural surface modeling and compositing using surface trees［J］.Computer Graphics Forum，2008：27（2）：321-330.

［7］ SHARF A，BLUMENKRANTS M，SHAMIR A，et al.SnapPaste：An interactive technique for easy mesh composition［J］.The Visual Computer，2006，22（9／10／11）：835-844.

［8］ KHO Y，GARLAND M.Sketching mesh deformations［C］∥Proceedings of the 2005 Symposium on Interactive 3D Graphics and Games.New York：ACM，2005：147-154.

［9］ 王雋，張宏鑫，許棟，等.勾畫式泊松網(wǎng)格編輯［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（11）：1723-1729.

［10］ FUNKHOUSER T，KAZHDAN M，SHILANE P，et al.Modeling by example［C］∥ACM Transactions on Graphics.New York：ACM，2004：652-663.

［11］ LEE Y，LEE S，SHAMIR A，et al.Mesh scissoring with minima rule and part salience［J］.Computer Aided Geometric Design，2005，22（5）：444-465.