徐 志，許宏麗

XU Zhi,XU Hongli

北京交通大學 計算機與信息技術學院，北京 100044

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

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

物體的點云模型是在物體表面掃面點的集合。點的采樣集合作為一種新的曲面表示方式，無需存儲維護全局一致的幾何拓撲信息，因而能夠對復雜的3D模型進行高效的繪制和靈活的集合處理?？焖儆嬎泓c云模型的體積具有重要意義，如在使用激光雷達作為信息采集設備的塌方預警系統(tǒng)中，需要通過判別物體變化的體積與位移來確定災害發(fā)生的等級；在模型自動識別系統(tǒng)中，通過計算多個點云模型的體積預先判別模型是否一致。

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

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

1 凸包近似求體積

1.1 三維凸包的構建

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

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

在三維空間中，凸包可以定義為“集合內所有點凸組合所構成的集合”。通俗來講，一組物品混合物的所有可能性構成了這組物品的凸包。

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

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

算法 Incre_Convex（P）

輸入：三維空間中的n個點組成的集合P

輸出：P的凸包

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

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

（3）取其余各點的一個隨機排列：p5，p6，p7，…，pn，循環(huán)逐一處理各點，并動態(tài)維護凸包。

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

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

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

（7）重復步驟（4）～（6），直至處理完所有的點。

（8）結束

1.2 投影法計算體積

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

圖1 投影法

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

圖2 上三角網格

圖3 下三角網格

已知上三角網格面與下三角網格面都有三角面片組成。以上三角網格面為例，對于每一個三角面片t與投影面XOY組成一個凸五面體，故有：

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

同時，也可以用這種方法來判斷凸包的三角面片是屬于上三角網格面還是下三角網格面。取三角面片的任一點在XOY面上的投影點與三角面片構成四面體，當ε=1時，該面片屬上上三角網格面，當ε=-1時，該面片屬于下三角網格面，當ε=0時，該三角面片與投影面XOY垂直。

構什么？幾何圖形是由點與線構成，對于線基于尺規(guī)可以構造直線與弧線.因為兩點確定一條直線，所以構直線其實就是構造兩點；因為弧線取決于圓心與半徑，圓心與弧上任一點確定，其弧線也就確定，所以構造弧線也是構造兩點.總而言之，可以明確構什么？就是構造點.

如圖4所示，對于凸五面體ABCabc體積：

在這里要注意點的順序要求。

圖4 凸五面體

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

算法 Vol_Convex3D（P）

輸入：三維空間中的n個點的三維凸包

輸出：三維凸包的體積

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

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

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

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

（6）結束。

2 實驗結果

由于點云的原始體積數(shù)據很難獲得，使用Image Ware產生若干點云數(shù)據并預先手動計算其真實體積，用其測試算法準確度。再取若干組實際點云模型，測試算法效率。實驗結果如圖5、表1所示。

圖5 測試點云模型

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

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

圖6 實際點云模型

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

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

3 結束語

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

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

[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]王泉德.任意三角網格模型體積的快速精確計算方法[J].計算機工程與應用，2009，45（18）：32-34.

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