1、計(jì)算機(jī)輔助設(shè)計(jì)的發(fā)展與應(yīng)用三維建模摘要：我們身在一個(gè)三維的世界中，三維的世界是立體的、真實(shí)的。同時(shí)，我們處于一個(gè) 信息化的時(shí)代里，信息化的時(shí)代是以計(jì)算機(jī)和數(shù)字化為表征的。隨著計(jì)算機(jī)在各行各業(yè)的廣 泛應(yīng)用，人們開始不滿足于計(jì)算機(jī)僅能顯示二維的圖像，更希望計(jì)算機(jī)能表達(dá)出具有強(qiáng)烈真 實(shí)感的現(xiàn)實(shí)三維世界。三維建?？梢允褂?jì)算機(jī)作到這一點(diǎn)。所謂三維建模，就是利用三維數(shù) 據(jù)將現(xiàn)實(shí)中的三維物體或場(chǎng)景在計(jì)算機(jī)中進(jìn)行重建，最終實(shí)現(xiàn)在計(jì)算機(jī)上模擬出真實(shí)的三維 物體或場(chǎng)景。而三維數(shù)據(jù)就是使用各種三維數(shù)據(jù)采集儀采集得到的數(shù)據(jù)，它記錄了有限體表 面在離散點(diǎn)上的各種物理參量。它包括的最基本的信息是物體的各離散點(diǎn)的三維坐標(biāo)，

2、其它 的可以包括物體表面的顏色、透明度、紋理特征等等。三維建模正在廣泛地應(yīng)用于越來越多 的領(lǐng)域，并且以其提供直觀、方便的三維圖像等特點(diǎn)在各領(lǐng)域中發(fā)揮越來越重要的作用。關(guān)鍵字：三維建模、三維模型繪制、傘狀網(wǎng)絡(luò)1、三維數(shù)據(jù)的應(yīng)用我們身在一個(gè)三維的世界中，三維的世界是立體的、真實(shí)的。同時(shí)，我們處于一個(gè)信息 化的時(shí)代里，信息化的時(shí)代是以計(jì)算機(jī)和數(shù)字化為表征的。隨著計(jì)算機(jī)在各行各業(yè)的廣泛應(yīng) 用，人們開始不滿足于計(jì)算機(jī)僅能顯示二維的圖像，更希望計(jì)算機(jī)能表達(dá)出具有強(qiáng)烈真實(shí)感 的現(xiàn)實(shí)三維世界。三維建?？梢允褂?jì)算機(jī)作到這一點(diǎn)。所謂三維建模，就是利用三維數(shù)據(jù)將 現(xiàn)實(shí)中的三維物體或場(chǎng)景在計(jì)算機(jī)中進(jìn)行重建，最終實(shí)現(xiàn)在

3、計(jì)算機(jī)上模擬出真實(shí)的三維物體 或場(chǎng)景。而三維數(shù)據(jù)就是使用各種三維數(shù)據(jù)采集儀采集得到的數(shù)據(jù)，它記錄了有限體表面在 離散點(diǎn)上的各種物理參量。它包括的最基本的信息是物體的各離散點(diǎn)的三維坐標(biāo)，其它的可 以包括物體表面的顏色、透明度、紋理特征等等。三維建模在建筑、醫(yī)用圖像、文物保護(hù)、 三維動(dòng)畫游戲、電影特技制作等領(lǐng)域起著重要的作用。在建筑領(lǐng)域，一個(gè)建筑物如果用普通 二維圖片（比如照片）表示，會(huì)造成對(duì)某些細(xì)節(jié)部位或內(nèi)部構(gòu)造觀察的不方便。而建造時(shí)使 用的圖紙雖然包含了大量的信息，對(duì)于非專業(yè)人士來說卻不容易看懂而且很不直觀。如果使 用三維建模的方法重建出這個(gè)建筑的三維模型，那么就可以直接觀察這個(gè)建筑的各個(gè)側(cè)面

4、， 整體構(gòu)造，甚至內(nèi)部的構(gòu)造，這無論對(duì)于建筑師觀看設(shè)計(jì)效果，還是對(duì)于客戶觀看都是很方 便的。在醫(yī)學(xué)方面，自從100年前倫琴發(fā)現(xiàn) X射線以來，醫(yī)學(xué)圖像處理技術(shù)已經(jīng)經(jīng)歷 了很長(zhǎng)的路程。得到三維人體解剖圖 一直是人們努力追求的目標(biāo)。德國(guó)漢堡大學(xué)醫(yī)用數(shù) 學(xué)和醫(yī)用計(jì)算機(jī)研究所的Hohne教授領(lǐng)導(dǎo)的研究小組，開展了項(xiàng)目名稱為 Voxel-Man（體素和人）的解剖三維可視化研究。利用Voxel-Man的工具，醫(yī)生可以模擬外科手術(shù) 和立體定位或開洞。Voxel-Man具有極高的外科臨床和教學(xué)價(jià)值，這在醫(yī)學(xué)發(fā)展史上是 一個(gè)新的里程碑。另一個(gè)三維建模在醫(yī)學(xué)中的應(yīng)用是虛擬手術(shù) 。美國(guó)最負(fù)盛名的私立醫(yī) 院集團(tuán)Maya

5、 Clinic的生物醫(yī)學(xué)圖像處理資源中心，自70年代以來就致力于計(jì)算機(jī)生物醫(yī) 學(xué)圖像的研究。在已有十余年經(jīng)驗(yàn)的基礎(chǔ)上，他們開發(fā)和設(shè)計(jì)了可以讓外科醫(yī)生觀察 CT 和 MRI數(shù)據(jù)的3D交互式外科輔助系統(tǒng)。醫(yī)生可以在手術(shù)前預(yù)先規(guī)劃手術(shù)方案，這樣醫(yī) 生做手術(shù)就會(huì)更加準(zhǔn)確，同時(shí)還可以在計(jì)算機(jī)上預(yù)演手術(shù)過程，使手術(shù)更安全。三維建模在 文物保護(hù)中也發(fā)揮著重要的作用。有的文物或古建筑由于年代太久遠(yuǎn)或者各種侵蝕難以保 存，有些文物有著珍貴的價(jià)值不能直接供人們觀賞。可以利用三維建模將文物和古建筑通過 影像采集、數(shù)字處理、數(shù)據(jù)壓縮等技術(shù)制成三維形象，然后人們就可以隨意的從各個(gè)角度觀 看和欣賞文物和古建筑，同時(shí)也是一

6、種保存和研究文物的辦法。當(dāng)數(shù)據(jù)積累到一定程度，還 可以開展網(wǎng)絡(luò)博物館等文物展覽項(xiàng)目，可以在保護(hù)文物的同時(shí)達(dá)到更廣泛推廣的目的。近年 國(guó)內(nèi)開始逐漸重視這方面的工作，比如故宮數(shù)字博物館就在積極籌建中，其太和殿及其周邊 場(chǎng)景的三維模型就已經(jīng)由日本凸版株式會(huì)社制作完成，實(shí)現(xiàn)了場(chǎng)景漫游，具有相當(dāng)?shù)恼鎸?shí)感， 細(xì)節(jié)表現(xiàn)也很優(yōu)秀。在電腦游戲業(yè)高度發(fā)達(dá)的今天，盡量追求游戲的真實(shí)和畫面的華麗幾乎是所有制作者的 共識(shí)。于是，三維游戲應(yīng)運(yùn)而生，開始僅僅是在游戲中加入三維動(dòng)畫，現(xiàn)在已經(jīng)出現(xiàn)了全程 使用三維場(chǎng)景的游戲，比如Square Soft的Final Fantasy系列。以其優(yōu)美的人物設(shè)計(jì)以 及豪華的3D場(chǎng)景征服了

7、無數(shù)玩家，而成為風(fēng)靡全球游戲Final Fantasy X的主人公球的 暢銷游戲。右上方的圖像中是Square Soft于2002年推出的大作 Final Fantasy X中 的男女主人公，從人物到場(chǎng)景，全都使用了三維模型，而且刻畫極為精致細(xì)膩，有很好的視 覺效果和沖擊力。對(duì)比以前比較呆板的2D游戲，其在真實(shí)性和吸引力上的優(yōu)勢(shì)是顯而易 見的。在電影特技制作方面，三維建模技術(shù)也有著廣泛的應(yīng)用。起先，電影中的很多特殊場(chǎng) 景如外星球、古代城市等都要通過搭建微縮模型來實(shí)現(xiàn)拍攝，不僅成本高、耗時(shí)長(zhǎng)、后期制 作困難，而且也不容易有真實(shí)的效果。對(duì)于某些危險(xiǎn)的鏡頭，需要精密的布置和策劃，采用 各種防護(hù)措施，

8、最后還是不能保證萬無一失。當(dāng)三維建模技術(shù)被引進(jìn)之后，現(xiàn)實(shí)世界中不可 能出現(xiàn)的場(chǎng)景都可以被完美地構(gòu)造出來，許多危險(xiǎn)的鏡頭現(xiàn)在只需要在電腦前操作鼠標(biāo)就可 以完成，而且制作速度快、效果好。在最近的一兩年，三維建模技術(shù)運(yùn)用于電影制作取得了 令人驚異的進(jìn)展：出現(xiàn)了第一部完全由電腦制作的3D 仿真電影一一最終幻想，這部 由美國(guó)哥倫比亞三星電影公司出品的數(shù)字巨片耗資2.4億美元，歷時(shí)4年，它首次用電腦 來制作所有的演員、道具、布景，影片中沒有一個(gè)真人，但是虛擬演員在線條、毛發(fā)、皮膚、 紋理、表情等方面已經(jīng)幾乎與真人別無二致。顯示了電影中虛擬人物的3D模型和最后制 成的效果，其真實(shí)程度之高讓人不得不感嘆三維建

9、模技術(shù)的神妙?？傊?，三維建模正在廣泛地應(yīng)用于越來越多的領(lǐng)域，并且以其提供直觀、方便的三維圖 像等特點(diǎn)在各領(lǐng)域中發(fā)揮越來越重要的作用。在三維建模中，最主要的問題就是使用三維數(shù)據(jù)進(jìn)行繪制，如何使得繪制出的模型有立 體感和真實(shí)感，要保證模型的表面平滑、無毛刺、無漏洞，達(dá)到比較理想的視覺效果；同時(shí) 還要較好地組織數(shù)據(jù)，減少存儲(chǔ)空間以便于數(shù)據(jù)的傳輸和加快顯示速度。下一章將介紹已有 的三維數(shù)據(jù)繪制方法以及本文提出的新方法。2、三維數(shù)據(jù)繪制方法2.1三維數(shù)據(jù)的獲取和網(wǎng)格繪制要建立真實(shí)物體的三維模型，首先要獲取樣本的相關(guān)屬性，如幾何形狀、表面紋理等等。 記錄這些信息的數(shù)據(jù)就稱為三維數(shù)據(jù)，我們定義采集樣本的信息

10、并且將其組織成為一種表達(dá) 與樣本一致的結(jié)構(gòu)的過程為三維數(shù)據(jù)的獲取。采集樣本三維信息的方法大致有以下幾種：直 接設(shè)計(jì)或測(cè)量：多用于早期建筑物三維模型的建立，用工程作圖的方式得到模型的三視圖。圖像方法：只通過照片建立三維模型，用拍照的方式同時(shí)獲得幾何和紋理的信息，以此 為基礎(chǔ)重建樣本的3D模型。機(jī)械探針(Mechanical probes)：通過機(jī)械探針和樣本的物理 接觸采集表面數(shù)據(jù)。要求樣本有一定硬度。體數(shù)據(jù)(Volumetric data)恢復(fù)：使用樣本的斷層圖 象恢復(fù)出其三維形狀。多用于醫(yī)藥部門，可使用的體數(shù)據(jù)包括X光圖片、CT圖片和MRT 圖片等。域掃描(Range scanning)：通

11、過估算從測(cè)量?jī)x器到樣本表面點(diǎn)的距離來確定點(diǎn)在空間 中的位置。包括光學(xué)三角測(cè)量，干涉測(cè)量等方法。在得到物體的三維數(shù)據(jù)后，建立三維模型 的方法也是多種多樣的。早期，三維模型大多是從三視圖和照片用手工建立起來的，這類建 模方法通常和某些軟件結(jié)合在一起，常用的如3D Studio、Auto CAD、3DS MAX等。 這樣的方法在概念上有嚴(yán)格的數(shù)學(xué)描述，對(duì)幾何形體有精確表達(dá)，可控制形狀的平滑并有很 多基于物理的高級(jí)建模工具。但這種方法需要物體的參數(shù)表達(dá)，模型不連續(xù)且在拓?fù)浣Y(jié)構(gòu)上 不靈活。目前最流行的方式是用多邊形網(wǎng)格來描述和繪制三維模型，它把三維模型表面的點(diǎn)連 接成以多邊形為單位的網(wǎng)格，是一種簡(jiǎn)單而高

12、效的表達(dá)方式。它可以表達(dá)復(fù)雜的表面，提供 很強(qiáng)的適應(yīng)性，其中尤以三角網(wǎng)格的使用最為廣泛。相對(duì)于早期的手工建模，多邊形網(wǎng)格的 方法采用了分段線性擬合的思想，可以在物體表面不規(guī)則地采集樣本點(diǎn)并完全不需要對(duì)物體 進(jìn)行參數(shù)化。因?yàn)樯鲜龅倪@些優(yōu)點(diǎn)，多邊形作為三維模型的基本要素已經(jīng)被廣泛地接受，多 邊形網(wǎng)格繪制的方法也獲得了大部分計(jì)算機(jī)硬件的支持，而且出現(xiàn)了很多基于多邊形網(wǎng)格的 高級(jí)使用方法。由于不同獲取方式得到的三維數(shù)據(jù)有不同的樣式和特點(diǎn)，作為目前主流的建模方式，多 邊形網(wǎng)格繪制對(duì)不同的原始點(diǎn)數(shù)據(jù)有不同的建網(wǎng)策略。下面先給出原始點(diǎn)數(shù)據(jù)的一些不同格 式。未組織數(shù)據(jù)(Unorganized data)：除了

13、采樣點(diǎn)外沒有其他附加信息。這是對(duì)物體最直接 但在建模過程中計(jì)算復(fù)雜度最高的表達(dá)方式。輪廓數(shù)據(jù)(Contour data)：在醫(yī)藥學(xué)應(yīng)用中模 型常被做成很薄的切片，并對(duì)每一個(gè)切片進(jìn)行數(shù)字化得到一條輪廓線。這些輪廓線可被近似 看做一組平行可交疊的閉合多邊形。體數(shù)據(jù)(Volumetric data):同樣在醫(yī)藥學(xué)應(yīng)用中， 用MRT或CT得到的數(shù)據(jù)稱為體數(shù)據(jù)。它們是一些三維柵格(3D-grid)，我們需要做的是 從中提取模型的表面，可以使用著名的Marching Cubes方法。但這個(gè)方法得不到最優(yōu)結(jié)果，如果體元柵格(Voxel grid)邊長(zhǎng)取得過大，會(huì)在模型表面發(fā)生混淆而得到繪制效果 不好的網(wǎng)格而

14、當(dāng)其邊長(zhǎng)減小時(shí)，計(jì)算復(fù)雜度隨其倒數(shù)做平方性增長(zhǎng)。域數(shù)據(jù)(Range data)： 通過域掃描得到的數(shù)據(jù)，并且已被規(guī)整化到同一坐標(biāo)系下。這類數(shù)據(jù)通常是包含深度信息或 三維點(diǎn)的矩形柵格，所以我們可以從中得到點(diǎn)的鄰接信息。其獲取難點(diǎn)是在不同掃描視點(diǎn)得 到的各幅域圖像上建立單一的網(wǎng)格。另一個(gè)問題是數(shù)據(jù)量的龐大，因?yàn)閽呙钑r(shí)的采樣是密集 且均勻的。面對(duì)以上不同結(jié)構(gòu)的數(shù)據(jù)，我們有不同的近似方式，所有這些方式可以分為兩類。 一類是插值(Interpolation)，這類方法中最后得到網(wǎng)格模型中的點(diǎn)就是初始的采樣點(diǎn)；另一 類是逼近(Approximation)，尤其對(duì)于采樣點(diǎn)極其密集的域數(shù)據(jù)，一般采用逼近的方法

15、而不 是插值。下面將介紹主要的近似方式?；谠煨?Sculpting based)的近似：屬于插值類 的方法，多用于未組織數(shù)據(jù)。這種近似方法一般先在點(diǎn)集合上建立四面體(通常使用 Delaunay三角剖分的方法)，得到物體的整體形狀，然后漸進(jìn)地進(jìn)行細(xì)化并取其合適的子集 作為最終的網(wǎng)格。該方法適合從采樣很稀疏的數(shù)據(jù)中重建表面，但計(jì)算復(fù)雜度和內(nèi)存消耗都 很大?；隗w(Volume based)的近似：屬于逼近類的方法，可用于未組織數(shù)據(jù)，也可用于 域數(shù)據(jù)等組織好的點(diǎn)云數(shù)據(jù)。對(duì)每個(gè)采樣點(diǎn)估算一個(gè)方法中自定義的距離并把它們記入一個(gè) 體元或八叉樹的結(jié)構(gòu)中，可以用 Marching Cubes方法在這樣的結(jié)構(gòu)

16、中建立網(wǎng)格。算法復(fù) 雜度由體元柵格的邊長(zhǎng)控制。增量法或區(qū)域增長(zhǎng)法(Incremental / Region-growing)：該方法 從一個(gè)選定的種子出發(fā)進(jìn)行增長(zhǎng)直到這個(gè)輸入數(shù)據(jù)被覆蓋。初始種子可以是一個(gè)三角面片、 一條邊、一幅域圖像或者一個(gè)線框逼近(Wireframe approximation)o不論在什么結(jié)構(gòu)的數(shù) 據(jù)上，全局建多邊形網(wǎng)格的方法計(jì)算都比較復(fù)雜，表達(dá)繁瑣，隨著數(shù)據(jù)量的增大，其開銷可 能呈指數(shù)增長(zhǎng)。這對(duì)于網(wǎng)絡(luò)傳輸和實(shí)時(shí)繪制來說是不可接受的缺點(diǎn)。2.2三維激光掃描儀和點(diǎn)繪制在上一節(jié)提到域掃描技術(shù)，現(xiàn)在隨著儀器技術(shù)的發(fā)展和軟件支持的完善已經(jīng)逐步普及，成為 一種很重要的三維數(shù)據(jù)獲取技

17、術(shù)，甚至引起了三維建模和繪制技術(shù)的革新。下面，先簡(jiǎn)略介 紹域掃描的過程。第一步，定標(biāo)。掃描過程中系統(tǒng)的坐標(biāo)是由儀器的硬件和周圍的環(huán)境共同決定的，所以事先 要確定一個(gè)統(tǒng)一的坐標(biāo)系。定標(biāo)的工作對(duì)得到精確的三維數(shù)據(jù)是至關(guān)重要的。第二步，掃描。物體表面在一個(gè)視點(diǎn)被采樣，得到一張密集的域圖像。要進(jìn)行多次的掃描才 可以得到覆蓋整個(gè)物體的采樣圖像。第三步，配準(zhǔn)。掃描所得的采樣圖像都處在各自的局部坐標(biāo)系中，它們必須被校準(zhǔn)到同一個(gè) 整體坐標(biāo)系中。在具體獲取數(shù)據(jù)的過程中，配準(zhǔn)是要借助定標(biāo)中確定的坐標(biāo)系信息實(shí)現(xiàn)的。掃描小物體 時(shí)可以固定掃描儀，記錄物體放置臺(tái)的轉(zhuǎn)動(dòng)角度，從而得到各個(gè)局部坐標(biāo)系間的關(guān)系。而在 掃描大場(chǎng)

18、景需要變換視點(diǎn)的時(shí)候，可以通過在場(chǎng)景中的固定位置擺放特殊標(biāo)識(shí)物來標(biāo)記各個(gè) 局部坐標(biāo)系，如Cyrax提供的有特殊反射率的靶標(biāo)。接著，我們介紹兩種常用的激光三維 掃描儀 FastScan和Cyrax。FastScan是被動(dòng)式的手持激光三維掃描儀，多用于采集小 型物體的三維數(shù)據(jù)。它由磁場(chǎng)定位系統(tǒng)和激光掃描系統(tǒng)組成。磁場(chǎng)定位系統(tǒng)包括磁場(chǎng)發(fā)射器 和磁場(chǎng)接收器，激光掃描系統(tǒng)包括激光發(fā)射器和激光接收器。在掃描過程中，要求磁場(chǎng)發(fā)射 器與被測(cè)物體盡量接近，最遠(yuǎn)不能超過75厘米。同時(shí)，激光掃描系統(tǒng)與被測(cè)物體距離應(yīng)保 持在15厘米到75厘米之間。當(dāng)激光掃過物體表面時(shí)，兩個(gè)CCD攝像頭和激光掃描 點(diǎn)之間構(gòu)成三角形，根

19、據(jù)三角測(cè)距原理，計(jì)算得到被掃描點(diǎn)與掃描儀的距離。同時(shí)，磁場(chǎng)接 收器收到磁場(chǎng)發(fā)射器的電磁信號(hào)，確定激光掃描儀在整個(gè)空間中的位置和姿態(tài)。這樣，就能 計(jì)算出被掃描點(diǎn)的空間幾何坐標(biāo)。因此，在掃描過程中只要保持物體和磁場(chǎng)發(fā)射器的相對(duì)位置不變，系統(tǒng)本身就可以對(duì)掃 描得到的幾何數(shù)據(jù)進(jìn)行自動(dòng)配準(zhǔn)。Cyrax是主動(dòng)式的激光三維掃描儀，需要支架和靶標(biāo)，用 于室外大型場(chǎng)景和建筑物三維數(shù)據(jù)的采集。它采用了雷達(dá)測(cè)距的原理：數(shù)字脈沖式激光器將 激光以其固有的發(fā)射速度發(fā)射到物體表面后接受其返回信號(hào)，這個(gè)過程的時(shí)間和激光的發(fā)射 速度相乘再除以二，就可以得到掃描儀到被測(cè)量點(diǎn)的距離。再利用精密的水平方向和垂直方 向的偏轉(zhuǎn)鏡就可以

20、得到激光在水平方向和垂直方向上的移動(dòng)距離，通過這個(gè)距離計(jì)算出被測(cè) 量點(diǎn)在水平和垂直方向上的坐標(biāo)。重復(fù)上述過程就可以得到物體表面全部點(diǎn)的三維坐標(biāo)。這 個(gè)掃描儀的測(cè)距精度在50米以內(nèi)可以達(dá)到26毫米而測(cè)量速度可以達(dá)到每秒一千點(diǎn)。 采用域掃描技術(shù)得到的點(diǎn)云數(shù)據(jù)是密集的、均勻的。在顯示的時(shí)候我們發(fā)現(xiàn)，把視點(diǎn)稍微拉 遠(yuǎn)，就可以使得屏幕顯示區(qū)域中每一個(gè)象素都至少有一個(gè)采樣點(diǎn)，這時(shí)不需要建網(wǎng)也可以 看到模型的三維效果。在如此密集的點(diǎn)云數(shù)據(jù)上直接建網(wǎng)會(huì)有很大的開銷，而最后得到的網(wǎng) 格對(duì)于顯示來說也過于密集了。所以一般要先經(jīng)過簡(jiǎn)化等步驟最后才能得到疏密合適的網(wǎng) 格。但這是一個(gè)很漫長(zhǎng)的計(jì)算過程，尤其是對(duì)表面幾何形

21、狀復(fù)雜的模型的建網(wǎng)過程，而且網(wǎng) 格表達(dá)仍然需要局部的參數(shù)化表達(dá)，在多分辨率顯示、壓縮和傳輸?shù)确矫嬉埠懿环奖?。于是?在三維數(shù)據(jù)獲取技術(shù)進(jìn)步、密集點(diǎn)云數(shù)據(jù)普及而網(wǎng)格繪制不能適應(yīng)其發(fā)展的情況下，點(diǎn)繪制 引起了人們的重視。點(diǎn)繪制的思想在1983年就已經(jīng)被提出，但直到2000年后才蓬勃發(fā)展 起來。最初，點(diǎn)繪制被使用在表達(dá)某些透明物體上，如煙霧、火焰和水等。但現(xiàn)在點(diǎn)繪制已 經(jīng)被用來繪制不透明的固體模型，其中面臨的主要難題就是如何表達(dá)出連續(xù)的表面。在網(wǎng)格 繪制中，面片與面片之間是沒有縫隙的，就不存在表面不連續(xù)的問題。但點(diǎn)繪制只顯示物體 表面的一些采樣點(diǎn)，雖然這些點(diǎn)是很密集的，但仍然會(huì)在點(diǎn)與點(diǎn)之間出現(xiàn)空洞。

22、所以必須要 有方法能填補(bǔ)模型表面的這些空洞，而這個(gè)方法又必須是快速的，否則就失去了點(diǎn)繪制的根 本優(yōu)勢(shì)。要解決這個(gè)問題，最直接的想法就是擴(kuò)大一個(gè)點(diǎn)的繪制區(qū)域。比如對(duì)于每一個(gè)點(diǎn)， 繪制一個(gè)以它為中心、和它同法向量的小平面，這個(gè)小平面要保證覆蓋住從這個(gè)點(diǎn)到周圍不 同方向上的幾個(gè)點(diǎn)的區(qū)域的一半以上，則從這個(gè)點(diǎn)的法向量附近方向上看，其周圍就不可能 出現(xiàn)空洞。但用平面取代點(diǎn)還是達(dá)不到很好的效果，因?yàn)楫?dāng)幾個(gè)相鄰點(diǎn)法向量一致而不處于 同一平面上時(shí)，用來代替點(diǎn)的小平面就會(huì)相互平行但不相交，從側(cè)面看仍然有漏洞。于是， 又有人用曲面取代點(diǎn)進(jìn)行繪制，只要保證每個(gè)點(diǎn)的曲面和其周圍曲面有相交，那從任何方向 上看都不會(huì)有漏

23、洞。此外，還有用球體或橢球體來取代點(diǎn)進(jìn)行繪制的方法，同樣可以消除 模型表面的空洞。在某些點(diǎn)繪制方法中，需要分析某個(gè)點(diǎn)的鄰域性狀，如該鄰域內(nèi)點(diǎn)分布密 度、曲率變化等，通過這些性狀來調(diào)整取代這個(gè)點(diǎn)的幾何體的形狀，得到更精確的模型表達(dá)和更好的繪制效果。從上面的描述中可以看到，點(diǎn)繪制是一種直接、簡(jiǎn)潔的繪制方式。由于它不需要對(duì)點(diǎn)云 數(shù)據(jù)在全局上做任何處理，最多就是考慮點(diǎn)鄰域內(nèi)的信息，因此在速度上有著網(wǎng)格繪制無法 比擬的優(yōu)勢(shì)，可以達(dá)到實(shí)時(shí)繪制的要求；而點(diǎn)繪制完全拋棄了連接信息，使得它的表達(dá)是精 練的，它的存儲(chǔ)量是極小的，給網(wǎng)絡(luò)傳輸提供了方便。但同時(shí)也要看到，點(diǎn)繪制得到的三維 模型只是在視覺效果上達(dá)到了表面

24、連續(xù)的要求，而無論從幾何關(guān)系還是從拓?fù)潢P(guān)系上講，它 都不像網(wǎng)格繪制那樣在模型的表面有連續(xù)性，這就造成了模型表達(dá)的不精確性。2.3基于局部分段線性擬合的繪制方法從前面的描述和分析中我們可以看到，全局建網(wǎng)的方法可以取得較好的視覺效果，但由于需 要考慮整個(gè)點(diǎn)云數(shù)據(jù)的結(jié)構(gòu)，算法的復(fù)雜度過高，不能適應(yīng)實(shí)時(shí)傳輸和繪制的需要；點(diǎn)繪制 是只考慮局部性狀的方法，雖然快速，但不能精確和真實(shí)地表達(dá)模型。兩種方法各有其優(yōu)劣， 且恰好補(bǔ)充了對(duì)方的不足。那么，是否存在一種折中的方法，使得其有網(wǎng)格的顯示效果，又 只需要考慮局部點(diǎn)云的信息呢？很自然的，我們想到了在局部建立網(wǎng)格的方法，就是下面要 介紹的基于局部分段線性擬合的繪

25、制方法。三角網(wǎng)格的繪制方法有很好的視覺效果，說明 以網(wǎng)格作為基本單位來近似地表達(dá)三維物體的表面是一個(gè)比較好的選擇。而點(diǎn)繪制中，以一 定大小的平面或某種曲面為基本單位就不能精確地表達(dá)三維物體的表面，但其基于局部信息 來重建平面的思想是可取的。于是，我們就考慮找到一種局部的三角網(wǎng)格，以其為基本單位 來表達(dá)三維物體的表面，但是這個(gè)局部三角網(wǎng)格應(yīng)該有怎樣的幾何性狀呢？考慮到要盡量達(dá) 到良好的視覺效果，這樣的網(wǎng)格應(yīng)該和全局建立的網(wǎng)格有幾何上的類似性。于是我們?nèi)ビ^察 已經(jīng)建立網(wǎng)格的一個(gè)三維模型中的某一個(gè)點(diǎn)，發(fā)現(xiàn)它和它的幾個(gè)近鄰點(diǎn)之間都有網(wǎng)格的連接 關(guān)系，以它自己為中心，形成了一個(gè)傘狀網(wǎng)格。我們受到啟發(fā)，就

26、使用這樣的傘狀網(wǎng)格作為 我們正在尋找的局部三角網(wǎng)格。一般情況下，對(duì)點(diǎn)云數(shù)據(jù)中的某一個(gè)點(diǎn)，尋找離它距離最近 的K個(gè)點(diǎn)，稱為它的K近鄰點(diǎn)，每?jī)蓚€(gè)相鄰的近鄰點(diǎn)和它本身連成一個(gè)三角面片，共K 個(gè)三角面片組成了一個(gè)連續(xù)的傘狀網(wǎng)格。于是，一個(gè)傘狀網(wǎng)格就表示出了這個(gè)點(diǎn)及其周圍一 個(gè)鄰域的幾何性狀。同樣的，對(duì)點(diǎn)云數(shù)據(jù)中的每一個(gè)點(diǎn)都繪制以它為中心的K近鄰傘狀網(wǎng) 格，可以肯定，在點(diǎn)云數(shù)據(jù)密度變化不大的情況下，這樣密集的傘狀網(wǎng)格能夠覆蓋整個(gè)三維 模型，其中會(huì)有很多的重復(fù)，但是其局部網(wǎng)格的性狀是規(guī)整和統(tǒng)一的。如此，三維模型就被 這樣的傘狀網(wǎng)格表達(dá)出來了。需要指出的是，此處的K不是一個(gè)固定值，它可以隨著點(diǎn)云 的密度和該

27、點(diǎn)所在的位置而變化。具體說來，點(diǎn)云密集時(shí)，可以取K=8或10，而點(diǎn)云稀 疏時(shí)，可以令K=6；當(dāng)中心點(diǎn)位于模型的邊緣時(shí)，只有一邊有近鄰點(diǎn)，就可以適當(dāng)?shù)販p小 K 的值，此時(shí)的網(wǎng)格也不是傘狀的?？傊?，要使最后得到的網(wǎng)格中面片盡量規(guī)整，比較接近全 局建網(wǎng)方法所得到的網(wǎng)格，才有好的視覺效果。方法的具體描述請(qǐng)看本文第三章。下面我們來初步分析本方法與全局網(wǎng)格繪制及局部點(diǎn)繪制的異同，具體量化的比較請(qǐng)看 本文的實(shí)驗(yàn)結(jié)果和分析部分。首先我們比較本方法和全局網(wǎng)格繪制的方法。從繪制效果上看，兩個(gè)方法最后都是用網(wǎng) 格來表達(dá)三維模型，所以應(yīng)該有著相似的效果。不同之處在于，全局建網(wǎng)的方法得到的三角 網(wǎng)格很規(guī)整、無重疊、無遺

28、漏，三角面片的數(shù)量少，模型表面更光滑。而本方法得到的網(wǎng)格 會(huì)有交叉和重疊的情況，面片數(shù)量多；在某些特定區(qū)域，如點(diǎn)云密度有變化的區(qū)域，還會(huì)有 空洞；模型表面也會(huì)出現(xiàn)一定數(shù)量的毛刺，尤其是在模型表面曲率發(fā)生不連續(xù)變化的邊界區(qū) 域，毛刺的情況比較明顯?？傮w來說，本方法在視覺效果上要略遜全局網(wǎng)格繪制一籌。從算 法復(fù)雜度來看，全局建網(wǎng)的方法需要考慮整個(gè)模型的拓?fù)浣Y(jié)構(gòu)，其計(jì)算過程是極其漫長(zhǎng)的， 而且一般需要人的手工干預(yù)，很難完全由電腦自動(dòng)完成。隨著數(shù)據(jù)量的增長(zhǎng)，其復(fù)雜度可能 出現(xiàn)指數(shù)級(jí)的增長(zhǎng)，在三維模型越來越復(fù)雜的今天，這是幾乎無法接受的缺點(diǎn)。本方法只考 慮局部信息，這就比全局建網(wǎng)的方法在效率上有了顯著的

29、提升。而且對(duì)于每一個(gè)點(diǎn)來說，計(jì) 算復(fù)雜度基本是固定的，因此，整個(gè)算法的復(fù)雜度隨著點(diǎn)的增加做線性增長(zhǎng)，使得本方法適 用于大數(shù)據(jù)量的場(chǎng)合。最后，在繪制的過程中，全局建網(wǎng)的方法需要記錄的信息繁多，除了 點(diǎn)坐標(biāo)外還要記錄面的組合方式，而且需要按照一定的順序和規(guī)則進(jìn)行存儲(chǔ)，這就給網(wǎng)絡(luò)傳 輸和快速繪制帶來了不便。而本方法只需要記錄點(diǎn)坐標(biāo)及其近鄰點(diǎn)編號(hào)，而且可以無序存儲(chǔ)， 保證了網(wǎng)絡(luò)傳輸?shù)目旖莶⒅С謱?shí)時(shí)繪制?？偠灾?，在時(shí)間和空間代價(jià)上，本方法相對(duì)于全 局網(wǎng)格繪制的方法擁有相當(dāng)明顯的優(yōu)勢(shì)。接著我們比較本方法和局部點(diǎn)繪制的方法。從繪制 效果上看，在每一個(gè)局部，我們用一個(gè)傘狀網(wǎng)格來表達(dá)點(diǎn)及其周圍一個(gè)鄰域的幾何性

30、狀，相 對(duì)于用一個(gè)平面或曲面來表達(dá)，這樣的表達(dá)更精確。而且由于中心點(diǎn)和周圍點(diǎn)有直接的連接 關(guān)系，當(dāng)以周圍點(diǎn)為中心繪制同樣的傘狀網(wǎng)格時(shí)，只會(huì)出現(xiàn)重復(fù)和交叉，不會(huì)出現(xiàn)由于層次 不同而產(chǎn)生的空洞。即是說，傘狀網(wǎng)格表達(dá)比平面或曲面表達(dá)有更小的誤差，而且傘狀網(wǎng)格 之間的拼接比之平面或曲面的拼接，更直接和容易，甚至只要判斷是否重復(fù)而不需要其他特 殊的考慮，省去了平面或曲面擬合的步驟，還能達(dá)到更好的拼接效果。因此，本方法得到的 模型會(huì)比點(diǎn)繪制更平滑、更精致，在視覺效果上有比較明顯的提升。從算法復(fù)雜度上看，兩 個(gè)方法都是基于局部點(diǎn)云數(shù)據(jù)的，在復(fù)雜度的變化趨勢(shì)上有相似的表現(xiàn)，區(qū)別只是在處理每 一個(gè)點(diǎn)的時(shí)候的計(jì)算

31、復(fù)雜度。收集鄰域信息是兩個(gè)方法都要做的，對(duì)收集到信息的計(jì)算是本 方法更復(fù)雜，而在后期對(duì)整個(gè)模型的整合方面點(diǎn)繪制的方法要復(fù)雜一些，但都沒有數(shù)量級(jí)上 的差異?？梢哉f，計(jì)算的快速和簡(jiǎn)單是兩個(gè)方法共同的優(yōu)點(diǎn)。同樣的，在繪制的過程中，兩 個(gè)方法需要存儲(chǔ)的信息量也沒有大的差別，都能適應(yīng)網(wǎng)絡(luò)傳輸和實(shí)時(shí)繪制。綜上所述，因?yàn)?算法思路的相似，在時(shí)間和空間代價(jià)上，本方法和局部點(diǎn)繪制的方法不相伯仲。3、基于局部分段線性擬合的點(diǎn)云數(shù)據(jù)繪制方法3.1總體描述和主要問題本方法的提出主要是為了通過網(wǎng)絡(luò)傳輸實(shí)現(xiàn)快速繪制，要求在保證繪制質(zhì)量的前提下數(shù) 據(jù)量小、計(jì)算簡(jiǎn)單快捷，方法的原始數(shù)據(jù)是點(diǎn)云數(shù)據(jù)，只包含了各個(gè)三維點(diǎn)在空間中的

32、坐標(biāo)。 基于以上條件，本方法分成兩個(gè)部分一一數(shù)據(jù)組織和繪制。數(shù)據(jù)組織就是對(duì)每一個(gè)需要計(jì) 算的點(diǎn)尋找其K近鄰，確定這些近鄰點(diǎn)的連接順序以便建立傘狀網(wǎng)格，并且要使得傘狀 網(wǎng)格本身以及其中的三角面片盡量規(guī)整。然后用一種標(biāo)準(zhǔn)的格式來記錄組織好的數(shù)據(jù)，為了 網(wǎng)絡(luò)傳輸?shù)姆奖?，要求這種標(biāo)準(zhǔn)格式的存儲(chǔ)量盡量小。面臨的主要問題如下：（1）需要計(jì)算的點(diǎn)的選擇。在動(dòng)手實(shí)驗(yàn)的過程中我發(fā)現(xiàn)由于傘狀網(wǎng)格有極其?高的重疊率， 點(diǎn)云數(shù)據(jù)中有相當(dāng)一部分的點(diǎn)，它們的傘狀網(wǎng)格和已有網(wǎng)格是完全重合的，因此這一部分點(diǎn) 可以不參與K近鄰的搜索，從而減少計(jì)算量和存儲(chǔ)量。通過分析，在本方法建立的模型中， 一個(gè)點(diǎn)一般有K條邊連接到它。當(dāng)一個(gè)點(diǎn)

33、被作為中心點(diǎn)使用過后，其邊數(shù)一般會(huì)達(dá)到或 接近K。當(dāng)一個(gè)沒有當(dāng)過中心點(diǎn)的點(diǎn)第一次被當(dāng)作近鄰點(diǎn)使用時(shí)，它的邊數(shù)由零增加到三 條（圖3.1中點(diǎn)O作為點(diǎn)A的近鄰點(diǎn)第一次被使用），此后每被當(dāng)作近鄰點(diǎn)使用一次，邊 數(shù)最少增加一條（圖3.2中點(diǎn)O作為點(diǎn)B的近鄰點(diǎn)被使用），最多增加三條（圖3.3中 點(diǎn)O作為點(diǎn)C的近鄰點(diǎn)被使用）。所以，在這里我們規(guī)定一個(gè)點(diǎn)作為中心點(diǎn)最多被使用一 次，而當(dāng)它被作為近鄰點(diǎn)使用（K-2）次后，就不再作為中心點(diǎn)使用了。（2）K近鄰點(diǎn)的搜索。要求盡量快速地找到K近鄰點(diǎn)，但并不需要近鄰點(diǎn)?是絕對(duì)精確 的。（3）近鄰點(diǎn)的組織。確定近鄰點(diǎn)的連接順序，使得它們最后連成的傘狀網(wǎng)格退是一個(gè)對(duì)角 線

34、和邊不相交的多邊形。在實(shí)現(xiàn)上，可以把近鄰點(diǎn)映射到同一個(gè)平面上然后按照夾角來排序。（4）網(wǎng)格規(guī)整化。首先，要保證三角面片盡量規(guī)整，即三角形中沒有過大梔也沒有過小的 角，如可以限定三角形的內(nèi)角在30度到135度之間。其次，要保證傘狀網(wǎng)格的規(guī)整性， 要求近鄰點(diǎn)比較均勻地分布在中心點(diǎn)周圍，最好能包圍住中心點(diǎn)。數(shù)據(jù)的記錄。數(shù)據(jù)組織的結(jié)果是得到一個(gè)標(biāo)準(zhǔn)格式的文件，文件第一部分是所有點(diǎn)的 三維坐標(biāo)列表，每個(gè)點(diǎn)用三個(gè)浮點(diǎn)數(shù)表示，點(diǎn)在列表中的位置對(duì)應(yīng)于該點(diǎn)的編號(hào)，第一行的 點(diǎn)為第0號(hào)點(diǎn)，以此類推。文件第二部分是經(jīng)過排序和規(guī)整化后的傘狀網(wǎng)格列表，記錄的 是按一定規(guī)則排列的近鄰點(diǎn)編號(hào)，其中第i行就代表以坐標(biāo)列表中編

35、號(hào)為(i-1)號(hào)的點(diǎn) 為中心點(diǎn)的近鄰點(diǎn)。如列表中第三行是如下一個(gè)整數(shù)序列：6, 15, 0，84，則表示了由四 個(gè)三角面片組成的一個(gè)傘狀網(wǎng)格，這四個(gè)三角面片分別由編號(hào)為2，6，15、2，15，0、 2, 0，84、2, 84, 6的點(diǎn)組成。注意，在這種記錄方式中，不會(huì)出現(xiàn)內(nèi)角過小的三角面 片，因?yàn)樵斐蛇@種情況的近鄰點(diǎn)可以從記錄序列中刪除而不會(huì)對(duì)其他面片造成影響。但這種 記錄方式無法消除內(nèi)角過大的面片，于是我們引入了一個(gè)特殊的標(biāo)識(shí)整數(shù)一2來阻止這種不 規(guī)則面片的繪制。比如，前面提到編號(hào)為2的點(diǎn)周圍有四個(gè)三角面片，但其中2, 0，84 這個(gè)面片內(nèi)角大于135度了，不需要繪制，則我們可以把第三行的整

36、數(shù)序列改寫為6, 15, 0，-2, 84，在繪制時(shí)見到一2,就不去繪制2, 0, 84這個(gè)不規(guī)整面片了。還有一種特殊 情況：點(diǎn)云數(shù)據(jù)中的有些點(diǎn)并1 )，如第96號(hào)點(diǎn)不需要繪制以它為中心的網(wǎng)號(hào)點(diǎn)不需要 繪制以它為中心的網(wǎng)格，則網(wǎng)格列表中的第97行用一個(gè)整數(shù)一1來標(biāo)識(shí)，繪制時(shí)可以直接 跳過。數(shù)據(jù)組織結(jié)束后，得到一個(gè)包含點(diǎn)坐標(biāo)列表和傘狀網(wǎng)格列表的文件，經(jīng)過網(wǎng)絡(luò)傳輸后 就可以進(jìn)入繪制的步驟。繪制就是根據(jù)既定的規(guī)則，把傘狀網(wǎng)格列表轉(zhuǎn)化成三角面片并將其 實(shí)際顯示5的描述。在這個(gè)過程中，要求快速并且達(dá)述。在這個(gè)過程中，要求快速并且達(dá) 耀到較好的顯示效果。重復(fù)面片的判斷。前面說過，本方法在繪制中會(huì)出現(xiàn)很多的

37、重復(fù)面片，一如果對(duì)每一 個(gè)面片都進(jìn)行繪制的話會(huì)浪費(fèi)大量的時(shí)間，甚至?xí)?duì)最后的繪制效果產(chǎn)生不良影響。因此， 我們必須定義一種結(jié)構(gòu)來記錄已經(jīng)繪制的面片，這種結(jié)構(gòu)首先要能夠?qū)崿F(xiàn)快速檢索，其次要 便于插入新的數(shù)據(jù)，還要盡量節(jié)省存儲(chǔ)空間。面片的拓?fù)溴e(cuò)誤。本方法繪制的網(wǎng)格中，面片除了重復(fù)之外，還會(huì)出現(xiàn)交叉，如圖3.4 中比較粗的線段所示，面片ABC與面片ABD就發(fā)生了交叉的拓?fù)溴e(cuò)誤。一般情況下， 這種錯(cuò)誤對(duì)視覺效果不會(huì)產(chǎn)生大的影響，但有時(shí)候，這種交叉現(xiàn)象會(huì)在模型表面造成小的空 洞，這種空洞只有在某個(gè)特定方向上可見。從算法上分析，這種拓?fù)溴e(cuò)誤在數(shù)據(jù)組織的過程 中是必然會(huì)出現(xiàn)的，在繪制的過程中也很難消除，只有

38、在記錄了所有需要繪制的面片后可以 通過一定算法消除，但解決起來很繁瑣。而這就違反了快速繪制的原則，因此，本文并沒有 解決這個(gè)問題，只是在3.3.2中提出了關(guān)于利用現(xiàn)有數(shù)據(jù)結(jié)構(gòu)消除拓?fù)溴e(cuò)誤的初步想法。所 謂模式識(shí)別，就是用計(jì)算機(jī)的方法來實(shí)現(xiàn)人對(duì)各種事物或現(xiàn)象的分析、描述、判斷和識(shí)別。 可以分為統(tǒng)計(jì)模式識(shí)別和結(jié)構(gòu)模式識(shí)別，統(tǒng)計(jì)模式識(shí)別系統(tǒng)大致由以下四個(gè)部分組成：數(shù)據(jù) 獲取、預(yù)處理、特征提取和選擇、分類決策。而 K 近鄰方法多用于統(tǒng)計(jì)模式識(shí)別的分 類決策中。所謂分類決策，就是把原始數(shù)據(jù)最能反映分類本質(zhì)的特征提取出來之后，在特征 空間中用統(tǒng)計(jì)方法把被識(shí)別對(duì)象歸為某一類別。基本做法是在樣本訓(xùn)練集基礎(chǔ)上確

39、定某個(gè)判 決規(guī)則，使按這種判決規(guī)則對(duì)被識(shí)別對(duì)象進(jìn)行分類所造成的錯(cuò)誤識(shí)別率最小或引起的損失最 小。有時(shí)候，一個(gè)數(shù)據(jù)的分類特征并不顯著，這時(shí)就可以找它在某一意義（比如歐氏距離） 上的近鄰數(shù)據(jù)，通過判斷其近鄰數(shù)據(jù)的分類特征，來決定該數(shù)據(jù)的分類。下面從模式識(shí)別的 角度簡(jiǎn)略介紹一下近鄰分類法中的K近鄰法。接下來，我們分析用來進(jìn)行網(wǎng)絡(luò)傳輸?shù)奈募笮。⒑徒ê镁W(wǎng)格的標(biāo)準(zhǔn)obj文件進(jìn)行 一個(gè)比較。注意，這里不考慮文件壓縮，而僅僅比較原始狀態(tài)下兩個(gè)文件的大小。一個(gè)標(biāo)準(zhǔn) 的obj文件分三個(gè)部分：第一部分是點(diǎn)的坐標(biāo)，有3n個(gè)浮點(diǎn)數(shù)；第二部分是點(diǎn)的法向量， 也有3n個(gè)浮點(diǎn)數(shù)；第三部分是三角網(wǎng)格，每一個(gè)網(wǎng)格用6個(gè)整數(shù)表

40、示，大約有2n個(gè)網(wǎng) 格，共12n個(gè)整數(shù)。所以，在obj文件中，每個(gè)點(diǎn)對(duì)應(yīng)12個(gè)整數(shù)和6個(gè)浮點(diǎn)數(shù)。由于 本方法不需要使用點(diǎn)的法向量，我們生成的文件只有兩部分：第一部分同樣是點(diǎn)坐標(biāo)，共3n 個(gè)浮點(diǎn)數(shù)；第二部分是點(diǎn)的近鄰點(diǎn)序列，這部分的大小隨著近鄰數(shù)K和搜索范圍M而變 化，同樣使用上一節(jié)的四個(gè)模型，實(shí)驗(yàn)中得到的數(shù)據(jù)如表4.2所示?？梢钥吹?，當(dāng)尋找6 近鄰時(shí)，近鄰點(diǎn)個(gè)數(shù)在5n左右；尋找8近鄰時(shí)，近鄰點(diǎn)個(gè)數(shù)在6n左右。而當(dāng)M變化 時(shí)，會(huì)影響近鄰搜索的精確性，從而對(duì)近鄰點(diǎn)個(gè)數(shù)產(chǎn)生不大的影響。于是本方法中，每個(gè)點(diǎn) 對(duì)應(yīng)56個(gè)整數(shù)和3個(gè)浮點(diǎn)數(shù)，在存儲(chǔ)空間上少于標(biāo)準(zhǔn)的obj文件。我們?cè)賮砜蠢L制部分的空間代價(jià)。一

41、個(gè)n?3維的double型矩陣來記錄點(diǎn)的坐標(biāo)。一個(gè)n 維數(shù)組，其中的元素是 k維型數(shù)組，用來記錄所有點(diǎn)的近鄰點(diǎn)數(shù)組，其總的存儲(chǔ)量是 5n6n個(gè)整數(shù)。接下來需要詳細(xì)分析的是我們自己定義的數(shù)據(jù)結(jié)構(gòu)RB樹。表4.3給出 了前面四個(gè)模型在尋找8近鄰的情況下RB樹的數(shù)目和所有樹的葉結(jié)點(diǎn)個(gè)數(shù)之和。在前面 介紹RB樹的結(jié)構(gòu)時(shí)已經(jīng)指出，模型中的一個(gè)三角網(wǎng)格對(duì)應(yīng)著一個(gè)葉結(jié)點(diǎn)，所以通過查看 模型的網(wǎng)格數(shù)就可以很方便地知道葉結(jié)點(diǎn)的總數(shù)了。分析實(shí)驗(yàn)數(shù)據(jù)我們發(fā)現(xiàn)，RB樹的數(shù)目 接近n，即是有n個(gè)根結(jié)點(diǎn)，而葉結(jié)點(diǎn)數(shù)目大約為4n。再觀察所有RB樹的結(jié)構(gòu)，發(fā)現(xiàn) 其樹干結(jié)點(diǎn)數(shù)大多為4,有一部分是3,其他情況較少，則大約有3n4

42、n個(gè)樹干結(jié)點(diǎn)。 每一個(gè)結(jié)點(diǎn)包含一個(gè)整數(shù)，根結(jié)點(diǎn)和葉結(jié)點(diǎn)各有一個(gè)指針，而樹干結(jié)點(diǎn)有兩個(gè)指針。所以， RB樹總的空間開銷是7n8n個(gè)整數(shù)和11n12n個(gè)指針。相對(duì)于標(biāo)準(zhǔn)obj文件用12n 個(gè)整數(shù)記錄連接關(guān)系，這個(gè)開銷要大一些，但可以實(shí)現(xiàn)快速檢索。3.2接著是其時(shí)間代價(jià)。此處為了集中精力在算法的討論上，我們忽略了實(shí)際繪制的時(shí)間，只計(jì)算輸入數(shù)據(jù)和判 斷三角面片是否要繪制的時(shí)間。輸入部分要讀入3n個(gè)浮點(diǎn)數(shù)和5n6n個(gè)整數(shù)，時(shí)間復(fù)雜 度是O(n)。而判斷的過程其實(shí)就是一個(gè)建立和搜索 RB樹的過程。按照前面的結(jié)論， 約有6n個(gè)面要參加判斷，但最后只繪制了 4n個(gè)。所以，共進(jìn)行了 4n次插入和6n次搜 索，平

43、均每次插入要進(jìn)行2次整數(shù)賦值和2次指針賦值，平均每次搜索要進(jìn)行4次取值 和比較。其時(shí)間復(fù)雜度也是O(n)。所以，整個(gè)過程應(yīng)該是隨著點(diǎn)數(shù)的增大做線性增長(zhǎng)的。 可以看見，礦石模型、馬的模型和人嘴模型的點(diǎn)數(shù)比大約是2.49： 2.05： 1，當(dāng)M=320時(shí)， 其輸入過程消耗時(shí)間比大約是2.21： 1.90： 1，計(jì)算過程消耗時(shí)間比大約是2.72： 2.12： 1； 當(dāng)M=640時(shí)，其輸入過程消耗時(shí)間比大約是2.14： 1.80： 1，計(jì)算過程消耗時(shí)間比大約是 2.60： 1.79： 1。輸入時(shí)間和計(jì)算時(shí)間隨著n的增大都呈現(xiàn)明顯的線性增長(zhǎng)趨勢(shì)，而當(dāng)M變 化時(shí)，對(duì)時(shí)間開銷沒有大的影響。從消耗時(shí)間的絕對(duì)量

44、上看，計(jì)算的過程最多是0.2秒， 完全滿足快速判斷的要求，說明我們的RB樹結(jié)構(gòu)設(shè)置是成功的。通過比較發(fā)現(xiàn)，我們的算法在時(shí)間代價(jià)上要大大優(yōu)于這些方法，這得益于我們基于局部 考慮問題的思路。當(dāng)然，我們?cè)诰W(wǎng)格的性狀和最后的視覺效果上也付出了一定的代價(jià)。這樣 的空洞就少了很多，底部也沒有了連接錯(cuò)誤。說明在點(diǎn)云稀疏且不均勻的時(shí)候，適當(dāng)增大M 同樣會(huì)改進(jìn)算法的效果。隨著 K的增大，在模型上已經(jīng)基本看不見空洞，只有少量毛刺， 這也是由邊緣點(diǎn)和突變邊界點(diǎn)判斷中取了過大的閾值引起的。說明適當(dāng)增大K同樣可以 改進(jìn)算法效果。但是，在這個(gè)實(shí)驗(yàn)中，總是出現(xiàn)判斷閾值過大的問題。分析其原因如下：當(dāng) 點(diǎn)分布不均勻的時(shí)候，如果

45、使用和點(diǎn)分布均勻時(shí)同樣的閾值，在點(diǎn)較稀疏的區(qū)域就會(huì)找不到 需要的點(diǎn)；但把閾值增大后，在點(diǎn)比較密集的區(qū)域就可能找到錯(cuò)誤的點(diǎn)而產(chǎn)生錯(cuò)誤的連接關(guān) 系或在模型表面出現(xiàn)毛刺。綜上所述，本方法對(duì)點(diǎn)云稀疏且分布不均勻的數(shù)據(jù)同樣適用，但最終得到的效果會(huì)差一 些。提高效果的關(guān)鍵在于邊緣點(diǎn)和突變邊界點(diǎn)判斷過程中閾值的適當(dāng)。從目前的分析來看， 使用一個(gè)固定的閾值似乎很難達(dá)到要求的效果，以后可以考慮根據(jù)數(shù)據(jù)各個(gè)局部的不同特 性，來取不同的閾值，應(yīng)該可以達(dá)到更好的效果。4、討論首先，本章將討論目前本方法中還存在的問題和初步的改進(jìn)方法。在前文中曾經(jīng)提到以下7個(gè)問題：（1）更快速、更精確地搜索K近鄰。如3.2.2中描述，現(xiàn)

46、有K近鄰算法的復(fù)雜度仍然 很高，而本方法中采用預(yù)先設(shè)定搜索范圍的方法又會(huì)對(duì)精確度造成影響。所以，如果能找到 一種更快速、更精確的K近鄰搜索方法，將會(huì)大幅度提升本方法的表現(xiàn)。（2）減少存儲(chǔ)量。在4.1中我們?cè)敿?xì)分析了本方法的空間開銷及記錄文件的昀存儲(chǔ)量。 發(fā)現(xiàn)其用來傳輸?shù)闹虚g文件其記錄方式略優(yōu)于標(biāo)準(zhǔn)obj文件，但繪制過程中要記錄的信息 量比較大。如何減少或壓縮這些信息是將來需要做的一個(gè)重要工作。（3）拓?fù)溴e(cuò)誤的消除。拓?fù)溴e(cuò)誤的定義參看3.1中的問題07從算法上分析，在本方法 中拓?fù)溴e(cuò)誤是無法避免的，但它對(duì)最后的視覺效果沒有大的影響。我們想到了一種消除拓?fù)?錯(cuò)誤的方法，但由于其空間時(shí)間代價(jià)過高的關(guān)

47、系沒有在本方法中被使用。實(shí)際上，這個(gè)想法 是有一定價(jià)值的。如果對(duì)我們得到的模型進(jìn)行消除拓?fù)溴e(cuò)誤并填補(bǔ)漏洞，最后得到的三角網(wǎng) 格效果會(huì)和全局建網(wǎng)得到的網(wǎng)格非常接近。而消除拓?fù)溴e(cuò)誤的方法相對(duì)于局部建網(wǎng)的方法來 說，其復(fù)雜度是很高的，但相對(duì)于全局建網(wǎng)的方法來說，它還是一個(gè)很快速、很簡(jiǎn)單的過程。 因此，如果我們的這個(gè)想法是切實(shí)有效的，那么就等于開創(chuàng)了一條從局部建立理想全局網(wǎng)格 的新道路，而且這個(gè)新方法在開銷上要遠(yuǎn)遠(yuǎn)低于現(xiàn)有的全局建網(wǎng)方法。（4）邊緣點(diǎn)和突變邊界點(diǎn)的判斷。這兩種點(diǎn)在模型中是很特殊的點(diǎn)，需要用攀特殊的策略 進(jìn)行處理和繪制，否則會(huì)對(duì)最后的視覺效果產(chǎn)生不良影響。本方法采用的判斷算法如3.2.4

48、 描述。但是在4.2的最后一個(gè)實(shí)驗(yàn)中我們發(fā)現(xiàn)，這個(gè)判斷算法在點(diǎn)云稀疏且分布不均勻的 時(shí)候沒有很好的效果，而且從其后的分析看來，這種不適應(yīng)性是由算法本身的局限造成的。 因此，這個(gè)算法有改進(jìn)的必要。目前的想法是，當(dāng)發(fā)現(xiàn)一個(gè)點(diǎn)的初試傘狀網(wǎng)格無法規(guī)整化而 需要進(jìn)行邊緣點(diǎn)和突變邊界點(diǎn)的判斷時(shí)，先求出該點(diǎn)所在局部點(diǎn)云密度大小及周圍密度變化 的情況，在密度大的區(qū)域或密度變大的方向上，把搜索判斷的閾值設(shè)得小一些，反之則增大 閾值?？傊?，使得判斷算法對(duì)點(diǎn)云的局部密度變化有自適應(yīng)性，而非通過單一閾值來控制。 中我們提出了一種分析點(diǎn)云局部信息并改動(dòng)算法使其與之相適應(yīng)相適應(yīng)的思路?？梢园堰@種 思路用在建立網(wǎng)格的過程中

49、，從而提升算法性能。（5）自適應(yīng)建網(wǎng)。在實(shí)驗(yàn)中我們發(fā)現(xiàn)，模型的某個(gè)區(qū)域是一個(gè)平面或者接近一個(gè)平面，而 對(duì)于密度大且分布均勻的點(diǎn)云數(shù)據(jù)來說，上面仍然有很密集的點(diǎn)。在全局建網(wǎng)中，可以先對(duì) 這些點(diǎn)進(jìn)行簡(jiǎn)化，只用幾個(gè)大的三角網(wǎng)格來表示這個(gè)區(qū)域；而在本方法中，對(duì)于這樣的點(diǎn)我 們同樣尋找其K近鄰并繪制傘狀網(wǎng)格。這是完全是沒有必要的，甚至?xí)a(chǎn)生毛刺對(duì)繪制 結(jié)果有不良影響。因此，我們可以判斷模型各區(qū)域的曲率變化情況，對(duì)于曲率變化大的區(qū)域， 采用直接找K近鄰的算法。對(duì)于曲率變化比較小的區(qū)域，則可以找中心點(diǎn)的t (t 1)階 近鄰，如t = 2時(shí)，就找中心點(diǎn)的第K+1個(gè)到第2K個(gè)近鄰，實(shí)行上述算法，再把其 前K個(gè)近鄰在點(diǎn)列表中標(biāo)識(shí)為不可用。模型表面該區(qū)域曲率變化越