改進的三角網格表面近似測地線算法

施逸飛,熊岳山,朱晨陽,施 鵬

(國防科學技術大學計算機學院高性能計算國家重點實驗室,長沙410073)

改進的三角網格表面近似測地線算法

施逸飛,熊岳山,朱晨陽,施 鵬

(國防科學技術大學計算機學院高性能計算國家重點實驗室,長沙410073)

三角網格表面的測地線計算問題可轉化為三角網格表面兩點間的最短路徑計算問題,為了快速地計算三角網格表面測地線,提出一種基于縮小最短路徑搜索區域的三角網格表面近似測地線算法。將三角網格沿坐標系三坐標軸方向進行空間單元劃分,使用A*算法求出兩點間的最短路徑盒子序列,進而得到新的搜索區域,計算三角網格上兩點間的最短路徑,迭代細分最短路徑鄰域內的邊以構造新的網格求解測地線。實驗結果表明,該算法能夠快速準確地計算出三角網格表面任意兩點間的近似測地線,有效解決大型三角網格上最短路徑計算速度慢的問題,計算速度較改進前的算法提高了10倍～59倍。將該算法應用到虛擬肝臟手術系統的區域標定中,可滿足虛擬場景中對計算實時性和效果真實性的要求。

測地線;三角網格;空間單元劃分;A*算法;虛擬肝臟手術;觸覺交互設備

1 概述

計算三角網格模型表面兩點間的測地線是計算幾何中的一個基礎性問題,被廣泛應用于計算機圖形學、地理信息系統、機器人學、虛擬現實、虛擬手術等領域,有重要的理論意義與應用價值。

目前已有多種針對三角網格模型的測地線算法,可分為2類:(1)計算三角網格上一點與其他所有點之間的測地線算法;(2)計算給定兩點間的測地線算法。在第(1)類測地線算法中,文獻［1］提出了使用連續的Dijkstra算法計算測地線的MMP算法,該算法的時間復雜度為O(n2logn);文獻［2］證明了MMP算法的實際運算速度比理論速度快得多,并提出了一種復雜度為O(nlogn)的測地線近似算法;文獻［3］提出了著名的CH算法,該算法選定網格上一點作為根結點,以網格的邊為葉子結點,構造一棵序列樹,任意點到選定點的測地線可以在O(n2)內計算得到;文獻［4］提出一種時間復雜度為O(n)的測地線近似算法,但事先需要對模型進行長時間預處理;文獻［5］將熱學擴散方法引入測地線的計算,將近似測地線的計算速度提高了一個數量級。在第(2)類測地線算法中,文獻［6］將三角網格模型轉化為帶權圖,利用Dijkstra算法計算圖上兩點間的最短路徑,再細分最短路徑鄰域上的邊來更新帶權圖,反復迭代計算最短路徑得到兩點間的近似測地線;文獻［2］在MMP算法的基礎上引入啟發性函數,使用連續的A*算法求取兩點間測地線。

本文在文獻［6］的基礎上,針對Dijkstra算法計算最短路徑速度較慢的問題,提出一種基于空間單元劃分的最短路徑搜索區域縮小算法,在最短路徑計算前排除明顯不在最短路徑附近的邊,提高最短路徑的計算速度。

2 最短路徑搜索區域縮小算法

基于空間單元劃分的最短路徑搜索區域縮小算法的思想為:先構造一個由多個大小相等的正方體盒子構成的搜索空間,求解盒子中心點間的最短路徑［7-8］,然后由最短路徑上盒子及其領域中的網格構成新的搜索區域,在該搜索區域中可求出較精確的最短路徑視為測地線。

將三角網格模型G進行空間單元劃分,設Xmax,Xmin,Ymax,Ymin,Zmax,Zmin分別為三角網格模型在X,Y,Z軸上的最大值和最小值,沿X軸方向所劃分的盒子數量為m,則單個盒子的長度GridSize為:

沿Y,Z方向劃分的盒子數量n,l分別為:

三角網格模型就被分為m×n×l個正方體盒子。

遍歷三角網格模型,找到每一個三角面片所在的正方體盒子,如果一個三角面片在多個正方體盒子中,則以三角面片質心所在的盒子為準。將包含三角面片的正方體盒子視為有效盒子,刪除不是有效盒子的正方體盒子。圖1是對Bunny模型進行空間單元劃分得到的所有正方體盒子和有效盒子。

圖1 Bunny模型的空間單元劃分

使用A*算法求解測地線兩端點所在盒子間的最短路徑［9］。A*算法是一種啟發式的搜索算法［10］,它把當前結點與起始節點的耗散g(n)和與目標節點的耗散h(n)結合起來對節點進行評價:

本文將g(n)設為起始盒子到當前盒子的距離,h(n)設為目標盒子到當前盒子的距離的一半,用f(n)來評價結點。

設給定測地線起點所在盒子的序號為indexs,終點所在盒子序號為indexe,則使用A*搜索算法計算得到的indexs到indexe的最短路徑L為一個相互連接的盒子序列,該盒子序列大致體現了兩點間測地線的形態。取出盒子序列以及其n-鄰域上盒子中包含的三角面片構成新的測地線搜索網格區域G′,兩點間的測地線必定位于新的搜索區域中。

整個算法可描述為:

算法SearchAreaRefining(G)輸入 完整的三角網格模型G

輸出 優化后的三角網格搜索區域G′

(1)將模型G所在空間劃分為若干個相等的正方體盒子。

(2)將含有三角面片的盒子記為有效盒子,刪除非有效的盒子。

(3)使用A*算法計算測地線起點和終點所在盒子indexs和indexe間的最短路徑,得到盒子序列L。

(4)取出盒子序列L及其n-領域上的盒子內所包含的三角面片,得到優化后的搜索區域G′。

圖2 Bunny模型搜索區域的優化

圖2是對Bunny網格模型搜索區域進行優化前后的對比,經過上述方法的優化,Bunny模型上兩點間最短路徑的搜索區域三角面片數量由原來的5 328個減小為556個,搜索區域大大縮小,在三角網格表面計算最短路徑的速度將顯著提高。判斷三角面片屬于哪個正方體盒子需要遍歷整個網格,計算量較大,但可以通過預處理提前計算完成,不會占用該算法的計算時間。因為計算最短路徑使用A*算法,得到盒子序列的計算無需遍歷所有有效盒子,同時有效盒子的數量往往比三角面片數量少得多,所以上述方法可以在很短的時間內得到盒子序列及其1-領域內的盒子。A*搜索算法的時間復雜度為O(n),通過盒子序列得到新的搜索區域的時間復雜度為O(1),本文算法總的時間復雜度為

O(n)。

3 迭代細分的近似測地線計算

本文算法可以計算三角網格上任意兩點間的測地線,測地線的起點和終點無需是三角網格的頂點。若三角網格面上的某點不為三角網格的頂點,可對該點所在的三角面片進行剖分,這樣任意三角網格表面的點都可轉化為三角網格的頂點。如圖3所示,剖分三角形ABC,可使點D成三角網格的頂點。

圖3 三角形剖分策略

三角形剖分完成后,可采用文獻［6］的方法計算三角網格表面任意兩頂點間的近似測地線。文獻［6］的方法首先將原三角網格模型轉換成無向鄰接圖,在圖中使用Dijkstra算法求得兩頂點間的最短路徑,接著細分最短路徑領域內的邊,使新加入的邊從原三角面片的內部通過,構成新的無向鄰接圖。反復細分最短路徑領域內的邊,并計算更新后圖中兩點間的最短路徑,直到前后兩次最短路徑之差小于給定閾值,求得的最短路徑即為兩點間的近似測地線。

圖4是使用文獻［6］中方法計算最短路徑的結果,圖4(a)中的粗線為初始網格中的最短路徑,圖4(b)中的粗線為近似測地線。

圖4 文獻[6]方法的計算結果

文獻［6］中方法需要在整個網格范圍內進行最短路徑計算,由于三角網格模型通常規模較大,該方法的主要時間消耗在初始最短路徑的計算中。使用基于空間單元劃分的最短路徑搜索區域縮小算法進行優化,可以提前排除與最短路徑距離較遠的邊,縮小搜索區域,減小初始最短路徑的計算時間。

4 算法實驗與分析

為了驗證本文算法,在 PC機(CPU為雙核1.40 GHz,RAM 2 GB)上進行了實驗,選取圖5所示的5個不同規模的三角網格模型,計算其中選定兩點間的測地線,結果如表1所示。可以看出,本文算法計算速度優于文獻［6］中的算法,三角網格模型規模越大,優勢越明顯。對于由69 451個三角面片構成的Bunny模型,本文算法的計算速度是文獻［6］算法的59倍,計算效率明顯提高。

圖5 三角網格模型和測地線

表1 求解模型表面測地線的實驗數據

圖5中所有模型的測地線均可被正確求解,證明了本文算法是切實可行的,且魯棒性好。對于較復雜的模型,可以通過增加盒子劃分數量的同時增大提取最短路徑盒子序列的n-鄰域操作中的n來提高結果的精度。

在含有13 070個三角面片的Liver模型上進行多組測地線計算,規定測地線相對長度為測地線長度除以模型長方體包圍盒對角線的長度,圖6為計算結果。可以看出,模型大小一定時,測地線越短,加速比越大。由于本文算法避免了在全局范圍內進行Dijkstra計算,計算時間只和測地線經過的三角面片數量有關,而與模型的大小無關。本文算法適合大規模三角網格上的測地線計算,對于大規模三角模型上短距離的測地線計算有明顯的時間優勢。

圖6 Liver模型上不同長度測地線的實驗數據

5 虛擬肝臟手術區域標定

虛擬肝臟手術是虛擬現實技術在現代醫學中的重要應用,它對虛擬場景的真實感、精確度、實時性和交互性的要求比普通虛擬現實系統更高［11］。虛擬肝臟區域標定是虛擬肝臟手術的重要步驟之一,是一個典型的三角網格上測地線的計算問題。區域標定操作使用虛擬手術電刀與肝臟表面的三角網格接觸,采集得到一連串離散點,計算這些離散點間的測地線。測地線是貼于三角網格表面的最短線段,依次連接相鄰兩離散點的測地線可以得到一條長曲線,模擬電刀在肝臟表面劃過的動作,如同用筆在紙上劃線。

本文虛擬肝臟手術系統的硬件為PC機(CPU四核3.40 GHz,RAM 8 GB)以及SensAble公司生產的PHANTOM觸覺交互設備［12］,系統軟件開發基于圖形開發包OpenGL和力反饋開發包OpenHaptic,OpenGL用來完成圖形的繪制工作, OpenHaptic用來完成觸覺系統的交互工作。為了模擬真實手術場景,在該系統的區域標定步驟中, PHANTOM觸覺交互設備在肝臟表面的采點速率不能低于每秒3個,相鄰兩點間的測地線必須在0.33 s內計算完成,若在整個三角網格模型范圍內進行Dijkstra最短路徑計算將無法滿足實時計算的要求。

PHANTOM采集到的點間距離通常不大,使用本文算法可以縮小最短路徑搜索區域,提高計算效率。將肝臟模型劃分為15×10×10個正方體盒子,近似測地線的計算進行5次迭代求解得到,離散點間的近似測地線如圖7中線段所示。測地線的平均計算時間為 0.03 s,測地線的平均計算誤差為0.07%,可以滿足虛擬場景的實時性和真實性的要求。

圖7 肝臟手術區域標定的模擬效果

6 結束語

本文提出了基于空間單元劃分的最短路徑搜索區域縮小算法,對三角網格表面兩點間近似測地線的算法進行了改進,使近似測地線迭代計算中初始最短路徑計算的速度明顯提高。實驗結果表明,該算法有效地解決了大型網格表面近似測地線計算效率低下的問題,近似測地線的計算時間較原算法大大減少。將該算法應用于虛擬肝臟手術系統中,滿足了模擬肝臟手術表面區域標定對實時性和真實性的需求。

對于復雜的、表面起伏較大的三角網格中測地線的計算,必須采用減小空間單元劃分的密度或者擴大有效盒子鄰域的方法來保證結果的正確性,這在一定程度上降低了計算效率,因此,如何根據三角網格的分布特征對模型進行非均勻單元劃分,提高算法的效率和精確性,是下一步需要研究的內容。

［1］ Mitchell J S B,Mount D M,Papadimitriou C H.The Discrete Geodesic Problem［J］.SIAM Journalon Computing,1987,16(4):647-668.

［2］ Surazhsky V,Surazhsky T,Kirsanov D,et al.Fast Exact and Approximate Geodesics on Meshes［J］.ACM Transactions on Graphics,2005,24(3):553-560.

［3］ Chen J,Han Y.Shortest Paths on a Polyhedron［C］// Proc.of the 6th Annual Symposium on Computational Geometry.［S.l.］:ACM Press,1990:360-369.

［4］ Xin Shiqing,Ying Xiang,He Ying.Constant-time All-pairs Geodesic Distance Query on Triangle Meshes［C］//Proc.of ACM SIGGRAPH Symposium onInteractive 3D Graphics and Games.［S.l.］:ACM Press,2012:31-38.

［5］ Crane K,Weischedel C,Wardetzky M.Geodesics in Heat:A New Approach to Computing Distance Based on Heat Flow［J］.ACM Transactions on Graphics,2013,32(5):152.

［6］ Kanai T,Suzuki H.Approximate Shortest Path on a Polyhedral Surface and Its Applications［J］.Computeraided Design,2001,33(11):801-811.

［7］ 楊 斌,范媛媛,王繼東.點云模型上近似測地線的計算［J］.計算機應用,2011,31(4):1050-1052.

［8］ 杜培林,屠長河,王文平.點云模型上測地線的計算［J］.計算機輔助設計與圖形學學報,2006,18(3): 438-442.

［9］ Xin Shiqing,Wang Guojin.Applying the Improved Chen and Han's Algorithm to Different Versions of Shortest Path Problems on a Polyhedral Surface［J］.Computeraided Design,2010,42(10):942-951.

［10］ Rusfell S,Norvig P.Artificial Intelligence——A Modern Approach［M］.2nd ed.New Jersey,USA:Prentice Hall Press,2004.

［11］ Wang Yanzhen,Xiong Yueshan,Xu Kai,et al.vKASS:A Surgical Procedure Simulation System for Arth-roscopic Anterior Cruciate Ligament Reconstruction［J］.Computer Animation and Virtual Worlds,2013,24(1):25-41.

［12］ 施 鵬,熊岳山,徐 凱,等.虛擬肝臟手術中實時動態滲血效果模擬［J］.計算機應用,2013,33(10):2911-2913,2917.

編輯 顧逸斐

Improved Surface Approximate Geodesic Algorithm on Triangle Mesh

SHI Yifei,XIONG Yueshan,ZHU Chenyang,SHI Peng
(State Key Laboratory of High Performance Computing,School of Computer, National University of Defense Technology,Changsha 410073,China)

The computation of approximate geodesics algorithm on triangle mesh can be transformed to the computation of the shortest path on triangle mesh.In order to figure out the geodesics on triangle mesh efficiently,an improved approximate geodesics algorithm is presented.A weighted graph is constructed by splitting triangle mesh along the Cartesian coordinate axes,thus the shortest path on lattice can be computed by A*algorithm and a new region of search can be defined.The neighboring edges of the shortest path are iteratively subdivided to construct a new weighted graphs to approach the geodesic.Experimental results show the improved algorithm can figure out the geodesics precisely and efficiently.The speed up ratio of the algorithm range is increased between 10 and 59.A region labeling method on virtual liver surgery based on the improved algorithm is also proposed,which can meet the computational real-time and quality requirements of virtual scene.

geodesic;triangle mesh;division of space unit;A*algorithm;virtual liver surgery;haptic interface device

10.3969/j.issn.1000-3428.2014.11.044

1000-3428(2014)11-0225-04

A

TP391

國家自然科學基金資助項目(61379103,61202333,61303185);高等院校博士點專項基金資助項目(20104307110003)。

施逸飛(1991-),男,碩士,主研方向:計算機圖形學,虛擬現實;熊岳山,教授、博士、博士生導師;朱晨陽、施 鵬,碩士。

2013-10-21

2013-12-19E-mail:jerrysyf@gmail.com

中文引用格式:施逸飛,熊岳山,朱晨陽,等.改進的三角網格表面近似測地線算法［J］.計算機工程,2014,40(11):225-228.

英文引用格式:Shi Yifei,Xiong Yueshan,Zhu Chenyang,et al.Improved Surface Approximate Geodesic Algorithm on Triangle Mesh［J］.Computer Engineering,2014,40(11):225-228.