摘要
3維建模技術在建築，地質地形勘測，醫學圖像建模，動畫設計等各方面都有廣泛的應用. 1個3維模型的建立過程包括3維原始數據的獲取、去除噪聲、曲面拼接、修補“洞”，最終得到1個可以在計算機上顯示的具有3維特徵的網格. 3維可視化技術包括表面繪製技術和體繪製技術。由於將已有的3維模型顯示在計算機上的技術已經很成熟，所以可視化技術的主要問題在於3維建模.
使用Delaunay方法來建模，由於Delaunay3角是儘量接近於等邊3角形的，所以用這種方法建的網格會比較均勻，顯示圖像的時候視覺效果就是整個圖像很勻稱，不會出現粗細不均或者漏洞百出的情況。
本文的內容分5章。第1章引言，主要介紹研究背景和目前的發展狀況以及可能的應用。第2章的第2部分就大概介紹了在2維空間建3角網的思路。在第3章裏面，詳細的說明了建立4面體網格的每1個步驟，其中附有說明圖和流程圖。第4章列出了實驗結果（1系列圖），驗證算法的正確性。這裏要說明的是，在實驗中只選了9個點，但這9個點建網的過程中出現了Tsung-Pao Fang所列出的所有需要特殊處理的情況，也就是說，如果用再多的點來做這個實驗，也不過就是這幾種情況的重複。後面的4幅圖是後來所作的工作，得到了1個正方體4頂點以及其中心點的建網結果，從這裏能清楚地看到4面體網格的結構，還有對貝殼數據點雲的部分建網結果，之所以沒有完成整個貝殼數據的建網是因爲數據中存在較多的5點或5點以上共球的情況，這種情況下Delaunay準則不再適用，建網會中斷，所以只完成了1個部分。第5章針對程序中存在的問題和我在畢業設計過程中遇到的困難進行了討論.
關鍵詞：Delaunay ；3維建模；4面體網格；局部搜尋。
Abstract
Three-dimension modeling technology is widely applied in the fields of architecture, geology and topography survey, medicine picture modeling, and cartoon design etc. The process of three-dimension modeling includes the following steps: first, obtaining three-dimension original data; second, removing yawp; third, putting curve surface together; fourth, mending “hole”; at last, reseau characterized by three-dimension will appear in PC. Three-dimension videotechnology consists of surface protracting technology and body protracting e the technology that making three-dimension model show in PC is proficient, the main problem of videotechnology lies in three-dimension modeling
Because Delaunay triangle is nearly equilateral triangle, modeling reseau with the method of Delaunay will be relatively well-proportioned. The whole image will looks shapely, not snatchy and inaccurate.
This paper includes five chapters. First chapter is Introduction, which introduce the background , recent development and the potential ter two gives a brief introduction of establishing triangle meshwork in two-dimension space. Chapter three explains every step to establish four-dimension reseau specifically, including demonstration and flow chart. Chapter Four lists the results with series of charts to test the method. Furthermore, nine dots are chosen. In the process of establishing meshwork with those nine dots, some special problems arise from Tsung-Pao Fang. That is to say , even if more dots are chosen, there are only the repetition of the above problems. The meshwork results are obtained from the later pictures. They clearly show the structure of four-dimension reseau and some meshwork results of shell data. The reason why the whole results are not achieved is that there are too many circumstances in which five or more dots share the same orb. In this case, the principle Delaunay is not in point any more, then the process of establishing meshwork will be intermitted. Chapter Five discusses some problems arising from the program and some difficulties in my thesis.
Keywords: Delaunay;three-dimension modeling; four-dimension reseau;partly search;
目錄
1 前言................................................................................................................................................... 1
2 Delaunay 3角剖分的基本原理...................................................................................................... 2
2.1 相關知識…….......................................................................…………….……………………….... 2
2.1.1 Voronoi 圖............................................................................................................................... 2
2.1.2 Delaunay 3角剖分................................................................................................................. 3
2.2 2維空間建Delaunay 3角網的基本思想....................................................................................... 4
2.2.1 數據點的預處理..................................................................................................................... 4
2.2.2 建立起始的3角形................................................................................................................. 6
2.2.3 建立3角網........................................................................................................................... 7
3 Delaunay 4面體網格的構建.......................................................................................................... 8
3.1 與算法相適應的數據結構.............................................................................................................. 8
3.2 3維平面構建Delaunay 4面體網格的算法................................................................................. 13
3.2.1 數據的輸入和預處理........................................................................................................... 13
3.2.2 整個算法的'起始點 .......................................................................................................... 14
3.2.3 搜尋與 距離最近的點 .................................. ............................................................. 14
3.2.4 尋找滿足Delaynay法則的第3個點 ............................... .............................................. 15
3.2.5 已知1個3角面片，搜尋第4個點..................................................................................... 16
3.2.6 構建Delaunay4面體網格.................................................................................................... 17
4 實驗結論.....................................................................................................................20
5 討論........................................................................................................................................................ 22
6 參考文獻..........................................................................................................................................24
7 致謝..................................................................................................................................................24
附錄............................................................................................................................................................25
1 前 言
3維建模技術在建築，地質地形勘測，醫學圖像建模，動畫設計等各方面都有廣泛的應用。在進行某項工程設計，或者醫療操作時，如果能建立計算機仿真平臺，透過這個平臺的仿真實驗來驗證設計方案的可行性及對此操作的成功率指標進行評估的話，不僅可以提高設計計劃的成功率，而且可以節省設計的時間和資金。透過仿真還可以對設計方案和有關參數進行驗證和修正，對於醫療方案的仿真，更是提高了手術治療的成功率，維護了病人的生命財產。
1個3維模型的建立過程包括：3維原始數據的獲取、去除噪聲、曲面拼接、修補“洞”，最終得到1個可以在計算機上顯示的具有3維特徵的網格。3維可視化技術包括表面繪製技術和體繪製技術。由於將已建好的3維模型顯示在計算機上的技術已經很成熟，所以可視化技術的主要問題在於3維建模。表面繪製是抽取出3維原始數據中的表面數據，然後將模型的表面資訊顯示在計算機上；體繪製不需要對3維原始數據作太多處理，由於這種方法建立的模型不僅有物體表面的資訊，還包含圖形內部點的資訊，甚至各點之間的相互作用或者連接關係，所以用體繪製方法得到的模型可以用來模擬物體的受力形變過程。目前國際上表面繪製技術已經很成熟了，隨之出現的各種軟件，如3d studio max等，都可以作圖像的表面建模，既方便快捷，效果也不錯。但是，在許多作仿真用途的模型中，特別是醫用模型，往往需要模型能夠真實地模仿實際物體受到外界干擾時會如何發生形變，這就需要把掃描對象物體得到的3維數據點雲用立體網格（區別於3角網或者多邊形網格這種表面建網得到的網格）來連接建網。建網的目的是要把3維圖形無論表面還是內部的點連接起來，用有限的連接關係建立起包括所有點的網絡，沒有任何點被遺漏也儘量沒有冗餘。當物體受外界作用發生形變的時候，因爲數據點之間的聯繫是確定的，所以作用範圍內的點及其相鄰點的受力情況和運動過程是可以透過簡單的力學計算得到的，因此我們可以應用這樣的模型來做各種力學和醫學等仿真。截止到目前爲止，還沒有現成的軟件能夠做這件事情。國際上也還沒有成熟的算法。我在畢業設計中所做的事情屬於體繪製的1部分，即基於3維數據點雲建立立體網格，所用的方法是基於Delaunay3角剖分原理建立Delaunay4面體網格。這種方法的優點是所建立的4面體與其他方法相比最接近正4面體，形狀最規則，且剖分的結果是唯1的。
目前國際上對立體仿真建模的研究最爲關注的是醫學方面的應用。但是用於醫學仿真操作的模型，必須具有和人體組織完全相同的形狀和結構，在手術刀切割等外界條件下，才能夠做出完全類似於真實人體的反應和形變，因爲其模擬的結果可以說是性命攸關的大事，所以要求有相當高的精度。
這項工作有着良好的發展和應用的前景。如果立體建網的技術成熟起來，基於真實物體的仿真模型將會被應用到生活的各個方面。不僅可以做工程和醫學仿真，隨着網上購物越來越走入人們的生活，我們可以某些商品建成可視又可“觸”的模型，人們在選購的時候不僅可以看到商品的樣子，還可以用鼠標和鍵盤對商品模型進行各種操作，看它的彈性、柔軟度等性質，從而用更直觀，更便捷的方法來了解商品的性能，而不是對着大篇幅的數字指標發呆。這種技術還可以同大型場景相結合，讓人們能夠在風景勝地、災難現場、文物古蹟等的虛擬現實世界漫遊，足不出戶就可以有身臨其境的感受，甚至去“接觸”物體。如果我們能夠建立仿真的地理模型，就可以做地震、暴雨等的災難模擬實驗，用來做災難預測和爲維修提供理論依據，從而節省大量不必要的開支。3維仿真模型的應用領域10分廣闊，伴隨着計算機走進千家萬戶的腳步，網絡將在我們的生活扮演越來越重要的角色，也許有1天，你會說：斷網了可讓我怎麼活，電腦和網絡就像今天的“電”1樣重要，到那個時候網絡上的模型都能很好的模擬真實世界的物體，3維仿真建模的技術才真正有了用武之地。
2 Delaunay3角剖分的基本原理
3角剖分的定義：若對平面剖分的所有邊界區域都是3角形，則這種平面剖分稱爲3角剖分。3角剖分是計算
[1]