點云數(shù)據(jù)三角化

1、第1章、1.1空間曲面上散亂數(shù)據(jù)三角剖分的概念目前有多種方法可以獲得物理模型的形狀信息。在制造工業(yè)中最常使用的是 坐標(biāo)測量機(Coordinate Measuring Machine,CMM)。坐標(biāo)測量機能精確測量物體表 面上點的位置，但其測量速度較慢，當(dāng)測量點數(shù)較多時，效率很低，一般用在對 精度要求較高的場合，如檢查零件的形狀精度、位置精度等。當(dāng)需要大量獲取零 件表面的數(shù)據(jù)點時，一般使用激光掃描儀(Laser Scanner)。激光掃描儀能在相對 較短的時間內(nèi)得到大量零件表面的數(shù)據(jù)點。另外一種在醫(yī)學(xué)上常用的測量設(shè)備是 計算機斷層掃描儀(Computerized Tomography,CT)。

2、CT得到的是物體的輪廓線， 數(shù)據(jù)點呈層狀分布，每一層代表物體的一個剖面。這些測量設(shè)備得到的數(shù)據(jù)點形式各不相同，雖然在局部上某些數(shù)據(jù)點具有有 組織的狀態(tài)，如激光掃描儀和CT所得的數(shù)據(jù)點呈現(xiàn)層狀的特點，但在全局上基 本均表現(xiàn)出散亂的特點。所謂散亂數(shù)據(jù)的三角剖分就是給定一組散亂數(shù)據(jù)點，將各數(shù)據(jù)點之間以三角形相互連接，形成一張三角網(wǎng)格。其實質(zhì)是以三角網(wǎng)格反映數(shù)據(jù)點與其鄰近 點間的拓?fù)溥B接關(guān)系。而正確的拓?fù)溥B接關(guān)系將有效揭示散亂數(shù)據(jù)集所蘊涵的原 始物體表面的形狀和拓?fù)浣Y(jié)構(gòu)。1.2空間曲面上散亂數(shù)據(jù)三角剖分的研究意義及應(yīng)用范圍空間曲面上散亂數(shù)據(jù)的三角剖分是構(gòu)造散亂數(shù)據(jù)插值曲面的必不可少的前 置處理步驟，也

3、是最重要最關(guān)鍵的一步，基于散亂數(shù)據(jù)點三角剖分構(gòu)造散亂數(shù)據(jù) 插值曲面的過程如圖1所示：圖1.1構(gòu)造散亂數(shù)據(jù)插值曲面的步驟空間曲面上散亂數(shù)據(jù)的三角剖分是在對測量數(shù)據(jù)點必要的處理之后進(jìn)行的， 它是構(gòu)造散亂數(shù)據(jù)插值曲面的前置處理步驟。平面域內(nèi)的散亂數(shù)據(jù)的三角剖分研 究己經(jīng)經(jīng)歷了相當(dāng)長的時間，相關(guān)理論與算法己經(jīng)相當(dāng)成熟，特別是Delaunay 三角剖分及其優(yōu)化準(zhǔn)則等研究成果使得平面內(nèi)的散亂數(shù)據(jù)點的三角剖分已經(jīng)不 再困難。但在把平面內(nèi)的算法推廣到空間曲面上時，由于空間曲面散亂數(shù)據(jù)點之 間拓?fù)潢P(guān)系的復(fù)雜性，對其直接剖分的理論和算法尚不完善。在處理空間曲面上 數(shù)據(jù)點時，一般的算法都是基于平面凸域的或者是已知各

4、種約束條件的情況，對 于與多值曲面對應(yīng)的空間曲面上散亂數(shù)據(jù)點的三角剖分算法研究的較少，且在算 法效率和剖分效果上還遠(yuǎn)遠(yuǎn)不能讓人滿意。散亂數(shù)據(jù)曲面重構(gòu)的難點在于如何在數(shù)據(jù)點集中快速自動得到鄰近點間正 確的拓?fù)溥B接關(guān)系。目前的測量設(shè)備能夠在短時間內(nèi)得到數(shù)萬乃至幾十萬數(shù)據(jù) 點，所能體現(xiàn)的曲面形狀信息越來越精細(xì)和復(fù)雜，因此對曲面構(gòu)造的效率和效果 提出了較高的要求。研究散亂數(shù)據(jù)特別是大規(guī)模散亂數(shù)據(jù)的三角剖分，對于迅速 構(gòu)建數(shù)據(jù)點之間的拓?fù)溥B接關(guān)系，進(jìn)而構(gòu)造插值曲面具有十分重要的意義。散亂數(shù)據(jù)的三角剖分不但是構(gòu)造散亂數(shù)據(jù)插值曲面的重要基礎(chǔ)，對三維數(shù)據(jù) 場的可視化、快速原型制造等新技術(shù)的研究也有巨大的推動作

5、用。因此廣泛應(yīng)用 于測量造型、計算機視覺、醫(yī)學(xué)、氣像、勘探、環(huán)保等領(lǐng)域中。本文所要研究三維散亂數(shù)據(jù)的直接剖分方法旨在探索解決與復(fù)雜曲面對應(yīng) 的散亂數(shù)據(jù)點的三角化方法，快速準(zhǔn)確地生成優(yōu)化的三角網(wǎng)格，為構(gòu)造散亂數(shù)據(jù) 插值曲面做好準(zhǔn)備。因此本文關(guān)于空間曲面上散亂數(shù)據(jù)三角剖分方法的研究對散 亂數(shù)據(jù)插值曲面的構(gòu)造以及逆向工程曲面重構(gòu)方法的研究有著重要的現(xiàn)實意義， 對三維數(shù)據(jù)場的可視化、基于CT圖像的體數(shù)據(jù)的三維模型重建等應(yīng)用研究也有 一定的借鑒與參考價值。第2章22.1引言空間曲面上散亂數(shù)據(jù)的三角剖分是科學(xué)計算與分析中的一種重要方法，在計 算幾何散亂數(shù)據(jù)插值曲面構(gòu)造和三維數(shù)據(jù)場可視化中得到了廣泛應(yīng)用。對

6、空間曲 面上散亂數(shù)據(jù)的三角剖分方法的研究不論是在二維平面區(qū)域還是在三維空間區(qū) 域上都己經(jīng)有了很多成果，尤其是對二維平面散亂數(shù)據(jù)三角剖分的研究，其理論 和算法已經(jīng)比較成熟，相對來說對空間曲面亂數(shù)據(jù)的三角剖分，特別是曲面形狀 比較復(fù)雜、散亂數(shù)據(jù)點的數(shù)目很大時，目前的算法在適應(yīng)性、執(zhí)行效率等方面還 有待進(jìn)一步提高。2.2問題描述及分類問題2.1:給定一組散亂數(shù)據(jù)點Vi(i=1,2,?，n)，如何將各數(shù)據(jù)點之間以三角 形相互連接，形成一張三角網(wǎng)格，并使網(wǎng)格質(zhì)量較優(yōu)。該問題的解是散亂點集Vi 的一個三角剖分T，其實質(zhì)是以三角網(wǎng)格M反映各個數(shù)據(jù)點與其鄰近點之間的 拓?fù)溥B接關(guān)系，從而揭示數(shù)據(jù)點之間的內(nèi)在本質(zhì)

7、聯(lián)系。三角剖分所涉及的問題在 實際應(yīng)用中根據(jù)數(shù)據(jù)點位置的不同有三種情況:二維，三維實體和空間曲面。根 據(jù)這種情況，空間曲面上散亂數(shù)據(jù)的三角剖分可分為對空間曲面上散亂數(shù)據(jù)投影 域的剖分和在空間中直接剖分兩種類型?？臻g曲面上散亂數(shù)據(jù)的投影域包括平面 域和球面域。直接三角剖分方法研究如何直接將空間曲面上散亂數(shù)據(jù)點在空間中 連接成一個優(yōu)化的三角網(wǎng)格。2.3三角剖分2.3.1定義定義2.1：給定Ed中k個不相同的點P , P , PP點集 123kP= a p + a p + a p +a p ( a gr, a 河，a + a + a + a =1) (3.1)112233kk k1123k是由p ,

8、 p2，p生成的凸集。定義2.2：給定一個點集的任意子集L, L的凸殼是包含L的最小的子集。定義2.3:給定平面內(nèi)的頂點的集合Vi(i=1,2,n),用不相交的直線段連接vi和vj, 1Wi,jWn,i勺.使得n個點的凸殼內(nèi)每一個區(qū)域是一個三角形。圖2.2平面點集的一種三角剖分一般來說，對頂點集合Vi的三角剖分不是唯一的，有多種剖分結(jié)果都能滿 足上述定義。當(dāng)然，其中只有部分結(jié)果的三角剖分網(wǎng)格的形態(tài)較優(yōu)，能夠滿足際 應(yīng)用的需求。在許多應(yīng)用中，最好是三角形盡可能是“等邊”的，或邊總長度最 小，當(dāng)三角剖分邊的總長度減至最小時，則稱為最小權(quán)三角剖分。2.3.2三角剖分基本理論Voronoi 圖與 De

9、launay 三角剖分平面三角剖分的實質(zhì)是以三角形反映數(shù)據(jù)點與其鄰近點之間的拓?fù)溥B接關(guān) 系。若能首先找出平面上一點的所有鄰近點，則問題2.1在平面上的情況就好辦 多了，為此需要解決下面的問題：問題2:給定平面中n個點的集合S=P1,P2,P3,P4對于平面中比其它點更 接近于P的點(x,y)軌跡是什么？圖2.3定義2.4:給定平面中n個點的集合s,V(pi)在平面S中比其它點更接近于的 Pi點的軌跡是n-1個半平面的交，它是一個不多于n-1條邊的凸多邊形域，稱 V(pi)為關(guān)聯(lián)于P的Voronoi多邊形或關(guān)聯(lián)于P的Voronoi域。圖2.4表示關(guān)聯(lián)于 pi的一個Voronoi多邊形，它是一個五

10、邊形，n=6。圖2.4對于S中的每一個點都可以作一個Voronoi多邊形，這樣的n個Voronoi多 邊形組成的圖成為Voronoi圖，記為Vor(S)，如圖2.5所示。該圖中的頂點分別 稱為Voronoi頂點和Voronoi邊。Vor(S)的邊是某點對的垂直平分線上的一條線段 或者半直線，從而為該點對所在的兩個多邊形域所共有。Vor(S)中有的多邊形域 是無界的。圖2.5在敘述Voronoi圖的性質(zhì)時作假設(shè):原來集合S中沒有四個點是共圓的。若此 假設(shè)不成立，則需要在證明中加入一些無關(guān)緊要的，但卻是冗長的陳述。在敘述Voronoi圖的性質(zhì)時作假設(shè)“原來集合S中沒有四個點是共圓的。若 此假設(shè)不成

11、立，則需要在證明中加入一些無關(guān)緊要的，但卻是冗長的陳述。圖2.6圖2.6定理2.1:對于S的Voronoi圖每一個頂點v，圓C(v)不包含S的其它點。由 于定理2.1： Vor(S)又稱為最近點意義下的Voronoi圖。定理2.2：在S中，Pi的每一個最近點確定Voronoi多邊形v(pi)的一條邊。忙甲什緲*P.圖2.7圖2.7 P的每一個最近鄰近點確定v(pi)定義2.5:Voronoi圖的直線對偶是由S的每個點對之間加入一個直線段以獲 得嵌入平面的圖，產(chǎn)生的圖是原來n個點上的一個圖。如圖2.5中的虛線所示。對偶的重要性主要歸于下面的Delaunay定理。定理2.3:Voronoi圖的直線

12、對偶是S的一個三角剖分。圖2.5中的虛線即是S 的一個三角剖分。Voronoi圖的這些性質(zhì)可以用來快速構(gòu)造Voronoi圖，且可應(yīng)用它解決最鄰 近點問題和三角剖分問題。定義2.6:在一個三角剖分中，若每一個三角形的外接圓為空(即在外接圓中 不含有其它點)，則該三角剖分稱為Delaunay三角剖分。對于給定的一組平面數(shù)據(jù)點集S，可以多種不同的三角剖分，其中Delaunay 三角剖分是最優(yōu)的，二維Delaunay三角剖分由滿足最小內(nèi)角最大準(zhǔn)則的三角形 組成。下一節(jié)將介紹詳細(xì)三角剖分準(zhǔn)則。2.3.2.2三角剖分優(yōu)化準(zhǔn)則在三角剖分過程中，往往用一種比較簡單的方法構(gòu)造散亂數(shù)據(jù)點的初始三角 網(wǎng)格，然后對其

13、進(jìn)行優(yōu)化，以獲得較優(yōu)化的三角形網(wǎng)格。優(yōu)化的方法和效果取決 于所采用的優(yōu)化準(zhǔn)則。平面三角剖分常采用的優(yōu)化準(zhǔn)則有Thiessen區(qū)域準(zhǔn)則、最 小內(nèi)角最大準(zhǔn)則、圓準(zhǔn)則。Sibson證明了這三個準(zhǔn)則的等價性，并指出符合這三個準(zhǔn)則的三角剖分只有 一個，艮口 Delaunay 三角化。今 Thiessen 區(qū)域準(zhǔn)則(Thiessen regioncriterion)Thiessen 區(qū)域指Voronoi分割后形成的多邊形區(qū)域。如果兩個區(qū)域具有非零長度的公共線 段，則稱這兩個區(qū)域的生成點為Thiessen強鄰接點(strongThiessen neighbours);如 果它們的公共部分僅是一個點，則稱為T

14、hiessen弱鄰接點(weak Thiessen neighbours)o 一個嚴(yán)格凸的四邊形至多有一對相對頂點是Thiessen強鄰接點。 Thiessen區(qū)域準(zhǔn)則指對一個嚴(yán)格凸的四邊形三角化時，將Thiessen強鄰接點相連， 若兩對頂點都是Thiessen弱鄰接點，則任選一對相連，這樣構(gòu)造的三角化是最優(yōu) 的，見圖2.8:圖2.8 Thiessen區(qū)域準(zhǔn)則最小內(nèi)角最大準(zhǔn)則在平面內(nèi)，對一個嚴(yán)格凸的四邊形進(jìn)行三角化時，有兩種選擇，最小內(nèi)角最大準(zhǔn)則就是要保證對角線兩側(cè)兩個三角形中的最小內(nèi)角最大。如圖2.9所示：圖2.9最小內(nèi)角最大準(zhǔn)則圓準(zhǔn)則嚴(yán)格凸的四邊形中的三個點確定一個圓，如果第四個頂點落在

15、圓內(nèi)，則將第 四個頂點與其相對的頂點相連，否則將另兩個相對頂點相連，如圖210所示：圖2.10圓準(zhǔn)則平面三角剖分優(yōu)化準(zhǔn)則理論為平面內(nèi)散亂點集的快速三角剖分提供了判斷 標(biāo)準(zhǔn)，也為三維空間散亂點集的三角剖分優(yōu)化標(biāo)準(zhǔn)提供了借鑒依據(jù)。2.3.3經(jīng)典三角化算法三角化算法雖然很多，但大多算法生成的是Delaunay三角網(wǎng)格，即以空外 接圓(球)準(zhǔn)則為優(yōu)化準(zhǔn)則。根據(jù)實現(xiàn)方法的不同，Delaunay三角化方法。主要有三類：換邊法(Swapping edges):首先構(gòu)造非優(yōu)化的初始三角化，然后對2個共邊三 角形形成的凸四邊形迭代換邊優(yōu)化。以Lawson為代表的對角線交換算法屬于換 邊法，換邊法適用于二維Del

16、aunay三角化，對于三維Delaunay三角化，則需要 對共面四面體進(jìn)行換面優(yōu)化。加點法(Adding points):從一個三角形開始，每次加一個點，保證每一步得到 的當(dāng)前三角化是局部優(yōu)化的。以英國Bath大學(xué)數(shù)學(xué)分校Bowyer,Green,Sibson為 代表的計算Dirichlet圖的方法屬于加點法，是較早成名的算法之一;以澳大利亞 悉尼大學(xué)地學(xué)系Watson為代表的空外接球法亦屬于加點法。加點法算法簡明， 是目前應(yīng)用最多的算法。分割占有法(Devide and conquer):將數(shù)據(jù)域遞歸細(xì)分為子 塊，每塊實現(xiàn)局部優(yōu)化三角化，然后合并。對應(yīng)于上述三類算法各有一些著名的 算法。Bo

17、wyer 算法該算法基于Dirichlet圖的構(gòu)造，適用于n維空間中的離散點集的網(wǎng)格剖分， 是英國Bath大學(xué)數(shù)學(xué)分校的A.Bowyer在總結(jié)該校Robin Sibson教授、 PeterJ.Green博士七十年代所做工作的基礎(chǔ)上，于1981年提出的。算法思路Bowyer算法是針對Voronoi圖的實現(xiàn)，首先開始于一個由n+1個數(shù)據(jù)點形 成的Delaunay單純體，這樣將得到一個包含一個真實頂點、而其它頂點為無窮 遠(yuǎn)點0的Voronoi圖:如圖2-17所示，往己有數(shù)據(jù)形成的Voronoi圖中加入新點Q， 從包含新點的Voronoi多邊形開始，利用Voronoi多邊形相鄰關(guān)系，找到最近點， 構(gòu)造

18、新加入點的Voronoi多邊形(粗虛線)。圖2-L7在已有山”叫皿圖中如入新泌堂成其MWQjKi爭訕莎的過程算法分析該算法整體效率為O(n(k +1/k),k為空間的維數(shù)。基于Voronoi圖的Bowyer 算法計算復(fù)雜，空間消耗大，算法時空效率不高。Watson 算法該算法是澳大利亞悉尼大學(xué)Geology與Geophyics系D.F Watson于1981年 提出的，是用計算機構(gòu)造品體模型的研究成果。算法思想首先給出由一個或多個外接球不包含其它數(shù)據(jù)點的單純體組成的初始網(wǎng)格， 然后往其中加入一個數(shù)據(jù)點，考察外接球的包含情況，去除包含新點的n維單純 體，用n+2個點能組合的、外接圓不包含其它點的

19、單純體取代。如圖2-18所示 是Watson算法的具體思路。具體實現(xiàn)時，可一次性全部找出并刪除所有包含新 加入點的單純體，得到一個包含新點的空洞，空洞的邊界面與新點相連，得到新 點加入后的Delaunay網(wǎng)格，這樣可避免進(jìn)行新生成單元的外接圓是否包含old points的計算，具體加入一點的算法流程敘述如下。算法流程加入新點，搜索單純體鏈表，查找外接球包含新點的單純體，所有包含 新點的單純體組成一個多面體。包含新點的單純體的各個面加入一個臨時鏈表，若一個面加入兩次，說 明是兩個單純體共享的面，必然位于多面體的內(nèi)部，從鏈表中刪除，若出現(xiàn)新點 位于外接球上的退化情形，則拋棄鏈表和新點，改用其它方法

20、處理。若未出現(xiàn)退化情形，則將新點與多面體的各個面相連，得到新的單純體。新點加入過程結(jié)束。算法分析Watson算法的思路非常簡明，易于編程實現(xiàn)。但當(dāng)出現(xiàn)k+2（k為空間維數(shù)） 點位于同一圓球面時，則三角化結(jié)果不唯一，這種情形稱為退化情形。如圖2-19, 為二維空間的退化情形。除了如圖2-20所示的規(guī)則數(shù)據(jù)，實際應(yīng)用中散亂數(shù)據(jù) 點集很少出現(xiàn)退化情形。但由于計算機的計算精度是有限的，當(dāng)新點與外接球球 面之間的距離小于預(yù)設(shè)計算精度，則認(rèn)為新點位于球面上;這種新點與球面距離 的計算誤差可能引起拓?fù)潢P(guān)系的不一致。2.3.3.3四叉樹、八叉樹方法四叉樹、八叉樹本身是數(shù)據(jù)結(jié)構(gòu)，當(dāng)用于空間編碼時，可進(jìn)行實體造型

21、，適 當(dāng)修改即成為網(wǎng)格剖分算法。M A Yerry.M S Shephard于 1983年、1984年發(fā)表 13 了四叉樹、八叉樹在二維、三維網(wǎng)格剖分中的應(yīng)用，有些文獻(xiàn)中將他們的算 法稱為Shephard-Yerry算法。Shephard-Yerry算法只適用于域剖分。網(wǎng)格單元可 以是四邊形/六面體，也可以是三角形/四面體。這種算法的特點是與實體造型相 結(jié)合，自動化程度高，網(wǎng)格密度可調(diào)整，剖分速度快，內(nèi)部單元形狀比較好，但 邊界單元形狀很難保證。在二維空間，以矩形網(wǎng)格為例，邊界單元共有16種被 截情形;三維六面體網(wǎng)格單元被邊界面截切后共有4096種情形，被切后的單元與 原有網(wǎng)格單元拓?fù)潢P(guān)系可能

22、不一致，需要進(jìn)行拓?fù)渥儞Q。此外，這種方法不具備 幾何不變性，即剖分對像旋轉(zhuǎn)后，剖分結(jié)果發(fā)生變化。韓國中央大學(xué)YH Jung和K Lee于1993年提出了一種直接基于四面體的八 叉樹空間編碼法。這種算法一步到位，內(nèi)部單元為四面體，邊界單元易于處理為 四面體，不需要拓?fù)渥儞Q?？傊?，Shephard-Yerry算法由于與實體造型技術(shù)相結(jié) 合，是一種很有前途的方法，一旦邊界單元得到很好處理，則必在實體網(wǎng)格剖分 方面占據(jù)主要地位。2.3.3.4換邊換面1977年，美國加利福利亞工學(xué)院噴氣推進(jìn)實驗室的Charles L.Lawson提出了 基于邊交換的二維Delaunay三角化。加拿大埃德蒙頓Albert

23、a大學(xué)計算機科學(xué)系 Barry Joe分別于1989年、1991年給出了基于局部換面的三維Delaunay三角化 的算法和證明。算法分析換邊換面法適用于離散點集剖分和域剖分，算法過程簡明，容易實現(xiàn)。但是 三維三角化算法過程中需要檢測的面很多，有效控制變換的范圍，合理的數(shù)據(jù)結(jié) 構(gòu)和快速的查詢法是提高速度的關(guān)鍵。換邊換面法的最大的困難在于如何處理不 可變換的情形，這是本文研究的關(guān)鍵問題。只有解決不可變換的情形，才能得到 delaunay三角剖分網(wǎng)格；否則，結(jié)果是非delaunay的。2.3.3.5網(wǎng)格的前言生成法。網(wǎng)格的前沿生成法從提出到現(xiàn)在發(fā)展最快，現(xiàn)在有了很多的算法。最早法國 學(xué)者S H Lo

24、于1985年在文獻(xiàn)中提出了網(wǎng)格前沿法的雛形，只將網(wǎng)格前沿法作為 節(jié)點連元的方法，沒有與節(jié)點生成同時考慮。英國學(xué)者J.Peraire,M.Vabdati,K.Morga.等于1987年實現(xiàn)了按方向細(xì)化的網(wǎng)格前沿法。此后 研究的各種網(wǎng)格前沿法最大的特征是能夠生成復(fù)雜形狀的非結(jié)構(gòu)網(wǎng)格，其按方向 細(xì)化的特點特別適合于三維可壓縮流的優(yōu)化算法。算法思路以剖分域的邊界為網(wǎng)格的初始前沿，按-設(shè)定的網(wǎng)格單元的形狀，尺度等要 求向域內(nèi)生成節(jié)點，連成單元，同時更新網(wǎng)格前沿，如此逐層向剖分域內(nèi)推進(jìn)， 直到所有的空間都被剖分。算法分析網(wǎng)格前沿法能夠處理比較復(fù)雜的對像，其主要特點是提供了控制網(wǎng)格密度和 質(zhì)量的手段。但是網(wǎng)

25、格前沿法中存在大量的查詢操作以及網(wǎng)格前沿面的相交檢 測，這些操作是很浪費時間的。很多算法在這兩點上作了快速的處理。下圖是網(wǎng) 格前沿法生成的三角網(wǎng)格實體。第3章空間曲面上散亂數(shù)據(jù)點的快速三角剖分算法實現(xiàn)3.1采用的數(shù)據(jù)結(jié)構(gòu)點類，點節(jié)點類，點鏈表類，邊類，邊節(jié)點類，邊鏈表類（多邊形類），三 角形類，三角形節(jié)點類，三角形鏈表類。以下對這幾種結(jié)構(gòu)做簡單的介紹（只介紹主要的）：點類中的數(shù)據(jù)成員class Point_Tdouble m_X;/空間點的坐標(biāo)double m_Y;double m_Z;下面是一些方法點節(jié)點類中的數(shù)據(jù)成員。class PNode_TPont_T m_Point;PNode_T*

26、m_Left;PNode_T*m_Right;下面是一些方法點鏈表類中的數(shù)據(jù)成員。class PNList_TPNode_T*m_Head;PNode_T*m_Tail;下面是一些方法略邊類中的數(shù)據(jù)成員。class Edge_TPont_T m_Point1;Pont_T m_Point2;Pont_T m_Point3;/所在三角形第三個點bool m_Used;/表示這條邊是活邊還是死邊/下面是一些方法略邊節(jié)點類中的數(shù)據(jù)成員。class ENode_TEdge_T m_Edge;ENode_T*m_Right;ENode_T*m_Left;/下面是一些方法略多邊形類中的數(shù)據(jù)成員。class

27、 Polygone_TENode_T*m_Head;ENode_T*m_Tail;Int m_LivingEdgeNum;/邊界前沿中的火邊數(shù)量。下面是一些方法略三角形類中的數(shù)據(jù)成員。class Triangle_TPont_T m_Point1;Pont_T m_Point2;Pont_T m_Point3;/所在三角形第三個點/下面是一些方法略三角形節(jié)點類中的數(shù)據(jù)成員class TriNode_TTriangle_T m_Triangle;TriNode_T*m_Right;TriNode_T*m_Left;/下面是一些方法略三角形鏈表類中的數(shù)據(jù)成員class TriNList_TTriN

28、ode_T*m_Head;TriNode_T*m_Tail;/下面是一些方法略點鏈表：存儲點云數(shù)據(jù)的一個單向鏈表。三角形鏈表：生成的三角形存儲在單鏈表中。前沿邊界（多邊形）：多邊形采用邊的雙循環(huán)鏈表的形式存儲。3.2三角剖分的過程定義：內(nèi)邊：三角剖分結(jié)果中被兩個三角形公用的邊。外邊：三角剖分的結(jié)果中只被一個三角形擁有的邊。內(nèi)點：如果一個點的相連邊都是內(nèi)邊這個點就是內(nèi)點?；钸叄簺]有經(jīng)歷找點生成新邊過程的邊。這里要強調(diào)，活邊經(jīng)歷找點生成新 邊過的程，可能找到了匹配點，可能沒找到匹配點，可能會產(chǎn)生0條新邊，1條 新邊或2條新邊。死邊：經(jīng)歷一次找點生成新邊過程的邊就是死邊。死邊可以是邊界邊，也可 以是

29、外邊。外邊框：由外邊首尾相連構(gòu)成的空間多邊形就是外邊框。邊界點：在外邊框中的頂點。外點：沒有被選擇過的點。3.2.1算法簡單描述：（1）：點云的預(yù)處理。（2）：構(gòu)造一個相對飽滿的初始三角形作為種子三角形。（3）：開始循環(huán)：如果外邊界框中的活邊的數(shù)量不是零，就繼續(xù)下面的步驟。 否則算法結(jié)束。（4）：對外邊框做循環(huán)：ENMov=:外邊框的頭節(jié)點。（5）：如果ENMov是活邊：選擇匹配的點，如果選擇到了匹配點就更新點 鏈表，更新三角形鏈表，更新外邊框鏈表；如果沒選擇到匹配點，把ENMov標(biāo) 志成死邊used=1。如果ENMov是死邊：什么也不做。（6）： ENMov=：外邊框更新前ENMov的下一個

30、節(jié)點。如果ENMov是空 的，那么返回（3），否則返回（5）。以下對算法中的各個步驟做詳細(xì)的解釋。3.2.2數(shù)據(jù)點的預(yù)處理（1）：把點云數(shù)據(jù)文件中的點讀到點單鏈表中。（2）： PNMov=:點鏈表的頭節(jié)點。（3）：在鏈表中刪掉PNMov節(jié)點后面到PNMov距離小于DIST的所有的節(jié) 點。其中DIST是一個可以指定的數(shù)，其數(shù)值越大剩下的點越少。（4）： PNMov=:點鏈表中PNMov的下一個節(jié)點。（5）： PNMov如果不是鏈表的尾節(jié)點：返回（3）。否則結(jié)束。處理后的點 相對少得多，也保證處理后的點云要相對的均勻，最主要的是去掉了曲率過大的 點。3.2.3初始三角形的建立（1）：先得到點云鏈表

31、中的第一個點作為firstPoint。（2）：然后得到在firstPoint后面，距離firstPoint最近點作為第二個點 secondPoint。（3）：這兩個點構(gòu)成了一條邊。在secondPoint后面的點中尋找距離第一條 邊的兩個端點的距離和最小的點作為第三個點thirdPoint。（4）：如果這個三角形的最小的內(nèi)角小于30度。那么選擇點云鏈表firstPoint 節(jié)點的下一個節(jié)點為firstPoint，返回（2）。否則，結(jié)束。3.2.4活邊尋找最佳匹配點的算法為了加快運算的速度我們采用包圍盒算法。一個點要成為當(dāng)前邊的候選點要 具備的必要條件。i:這個點和當(dāng)前邊構(gòu)成的三角形于當(dāng)前邊所在的三角形鉤成的面角要大于給 定的閥值 MINFACEANGLEO卜面介紹空間中兩個面的二面角的計算方法。三角形p1p2p3和三角形p1p2p4所成的二面角的大小等于向量p5p4與向量 p6p3所成的角P1p5是p1p4在p1p2上面的投影向量,p1p6是向量p1p3在