Delaunay方法三維建模

1、Delaunay方法三維建模    摘要3維建模技術(shù)在建筑，論文代寫地質(zhì)地形勘測，醫(yī)學圖像建模，動畫設計等各方面都有廣泛的應用. 1個3維模型的建立過程包括3維原始數(shù)據(jù)的獲取、去除噪聲、曲面拼接、修補“洞”，最終得到1個可以在計算機上顯示的具有3維特征的網(wǎng)格. 3維可視化技術(shù)包括表面繪制技術(shù)和體繪制技術(shù)。由于將已有的3維模型顯示在計算機上的技術(shù)已經(jīng)很成熟，所以可視化技術(shù)的主要問題在于3維建模.使用Delaunay方法來建模，由于Delaunay3角是盡量接近于等邊3角形的，所以用這種方法建的網(wǎng)格會比較均勻，顯示圖像的時候視覺效果就是整個圖像很勻稱，不會出

2、現(xiàn)粗細不均或者漏洞百出的情況。本文的內(nèi)容分5章。第1章引言，主要介紹研究背景和目前的發(fā)展狀況以及可能的應用。第2章的第2部分就大概介紹了在2維空間建3角網(wǎng)的思路。在第3章里面，詳細的說明了建立4面體網(wǎng)格的每1個步驟，其中附有說明圖和流程圖。第4章列出了實驗結(jié)果（1系列圖），驗證算法的正確性。這里要說明的是，在實驗中只選了9個點，但這9個點建網(wǎng)的過程中出現(xiàn)了Tsung-Pao Fang所列出的所有需要特殊處理的情況，也就是說，如果用再多的點來做這個實驗，也不過就是這幾種情況的重復。后面的4幅圖是后來所作的工作，得到了1個正方體4頂點以及其中心點的建網(wǎng)結(jié)果，從這里能清楚地看到4面體網(wǎng)格的結(jié)構(gòu)，還有

3、對貝殼數(shù)據(jù)點云的部分建網(wǎng)結(jié)果，之所以沒有完成整個貝殼數(shù)據(jù)的建網(wǎng)是因為數(shù)據(jù)中存在較多的5點或5點以上共球的情況，這種情況下Delaunay準則不再適用，建網(wǎng)會中斷，所以只完成了1個部分。第5章針對程序中存在的問題和我在畢業(yè)設計過程中遇到的困難進行了討論. 關(guān)鍵詞：Delaunay ；3維建模；4面體網(wǎng)格；局部搜索。 AbstractThree-dimension modeling technology is widely applied in the fields of architecture, geology and topography survey, medicine picture m

4、odeling, 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

5、 PC. Three-dimension videotechnology consists of surface protracting technology and body protracting technology.Since the technology that making three-dimension model show in PC is proficient, the main problem of videotechnology lies in three-dimension modelingBecause Delaunay triangle is nearly equ

6、ilateral 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

7、development.Chapter 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 met

8、hod. 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

9、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 a

10、ny 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 前言. 12 Delaunay 3角剖分的

11、基本原理. 22.1 相關(guān)知識. 22.1.1 Voronoi 圖. 22.1.2 Delaunay 3角剖分. 32.2 2維空間建Delaunay 3角網(wǎng)的基本思想. 42.2.1 數(shù)據(jù)點的預處理. 42.2.2 建立起始的3角形. 62.2.3 建立3角網(wǎng). 73 Delaunay 4面體網(wǎng)格的構(gòu)建. 83.1 與算法相適應的數(shù)據(jù)結(jié)構(gòu). 83.2 3維平面構(gòu)建Delaunay 4面體網(wǎng)格的算法. 133.2.1 數(shù)據(jù)的輸入和預處理. 133.2.2 整個算法的起始點 . 143.2.3 搜索與 距離最近的點 . . 143.2.4 尋找滿足Delaynay法則的第3個點 . . 153.

12、2.5 已知1個3角面片，搜索第4個點. 163.2.6 構(gòu)建Delaunay4面體網(wǎng)格. 174 實驗結(jié)論.205 討論. 226 參考文獻.247 致謝.24    附錄.25 1 前 言 3維建模技術(shù)在建筑，地質(zhì)地形勘測，醫(yī)學圖像建模，動畫設計等各方面都有廣泛的應用。在進行某項工程設計，或者醫(yī)療操作時，如果能建立計算機仿真平臺，通過這個平臺的仿真實驗來驗證設計方案的可行性及對此操作的成功率指標進行評估的話，不僅可以提高設計計劃的成功率，而且可以節(jié)省設計的時間和資金。通過仿真還可以對設計方案和有關(guān)參數(shù)進行驗證和修正，對于醫(yī)療方案的仿真，更是提高了手術(shù)

13、治療的成功率，維護了病人的生命財產(chǎn)。1個3維模型的建立過程包括：3維原始數(shù)據(jù)的獲取、去除噪聲、曲面拼接、修補“洞”，最終得到1個可以在計算機上顯示的具有3維特征的網(wǎng)格。3維可視化技術(shù)包括表面繪制技術(shù)和體繪制技術(shù)。由于將已建好的3維模型顯示在計算機上的技術(shù)已經(jīng)很成熟，所以可視化技術(shù)的主要問題在于3維建模。表面繪制是抽取出3維原始數(shù)據(jù)中的表面數(shù)據(jù)，然后將模型的表面信息顯示在計算機上；體繪制不需要對3維原始數(shù)據(jù)作太多處理，由于這種方法建立的模型不僅有物體表面的信息，還包含圖形內(nèi)部點的信息，甚至各點之間的相互作用或者連接關(guān)系，所以用體繪制方法得到的模型可以用來模擬物體的受力形變過程。目前國際上表面繪制

14、技術(shù)已經(jīng)很成熟了，隨之出現(xiàn)的各種軟件，如3d studio max等，都可以作圖像的表面建模，既方便快捷，效果也不錯。但是，在許多作仿真用途的模型中，特別是醫(yī)用模型，往往需要模型能夠真實地模仿實際物體受到外界干擾時會如何發(fā)生形變，這就需要把掃描對象物體得到的3維數(shù)據(jù)點云用立體網(wǎng)格（區(qū)別于3角網(wǎng)或者多邊形網(wǎng)格這種表面建網(wǎng)得到的網(wǎng)格）來連接建網(wǎng)。建網(wǎng)的目的是要把3維圖形無論表面還是內(nèi)部的點連接起來，用有限的連接關(guān)系建立起包括所有點的網(wǎng)絡，沒有任何點被遺漏也盡量沒有冗余。當物體受外界作用發(fā)生形變的時候，因為數(shù)據(jù)點之間的聯(lián)系是確定的，所以作用范圍內(nèi)的點及其相鄰點的受力情況和運動過程是可以通過簡單的力學

15、計算得到的，因此我們可以應用這樣的模型來做各種力學和醫(yī)學等仿真。截止到目前為止，還沒有現(xiàn)成的軟件能夠做這件事情。國際上也還沒有成熟的算法。我在畢業(yè)設計中所做的事情屬于體繪制的1部分，即基于3維數(shù)據(jù)點云建立立體網(wǎng)格，所用的方法是基于Delaunay3角剖分原理建立Delaunay4面體網(wǎng)格。這種方法的優(yōu)點是所建立的4面體與其他方法相比最接近正4面體，形狀最規(guī)則，且剖分的結(jié)果是唯1的。目前國際上對立體仿真建模的研究最為關(guān)注的是醫(yī)學方面的應用。但是用于醫(yī)學仿真操作的模型，必須具有和人體組織完全相同的形狀和結(jié)構(gòu)，在手術(shù)刀切割等外界條件下，才能夠做出完全類似于真實人體的反應和形變，因為其模擬的結(jié)果可以說是性命攸關(guān)的大事，所以要求有相當高的精度。這項工作有著良好的發(fā)展和應用的前景。如果立體建網(wǎng)的技術(shù)成熟起來，基于真實物體的仿真模型將會被應用到生活的各個方面。不僅可以做工程和醫(yī)學仿真，隨著網(wǎng)上購物越來越走入人們的生活，我們可以某些商品建成可視又可“觸”的模型，人們在選購的時候不僅可以看到商品的樣子，還可以用鼠標和鍵盤對商品模型進行各種操作，看它的彈性、柔軟度等性質(zhì)，從而用更直觀，更便捷的方法來了解商品的性能，而不是對著大篇幅的數(shù)字指標發(fā)呆。這種技術(shù)還可以同大型場景相結(jié)合，讓人們能夠在風景勝地