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

2、其它 的可以包括物體表面的顏色、透明度、紋理特征等等。三維建模正在廣泛地應用于越來越多 的領域，并且以其提供直觀、方便的三維圖像等特點在各領域中發揮越來越重要的作用。關鍵字：三維建模、三維模型繪制、傘狀網絡1、三維數據的應用我們身在一個三維的世界中，三維的世界是立體的、真實的。同時，我們處于一個信息 化的時代里，信息化的時代是以計算機和數字化為表征的。隨著計算機在各行各業的廣泛應 用，人們開始不滿足于計算機僅能顯示二維的圖像，更希望計算機能表達出具有強烈真實感 的現實三維世界。三維建模可以使計算機作到這一點。所謂三維建模，就是利用三維數據將 現實中的三維物體或場景在計算機中進行重建，最終實現在

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、所以必須要 有方法能填補模型表面的這些空洞，而這個方法又必須是快速的，否則就失去了點繪制的根 本優勢。要解決這個問題，最直接的想法就是擴大一個點的繪制區域。比如對于每一個點， 繪制一個以它為中心、和它同法向量的小平面，這個小平面要保證覆蓋住從這個點到周圍不 同方向上的幾個點的區域的一半以上，則從這個點的法向量附近方向上看，其周圍就不可能 出現空洞。但用平面取代點還是達不到很好的效果，因為當幾個相鄰點法向量一致而不處于 同一平面上時，用來代替點的小平面就會相互平行但不相交，從側面看仍然有漏洞。于是， 又有人用曲面取代點進行繪制，只要保證每個點的曲面和其周圍曲面有相交，那從任何方向 上看都不會有漏

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

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

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

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

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

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

29、提升。而且對于每一個點來說，計 算復雜度基本是固定的，因此，整個算法的復雜度隨著點的增加做線性增長，使得本方法適 用于大數據量的場合。最后，在繪制的過程中，全局建網的方法需要記錄的信息繁多，除了 點坐標外還要記錄面的組合方式，而且需要按照一定的順序和規則進行存儲，這就給網絡傳 輸和快速繪制帶來了不便。而本方法只需要記錄點坐標及其近鄰點編號，而且可以無序存儲， 保證了網絡傳輸的快捷并支持實時繪制。總而言之，在時間和空間代價上，本方法相對于全 局網格繪制的方法擁有相當明顯的優勢。接著我們比較本方法和局部點繪制的方法。從繪制 效果上看，在每一個局部，我們用一個傘狀網格來表達點及其周圍一個鄰域的幾何性

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

31、復雜度。收集鄰域信息是兩個方法都要做的，對收集到信息的計算是本 方法更復雜，而在后期對整個模型的整合方面點繪制的方法要復雜一些，但都沒有數量級上 的差異。可以說，計算的快速和簡單是兩個方法共同的優點。同樣的，在繪制的過程中，兩 個方法需要存儲的信息量也沒有大的差別，都能適應網絡傳輸和實時繪制。綜上所述，因為 算法思路的相似，在時間和空間代價上，本方法和局部點繪制的方法不相伯仲。3、基于局部分段線性擬合的點云數據繪制方法3.1總體描述和主要問題本方法的提出主要是為了通過網絡傳輸實現快速繪制，要求在保證繪制質量的前提下數 據量小、計算簡單快捷，方法的原始數據是點云數據，只包含了各個三維點在空間中的

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

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

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

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

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

37、重復面片，一如果對每一 個面片都進行繪制的話會浪費大量的時間，甚至會對最后的繪制效果產生不良影響。因此， 我們必須定義一種結構來記錄已經繪制的面片，這種結構首先要能夠實現快速檢索，其次要 便于插入新的數據，還要盡量節省存儲空間。面片的拓撲錯誤。本方法繪制的網格中，面片除了重復之外，還會出現交叉，如圖3.4 中比較粗的線段所示，面片ABC與面片ABD就發生了交叉的拓撲錯誤。一般情況下， 這種錯誤對視覺效果不會產生大的影響，但有時候，這種交叉現象會在模型表面造成小的空 洞，這種空洞只有在某個特定方向上可見。從算法上分析，這種拓撲錯誤在數據組織的過程 中是必然會出現的，在繪制的過程中也很難消除，只有

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

39、定某個判 決規則，使按這種判決規則對被識別對象進行分類所造成的錯誤識別率最小或引起的損失最 小。有時候，一個數據的分類特征并不顯著，這時就可以找它在某一意義（比如歐氏距離） 上的近鄰數據，通過判斷其近鄰數據的分類特征，來決定該數據的分類。下面從模式識別的 角度簡略介紹一下近鄰分類法中的K近鄰法。接下來，我們分析用來進行網絡傳輸的文件大小，并和建好網格的標準obj文件進行 一個比較。注意，這里不考慮文件壓縮，而僅僅比較原始狀態下兩個文件的大小。一個標準 的obj文件分三個部分：第一部分是點的坐標，有3n個浮點數；第二部分是點的法向量， 也有3n個浮點數；第三部分是三角網格，每一個網格用6個整數表

40、示，大約有2n個網 格，共12n個整數。所以，在obj文件中，每個點對應12個整數和6個浮點數。由于 本方法不需要使用點的法向量，我們生成的文件只有兩部分：第一部分同樣是點坐標，共3n 個浮點數；第二部分是點的近鄰點序列，這部分的大小隨著近鄰數K和搜索范圍M而變 化，同樣使用上一節的四個模型，實驗中得到的數據如表4.2所示。可以看到，當尋找6 近鄰時，近鄰點個數在5n左右；尋找8近鄰時，近鄰點個數在6n左右。而當M變化 時，會影響近鄰搜索的精確性，從而對近鄰點個數產生不大的影響。于是本方法中，每個點 對應56個整數和3個浮點數，在存儲空間上少于標準的obj文件。我們再來看繪制部分的空間代價。一

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

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

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

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

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

46、有K近鄰算法的復雜度仍然 很高，而本方法中采用預先設定搜索范圍的方法又會對精確度造成影響。所以，如果能找到 一種更快速、更精確的K近鄰搜索方法，將會大幅度提升本方法的表現。（2）減少存儲量。在4.1中我們詳細分析了本方法的空間開銷及記錄文件的昀存儲量。 發現其用來傳輸的中間文件其記錄方式略優于標準obj文件，但繪制過程中要記錄的信息 量比較大。如何減少或壓縮這些信息是將來需要做的一個重要工作。（3）拓撲錯誤的消除。拓撲錯誤的定義參看3.1中的問題07從算法上分析，在本方法 中拓撲錯誤是無法避免的，但它對最后的視覺效果沒有大的影響。我們想到了一種消除拓撲 錯誤的方法，但由于其空間時間代價過高的關

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

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

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