Delaunay方法三維建模

摘要
3維建模技術(shù)在建筑，地質(zhì)地形勘測(cè)，醫(yī)學(xué)圖像建模，動(dòng)畫設(shè)計(jì)等各方面都有廣泛的應(yīng)用. 1個(gè)3維模型的建立過程包括3維原始數(shù)據(jù)的獲取、去除噪聲、曲面拼接、修補(bǔ)“洞”，最終得到1個(gè)可以在計(jì)算機(jī)上顯示的具有3維特征的網(wǎng)格. 3維可視化技術(shù)包括表面繪制技術(shù)和體繪制技術(shù)。由于將已有的3維模型顯示在計(jì)算機(jī)上的技術(shù)已經(jīng)很成熟，所以可視化技術(shù)的主要問題在于3維建模.
使用Delaunay方法來建模，由于Delaunay3角是盡量接近于等邊3角形的，所以用這種方法建的網(wǎng)格會(huì)比較均勻，顯示圖像的時(shí)候視覺效果就是整個(gè)圖像很勻稱，不會(huì)出現(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個(gè)步驟，其中附有說明圖和流程圖。第4章列出了實(shí)驗(yàn)結(jié)果（1系列圖），驗(yàn)證算法的正確性。這里要說明的是，在實(shí)驗(yàn)中只選了9個(gè)點(diǎn)，但這9個(gè)點(diǎn)建網(wǎng)的過程中出現(xiàn)了Tsung-Pao Fang所列出的所有需要特殊處理的情況，也就是說，如果用再多的點(diǎn)來做這個(gè)實(shí)驗(yàn)，也不過就是這幾種情況的重復(fù)。后面的4幅圖是后來所作的工作，得到了1個(gè)正方體4頂點(diǎn)以及其中心點(diǎn)的建網(wǎng)結(jié)果，從這里能清楚地看到4面體網(wǎng)格的結(jié)構(gòu)，還有對(duì)貝殼數(shù)據(jù)點(diǎn)云的部分建網(wǎng)結(jié)果，之所以沒有完成整個(gè)貝殼數(shù)據(jù)的建網(wǎng)是因?yàn)閿?shù)據(jù)中存在較多的5點(diǎn)或5點(diǎn)以上共球的情況，這種情況下Delaunay準(zhǔn)則不再適用，建網(wǎng)會(huì)中斷，所以只完成了1個(gè)部分。第5章針對(duì)程序中存在的問題和我在畢業(yè)設(shè)計(jì)過程中遇到的困難進(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)知識(shí)…….......................................................................…………….……………………….... 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ù)點(diǎn)的預(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 整個(gè)算法的起始點(diǎn) .......................................................................................................... 14
3.2.3 搜索與 距離最近的點(diǎn) .................................. ............................................................. 14
3.2.4 尋找滿足Delaynay法則的第3個(gè)點(diǎn) ............................... .............................................. 15
3.2.5 已知1個(gè)3角面片，搜索第4個(gè)點(diǎn)..................................................................................... 16
3.2.6 構(gòu)建Delaunay4面體網(wǎng)格.................................................................................................... 17
4  實(shí)驗(yàn)結(jié)論.....................................................................................................................20
5  討論........................................................................................................................................................ 22
6  參考文獻(xiàn)..........................................................................................................................................24
7  致謝..................................................................................................................................................24
附錄............................................................................................................................................................25

1  前 言

3維建模技術(shù)在建筑，地質(zhì)地形勘測(cè)，醫(yī)學(xué)圖像建模，動(dòng)畫設(shè)計(jì)等各方面都有廣泛的應(yīng)用。在進(jìn)行某項(xiàng)工程設(shè)計(jì)，或者醫(yī)療操作時(shí)，如果能建立計(jì)算機(jī)仿真平臺(tái)，通過這個(gè)平臺(tái)的仿真實(shí)驗(yàn)來驗(yàn)證設(shè)計(jì)方案的可行性及對(duì)此操作的成功率指標(biāo)進(jìn)行評(píng)估的話，不僅可以提高設(shè)計(jì)計(jì)劃的成功率，而且可以節(jié)省設(shè)計(jì)的時(shí)間和資金。通過仿真還可以對(duì)設(shè)計(jì)方案和有關(guān)參數(shù)進(jìn)行驗(yàn)證和修正，對(duì)于醫(yī)療方案的仿真，更是提高了手術(shù)治療的成功率，維護(hù)了病人的生命財(cái)產(chǎn)。
1個(gè)3維模型的建立過程包括：3維原始數(shù)據(jù)的獲取、去除噪聲、曲面拼接、修補(bǔ)“洞”，最終得到1個(gè)可以在計(jì)算機(jī)上顯示的具有3維特征的網(wǎng)格。3維可視化技術(shù)包括表面繪制技術(shù)和體繪制技術(shù)。由于將已建好的3維模型顯示在計(jì)算機(jī)上的技術(shù)已經(jīng)很成熟，所以可視化技術(shù)的主要問題在于3維建模。表面繪制是抽取出3維原始數(shù)據(jù)中的表面數(shù)據(jù)，然后將模型的表面信息顯示在計(jì)算機(jī)上；體繪制不需要對(duì)3維原始數(shù)據(jù)作太多處理，由于這種方法建立的模型不僅有物體表面的信息，還包含圖形內(nèi)部點(diǎn)的信息，甚至各點(diǎn)之間的相互作用或者連接關(guān)系，所以用體繪制方法得到的模型可以用來模擬物體的受力形變過程。目前國(guó)際上表面繪制技術(shù)已經(jīng)很成熟了，隨之出現(xiàn)的各種軟件，如3d studio max等，都可以作圖像的表面建模，既方便快捷，效果也不錯(cuò)。但是，在許多作仿真用途的模型中，特別是醫(yī)用模型，往往需要模型能夠真實(shí)地模仿實(shí)際物體受到外界干擾時(shí)會(huì)如何發(fā)生形變，這就需要把掃描對(duì)象物體得到的3維數(shù)據(jù)點(diǎn)云用立體網(wǎng)格（區(qū)別于3角網(wǎng)或者多邊形網(wǎng)格這種表面建網(wǎng)得到的網(wǎng)格）來連接建網(wǎng)。建網(wǎng)的目的是要把3維圖形無論表面還是內(nèi)部的點(diǎn)連接起來，用有限的連接關(guān)系建立起包括所有點(diǎn)的網(wǎng)絡(luò)，沒有任何點(diǎn)被遺漏也盡量沒有冗余。當(dāng)物體受外界作用發(fā)生形變的時(shí)候，因?yàn)閿?shù)據(jù)點(diǎn)之間的聯(lián)系是確定的，所以作用范圍內(nèi)的點(diǎn)及其相鄰點(diǎn)的受力情況和運(yùn)動(dòng)過程是可以通過簡(jiǎn)單的力學(xué)計(jì)算得到的，因此我們可以應(yīng)用這樣的模型來做各種力學(xué)和醫(yī)學(xué)等仿真。截止到目前為止，還沒有現(xiàn)成的軟件能夠做這件事情。國(guó)際上也還沒有成熟的算法。我在畢業(yè)設(shè)計(jì)中所做的事情屬于體繪制的1部分，即基于3維數(shù)據(jù)點(diǎn)云建立立體網(wǎng)格，所用的方法是基于Delaunay3角剖分原理建立Delaunay4面體網(wǎng)格。這種方法的優(yōu)點(diǎn)是所建立的4面體與其他方法相比最接近正4面體，形狀最規(guī)則，且剖分的結(jié)果是唯1的。
目前國(guó)際上對(duì)立體仿真建模的研究最為關(guān)注的是醫(yī)學(xué)方面的應(yīng)用。但是用于醫(yī)學(xué)仿真操作的模型，必須具有和人體組織完全相同的形狀和結(jié)構(gòu)，在手術(shù)刀切割等外界條件下，才能夠做出完全類似于真實(shí)人體的反應(yīng)和形變，因?yàn)槠淠�擬的結(jié)果可以說是性命攸關(guān)的大事，所以要求有相當(dāng)高的精度。
這項(xiàng)工作有著良好的發(fā)展和應(yīng)用的前景。如果立體建網(wǎng)的技術(shù)成熟起來，基于真實(shí)物體的仿真模型將會(huì)被應(yīng)用到生活的各個(gè)方面。不僅可以做工程和醫(yī)學(xué)仿真，隨著網(wǎng)上購(gòu)物越來越走入人們的生活，我們可以某些商品建成可視又可“觸”的模型，人們?cè)谶x購(gòu)的時(shí)候不僅可以看到商品的樣子，還可以用鼠標(biāo)和鍵盤對(duì)商品模型進(jìn)行各種操作，看它的彈性、柔軟度等性質(zhì)，從而用更直觀，更便捷的方法來了解商品的性能，而不是對(duì)著大篇幅的數(shù)字指標(biāo)發(fā)呆。這種技術(shù)還可以同大型場(chǎng)景相結(jié)合，讓人們能夠在風(fēng)景勝地、災(zāi)難現(xiàn)場(chǎng)、文物古跡等的虛擬現(xiàn)實(shí)世界漫游，足不出戶就可以有身臨其境的感受，甚至去“接觸”物體。如果我們能夠建立仿真的地理模型，就可以做地震、暴雨等的災(zāi)難模擬實(shí)驗(yàn)，用來做災(zāi)難預(yù)測(cè)和為維修提供理論依據(jù)，從而節(jié)省大量不必要的開支。3維仿真模型的應(yīng)用領(lǐng)域10分廣闊，伴隨著計(jì)算機(jī)走進(jìn)千家萬戶的腳步，網(wǎng)絡(luò)將在我們的生活扮演越來越重要的角色，也許有1天，你會(huì)說：斷網(wǎng)了可讓我怎么活，電腦和網(wǎng)絡(luò)就像今天的“電”1樣重要，到那個(gè)時(shí)候網(wǎng)絡(luò)上的模型都能很好的模擬真實(shí)世界的物體，3維仿真建模的技術(shù)才真正有了用武之地。
2  Delaunay3角剖分的基本原理

3角剖分的定義：若對(duì)平面剖分的所有邊界區(qū)域都是3角形，則這種平面剖分稱為3角剖分。3角剖分是計(jì)算

[1]  

【Delaunay方法三維建模】相關(guān)文章：

小學(xué)數(shù)學(xué)建模的定位與教學(xué)方法05-06

運(yùn)動(dòng)型多功能車（SUV）汽車后橋設(shè)計(jì)及三維建模03-02

基于NURBS曲面建模的UTD方法的方向圖求解11-22

三維坐標(biāo)轉(zhuǎn)換的公共點(diǎn)選擇方法03-07

論地質(zhì)工程復(fù)雜地質(zhì)體三維建模和可視化研究03-01

在高等數(shù)學(xué)教學(xué)中體現(xiàn)數(shù)學(xué)建模思想的方法11-25

CODARTS建模方法在嵌入式軟件開發(fā)中的應(yīng)用03-18

試論大學(xué)數(shù)學(xué)建模方法教學(xué)策略在中學(xué)的有效應(yīng)用03-17

物理建模論文11-21