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

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

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

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

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

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

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

7、聯(lián)系。三角剖分所涉及的問(wèn)題在 實(shí)際應(yīng)用中根據(jù)數(shù)據(jù)點(diǎn)位置的不同有三種情況:二維，三維實(shí)體和空間曲面。根 據(jù)這種情況，空間曲面上散亂數(shù)據(jù)的三角剖分可分為對(duì)空間曲面上散亂數(shù)據(jù)投影 域的剖分和在空間中直接剖分兩種類(lèi)型?？臻g曲面上散亂數(shù)據(jù)的投影域包括平面 域和球面域。直接三角剖分方法研究如何直接將空間曲面上散亂數(shù)據(jù)點(diǎn)在空間中 連接成一個(gè)優(yōu)化的三角網(wǎng)格。2.3三角剖分2.3.1定義定義2.1：給定Ed中k個(gè)不相同的點(diǎn)P , P , PP點(diǎn)集 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：給定一個(gè)點(diǎn)集的任意子集L, L的凸殼是包含L的最小的子集。定義2.3:給定平面內(nèi)的頂點(diǎn)的集合Vi(i=1,2,n),用不相交的直線段連接vi和vj, 1Wi,jWn,i勺.使得n個(gè)點(diǎn)的凸殼內(nèi)每一個(gè)區(qū)域是一個(gè)三角形。圖2.2平面點(diǎn)集的一種三角剖分一般來(lái)說(shuō)，對(duì)頂點(diǎn)集合Vi的三角剖分不是唯一的，有多種剖分結(jié)果都能滿 足上述定義。當(dāng)然，其中只有部分結(jié)果的三角剖分網(wǎng)格的形態(tài)較優(yōu)，能夠滿足際 應(yīng)用的需求。在許多應(yīng)用中，最好是三角形盡可能是“等邊”的，或邊總長(zhǎng)度最 小，當(dāng)三角剖分邊的總長(zhǎng)度減至最小時(shí)，則稱(chēng)為最小權(quán)三角剖分。2.3.2三角剖分基本理論Voronoi 圖與 De

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

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

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

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

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證明了這三個(gè)準(zhǔn)則的等價(jià)性，并指出符合這三個(gè)準(zhǔn)則的三角剖分只有 一個(gè)，艮口 Delaunay 三角化。今 Thiessen 區(qū)域準(zhǔn)則(Thiessen regioncriterion)Thiessen 區(qū)域指Voronoi分割后形成的多邊形區(qū)域。如果兩個(gè)區(qū)域具有非零長(zhǎng)度的公共線 段，則稱(chēng)這兩個(gè)區(qū)域的生成點(diǎn)為T(mén)hiessen強(qiáng)鄰接點(diǎn)(strongThiessen neighbours);如 果它們的公共部分僅是一個(gè)點(diǎn)，則稱(chēng)為T(mén)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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