一種基于凸包近似的快速體積計(jì)算方法

徐 志，許宏麗

XU Zhi,XU Hongli

北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044

School of Computer&Information Technology,Beijing Jiaotong University,Beijing 100044,China

近年來基于點(diǎn)的圖形學(xué)（Point-based Graphic）研究受到了廣泛的關(guān)注。人們對(duì)點(diǎn)的技術(shù)進(jìn)行大量的工作，特別是在點(diǎn)云表示、點(diǎn)云造型、點(diǎn)云繪制等方面取得了許多新的進(jìn)展[1]。然而，點(diǎn)云模型還很難應(yīng)用到實(shí)際的應(yīng)用系統(tǒng)中，原因就是點(diǎn)云模型的體積等積分屬性很難計(jì)算。體積是點(diǎn)云模型重要的幾何屬性，在許多應(yīng)用場(chǎng)景需要被頻繁地計(jì)算。

物體的點(diǎn)云模型是在物體表面掃面點(diǎn)的集合。點(diǎn)的采樣集合作為一種新的曲面表示方式，無需存儲(chǔ)維護(hù)全局一致的幾何拓?fù)湫畔?，因而能夠?qū)?fù)雜的3D模型進(jìn)行高效的繪制和靈活的集合處理。快速計(jì)算點(diǎn)云模型的體積具有重要意義，如在使用激光雷達(dá)作為信息采集設(shè)備的塌方預(yù)警系統(tǒng)中，需要通過判別物體變化的體積與位移來確定災(zāi)害發(fā)生的等級(jí)；在模型自動(dòng)識(shí)別系統(tǒng)中，通過計(jì)算多個(gè)點(diǎn)云模型的體積預(yù)先判別模型是否一致。

目前，就點(diǎn)云模型而言，體積的計(jì)算首先要重構(gòu)點(diǎn)云曲面模型。近年來，曲面重建算法現(xiàn)在是計(jì)算機(jī)圖形學(xué)領(lǐng)域的熱門研究課題，經(jīng)典算法有零集法、Poisson重建法[2]、Delaunay網(wǎng)格重建[3]及基于徑向基函數(shù)的方法。Ohtake分別把多尺度CS-RBF與自適應(yīng)CS-RBF應(yīng)用到點(diǎn)云數(shù)據(jù)的三維建模中，其模型表面的質(zhì)量更好，其抗噪能力也更強(qiáng)[4]。但是使用重建曲面來計(jì)算體積的方法，把工作集中在重構(gòu)算法上，需要額外消耗大量的運(yùn)算時(shí)間與空間，這樣，對(duì)于只需要快速求取體積的應(yīng)用系統(tǒng)中多出了許多工作。重建曲面可能會(huì)失敗從而導(dǎo)致無法求取體積，以至于系統(tǒng)失效。

三維凸包在諸多應(yīng)用中都發(fā)揮著重要作用，在計(jì)算機(jī)動(dòng)畫領(lǐng)域內(nèi)，凸包被用來近似相撞物體加速碰撞檢測(cè)，大大減少了檢測(cè)所耗的時(shí)間[5]。本文把重點(diǎn)工作放在如何快速地求取物體體積上，這就需要折中物體的近似程度。一方面，希望它們盡可能簡(jiǎn)單，這樣求體積的代價(jià)才會(huì)更低，而另一方面，新的物體近似的越是簡(jiǎn)單，所求的體積的誤差也就越大。在各種方案中，有一個(gè)選擇就是采用包圍球的方式，而包圍盒的體積代價(jià)很小，但是對(duì)于許多物體來說包圍球的效果并不好。另外一個(gè)選擇就是選擇凸包，盡管與球體相比，凸包的計(jì)算更為復(fù)雜，但是大多數(shù)物體都可以通過凸包得到更好的近似。

1 凸包近似求體積

1.1 三維凸包的構(gòu)建

從數(shù)學(xué)上看，在實(shí)向量空間中點(diǎn)集P凸包定義為包含P的最小凸集。在線性代數(shù)上，凸包定義為點(diǎn)集P的所有凸組合，公式表示為：

其中α，n為常系數(shù)。

在三維空間中，凸包可以定義為“集合內(nèi)所有點(diǎn)凸組合所構(gòu)成的集合”。通俗來講，一組物品混合物的所有可能性構(gòu)成了這組物品的凸包。

由歐拉公式可知，對(duì)于任意凸多胞體P，若體內(nèi)包含n個(gè)頂點(diǎn)，則P中所含的邊不會(huì)超過3n-6條，所含的小平面不會(huì)超過2n-4條。所謂的單純多胞體即上述邊及小平面達(dá)到最大的情況。因此，在三維空間中，任意n個(gè)點(diǎn)的凸包的復(fù)雜度為O(n)[6]。

在這里，將借助隨機(jī)增量式算法來構(gòu)造點(diǎn)集P的凸包。首先定義可見區(qū)域和地平線。假設(shè) pr落在凸包??(pr-1)之外，站在 pr點(diǎn)的位置，朝 ??(pr-1)看去，在 ??(pr-1)的表面上，那些可見的小平面連在一起組成了一個(gè)連通區(qū)域，把它稱之為點(diǎn) pr在凸包??(pr-1)上的可見區(qū)域。而圍成這個(gè)區(qū)域的??(pr-1)上的邊組成的折線，稱之為點(diǎn) pr在凸包??(pr-1)上的地平線。具體算法描述如下：

算法 Incre_Convex（P）

輸入：三維空間中的n個(gè)點(diǎn)組成的集合P

輸出：P的凸包

（1）在P中選出不共面的四個(gè)點(diǎn)，構(gòu)成一個(gè)四面體，作為初始凸包 ??(p4)。

（2）初始化凸包??(p4)，確定各個(gè)面的方向，對(duì)凸包外的可見點(diǎn)成右手系方向。

（3）取其余各點(diǎn)的一個(gè)隨機(jī)排列：p5，p6，p7，…，pn，循環(huán)逐一處理各點(diǎn)，并動(dòng)態(tài)維護(hù)凸包。

（4）若 pr落在 ??(pr-1)的內(nèi)部或邊界，則有 ??(pr-1)=??(pr)，轉(zhuǎn)步驟（5）。

（5）若 pr落在 ??(pr-1)的外部，深度搜索遍歷 ??(pr-1)，尋找點(diǎn) pr在凸包??(pr-1)上的地平線和所在平面。

（6）將 pr在凸包 ??(pr-1)上的可見區(qū)域內(nèi)的所有面刪除，并沿著地平線將 pr連接形成新的面，同時(shí)維護(hù)它的方向，將其加入凸包 ??(pr-1)，形成新的凸包 ??(pr)。

（7）重復(fù)步驟（4）～（6），直至處理完所有的點(diǎn)。

（8）結(jié)束

1.2 投影法計(jì)算體積

注意到上述所求三維凸包實(shí)際上是個(gè)三角網(wǎng)格模型，可以使用投影法[7]來計(jì)算三維凸包的體積。首先選擇一個(gè)不與凸包任意三角面片相交的面作為投影面，為簡(jiǎn)化計(jì)算和便于理解，選擇XOY平面作為投影面。如圖1所示，將三維凸包??(P)正投影在平面XOY上，得到投影面P，以該投影面的邊界為準(zhǔn)線，垂直于投影平面的直線為母線作棱柱，此棱柱側(cè)面與凸包外殼的交面在投影平面上的正投影即是投影區(qū)域的邊界，如圖1所示。

圖1 投影法

以上述正投影的方法，此棱柱側(cè)面與凸包外殼的交面可以將凸包分為上三角網(wǎng)格面PU、下三角網(wǎng)格面PL和與棱柱側(cè)面相重合的三角網(wǎng)格Pc。PU與PL與其在平面XOY下的投影組成兩個(gè)凸多面體TU與TL，而三角網(wǎng)格Pc與平面XOY垂直，故所求凸包體積V(??(P))=V(TU)-V(TL)，如圖2，圖3所示。

圖2 上三角網(wǎng)格

圖3 下三角網(wǎng)格

已知上三角網(wǎng)格面與下三角網(wǎng)格面都有三角面片組成。以上三角網(wǎng)格面為例，對(duì)于每一個(gè)三角面片t與投影面XOY組成一個(gè)凸五面體，故有：

對(duì)于每一個(gè)凸五面體的體積V(Δi)可以分解為三個(gè)小四面體體積之和。由解析幾何知，四面體積可以由邊向量的混合積得到。以向量a，b，c為棱的四面體的體積可以表示為：(abc)=6εV ，當(dāng) a，b，c構(gòu)成右手系時(shí) ε=1，當(dāng) a，b，c構(gòu)成左手系時(shí)ε=-1。

同時(shí)，也可以用這種方法來判斷凸包的三角面片是屬于上三角網(wǎng)格面還是下三角網(wǎng)格面。取三角面片的任一點(diǎn)在XOY面上的投影點(diǎn)與三角面片構(gòu)成四面體，當(dāng)ε=1時(shí)，該面片屬上上三角網(wǎng)格面，當(dāng)ε=-1時(shí)，該面片屬于下三角網(wǎng)格面，當(dāng)ε=0時(shí)，該三角面片與投影面XOY垂直。

構(gòu)什么？幾何圖形是由點(diǎn)與線構(gòu)成，對(duì)于線基于尺規(guī)可以構(gòu)造直線與弧線.因?yàn)閮牲c(diǎn)確定一條直線，所以構(gòu)直線其實(shí)就是構(gòu)造兩點(diǎn)；因?yàn)榛【€取決于圓心與半徑，圓心與弧上任一點(diǎn)確定，其弧線也就確定，所以構(gòu)造弧線也是構(gòu)造兩點(diǎn).總而言之，可以明確構(gòu)什么？就是構(gòu)造點(diǎn).

如圖4所示，對(duì)于凸五面體ABCabc體積：

在這里要注意點(diǎn)的順序要求。

圖4 凸五面體

至此就求出了整個(gè)三維凸包的體積，由此得出算法的基本描述。

算法 Vol_Convex3D（P）

輸入：三維空間中的n個(gè)點(diǎn)的三維凸包

輸出：三維凸包的體積

（2）遍歷輸入凸包的每一個(gè)三角面片 p1p2p3，分別求其在XOY面上的投影 pt1pt2pt3。

（3）按照右手法則，分解凸五面體 p1p2p3pt1pt2pt3，其固定順序見式子。

（4）判斷三角面片 p1p2p3是否在 pt1的可見區(qū)域內(nèi)，若在，則所求體積符號(hào)為負(fù)，若不在，所求體積符號(hào)為正。

（5）求和，所有凸五面體體積的代數(shù)和即所求體積。

（6）結(jié)束。

2 實(shí)驗(yàn)結(jié)果

由于點(diǎn)云的原始體積數(shù)據(jù)很難獲得，使用Image Ware產(chǎn)生若干點(diǎn)云數(shù)據(jù)并預(yù)先手動(dòng)計(jì)算其真實(shí)體積，用其測(cè)試算法準(zhǔn)確度。再取若干組實(shí)際點(diǎn)云模型，測(cè)試算法效率。實(shí)驗(yàn)結(jié)果如圖5、表1所示。

圖5 測(cè)試點(diǎn)云模型

表1 測(cè)試數(shù)據(jù)體積、正確率表

實(shí)驗(yàn)結(jié)果表明，算法在計(jì)算凸形點(diǎn)云模型上準(zhǔn)確率高，而對(duì)于非凸物體存在一定誤差。在實(shí)驗(yàn)環(huán)境Pentium D 2.8 GHz，DEV C++環(huán)境下使用實(shí)際點(diǎn)云數(shù)據(jù)模型結(jié)果如圖6、表2所示。

圖6 實(shí)際點(diǎn)云模型

表2 測(cè)試數(shù)據(jù)體積、算法時(shí)間表

由于算法減少了完全重構(gòu)三維模型的過程，簡(jiǎn)化了后一步求取體積的過程，其后續(xù)求體積的時(shí)間復(fù)雜度為O(n)，因此算法主要依賴于凸包算法的復(fù)雜度，減少了很多不必要的時(shí)間消耗，實(shí)驗(yàn)表明，算法可快速有效地求解處理具有復(fù)雜拓?fù)浣Y(jié)構(gòu)的點(diǎn)云模型，杜絕了傳統(tǒng)曲面算法重構(gòu)求解失敗的可能。

3 結(jié)束語

本文針對(duì)要求實(shí)時(shí)性可靠性較高的點(diǎn)云模型體積計(jì)算系統(tǒng)，設(shè)計(jì)了一種快速凸包近似計(jì)算方法，實(shí)現(xiàn)了一種無須進(jìn)行點(diǎn)云模型重建曲面直接求取點(diǎn)云體積的算法，避免了重構(gòu)時(shí)消耗的大量時(shí)間，也杜絕了對(duì)于有較為復(fù)雜的拓?fù)浣Y(jié)構(gòu)的點(diǎn)云模型，重建曲面可能會(huì)失敗從而導(dǎo)致無法求取體積的情況。最后進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)表明本算法能快速地求出點(diǎn)云模型的體積，對(duì)于凸形模型準(zhǔn)確率高，而非凸的模型存在一定誤差，其準(zhǔn)確率還有待提高，其更適合于計(jì)算對(duì)象是凸的或者對(duì)要求精度不高但實(shí)時(shí)性要求高的系統(tǒng)。

另外，算法的效率還有待提高，對(duì)于某些系統(tǒng)上存在大量的點(diǎn)云數(shù)據(jù)，考慮采用建立內(nèi)外包圍盒的方法先對(duì)數(shù)據(jù)點(diǎn)進(jìn)行精簡(jiǎn)[8]并對(duì)三維凸包算法的時(shí)間復(fù)雜度進(jìn)行優(yōu)化研究，進(jìn)一步提高算法的準(zhǔn)確率和效率。

[1]Gross M，Pfister H.Point-based graphics[M].[S.l.]：Morgan Kaufmann Publisher，2007：1-3.

[2]Kazhdan M，Bolitho M，Hoppe H.Poisson surface reconstruction[C]//Polthier K，Sheffer A.Symposium on Geometry Processing.Switzerland：The Eurographics Association，2006：61-70.[3]Dey T，Giesen，Hudson.Delaunay based shape reconstruction from large data[C]//Parallel and Large-Data Visualization and Graphics Proceedings，2001.

[4]Ohtake Y，Belyaev A，Seidel H P.A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions[C]//Proceedings of Shape Modeling International，2003：153-161.

[5]Berg M D，Kreveld M V，Overmars M，et al.Computational geometry：algorithms and applications[M].鄧俊輝，譯.[S.l.]：Springer-Verlag，2005.

[6]Barber C B，Dobkin D P.The quickhull algorithm for convex hulls[J].ACM Transactions on Mathematical Software，1996，22.

[7]王泉德.任意三角網(wǎng)格模型體積的快速精確計(jì)算方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（18）：32-34.

[8]孫殿柱，朱昌志，李延瑞.三維散亂點(diǎn)云凸包快速求解算法[J].機(jī)械設(shè)計(jì)與研究，2009，25（4）：11-14.