- 相關(guān)推薦
Delaunay方法三維建模
摘要
3維建模技術(shù)在建筑，地質(zhì)地形勘測，醫(yī)學(xué)圖像建模，動畫設(shè)計等各方面都有廣泛的應(yīng)用. 1個3維模型的建立過程包括3維原始數(shù)據(jù)的獲取、去除噪聲、曲面拼接、修補(bǔ)“洞”，最終得到1個可以在計算機(jī)上顯示的具有3維特征的網(wǎng)格. 3維可視化技術(shù)包括表面繪制技術(shù)和體繪制技術(shù)。由于將已有的3維模型顯示在計算機(jī)上的技術(shù)已經(jīng)很成熟，所以可視化技術(shù)的主要問題在于3維建模.
使用Delaunay方法來建模，由于Delaunay3角是盡量接近于等邊3角形的，所以用這種方法建的網(wǎng)格會比較均勻，顯示圖像的時候視覺效果就是整個圖像很勻稱，不會出現(xiàn)粗細(xì)不均或者漏洞百出的情況。
本文的內(nèi)容分5章。第1章引言，主要介紹研究背景和目前的發(fā)展?fàn)顩r以及可能的應(yīng)用。第2章的第2部分就大概介紹了在2維空間建3角網(wǎng)的思路。在第3章里面，詳細(xì)的說明了建立4面體網(wǎng)格的每1個步驟，其中附有說明圖和流程圖。第4章列出了實驗結(jié)果（1系列圖），驗證算法的正確性。這里要說明的是，在實驗中只選了9個點，但這9個點建網(wǎng)的過程中出現(xiàn)了Tsung-Pao Fang所列出的所有需要特殊處理的情況，也就是說，如果用再多的點來做這個實驗，也不過就是這幾種情況的重復(fù)。后面的4幅圖是后來所作的工作，得到了1個正方體4頂點以及其中心點的建網(wǎng)結(jié)果，從這里能清楚地看到4面體網(wǎng)格的結(jié)構(gòu)，還有對貝殼數(shù)據(jù)點云的部分建網(wǎng)結(jié)果，之所以沒有完成整個貝殼數(shù)據(jù)的建網(wǎng)是因為數(shù)據(jù)中存在較多的5點或5點以上共球的情況，這種情況下Delaunay準(zhǔn)則不再適用，建網(wǎng)會中斷，所以只完成了1個部分。第5章針對程序中存在的問題和我在畢業(yè)設(shè)計過程中遇到的困難進(jìn)行了討論.
關(guān)鍵詞：Delaunay ；3維建模；4面體網(wǎng)格；局部搜索。
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 technology.Since 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 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 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 相關(guān)知識…….......................................................................…………….……………………….... 2
2.1.1 Voronoi 圖............................................................................................................................... 2
2.1.2 Delaunay 3角剖分................................................................................................................. 3
2.2 2維空間建Delaunay 3角網(wǎng)的基本思想....................................................................................... 4
2.2.1 數(shù)據(jù)點的預(yù)處理..................................................................................................................... 4
2.2.2 建立起始的3角形................................................................................................................. 6
2.2.3 建立3角網(wǎng)........................................................................................................................... 7
3 Delaunay 4面體網(wǎng)格的構(gòu)建.......................................................................................................... 8
3.1 與算法相適應(yīng)的數(shù)據(jù)結(jié)構(gòu).............................................................................................................. 8
3.2 3維平面構(gòu)建Delaunay 4面體網(wǎng)格的算法................................................................................. 13
3.2.1 數(shù)據(jù)的輸入和預(yù)處理........................................................................................................... 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 構(gòu)建Delaunay4面體網(wǎng)格.................................................................................................... 17
4 實驗結(jié)論.....................................................................................................................20
5 討論........................................................................................................................................................ 22
6 參考文獻(xiàn)..........................................................................................................................................24
7 致謝..................................................................................................................................................24
附錄............................................................................................................................................................25
1 前 言
3維建模技術(shù)在建筑，地質(zhì)地形勘測，醫(yī)學(xué)圖像建模，動畫設(shè)計等各方面都有廣泛的應(yīng)用。在進(jìn)行某項工程設(shè)計，或者醫(yī)療操作時，如果能建立計算機(jī)仿真平臺，通過這個平臺的仿真實驗來驗證設(shè)計方案的可行性及對此操作的成功率指標(biāo)進(jìn)行評估的話，不僅可以提高設(shè)計計劃的成功率，而且可以節(jié)省設(shè)計的時間和資金。通過仿真還可以對設(shè)計方案和有關(guān)參數(shù)進(jìn)行驗證和修正，對于醫(yī)療方案的仿真，更是提高了手術(shù)治療的成功率，維護(hù)了病人的生命財產(chǎn)。
1個3維模型的建立過程包括：3維原始數(shù)據(jù)的獲取、去除噪聲、曲面拼接、修補(bǔ)“洞”，最終得到1個可以在計算機(jī)上顯示的具有3維特征的網(wǎng)格。3維可視化技術(shù)包括表面繪制技術(shù)和體繪制技術(shù)。由于將已建好的3維模型顯示在計算機(jī)上的技術(shù)已經(jīng)很成熟，所以可視化技術(shù)的主要問題在于3維建模。表面繪制是抽取出3維原始數(shù)據(jù)中的表面數(shù)據(jù)，然后將模型的表面信息顯示在計算機(jī)上；體繪制不需要對3維原始數(shù)據(jù)作太多處理，由于這種方法建立的模型不僅有物體表面的信息，還包含圖形內(nèi)部點的信息，甚至各點之間的相互作用或者連接關(guān)系，所以用體繪制方法得到的模型可以用來模擬物體的受力形變過程。目前國際上表面繪制技術(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)絡(luò)，沒有任何點被遺漏也盡量沒有冗余。當(dāng)物體受外界作用發(fā)生形變的時候，因為數(shù)據(jù)點之間的聯(lián)系是確定的，所以作用范圍內(nèi)的點及其相鄰點的受力情況和運(yùn)動過程是可以通過簡單的力學(xué)計算得到的，因此我們可以應(yīng)用這樣的模型來做各種力學(xué)和醫(yī)學(xué)等仿真。截止到目前為止，還沒有現(xiàn)成的軟件能夠做這件事情。國際上也還沒有成熟的算法。我在畢業(yè)設(shè)計中所做的事情屬于體繪制的1部分，即基于3維數(shù)據(jù)點云建立立體網(wǎng)格，所用的方法是基于Delaunay3角剖分原理建立Delaunay4面體網(wǎng)格。這種方法的優(yōu)點是所建立的4面體與其他方法相比最接近正4面體，形狀最規(guī)則，且剖分的結(jié)果是唯1的。
目前國際上對立體仿真建模的研究最為關(guān)注的是醫(yī)學(xué)方面的應(yīng)用。但是用于醫(yī)學(xué)仿真操作的模型，必須具有和人體組織完全相同的形狀和結(jié)構(gòu)，在手術(shù)刀切割等外界條件下，才能夠做出完全類似于真實人體的反應(yīng)和形變，因為其模擬的結(jié)果可以說是性命攸關(guān)的大事，所以要求有相當(dāng)高的精度。
這項工作有著良好的發(fā)展和應(yīng)用的前景。如果立體建網(wǎng)的技術(shù)成熟起來，基于真實物體的仿真模型將會被應(yīng)用到生活的各個方面。不僅可以做工程和醫(yī)學(xué)仿真，隨著網(wǎng)上購物越來越走入人們的生活，我們可以某些商品建成可視又可“觸”的模型，人們在選購的時候不僅可以看到商品的樣子，還可以用鼠標(biāo)和鍵盤對商品模型進(jìn)行各種操作，看它的彈性、柔軟度等性質(zhì)，從而用更直觀，更便捷的方法來了解商品的性能，而不是對著大篇幅的數(shù)字指標(biāo)發(fā)呆。這種技術(shù)還可以同大型場景相結(jié)合，讓人們能夠在風(fēng)景勝地、災(zāi)難現(xiàn)場、文物古跡等的虛擬現(xiàn)實世界漫游，足不出戶就可以有身臨其境的感受，甚至去“接觸”物體。如果我們能夠建立仿真的地理模型，就可以做地震、暴雨等的災(zāi)難模擬實驗，用來做災(zāi)難預(yù)測和為維修提供理論依據(jù)，從而節(jié)省大量不必要的開支。3維仿真模型的應(yīng)用領(lǐng)域10分廣闊，伴隨著計算機(jī)走進(jìn)千家萬戶的腳步，網(wǎng)絡(luò)將在我們的生活扮演越來越重要的角色，也許有1天，你會說：斷網(wǎng)了可讓我怎么活，電腦和網(wǎng)絡(luò)就像今天的“電”1樣重要，到那個時候網(wǎng)絡(luò)上的模型都能很好的模擬真實世界的物體，3維仿真建模的技術(shù)才真正有了用武之地。
2 Delaunay3角剖分的基本原理
3角剖分的定義：若對平面剖分的所有邊界區(qū)域都是3角形，則這種平面剖分稱為3角剖分。3角剖分是計算
[1]
【Delaunay方法三維建�！肯嚓P(guān)文章：
數(shù)學(xué)建模論文模板07-22
數(shù)學(xué)建模論文模板07-22
數(shù)據(jù)建模論文格式06-29
簡單的數(shù)學(xué)建模小論文09-02
數(shù)學(xué)建模論文模板15篇[通用]07-21
數(shù)學(xué)建模優(yōu)秀論文（通用10篇）08-02
淺談光學(xué)三維測量技術(shù)05-22