論文：如何實現(xiàn)三維表面建模

PAGE

分類號密級

UDC編號

碩士學(xué)位論文

論文題目如何實現(xiàn)三維表面建模

學(xué)科、專業(yè)計算機(jī)科學(xué)與技術(shù)

研究生姓名

導(dǎo)師姓名及

專業(yè)技術(shù)職務(wù)副教授

MSTHESIS

原創(chuàng)性聲明

本人聲明，所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了論文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得中南大學(xué)或其他單位的學(xué)位或證書而使用過的材料。與我共同工作的同志對本研究所作的貢獻(xiàn)均已在論文中作了明確的說明。

作者簽名：日期：年月日

學(xué)位論文版權(quán)使用授權(quán)書

作者簽名：導(dǎo)師簽名日期年月日

[3]

。體繪制認(rèn)為每一個體素都具有一定的屬性，比如透明度、光亮度，然后根據(jù)光照模型和體素介質(zhì)屬性分配一定的不透明度和光強(qiáng)度，并在視線方向上積分計算，最后將計算得出的半透明圖像在屏幕上顯示出來，處理過程如圖1-1所示。

圖1-1體繪制方法處理過程

體數(shù)據(jù)的顯示方法，從本質(zhì)上來說都是利用光線投射的理論，可分為兩種顯示過程。第一種體繪制方法以空間圖像為序。這種方法以像素順序進(jìn)行，即處理完一個像素后接著處理另一個像素。第二種方法是以空間對象為序。這種方法以體素順序進(jìn)行，即處理完當(dāng)前體素后接著處理下一個體素。此方法需要考慮體素遍歷時的順序，從后往前和從前往后的結(jié)合順序是有所不同的

REF_Ref259393861\r\h

[4]

。

光線投射算法就是一個典型的以空間圖像為序的算法

REF_Ref259393560\r\h

[3]

。該算法的基本思想是：首先屏幕上的每一個像素點(diǎn)發(fā)出一條射線，此射線將橫穿三維數(shù)據(jù)場的體素矩陣，接著在這條射線上進(jìn)行等距采樣，根據(jù)采樣點(diǎn)最近數(shù)據(jù)點(diǎn)的不透明度和顏色值對采樣點(diǎn)進(jìn)行插值，求解出采樣點(diǎn)的不透明度和顏色值；然后，根據(jù)不同的圖像合成方式，對采樣點(diǎn)的不透明度和顏色值進(jìn)行合成；最后，對光線上的所有采樣點(diǎn)都插值完后，屏幕對應(yīng)像素點(diǎn)的顏色值和亮度值就已經(jīng)計算出來了。根據(jù)上述步驟，當(dāng)屏幕所有的像素點(diǎn)值都計算完時，就得到了整個體數(shù)據(jù)的完整圖像，如圖1-2所示。

（a）三維視圖（b）頂視圖

圖1-2體的光線投射

以空間對象為序進(jìn)行體繪制的方法叫做單元投影算法

REF_Ref259394068\r\h

[4]

。該方法首先需給出投影方向和投影平面，然后把所有體素依一定的順序投影到圖像平面，并計算出每個數(shù)據(jù)點(diǎn)對屏幕像素點(diǎn)的貢獻(xiàn)度，得到最終的圖像。目前有多種投影算法，如Splatting算法

REF_Ref259394385\r\h

[6]

和Shear-Warp算法等

REF_Ref259394478\r\h

[7]

。

在實際應(yīng)用中，特別是在醫(yī)學(xué)圖像診斷中，光線投射算法速度較慢。許多學(xué)者提出了各種加速體繪制方法

REF_Ref261183657\r\h

[8]

REF_Ref261183988\r\h

[9]

，能在較短的時間內(nèi)得到了較好的體繪制圖像質(zhì)量。因而到目前為止，該算法仍是一種使用較為廣泛的體繪制方法

REF_Ref259394509\r\h

[10]

REF_Ref259394511\r\h

[11]

。

1.2.2面繪制方法

面繪制是從原始數(shù)據(jù)中重建中間的幾何圖元，然后用真實感圖形學(xué)技術(shù)對幾何圖元進(jìn)行繪制。面繪制可分為兩種：（1）基于輪廓線拼接（切片級）的面繪制；（2）基于等值面（體素級）的面繪制。

1、基于輪廓線拼接（切片級）的面繪制

基于輪廓線拼接的面繪制是最早被用來進(jìn)行面繪制的方法

REF_Ref259394677\r\h

[12]

。Keppel于1975年提出了最早的輪廓線法思想。該思想采用三角面片來覆蓋物體的表面，并以面片所圍成的最大體積作為約束條件，實現(xiàn)物體的表面建模

REF_Ref259394696\r\h

[13]

。該方法成為了三維表面建模算法的基礎(chǔ)，隨后有許多學(xué)者對該方法進(jìn)行了研究和改進(jìn)

REF_Ref259394712\r\h

[14]

REF_Ref259394715\r\h

[15]

。

由于基于輪廓線拼接的面繪制方法約束性不強(qiáng)，導(dǎo)致它們具有很大的隨意性。在輪廓線形態(tài)復(fù)雜多變，輪廓線位置、方向和形狀差異較大的情況下，重建的效果不理想，雖然許多學(xué)者作了大量的研究，但是仍然沒有從根本上得到完全解決。輪廓對應(yīng)、拼接和分支問題的具體的原理將在本文第二章進(jìn)行詳細(xì)的闡述。

2、基于等值面（體素級）的面繪制

基于等值面的面繪制思想是：首先依次對每個體素進(jìn)行處理，確定出其所包含的等值面片；然后將所有的體素的面片連接起來形成整個物體表面。所謂等值面就是指如果把體數(shù)據(jù)看成是某個空間區(qū)域內(nèi)關(guān)于某種物理屬性的采樣集合，通過插值來估計非采樣點(diǎn)和鄰近采樣點(diǎn)上的采樣值，則該空間區(qū)域內(nèi)所有具有某一個屬性的點(diǎn)集合定義成為一個或多個曲面，稱之為等值面。

近年來，基于等值面的面繪制得到了廣泛的關(guān)注,并取得了許多重要的成果。Herman等

REF_Ref259394741\r\h

[16]

是最早提出立方體方法的等值面繪制方法。它采用邊界體素的六個面來擬合等值面。Cline等

REF_Ref259433370\r\h

[17]

提出剖分立方體的等值面構(gòu)造方法。該方法采用點(diǎn)來構(gòu)造等值面，但只有在點(diǎn)比較密集時，才呈現(xiàn)“實體”模型。Lorenson等

REF_Ref259394760\r\h

[18]

在1987年提出了一種基于體素的典型面繪制算法——MC算法。目前MC算法已成為最流行的等值面構(gòu)造算法，它對科學(xué)計算可視化產(chǎn)生了巨大的影響。但是，MC算法同樣還存在著缺陷，主要表現(xiàn)在等值面的拓?fù)浣Y(jié)構(gòu)錯誤

REF_Ref259394778\r\h

[19]

、繪制精度不高

REF_Ref261181922\r\h

[20]

REF_Ref259394793\r\h

[21]

、占用存儲空間大和處理速度較慢

REF_Ref259394809\r\h

[22]

REF_Ref261035697\r\h

[23]

等方面。J.Durst首先提出了MC算法中的二義性問題。為了克服MC的二義性問題，人們提出了MarchingTetrahedra算法

REF_Ref259394843\r\h

[24]

。由于MC算法非常具有代表性，因此在科學(xué)計算可視化的各種雜志和會議上，還經(jīng)常有關(guān)于MC算法的改進(jìn)算法

REF_Ref259394857\r\h

[25]

。

基于體素級和基于切片級的建模方法分別適用于不同的原始數(shù)據(jù)。體素級面繪制會產(chǎn)生大量的小面片，占用額外空間，給圖形的顯示和更新帶來麻煩。因此，如何減少冗余的小面片是一個值得研究的課題

REF_Ref259394881\r\h

[26]

。切片級建模相對于體素級而言壓縮了大量冗余的數(shù)據(jù)，但是存在輪廓線拼接的多義性問題。在分支問題上，該問題尤為明顯。

由于切片級的面繪制存在著輪廓對應(yīng)、輪廓拼接、輪廓分支等問題，其中輪廓對應(yīng)和分支問題是難點(diǎn)問題?，F(xiàn)有的輪廓線拼接算法在分支問題上只側(cè)重于解決一條輪廓線與多條輪廓線間的正確拼接問題，而在實際應(yīng)用中往往并不是這么簡單，這使得這些算法在輪廓線的拼接上存在著很大缺陷。為此，M.W.Jones、張勇等人將此問題轉(zhuǎn)化為體數(shù)據(jù)中的等值面構(gòu)造問題

REF_Ref261172371\r\h

[27]

REF_Ref261175032\r\h

[28]

。

除了上述兩種主要方法，有些學(xué)者還提出了用數(shù)學(xué)方法來解決表面重建問題

REF_Ref259432922\r\h

[29]

。這些方法大多以表面上所有點(diǎn)的曲率之和最小為約束條件，用偏微分方法來表示表面，并求出微分方程的解。這種方法計算量大，并且最后還是要通過體數(shù)據(jù)來進(jìn)行表面顯示。

1.3主要研究內(nèi)容

針對研究現(xiàn)狀，本文主要研究了基于斷層數(shù)據(jù)序列構(gòu)建三維幾何模型的表面建模方法及其實現(xiàn)。研究和實驗中的數(shù)據(jù)均為危機(jī)礦山項目中的數(shù)據(jù)。

表面建模算法的研究進(jìn)展很大程度上決定了三維表面建模系統(tǒng)的發(fā)展以及功能的開發(fā)，是實現(xiàn)表面重建的關(guān)鍵。研究選擇一種最佳的表面建模算法，對表面建模有著至關(guān)重要的作用。本文通過研究現(xiàn)階段一些主要的表面建模算法，分析各算法的優(yōu)缺點(diǎn)，并根據(jù)當(dāng)前項目以及應(yīng)用需要，選擇最適合的表面建模算法。

MC算法是被證明了的基于等值面面繪制的經(jīng)典算法之一。為了實現(xiàn)最好的面繪制效果，本文通過對MC算法原理和算法流程的研究，從克服該算法的缺陷以及提高表面繪制質(zhì)量和速度著手，提出一種新的表面建模算法——MP算法，以實現(xiàn)最佳的繪制效果。MP算法通過對輪廓線進(jìn)行體數(shù)據(jù)的構(gòu)造，并抽取體數(shù)據(jù)中等值面，實現(xiàn)物體表面的生成。同時為了滿足用戶的不同應(yīng)用目的，以及對繪制質(zhì)量和繪制速度的具體要求，本文從MP算法的關(guān)鍵步驟入手，提供了多種表面生成模式供用戶選擇，以最大程度地滿足表面建模的需求。

在等值面與輪廓線的逼近精度問題上，本文提出了一種分類處理輪廓線的漸近算法。該算法將基于輪廓線拼接算法引入到基于等值面的面繪制算法中，利用基于輪廓線拼接算法的優(yōu)點(diǎn)，將原輪廓線進(jìn)行平移，然后在等值輪廓線與原輪廓線之間采用一種輪廓線“分段對應(yīng)拼接”方法，使重建出的物體表面與輪廓線達(dá)到完全吻合。同時，該算法在投影輪廓線之間采用基于等值面的面繪制算法進(jìn)行表面建模，實現(xiàn)整個物體的表面生成，取得了較好的效果。

基于上述研究，本文最終實現(xiàn)了一個高質(zhì)量的表面建模子系統(tǒng)。此表面建模子系統(tǒng)作為危機(jī)礦山三維信息評價系統(tǒng)的一部分，主要實現(xiàn)礦山三維斷層數(shù)據(jù)序列的讀取、剖面編輯、體數(shù)據(jù)的構(gòu)造、等值面的生成，以及用戶對表面模型進(jìn)行交互操作等功能。

1.4論文的組織結(jié)構(gòu)

本文共分為六章，分別為緒論、三維表面建模技術(shù)、基于MP的三維建模方法、分類處理輪廓線的漸近算法、模型可視化與三維表面建模系統(tǒng)的實現(xiàn)、結(jié)論與展望。

第一章是緒論。該章首先介紹了三維表面建模技術(shù)的研究背景和重要意義，然后分析了三維建模技術(shù)在國內(nèi)外的研究現(xiàn)狀與水平，最后給出了本課題的研究內(nèi)容和文章的組織結(jié)構(gòu)。

第二章研究了三維表面建模技術(shù)。該章詳細(xì)地研究了兩類主要的三維表面建模方法，即基于輪廓線連接的表面建模方法和基于等值面面繪制的表面建模方法。文章分別研究了它們的方法思路、優(yōu)缺點(diǎn)和適用情況，其中對MC算法進(jìn)行了重點(diǎn)研究，包括該算法的基本原理和實現(xiàn)步驟。

第三章介紹本文提出的MP算法。該章根據(jù)MC算法的基本原理，結(jié)合當(dāng)前項目中的具體應(yīng)用要求，提出了基于MP的三維表面建模算法。本章重點(diǎn)介紹了MP算法的基本思想及步驟，并對MP算法進(jìn)行了算法分析和實驗驗證。

第四章研究了分類處理輪廓線的漸近算法。該章在當(dāng)前項目應(yīng)用背景的基礎(chǔ)上，提出了分類處理輪廓線的漸近算法，主要介紹了該算法的關(guān)鍵步驟，分析了算法的時間復(fù)雜性，最后本章還對分類處理輪廓線的漸近算法進(jìn)行了實驗驗證。

第五章首先簡要地研究了OpenGL實現(xiàn)模型可視化的基本原理，其次介紹了本文設(shè)計的一個表面建模子系統(tǒng)，并用本文算法實現(xiàn)了某礦體的三維空間模型，最后給出了效果圖。

第六章是全文的最后一章，該章首先對自己的工作進(jìn)行了全面的總結(jié)，然后對自己將來工作的研究和改進(jìn)進(jìn)行了討論。

碩士學(xué)位論文第二章三維表面建模技術(shù)

PAGE

109

第二章三維表面建模技術(shù)

三維表面建模技術(shù)有幾種比較典型的方法，通常主要可分為兩種：（1）基于輪廓線拼接的建模方法；（2）基于體素級的建模方法。除了這兩種方法外，還有一些其他的建模技術(shù)

REF_Ref259432945\r\h

[30]

REF_Ref261175206\r\h

[31]

，這些方法適用于不同的應(yīng)用領(lǐng)域。本章首先介紹了基于輪廓線拼接的建模方法，分析了該方法的主要難題，然后介紹了基于體素級的建模方法，并著重研究了MC的表面建模方法，最后還簡單介紹了一些其他建模技術(shù)。

2.1基于輪廓線拼接的建模方法

2.1.1基本原理

基于輪廓線拼接的建模方法基本原理是首先找出相鄰斷層剖面上相應(yīng)的輪廓線及其對應(yīng)點(diǎn)，然后用三角片連接起來，最后繪制出這些三角片。該方法可以看成是對規(guī)則的離散采樣點(diǎn)進(jìn)行表面建模的問題。如圖2-1所示，該算法通?？煞纸鉃樗膫€基本問題：（1）輪廓對應(yīng)；（2）輪廓拼接；（3）輪廓分支；（4）表面擬合。

圖2-1基于輪廓線拼接的表面重建問題示意圖

2.1.2基于輪廓線拼接的主要難題

1、輪廓對應(yīng)問題

輪廓線對應(yīng)問題發(fā)生在相鄰層剖面上或其中一個剖面上有多條輪廓線的場合。在實際應(yīng)用中，這是經(jīng)常會碰到情形。要解決該問題，需解決輪廓線之間的對應(yīng)關(guān)系問題，也就是要確定一個剖面上的哪條輪廓線與另一個剖面的哪條輪廓線進(jìn)行連接。該問題在輪廓線錯位嚴(yán)重且形狀相似度很小的情況下，更加難以解決?，F(xiàn)常用的方法有輪廓覆蓋法和基于全局的最小生成樹法等。

基于輪廓覆蓋法的輪廓對應(yīng)只是一種局部判斷準(zhǔn)則，該準(zhǔn)則通過對相鄰剖面上輪廓線包圍盒重疊大小的計算，來進(jìn)行輪廓線對應(yīng)關(guān)系的判定

REF_Ref259432970\r\h

[32]

。當(dāng)輪廓線間的距離較遠(yuǎn)或形態(tài)差異比較大時，該方法不能可靠、準(zhǔn)確地判斷輪廓線的對應(yīng)關(guān)系，這時需要綜合考慮整個輪廓線組。

Meyers提出采用外接橢圓近似代表輪廓，用多邊形近似表示凹輪廓，由此建立一個全部輪廓線的無向圖

REF_Ref259432995\r\h

[33]

。在無向圖中，每條輪廓線用節(jié)點(diǎn)來表示，若兩條輪廓線之間是對應(yīng)的，那么在圖中將會有一條對應(yīng)邊。因此，可通過無向圖的最小生成樹計算來獲得輪廓線之間的對應(yīng)關(guān)系。最小生成樹方法考慮了全局信息，能全面考慮對輪廓線的對應(yīng)關(guān)系，獲得了比較準(zhǔn)確的結(jié)果。

2、輪廓拼接問題

用三角面片或者多邊形構(gòu)造通過相鄰剖面上對應(yīng)輪廓的表面的過程稱為輪廓拼接

REF_Ref259433031\r\h

[34]

。該問題需要確定輪廓線上點(diǎn)的對應(yīng)關(guān)系，并利用三角面片或多邊形來表示輪廓間的物體表面。常用的拼接方法有：圓環(huán)圖方法的輪廓拼接和輪廓匹配方法的輪廓拼接。

假設(shè)、為兩個待進(jìn)行拼接的對應(yīng)輪廓，其中、上的點(diǎn)序列分別為：，，其中，。圖2-2（a）為m=6，n=7個頂點(diǎn)的輪廓。連接同一輪廓上的兩個相鄰點(diǎn)所得到的邊稱作輪廓段，而連接不同輪廓上的兩個點(diǎn)所得到的邊稱作跨段。建立一個圖，用結(jié)點(diǎn)表示跨段，當(dāng)兩個跨段有一個公共點(diǎn)時，用弧把這兩個跨段所對應(yīng)的結(jié)點(diǎn)連接起來，這樣所得到的圖稱之為圓環(huán)圖，如圖2-2（b）。

（a）輪廓拼接圖（b）圓環(huán)圖

圖2-2基于圓環(huán)圖的輪廓拼接

H.Fuchs提出了一個可接受表面的定義形式

REF_Ref259433045\r\h

[35]

：

（1）任意一條輪廓段能且僅能存在于一個三角面片中。因此，可以得出結(jié)論：若兩輪廓線的輪廓段數(shù)分別為m、n，那么正確的三維物體表面應(yīng)該有m+n個三角面片組成；

（2）如果一條跨段為某一個三角面片的左跨段，那么該跨段只能作為另一個三角面片的右跨段。

對于圖2-2中的圓環(huán)圖，如果沒有任何條件加以約束，圓環(huán)圖中將存在著很多通路。如果給圓環(huán)圖的每條弧賦予一個權(quán)值（其中權(quán)值是對弧所表示的三角面片的某個度量，如跨段長度、面積等），那么一個環(huán)的費(fèi)用就可以用該環(huán)上的所有弧的權(quán)值之和來表示。尋找一個環(huán)在某個度量下的最優(yōu)解就是要在圓環(huán)圖中搜索出某個環(huán)，并使它的費(fèi)用最大或最小。目前，已有的準(zhǔn)則有體積最大

REF_Ref259394696\r\h

[13]

、表面積最小

REF_Ref259433078\r\h

[36]

、跨度長度之和最小

REF_Ref259433093\r\h

[37]

或者方向一致

REF_Ref259433103\r\h

[38]

，即輪廓點(diǎn)匹配方向最大程度地與質(zhì)心匹配方向一致。

基于輪廓匹配的輪廓拼接方法的基本思想是對預(yù)先給定的兩條對應(yīng)輪廓線，查找其中一條輪廓線上點(diǎn)與另一條輪廓線上點(diǎn)的對應(yīng)關(guān)系。目前，彈性匹配

REF_Ref259433122\r\h

[39]

是解決形變匹配的有效方法之一。Burr

REF_Ref259433137\r\h

[40]

在彈性匹配算法中使用了動態(tài)協(xié)作模型模擬彈性模型實現(xiàn)非剛體的匹配。為克服彈性匹配方法存在的計算復(fù)雜和內(nèi)部制約力不強(qiáng)的缺點(diǎn)，文獻(xiàn)

REF_Ref259433152\r\h

[41]

提出了一種基于線性彈性模型的形變輪廓匹配方法。

當(dāng)相鄰層的輪廓線具有幾何相似性時，蘇安等提出一種基于相鄰層輪廓線幾何形狀匹配的三維重建算法

REF_Ref261176701\r\h

[42]

。雖然該算法對一些過渡性很好的輪廓線能取得較好的重建效果，但是對突變性很大的輪廓線，該算法并不適用。李小勇等

REF_Ref261185705\r\h

[43]

采用模擬退火遺傳算法實現(xiàn)表面拼接，提高了傳統(tǒng)的全局法輪廓線拼接算法的效率。

3、輪廓分支問題

輪廓分支問題產(chǎn)生于一個物體在相鄰斷層上的輪廓個數(shù)不相等的情況?；谳喞€拼接的表面建模算法中，分支問題是一個關(guān)鍵性問題。因為僅僅通過分支的局部信息來確定輪廓線對應(yīng)關(guān)系，往往得不到很好的結(jié)果，所以需要通過全局的拓?fù)浜蛶缀谓Y(jié)構(gòu)來確定對應(yīng)關(guān)系。目前方法主要有兩類：（1）分解或組合輪廓線的方法；（2）相鄰層間插入中間層輪廓線或插入中軸線的方法。

（1）分解或組合輪廓線的方法

這類方法在分解或連接輪廓線的位置選擇上非常重要。何小海

REF_Ref259433165\r\h

[44]

利用數(shù)學(xué)形態(tài)學(xué)中的膨脹算法分解單支輪廓，XuMeihe

REF_Ref259433178\r\h

[45]

提出了一種根據(jù)輪廓凸包周長和輪廓中心位置分解單支輪廓的方法，黃永麗

REF_Ref259433191\r\h

[46]

采用按照周長比率解決分支問題，李小勇等

REF_Ref261179181\r\h

[47]

將Delaunay三角剖分應(yīng)用到分支問題上，他們提出的這些方法對于解決獨(dú)立分支有很好的效果。另外，還有一些學(xué)者

REF_Ref259433212\r\h

[48]

REF_Ref259433217\r\h

[49]

REF_Ref259433221\r\h

[50]

也采用此類方法將一條輪廓線分解為兩條輪廓線來解決分支問題。

（2）在相鄰層間插入中間層輪廓線或插入中軸線的方法

Christiansen和Sederberg

REF_Ref259433093\r\h

[37]

最早提出構(gòu)建過渡輪廓來解決一對二分支問題。他們通過構(gòu)建過渡輪廓線，在兩個分支輪廓線的最小距離點(diǎn)之間添加一個內(nèi)橋，然后將分支后的兩個封閉區(qū)域通過該點(diǎn)合二為一，這樣就把問題轉(zhuǎn)化為一對一的單輪廓線的連接。這類方法一般計算量大。Meyers等

REF_Ref259433266\r\h

[51]

將分支輪廓投影到基礎(chǔ)輪廓上，將其作為基礎(chǔ)輪廓線的孔來處理，計算帶孔輪廓的中心軸線，并用其來構(gòu)造過渡輪廓，這種方法構(gòu)造的輪廓形狀與基礎(chǔ)輪廓形狀相似。J.Jeong，K.kim

REF_Ref259433277\r\h

[52]

通過使用距離映射插入中間輪廓線來解決分支問題。Joaquin

REF_Ref259433296\r\h

[53]

將兩層的輪廓線映射到同一斷層平面上，利用提取骨架的方法生成中間層。

另外，Barequet

REF_Ref259433304\r\h

[54]

提出了一種以動態(tài)規(guī)劃為基礎(chǔ)的最優(yōu)三角剖分策略的方法。該算法通過其他途徑來解決分支問題，避開了傳統(tǒng)的分支處理方法。

總之，由于約束性的缺乏，基于輪廓線拼接的建模方法具有很大的隨意性。特別是在輪廓線形態(tài)復(fù)雜，輪廓線位置錯位嚴(yán)重，方向和形狀差異較大時，該方法重建的結(jié)果不理想。雖然目前有大量的研究工作

REF_Ref260733121\r\h

[55]

REF_Ref259433320\r\h

[56]

，但仍然不能從根本上完全解決。

2.2基于體素級的建模方法

2.2.1體素模型定義

體素的定義分為兩種

REF_Ref259433333\r\h

[57]

：一種類似于二維圖像中的像素定義，將體素定義為體數(shù)據(jù)中的一個采樣點(diǎn)；另一種則以相鄰的8個采樣點(diǎn)組成為一個體素。本文采用后一種定義方式。

對某一個區(qū)域內(nèi)的三維空間進(jìn)行采樣，若采樣間距為，，，且采樣點(diǎn)在x，y，z三個方向上是分布均勻的，那么可以用三維數(shù)字矩陣來表示體數(shù)據(jù)

REF_Ref259433333\r\h

[57]

。一個體素由8個相鄰的采樣點(diǎn)所定義的立方體區(qū)域。8個采樣點(diǎn)稱為體素的頂點(diǎn)。它們的坐標(biāo)分別為，，，，，，，。

圖2-3體素模型

設(shè)體素內(nèi)的任意一待求值點(diǎn)，（）為與點(diǎn)為同一個平面上的點(diǎn)，它們關(guān)系如圖2-3所示。的值采用該體素的8個頂點(diǎn)進(jìn)行三線性插值來估計。首先將物理坐標(biāo)轉(zhuǎn)化為圖像坐標(biāo)，其中，，。然后根據(jù)公式（2-1）進(jìn)行計算

公式（2-1）

又因為

公式（2-2）

公式（2-3）

公式（2-4）

其中

將式（2-2）、（2-3）、（2-4）代入式（2-1）整理可得

公式（2-5）

其中（）為常數(shù)，它們由體素的8個頂點(diǎn)值唯一確定。

2.2.2等值面定義

等值面是三維空間中具有相同值的點(diǎn)的集合，采用公式（2-6）來表示

，c為常數(shù)公式（2-6）

若當(dāng)前體素的8個頂點(diǎn)值均小于或大于常數(shù)時，那么等值面不經(jīng)過該體素。

要計算邊界體素與等值面的交線，可設(shè)體素中等值面的方程為，根據(jù)體素中任意一點(diǎn)值的計算公式（2-5），得到假設(shè)的表面方程為

公式（2-7）

由公式（2-7）可看出，所求的交線是一條雙曲線。除體數(shù)據(jù)的邊界處外，兩個共面體素之間的交線是它們的公共面與等值面的交線，因此不存在兩體素之間交線不吻合的情況。

2.2.3等值面構(gòu)造

等值面的構(gòu)造是實現(xiàn)基于面繪制方法的表面建模的關(guān)鍵步驟，等值面構(gòu)造方法是否合理，直接影響著表面的生成效果。等值面構(gòu)造方法主要有三種：（1）立方體法

REF_Ref259394741\r\h

[16]

；（2）剖分立方體法

REF_Ref259433370\r\h

[17]

；（3）移動立方體法

REF_Ref259394760\r\h

[18]

。

Lorenson

REF_Ref259394760\r\h

[18]

等在1987年提出的MC算法是基于體素的一種典型的面繪制算法。本文提出的算法是以MC算法思想為基礎(chǔ)，所以在下一節(jié)將對MC算法做重點(diǎn)研究。

2.3MC算法

MC算法基本原理是

REF_Ref259393516\r\h

[1]

：將數(shù)據(jù)場中上下相鄰兩層剖面的8個數(shù)據(jù)點(diǎn)組成一個體素，依次遍歷數(shù)據(jù)場中的體素，查找包含等值面的體素，即邊界體素，然后進(jìn)行等值面的抽取，形成最終的物體表面。

2.3.1確定體素中等值面的剖分方式

MC算法求取等值面與體素棱邊的交點(diǎn)是以數(shù)據(jù)場值沿棱邊連續(xù)線性變化為前提的。因此，如果體素的一個頂點(diǎn)的數(shù)據(jù)場值大于或等于預(yù)先設(shè)定的閥值，說明該點(diǎn)位于等值面之內(nèi)，標(biāo)記該點(diǎn)狀態(tài)值為“1”。反之，則說明該點(diǎn)位于等值面之外，標(biāo)記該點(diǎn)狀態(tài)值為“0”。在這兩個頂點(diǎn)所在的棱邊上有且僅有一點(diǎn)是等值面與該邊的交點(diǎn)。每個體素有8個頂點(diǎn)，對于每個頂點(diǎn)，它們都有0、1兩個狀態(tài)值。若按頂點(diǎn)標(biāo)志值的不同劃分體素，則共有種狀態(tài)。由于分別識別和處理256種情況將會是一個復(fù)雜而又容易出錯的過程。因此，MC算法根據(jù)互補(bǔ)對稱性和旋轉(zhuǎn)對稱性對這256種情況簡化成15種

REF_Ref259433419\r\h

[58]

。

（a）互補(bǔ)對稱性（b）旋轉(zhuǎn)對稱性

圖2-4對稱性對體素構(gòu)型種類的簡化

圖2-5體素中等值面的15種基本構(gòu)型

在實際應(yīng)用中，為了能夠構(gòu)造圖2-5中所示的MC等值面的基本構(gòu)型，需設(shè)計兩個長度為256的查找表。一個為邊查找表，用它來記錄所有情況下的等值面連接方式，即等值面與體素的哪些棱邊有交點(diǎn)的情況。另一個為三角形結(jié)構(gòu)查找表，它記錄著對應(yīng)邊查找表中的等值面交點(diǎn)的連接方式。體素每個頂點(diǎn)可代表一個狀態(tài)位，用一個字節(jié)來存儲一個體素8個頂點(diǎn)索引號，即通過索引可得到一個0~255之間的索引值，每一個值說明了等值面與體素棱邊的相交情況。

圖2-6體素中等值面剖面的確定過程

如圖2-6所示，分別表示體素8個頂點(diǎn)的狀態(tài)值，由它組成一個邊查找表的索引值cubeIndex，分別為體素的12條棱與等值面的相交情況狀態(tài)值，由它組成三角形結(jié)構(gòu)查找表的索引值triIndex。根據(jù)cubeIndex查找到對應(yīng)的triIndex，最終根據(jù)triIndex的索引內(nèi)容，即等值面接方式，確定體素中等值面的基本構(gòu)型。

2.3.2等值面與體素邊界的交點(diǎn)

對于當(dāng)前被處理體素的某一條棱邊，如果其兩頂點(diǎn)，的標(biāo)記值不同，那么等值面一定與此邊相交，且僅有一個交點(diǎn)，并可利用線性插值的方法來求取該交點(diǎn)。線性插值方法定義為：如果為體元的一條棱，，為的兩端點(diǎn)，，分別為，的場函數(shù)值，那么給定等值面值，棱上的插值點(diǎn)可用下面表達(dá)式來計算：

公式（2-8）

其中。

2.3.3等值面的法向計算

為了獲得真實感的等值面圖形，需要給圖形選擇適當(dāng)?shù)木植棵婀庹漳Ｐ瓦M(jìn)行光照計算，因而必須給出形成等值面的各三角面片的法向分量。由于等值面上的任意一點(diǎn)，其沿面的切線方向的梯度分量應(yīng)該是零，因此，該點(diǎn)的梯度矢量的方向也就代表了等值面在該點(diǎn)的法向

REF_Ref259433462\r\h

[59]

，MC算法就是利用這一原理獲得三角面片的法向向量。

設(shè)體數(shù)據(jù)規(guī)模為，點(diǎn)為三維數(shù)據(jù)場中的任意一點(diǎn)，的空間坐標(biāo)和數(shù)據(jù)值分別為、（，，）。計算點(diǎn)的梯度值，可首先采用中心差分法計算體素點(diǎn)處的梯度。即

公式（2-9）

公式中的，，分別為體素的棱長。通過公式求出后，需對進(jìn)行單位化，即，得出的即為點(diǎn)的法向量。

采用上述方法，依次計算出體素8個頂點(diǎn)法向量，并通過線性插值可以求得體素棱邊與等值面片的交點(diǎn)法向量：

公式（2-10）

上述公式中表示交點(diǎn)的法向量，,表示棱邊兩個端點(diǎn)的法向量，兩個端點(diǎn)的像素值用、表示，isovalue為該等值面的閥值。整個三角面片的法向量可由三角面片的三個頂點(diǎn)法向量的平均值來計算，即。

2.4其他建模技術(shù)

除了前面介紹的兩種主要表面建模技術(shù)外，還有其它一些物體表面建模技術(shù)，大致可分為曲面擬合、顯示重建、分段線性重建和基于人工神經(jīng)網(wǎng)絡(luò)的重建四大類

REF_Ref259433558\r\h

[60]

。每類方法都有其自己的特點(diǎn)和適用范圍。在實際應(yīng)用中，可以有選擇性地采用不同的方法來滿足實際要求。

曲面擬合方法又可分為B樣條曲面擬合、NURBS曲面擬合、細(xì)分曲面擬合和隱函數(shù)曲面擬合四種方法。其中B樣條曲面擬合適合于形狀復(fù)雜的曲面，NURBS曲面擬合適合于小規(guī)模數(shù)據(jù)集、拓?fù)浜唵蔚那?。對任意拓?fù)?、?fù)雜的光滑曲面宜采用光滑細(xì)分的曲面擬合方法，結(jié)果會比較理想。

2.5本章小結(jié)

本章研究了三維表面建模技術(shù)。本章首先介紹了基于輪廓線拼接的表面建模技術(shù)，并重點(diǎn)研究了該方法存在的難點(diǎn)問題，然后研究了基于體素級的建模方法，并重點(diǎn)介紹了標(biāo)準(zhǔn)MC算法，研究了MC算法的基本原理，最后還對其他建模技術(shù)進(jìn)行了簡單介紹。

碩士學(xué)位論文第三章基于MP的三維表面建模算法

第三章基于MP的三維表面建模算法

3.1MP算法概述

MC算法對于體數(shù)據(jù)而言是一種非常有效的等值面建模方法。在醫(yī)學(xué)方面，通過MC算法將核磁共振圖像（MRI）進(jìn)行表面建模，構(gòu)造出三維表面模型，指導(dǎo)醫(yī)生進(jìn)行手術(shù)，這大大提高了醫(yī)生的手術(shù)成功率。由2.1.2節(jié)可知，基于輪廓線的拼接算法存在著輪廓線對應(yīng)、分支和拼接等難題。如果剖面的間距比較小且能保持相互平行，同時兩對應(yīng)輪廓線能保持較高的重合程度且形狀相似，那么該算法基本能滿足實際需要。但是該算法在分支問題上只側(cè)重于解決一條輪廓線與多條輪廓線間的正確拼接問題，實際中卻往往不是這么單一的情況，造成這些算法對相鄰輪廓線的拼接存在很大缺陷，而MC算法能彌補(bǔ)基于輪廓線拼接算法中許多缺陷。為此，M.W.Jones

REF_Ref261172371\r\h

[27]

等人曾提出將多輪廓線間形體重建問題轉(zhuǎn)化為體數(shù)據(jù)中等值面構(gòu)造問題的思想，先后又有許多學(xué)者對該算法進(jìn)行了改進(jìn)

REF_Ref261175032\r\h

[28]

。

本章首先根據(jù)MC算法思想，提出一種新的基于輪廓線重建物體表面算法——移動棱臺算法。該算法能解決輪廓線的對應(yīng)和分支問題。同時，還能解決當(dāng)輪廓線重合度低時，MC算法重建表面失敗的問題。最后，本文對所提出的算法進(jìn)行了時間復(fù)雜度分析以及實驗效果對比。

3.2基本定義

定義3-1有序連接所有體素上下面棱邊上的等值點(diǎn)，所生成的連線稱為等值輪廓線。在上剖面的等值輪廓線稱為上等值輪廓線，下剖面的等值輪廓線稱為下等值輪廓線。

定義3-2剖面P上的等值輪廓線L與原輪廓線L’之間的吻合程度稱為逼近度，用Cd表示。L與L’的吻合程度越高，逼近度Cd也就越高，反之亦然。

定義3-3設(shè)兩相鄰剖面、，和上待重建輪廓線分別為C1和C2。將C1平行投影到上形成輪廓線C1’，C1’與C2交集的大小稱為重合度，用Cs表示。C1’與C2交集越大，Cs也越大，反之亦然。

3.3數(shù)據(jù)結(jié)構(gòu)

為了更好地表達(dá)MP算法，本文先介紹幾個基本的數(shù)據(jù)類型。它們是MP表面建模算法的數(shù)據(jù)基礎(chǔ)。

（1）CPoint類

CPoint類是整個程序中最基礎(chǔ)的類，后面的介紹的幾個類都是以這個類為基礎(chǔ)。該類對應(yīng)于三角形的頂點(diǎn)，基本屬性包括三維空間一點(diǎn)的x、y、z坐標(biāo)（雙精度浮點(diǎn)型），m_ID為頂點(diǎn)的索引號。我們還要建立一個動態(tài)數(shù)組m_points對網(wǎng)格的所有頂點(diǎn)進(jìn)行統(tǒng)一管理。類的具體形式如下：

classCPoint{

public:

……

//Attributes

doublem_dX;

doublem_dY;

doublem_dZ;

int m_ID;

};

typedefCArray<CPoint,&CPoint>CPointArray;

CPointArraym_points;

（2）CEdge類

CEdge類表示三角形的邊，其基本屬性包括線段兩個端點(diǎn)編號以及共用此邊的兩個三角形的索引號（如圖3-1（a）所示）。使用一個動態(tài)數(shù)組m_edges統(tǒng)一管理三角邊。其具體形式如下：

classCEdge{

public:

……

//Attributes

intm_startPointID;

intm_endPointID;

intm_adjTriaID[2];

intm_ID;

};

typedefCArray<CEdge,&CEdge>CEdgeArray;

CEdgeArraym_edges;

（3）CTriangle類

CTriangle類表示三角面片，它包含三角形的三個頂點(diǎn)的索引、三條邊的索引（三個頂點(diǎn)和邊以逆時針方式排列編號）、此三角形相鄰的三個三角形的索引（如圖3-1（a）所示）以及此三角形的序號和三角形的法向量，以動態(tài)數(shù)組m_triangles統(tǒng)一管理。具體形式如下：

classCTriangle{

public:

……

//Attributes

intm_pointIndex[3];

intm_edgeIndex[3];

intm_adjTriaID[3];

int m_ID;

doublem_norma[3];

};

typedefCArray<CTriangle,&CTriangle>CTriangleArray;

CTriangleArraym_triangles;

（4）CCube類

CCube類對應(yīng)MP算法所處理的體素單元，基本屬性包含了八個體素頂點(diǎn)索引。體素頂點(diǎn)類型由CCubePoint類定義，是CPoint類的子類，增加了頂點(diǎn)的權(quán)重值m_value

，當(dāng)前體素的前后左右上下的體素編號以及當(dāng)前體素單元的編號。當(dāng)前的體素有與等值面有交的狀態(tài)值m_hasFace，用動態(tài)數(shù)組m_meshArray來存儲所有的體素，具體形式如下：

classCCube{

public:

……

//Attributes

int m_cubePointID[8];

intm_ID;

intm_leftCubeID;

intm_rightCubeID;

intm_upCubeID;

intm_bottomCubeID;

int m_frontCubeID;

intm_backCubeID;

BOOLm_hasFace;

};

classCCubePoint:publicCPoint{

public:

……

//Attributes

doublem_value

;

};

typedefCArray<CCube,&CCube>CMeshArray;

CMeshArraym_meshArray;

（a）點(diǎn)、邊和三角形拓?fù)潢P(guān)系（b）體素之間拓?fù)潢P(guān)系

圖3-1點(diǎn)、邊、三角形和體素的拓?fù)潢P(guān)系

3.4MP算法基本原理

與MC算法類似，MP算法所處理的數(shù)據(jù)也是三維空間體數(shù)據(jù)。各種影像設(shè)備是體數(shù)據(jù)獲得的主要途徑，比如核磁共振、CT和超聲等影像數(shù)據(jù)。在地質(zhì)學(xué)中，地層體數(shù)據(jù)主要來源于自然或者人工爆炸產(chǎn)生的地震波，從而對地質(zhì)進(jìn)行結(jié)構(gòu)分析。

圖3-2MP算法實現(xiàn)輪廓線生成等值面的處理過程

本項目主要是通過對礦山剖面的編輯，圈出礦體輪廓線。礦體輪廓線并非是三維空間體數(shù)據(jù)，要采用MP算法實現(xiàn)基于輪廓線的物體表面建模，則需增加對輪廓線向體數(shù)據(jù)轉(zhuǎn)化的步驟。如圖3-2所示，MP算法實現(xiàn)物體表面建模主要有兩個關(guān)鍵步驟：（1）體數(shù)據(jù)的構(gòu)造；（2）等值面的生成。

3.4.1體數(shù)據(jù)的構(gòu)造

體數(shù)據(jù)是MP算法的基礎(chǔ)。算法首先將輪廓線所在的剖面統(tǒng)一定義為規(guī)模為Nx×Ny的二維網(wǎng)格，在與一系列平面相垂直的方向上定義一個Z軸后,每一個網(wǎng)格點(diǎn)可以被認(rèn)為是Nx×Ny×Nz空間的一個點(diǎn)，這里網(wǎng)格點(diǎn)取為像素點(diǎn)。體數(shù)據(jù)的構(gòu)造就是將每一個網(wǎng)格頂點(diǎn)的場函數(shù)值作為體素頂點(diǎn)的權(quán)值,形成規(guī)模為Nx×Ny×Nz的體數(shù)據(jù)

REF_Ref261175032\r\h

[28]

。

設(shè)一系列平面上的多條輪廓線及場函數(shù)，對與輪廓線所在平面上的每個網(wǎng)格點(diǎn)v，定義其場函數(shù)值符號為

REF_Ref259393516\r\h

[1]

：（1）如果點(diǎn)v在全部輪廓線之外，則函數(shù)值為負(fù)；（2）如果點(diǎn)v在某一條輪廓線上，則函數(shù)值為0；（3）如果點(diǎn)v在某一條輪廓線之內(nèi)，則函數(shù)值為正。場函數(shù)的選擇合理與否直接關(guān)系到體數(shù)據(jù)構(gòu)造的優(yōu)劣，優(yōu)良的場函數(shù)能消除明顯的突變現(xiàn)象。其中，歐式距離函數(shù)是常用的場函數(shù)。歐式距離函數(shù)定義如下：

公式（3-1）

其中是由點(diǎn)到同層剖面上所有輪廓線上點(diǎn)的最近距離。

雖然采用歐式距離函數(shù)作為場函數(shù)能消除明顯的突變現(xiàn)象，但由于體素頂點(diǎn)與輪廓線的關(guān)聯(lián)性不是很緊密，丟失了與輪廓線相關(guān)的大部分有用信息，例如輪廓線的精確軌跡以及走向，這樣使得等值輪廓線與原輪廓線存在著空隙，即逼近度Cd低。因此，需要首先對輪廓線進(jìn)行預(yù)處理。

1、輪廓線的預(yù)處理

假設(shè)待重建表面的輪廓線組均為封閉的輪廓線?，F(xiàn)計算第i層（）的輪廓線所在剖面上的每個網(wǎng)格點(diǎn)的狀態(tài)函數(shù)值。圖3-3（a）顯示了一個剖面網(wǎng)格化之后當(dāng)中的三個網(wǎng)格單元。其中，ABCD網(wǎng)格單元的四個頂點(diǎn)分別為A、B、C、D，線段EF為剖面上輪廓線的一段，A、C點(diǎn)輪廓線的外部，B、D點(diǎn)輪廓線的里面。根據(jù)公式（3-1）可知：每個網(wǎng)格點(diǎn)的狀態(tài)函數(shù)值就是網(wǎng)格點(diǎn)到當(dāng)前剖面上輪廓線上點(diǎn)的最短距離，因此，可以得出A、B點(diǎn)到點(diǎn)E以及C、D點(diǎn)到點(diǎn)F是最短的，設(shè)場函數(shù)值分別為、、、。

（a）等值輪廓線與原輪廓線出現(xiàn)的不吻合

（b）在整個剖面上出現(xiàn)逼近度Cd差的問題

圖3-3未對輪廓線上點(diǎn)插值時等值輪廓線的連線情況

在計算等值面與單元格邊界的交點(diǎn)時，本文采用線性插值法。如果P1、P2為要進(jìn)行線性插值的線段的兩端點(diǎn)，V1、V2分別為他們的場函數(shù)值，那么插值點(diǎn)P可用下面表達(dá)式來計算：

公式（3-2）

其中isovalue是等值面值，本文的等值面值設(shè)為0。理想狀態(tài)下，只有AB和CD邊計算出的等值點(diǎn)I、J分別落在點(diǎn)G和H上。這樣等值點(diǎn)的連線才能與輪廓線邊EF吻合。假設(shè)A、C點(diǎn)位于線段EF的外側(cè)，B、D點(diǎn)位于線段EF的內(nèi)側(cè)，此時需要滿足式（3-3）才能實現(xiàn)式（3-4）點(diǎn)與點(diǎn)重合，即

公式（3-3）

公式（3-4）

其中符號表示AE兩點(diǎn)間的歐式距離。

（a）對輪廓線點(diǎn)插值后的逼近度

（b）對輪廓線點(diǎn)插值后整個剖面上的吻合情況

圖3-4增加輪廓線上點(diǎn)后的等值輪廓線

在大多數(shù)實際情況下，由于體素頂點(diǎn)的權(quán)值不能很好的反映輪廓線的信息，因此公式（3-3）和公式（3-4）并不完全成立，這時計算得出的等值輪廓線與輪廓線重合度低，造成重建出的物體表面將會有很大的誤差（如圖3-3中邊所示）。如果能在線段EF上找到一點(diǎn)使其到A、B點(diǎn)的距離最短，且Q盡量接近點(diǎn)G，那么將在很大程度上減少這個誤差。如圖3-4所示，在線段EF中間適當(dāng)?shù)剡M(jìn)行點(diǎn)等距插值（圖中星號標(biāo)示），此時，點(diǎn)A、B、C、D到線段EF的最近點(diǎn)已經(jīng)逼近G和H。按照公式（3-4）計算得出的等值點(diǎn)I、J的連線IJ已經(jīng)與EF邊近似吻合，如果再增加插值點(diǎn)的個數(shù)，那么在容忍的誤差范圍內(nèi)，可以把邊與輪廓線段EF看作近似重合，即：。這樣在很大程度上提高了重建表面的質(zhì)量。

由以上分析，對輪廓線進(jìn)行預(yù)處理算法較簡單，主要步驟如下：

算法3.1對輪廓線進(jìn)行插值的算法——ContourAddPoints(contour,nx,ny,newContour)

輸入：輪廓線contour，網(wǎng)格規(guī)模nx×ny；

輸出：進(jìn)過對輪廓線進(jìn)行點(diǎn)加密后的新輪廓線newContour；

Step1根據(jù)剖面的長和寬以及網(wǎng)格規(guī)模大小nx×ny，計算出網(wǎng)格單元的長和寬值，并取較小的值作為閥值f，即f=min；

Step2取輪廓線contour的第i條線段li（，n為輪廓線上的線段數(shù)目）；

Step3計算的線段li的長度d，，判斷d與f的大小，若，轉(zhuǎn)Step2，否則轉(zhuǎn)Step4；

Step4在線段li上線性插入個點(diǎn)，若i<n，則轉(zhuǎn)Step2，否則轉(zhuǎn)Step5；

Step5算法結(jié)束。

對原輪廓線的點(diǎn)進(jìn)行插值提高了原輪廓線與等值輪廓線的逼近度，使得重建出的物體表面能更精確的接近原始物體真正形狀。但是，簡單地增加原輪廓線上的點(diǎn)，也不能使等值輪廓線無限地逼近。此外，歐式距離的計算是一個很耗時的過程，因此還需要對剖面進(jìn)行更進(jìn)一步處理。

2、外包棱臺的求取

輪廓線的預(yù)處理對于體數(shù)據(jù)的構(gòu)造有著非常重要的作用。它既能提高等值輪廓線的逼近程度，又能更好的反映原輪廓線的信息屬性。要構(gòu)造出逼近度更高的等值輪廓線，需要對網(wǎng)格規(guī)模進(jìn)行調(diào)整。網(wǎng)格規(guī)模的大小與圖像的分辨率相似，規(guī)模大則逼近度高些，反之亦然。在圖3-5（a）中網(wǎng)格規(guī)模大小為6×5，等值輪廓線與原輪廓線逼近度較低，圖3-5（b）中增大了網(wǎng)格規(guī)模至12×10，此時逼近度有了顯著的提高。

提高輪廓線上點(diǎn)的密度和增大網(wǎng)格規(guī)模都會增加網(wǎng)格頂點(diǎn)的場函數(shù)值的求解次數(shù)，影響表面重建速度。設(shè)網(wǎng)格規(guī)模為n1×n2，輪廓線總的點(diǎn)數(shù)目為n3，其中，，均大于0。根據(jù)公式（3-1）可知，求取每一個網(wǎng)格頂點(diǎn)權(quán)值需要對當(dāng)前剖面上輪廓線上的所有點(diǎn)進(jìn)行歐式距離計算，計算的次數(shù)為n1×n2，總計算次數(shù)為C1=n1×n2×n3，若提高網(wǎng)格規(guī)模為m1×m2，輪廓線進(jìn)行點(diǎn)的插值后個數(shù)為m3，總計算次數(shù)為C2=m1×m2×m3，其中m1>n1，m2>n2，m3>n3，則增加了C2-C1次場函數(shù)值的求解。由于計算各剖面的所有網(wǎng)格點(diǎn)的狀態(tài)函數(shù)值將會十分耗時，所以需減少網(wǎng)格點(diǎn)的計算以求得理想的重建速度。

（a）網(wǎng)格規(guī)模為6×5（b）網(wǎng)格規(guī)模為12×10

圖3-5網(wǎng)格規(guī)模與等值輪廓線逼近度

W.M.Jones采用等值面是否通過某體素的方法來判斷是否計算該體素頂點(diǎn)的距離函數(shù)值。這樣雖然節(jié)約了一些計算時間，但還是計算了許多冗余點(diǎn)

REF_Ref261172371\r\h

[27]

。紀(jì)鳳欣等

REF_Ref261175032\r\h

[28]

通過“連接表面投影區(qū)”比較兩相鄰剖面上對應(yīng)像素點(diǎn)的狀態(tài)值，以確定影響等值面生成的像素點(diǎn)。在像素點(diǎn)的距離函數(shù)計算過程中，只對有等值面生成有影響的像素點(diǎn)進(jìn)行距離函數(shù)計算，達(dá)到節(jié)約計算時間的目的。但是等值輪廓線與原輪廓線的逼近度Cd不高，且生成的物體表面精確度不高，在兩剖面上的輪廓線重合度Cs為空的極端情況下，無法實現(xiàn)表面重建。為此，本文采用相鄰輪廓線投影區(qū)域的集合運(yùn)算來提高重建表面的速度。

（a）投影在一個剖面上的輪廓線 （b）有效投影區(qū)域?qū)?yīng)的體表面

圖3-6相鄰剖面上的輪廓線區(qū)域R

如圖3-6（a）中所示，剖面Si+1上有兩條輪廓線Ci’與Ci+1，輪廓線Ci’為平面Si上的輪廓線Ci在Si+1平面上的投影（Si與Si+1為平行的剖面），現(xiàn)假設(shè)輪廓線Ci+1對重建表面有影響的區(qū)域為A，輪廓線Ci’對重建表面有影響的區(qū)域為B，則從圖3-6（b）中可以看出，需重建的物體表面在平面Si+1的投影正好位于有陰影的區(qū)域內(nèi)，因此，在計算網(wǎng)格點(diǎn)的場函數(shù)值時，可以忽略一些對表面重建無影響的網(wǎng)格點(diǎn)的場函數(shù)值計算。用R表示陰影部分，則R的范圍為A和B的并集結(jié)果再差上A和B的交集，用公式（3-5）表示為：

公式（3-5）

判斷剖面上網(wǎng)格點(diǎn)是否位于區(qū)域R內(nèi)，主要通過網(wǎng)格點(diǎn)與輪廓線內(nèi)外關(guān)系來求解。設(shè)當(dāng)前剖面上的所有網(wǎng)格頂點(diǎn)集為，輪廓線，，k、n分別為頂點(diǎn)數(shù)和兩相鄰剖面上的輪廓線數(shù)，為k個標(biāo)示位（），標(biāo)示每個頂點(diǎn)跟區(qū)域R的內(nèi)外關(guān)系，在輪廓線內(nèi)用1表示，否則用0表示。算法主要步驟描述如下：

算法3.2求取有效區(qū)域R的算法——GetEffectiveRegion(V,C,,)

輸入：網(wǎng)格點(diǎn)集，上剖面輪廓線，下剖面輪廓線；

輸出：頂點(diǎn)的權(quán)值；

Step1取當(dāng)前網(wǎng)格頂點(diǎn)（），判斷是否在任意一條輪廓線內(nèi)，若在，則，否則；

Step2判斷跟輪廓線組的關(guān)系，若位于的任意一條中，則將mi與1進(jìn)行異或，否則mi與0進(jìn)行異或，并將結(jié)果存入mi中；

Step3，若i<k，則轉(zhuǎn)Step1，否則轉(zhuǎn)Step4；

Step4算法結(jié)束。

根據(jù)mi的值，就可以省略mi值為0的網(wǎng)格點(diǎn)的場函數(shù)值計算，從而加快了體數(shù)據(jù)的構(gòu)造速度。

當(dāng)相鄰的兩剖面上的輪廓線投影到同一個剖面沒有公共部分時，即重合度，公式（3-5）的解，說明在三維空間上沒有具有影響體表面的有效區(qū)域。而實際上，這只是兩輪廓線錯開的程度很大所生成的錯誤結(jié)果。

現(xiàn)以圖3-7為例進(jìn)行說明，在圖3-7（a）中，p，q為兩相鄰剖面，v1、v2為剖面上的對應(yīng)網(wǎng)格點(diǎn)，即線段v1v2同時垂直于p，q剖面，剖面上的輪廓線c1和c2的重合度為0。根據(jù)公式（3-1）可知，剖面上每個網(wǎng)格頂點(diǎn)的場函數(shù)值僅跟各自剖面上的輪廓線位置有關(guān)，構(gòu)成體素一條棱的上下頂點(diǎn)，它們的場函數(shù)值不存在任何關(guān)聯(lián)性。將v1、v2同時沿著圖3-7（a）中豎截線左右移動，可以發(fā)現(xiàn)v1、v2的場函數(shù)值符號將不存在同時為正的情況。圖3-7（b）為采用MC算法重建表面的結(jié)果（縱截面圖），剖面p，q上的網(wǎng)格點(diǎn)場函數(shù)值如圖中數(shù)字標(biāo)示所示，上下剖面并沒有拼接起來，而是各自形成凸起的表面，導(dǎo)致表面拓?fù)浣Y(jié)構(gòu)不正確。

（a）重合度為空的兩輪廓線（b）一組體素頂點(diǎn)的場函數(shù)值分布（縱截圖）

圖3-7相鄰剖面輪廓線重合度低時的表面重建

導(dǎo)致上述問題的原因在于：如果為空，那么根據(jù)公式（3-1）的定義，體素的上下面8個頂點(diǎn)的場函數(shù)值都只可能異號。按照MC抽取等值面原則，等值點(diǎn)只可能落在體素上下對應(yīng)頂點(diǎn)之間，即體素的側(cè)棱上，使生成的上下表面成為互不連接單獨(dú)等值面（圖3-7（b））。重合區(qū)域越大，能連接上下面的體素個數(shù)越多，所重建出的表面越接近真實形態(tài)。由此可知，輪廓線重合度越高，重建的效果越好，反之越差。解決這類問題的常規(guī)方法就是在兩輪廓線之間插入中間輪廓線，使輪廓線合理過渡，但該方法增加了額外的操作負(fù)擔(dān)。

為克服上述問題的出現(xiàn)，本文采用外包棱臺來解決。本文先假定所有的剖面是相互平行且大小一致的矩形，輪廓線均位于對應(yīng)的剖面內(nèi)。外包棱臺是指對應(yīng)連接剖面上下輪廓線的矩形包圍盒頂點(diǎn)后得到的棱臺。外包棱臺確定了待重建輪廓線之間的對應(yīng)關(guān)系，它是MP算法的關(guān)鍵。如圖3-8所示，計算外包棱臺的主要步驟如下：

算法3.3計算外包棱臺的算法——GetPrismoid(P,S,B)

輸入：剖面上輪廓線的所有點(diǎn)集（n>0），兩相鄰剖面（）；

輸出：外包棱臺B的八個頂點(diǎn)ABCD；

Step1計算所有點(diǎn)集到剖面上邊的歐式距離，并找出最短與最長距離距離值minDis，masDis；

Step2將點(diǎn)集投影到上，得到投影點(diǎn)集，計算點(diǎn)集中兩點(diǎn)間的最大的距離值；

Step3以為長度，對邊分別平移minDis，masDis，得到AB、CD邊，連接兩邊得到包圍矩形盒ABCD；

Step4對另外一條輪廓線重復(fù)Step1—Step3操作步驟，得到另外一個包圍矩形盒EFGH，并有序連接ABCDEFGH形成外包棱臺；

Step5算法結(jié)束。

圖3-8（2）顯示的是將相鄰剖面、上的矩形包圍盒、進(jìn)行對應(yīng)頂點(diǎn)的連接，形成整個外包棱臺。

（a）剖面上棱臺四個頂點(diǎn)的求?。╞）整個外包棱臺

圖3-8相鄰剖面上輪廓線的外包棱臺

對于圖3-7中的情形，首先將輪廓線進(jìn)行外包棱臺的構(gòu)建，然后將外包棱臺網(wǎng)格化。如圖3-9（a）所示，C1為剖面P上輪廓線，其影響區(qū)域為A，C2為剖面Q上的輪廓線，影響區(qū)域為B。從圖3-9（b）中可知，棱臺的上下底是相鄰剖面上對應(yīng)輪廓線矩形包圍盒，強(qiáng)制性地使C1斜對應(yīng)于C2，使得A與B的交集。根據(jù)公式（3-5）可知，體表面有影響的區(qū)域，上下相鄰網(wǎng)格點(diǎn)的場函數(shù)值符號同為正的棱對數(shù)也一定不為0，則體素的上下面上將會有等值交點(diǎn)，因而可正確抽取出等值面。

（a）外包棱臺的構(gòu)建（b）一組體素頂點(diǎn)的場函數(shù)值分布（縱截圖）

圖3-9MP算法解決輪廓線重合度低的表面重建

外包棱臺進(jìn)行網(wǎng)格化的步驟相對簡單，只需將棱臺上下底面分別按給定的體數(shù)據(jù)規(guī)模進(jìn)行等距網(wǎng)格化分，并將對應(yīng)網(wǎng)格頂點(diǎn)組合成體素，最終構(gòu)造出規(guī)模為的體素組。采用外包棱臺構(gòu)造體素主要目的在于解決輪廓線重合度的問題。如圖3-10所示，圖中網(wǎng)格規(guī)模Nx×Ny×Nz為5×3×1。按體素的定義方式，將8個相鄰的網(wǎng)格點(diǎn)進(jìn)行組合形成一個棱臺。通過把外包棱臺細(xì)分，得到一系列的體素組。由圖中可知，得到的體素的15種基本構(gòu)型與MC算法的構(gòu)型略有不同。但每個體素的形態(tài)僅僅是上下矩形偏移或者是縮放，彼此能夠很好地對應(yīng)起來，故不影響體素中等值面生成。

圖3-10外包棱臺的網(wǎng)格化

根據(jù)算法3.1、3.2和3.3，可以得出構(gòu)造體數(shù)據(jù)的算法3.4。本文先假定輪廓線均不超出剖面上的區(qū)域范圍，且剖面是規(guī)則的平行矩形，并做如下變量說明：設(shè)一系列剖面Si（，n為總共的剖面數(shù)且大小一致），輪廓線組Cj（，m為總共的輪廓線數(shù)），vk為一個剖面上的網(wǎng)格點(diǎn)組，為剖面Si上的每個網(wǎng)格點(diǎn)是否位于有效區(qū)域R的標(biāo)示位，每個由Nx×Ny個標(biāo)志位組成。通過前面的闡述，得到構(gòu)造規(guī)模為Nx×Ny×Nz的體數(shù)據(jù)的算法，算法步驟如下：

算法3.4體數(shù)據(jù)構(gòu)造的算法——CreateVolumeData(sections,contours,volumeData)

輸入：剖面組sections，它由一系列剖面Si組成，contours為剖面上的輪廓線組，它由一系列輪廓線Ci組成；

輸出：體數(shù)據(jù)volumeData；

Step1根據(jù)算法3.3計算剖面Si與Si+1上的輪廓線Ci和Ci+1的外包棱臺BP；

Step2對外包棱臺BP進(jìn)行規(guī)模為Nx×Ny的網(wǎng)格化，取剖面Si和Si+1以及對應(yīng)剖面上的輪廓線Ci和Ci+1，根據(jù)算法3.1對輪廓線進(jìn)行點(diǎn)插值；

Step3按算法3.2進(jìn)行進(jìn)行有效區(qū)域計算，并將結(jié)果賦值給和；

Step4依次取Si和Si+1上的網(wǎng)格點(diǎn)vk（），判斷vk點(diǎn)對應(yīng)的標(biāo)志位，若標(biāo)示位為1，則按公式（3-1）計算vk的場函數(shù)值，否則不計算，直接賦值成浮點(diǎn)數(shù)的負(fù)最大值；

Step5，若，轉(zhuǎn)Step4，否則轉(zhuǎn)Step6；

Step6，若，轉(zhuǎn)Step1，否則轉(zhuǎn)Step7；

Step7將結(jié)果賦值給volumeData，算法結(jié)束。

3.4.2等值面的生成

假定預(yù)先給定的等值面閥值C0，等值面的生成就是根據(jù)兩相鄰頂點(diǎn)的場函數(shù)值生成等值點(diǎn)，然后將每個體元中的所有等值點(diǎn)按組合方式連接起來形成邊界多邊形，最后進(jìn)行三角化，生成數(shù)值為C0的等值面的過程。MP算法的等值面與體素棱邊交點(diǎn)求取原則是以數(shù)據(jù)場值沿棱邊連續(xù)線性變化為前提的。因此，如果體素的一個頂點(diǎn)的數(shù)據(jù)場值大于或等于給定的預(yù)先設(shè)定的閥值，說明該點(diǎn)位于等值面之內(nèi)，標(biāo)記該點(diǎn)狀態(tài)值為“1”。反之，則說明該點(diǎn)位于等值面之外，標(biāo)記該點(diǎn)狀態(tài)值為“0”。這兩個頂點(diǎn)所在的棱邊之間有且僅有一個等值面與該邊的交點(diǎn)。根據(jù)上述的分類規(guī)則和體素頂點(diǎn)的數(shù)據(jù)場值，可對體素的8個頂點(diǎn)進(jìn)行分類，最終確定等值面的剖分方式。

每個體素有8個頂點(diǎn)，對于每個頂點(diǎn)，它們都有0、1兩個狀態(tài)值。若按頂點(diǎn)標(biāo)志值的不同劃分體素，則共有種狀態(tài)。類似于MC算法，對256種不同的情況分別進(jìn)行識別和處理雖然可以實現(xiàn)，但會是一個復(fù)雜而又容易出錯的過程。所以需要采用旋轉(zhuǎn)對稱性和互補(bǔ)對稱性將256種情況進(jìn)行簡化，最終得出15種等值面抽取情況。由于15種基本構(gòu)型跟MC算法相似（圖2-5），在此不再介紹。

（a）體素頂點(diǎn)的場函數(shù)值計算（b）體素中等值面的抽取

圖3-11體數(shù)據(jù)的構(gòu)造與等值面的抽取

圖3-11（b）為外包棱臺中網(wǎng)格化后一個的小棱臺，網(wǎng)格點(diǎn)v0、v2在輪廓線內(nèi)，場函數(shù)值為正，、在輪廓線外，場函數(shù)值為負(fù)，所以在棱v0v3、v2v3、v4v7和v6v7上分別有等值點(diǎn)，根據(jù)MC算法的等值點(diǎn)連接方式生成等值面。

假設(shè)體素頂點(diǎn)的函數(shù)值沿體素棱邊是線性變化的，可以線性插值方法求出等值面與棱邊的等值點(diǎn)值。將這些交點(diǎn)連接起來，構(gòu)成等值多邊形。按照類似于MC算法的15種基本構(gòu)型，將等值多邊形進(jìn)行三角剖分，生成最終的三角片。

為了獲得更具有真實感的等值面圖形，圖形需要選擇適當(dāng)?shù)木植棵婀庹漳Ｐ瓦M(jìn)行光照計算。但是，光照計算又需要計算等值面片的三角面片的法向量。MP算法跟MC算法中的等值面的法向計算過程相同，利用公式（2-9）和（2-10）可求出三角片的法向量，實現(xiàn)真實的等值面繪制。

3.4.3MP算法抽取等值面的算法流程

根據(jù)前面對MP算法的介紹，MP進(jìn)行表面建模的步驟如下：

Step1將剖面和輪廓線數(shù)據(jù)讀入內(nèi)存；

Step2讀取兩層剖面和剖面上的輪廓線數(shù)據(jù)，計算外包棱臺，并將外包棱臺進(jìn)行網(wǎng)格化，生成體素；

Step3根據(jù)網(wǎng)格規(guī)模，對輪廓線進(jìn)行預(yù)處理，并進(jìn)行體素頂點(diǎn)場函數(shù)值的計算；

Step4將體素每個頂點(diǎn)的函數(shù)值與給定的等值面值做比較，根據(jù)比較結(jié)果，得到該體素的MC邊查找表的索引值；

Step5采用MC邊查找表，查找對應(yīng)的體素等值面連接方式；

Step6通過線性插值方法，計算出邊界體素的棱與等值面的交點(diǎn)；

Step7利用公式（2-9）求出體素各頂點(diǎn)處的法向，再利用公式（2-10）求出三角形各頂點(diǎn)處的法向；

Step8根據(jù)各三角面片各頂點(diǎn)的坐標(biāo)值及法向量繪制局部等值面圖象；

Step9檢測所有體素是否全部處理完畢，如否，則進(jìn)行到下一個體素，轉(zhuǎn)到Step2步處理；

Step10算法結(jié)束。

3.5MP算法的優(yōu)缺點(diǎn)

MP算法解決了基于輪廓線拼接以及MC算法實現(xiàn)輪廓線重建中一系列問題。當(dāng)然，MP算法同時存在著自己的缺陷，主要?dú)w納如下：

1、解決了基于輪廓線拼接的分支和對應(yīng)問題

輪廓線的對應(yīng)和輪廓線分支一直是基于輪廓線拼接算法的兩大問題，MP算法有效地避開了這兩大問題，省去了人工干預(yù)，取得了比較好的結(jié)果。同時，MP算法重建的表面形態(tài)要比基于輪廓線拼接的形態(tài)更為理想。

2、克服了輪廓線重合度低的建模問題

MP算法克服了MC算法中輪廓線重合度低和空時的表面建模問題。傳統(tǒng)的方法通過在待重建的輪廓線之間插入中間輪廓線的方法來解決這個問題。該方法在解決輪廓線重合度低的問題上能起到一定的效果，但給用戶帶來額外的負(fù)擔(dān)，特別是當(dāng)輪廓線密集時，額外的工作量會使用戶難以接受。同時，要使兩剖面之間的輪廓線能順利地自然過渡，插入中間輪廓線的方法還存在著一定的難度。

3、降低了等值輪廓線與原輪廓線間的逼近誤差

MP算法從增加輪廓線上點(diǎn)的數(shù)目和提高網(wǎng)格規(guī)模大小兩個方面來提高輪廓線的逼近度，起到了很好的效果。同時為了防止表面建模的計算量隨著網(wǎng)格規(guī)模和輪廓線點(diǎn)數(shù)目的增加而上升，MP算法采用了輪廓線投影有效區(qū)域策略來減少場函數(shù)值的計算量，節(jié)約了表面建模時間。

4、MP算法無法適用于開曲線的建模

由于MP算法是基于體數(shù)據(jù)的表面建模方法，所以在對輪廓線進(jìn)行表面建模時需要加入體數(shù)據(jù)的構(gòu)造過程。而體數(shù)據(jù)是通過閉合輪廓線來構(gòu)造的，使得MP算法只適合于閉合輪廓線的表面建模。

3.6算法分析與實驗效果

為分析算法的時間復(fù)雜度，本文先作如下假設(shè)：網(wǎng)格規(guī)模大小為，兩剖面的輪廓線條數(shù)分別為、，每條輪廓線的平均頂點(diǎn)數(shù)為，其中、、、、均大于0。

1、MP算法的時間復(fù)雜度

算法整個計算時間主要與體數(shù)據(jù)的構(gòu)造、等值面的生成相關(guān)。體數(shù)據(jù)的構(gòu)造又分為外包棱臺的求取、輪廓線的預(yù)處理以及輪廓線投影有效區(qū)域的計算三部分。而等值面的生成由邊查找表的查詢、面查找表的查詢兩部分組成。

本文首先在計算外包棱臺時，計算量主要集中在對當(dāng)前剖面上的輪廓線點(diǎn)集到剖面一條邊的投影以及距離值的計算，總需計算的次數(shù)為，由于，，因此算法的復(fù)雜度為線性時間復(fù)雜度。輪廓線預(yù)處理環(huán)節(jié)中，只需對每條輪廓線的每條邊進(jìn)行插值，總次數(shù)為，所以時間復(fù)雜度也為。在有效區(qū)域的求取中，對每個網(wǎng)格點(diǎn)需要對兩剖面上的所有輪廓線進(jìn)行內(nèi)外關(guān)系判斷，判斷一次的時間復(fù)雜度為，總計算次數(shù)為，由于，，所以時間復(fù)雜度為，又因為

所以算法的時間復(fù)雜度近似為，其中。綜合以上各步驟，體數(shù)據(jù)的構(gòu)造的總的算法時間復(fù)雜性近似為：

等值面的生成主要是依次對每個體素進(jìn)行等值面的抽取，包括對邊查找表和面查找表的操作，計算總次數(shù)為，由于邊查找表和面查找表操作的時間復(fù)雜度為線性時間復(fù)雜度，所以時間復(fù)雜度為。

綜上分析，MP算法的總的時間復(fù)雜度近似為，其中。

2、算法實驗效果

本文通過實驗對算法進(jìn)行了仿真和驗證，試驗硬件平臺為一臺主頻為3.0G的雙核PC，1G內(nèi)存，軟件開發(fā)環(huán)境為WindowsXP操作系統(tǒng)，VisualC++7.0，顯示處理庫OpenGL，C0取值為0。

（1）分支和對應(yīng)問題的實驗效果

本章提出的MP算法具有解決輪廓線對應(yīng)問題和分支問題方面的優(yōu)點(diǎn)，還能處理每層輪廓線含有多條閉合輪廓線的情況，不需要人工干預(yù)，自動完成拼接。在圖3-12中，分別采用文獻(xiàn)

REF_Ref259433558\r\h

[60]

中的人工手動分支的輪廓線拼接方法和MP算法進(jìn)行了表面重建。（a）、（c）顯示了采用文獻(xiàn)

REF_Ref259433558\r\h

[60]

中的手動分支的輪廓線拼接方法重建的表面效果，（b）、（d）為采用MP算法的重建效果。由圖可知，（b）、（d）圖重建的表面形態(tài)顯然要優(yōu)于（a）、（c），且無需進(jìn)行手動分支操作。

（a）手動分支重建結(jié)果（b）MP算法重建結(jié)果

（c）手動分支重建的結(jié)果（d）MP算法重建結(jié)果

圖3-12對有分支問題和對應(yīng)問題的輪廓線重建效果

（2）輪廓線重合度和逼近精度的實驗效果

圖3-13中顯示了兩種不同情況的輪廓線，圖3-13（a）中是兩條規(guī)則輪廓線且它們的輪廓線重合度為空，圖3-14（b）中的輪廓線重合度為空，同時它們的形態(tài)差異比較大。圖3-14（a）為采用MC算法重建的表面效果，結(jié)果為兩個凸的表面。采用MP算法解決了重合度為空時的重建問題（如圖3-14（b）所示）。圖3-15（a）是MP算法對圖3-13（b）中輪廓線重建的線框模型，圖3-15（b）為采用光照渲染后的實驗效果。

（a）重合度為空的兩輪廓線（b）形狀差異很大的兩輪廓線

圖3-13兩種不同形態(tài)的輪廓線

（a）MC算法重建結(jié)果（b）MP算法重建結(jié)果

圖3-14輪廓線重合度為0時MP算法與MC算法重建表面效果對比

（a）MP算法重建的線框模型（b）MP算法重建的表面模型

圖3-15輪廓線重合度不高且形態(tài)差異很大時MP算法重建表面效果

從結(jié)果中可以看出，MP算法能較好的解決輪廓線重合度不高時的重建問題，彌補(bǔ)了需插入中間輪廓線才能完成表面重建的缺陷。同時，當(dāng)兩輪廓線形態(tài)差異大時，重建的表面形態(tài)也較理想。

（3）實際數(shù)據(jù)的實驗效果與分析

通過某礦體剖面數(shù)據(jù)進(jìn)行實驗對算法進(jìn)行了效率分析，建立礦體模型如圖3-16所示。

（a）某礦體實際建?？梢暬Ч╞）帶分支的礦體輪廓線可視化效果

圖3-16MP算法實際數(shù)據(jù)試驗結(jié)果

表3-1給出了網(wǎng)格規(guī)模和輪廓線條數(shù)兩方面因素對MP算法的影響，并對實驗數(shù)據(jù)進(jìn)行了統(tǒng)計。

表3-1MP算法對不同網(wǎng)格規(guī)模和輪廓線條數(shù)的性能測試

圖號

網(wǎng)格規(guī)模

輪廓線條數(shù)

三角面片數(shù)

時間消耗（s）

平均每層時間（s）

圖3-16（a）

圖3-16（a）

圖3-16（b）

圖3-16（b）

30×30

40×40

30×30

40×40

21

21

4

4

8294

12876

1324

2080

2.611

4.464

0.204

0.343

0.13055

0.2232

0.102

0.1715

從表中可知，MP算法運(yùn)算效率比較高，同時重建的表面效果比較理想。但是隨著網(wǎng)格規(guī)模的增加，算法所耗費(fèi)的時間也隨之增加。因此，在實際應(yīng)用中可以根據(jù)具體應(yīng)用需求對算法的網(wǎng)格規(guī)模進(jìn)行合理設(shè)置，使MP算法在速度和繪制質(zhì)量上都能獲得一個較優(yōu)的結(jié)果。從表中還可以得出，MP算法重建的物體表面存在著三角面片過多的情況，隨著網(wǎng)格規(guī)模的增大，三角面片數(shù)量呈上升的趨勢。該問題將導(dǎo)致表面模型占用較多的存儲空間，影響數(shù)據(jù)的實時顯示。

3.7本章小結(jié)

本章根據(jù)MC算法原理提出了MP表面建模算法。MP算法具有MC算法的優(yōu)點(diǎn)，能成功解決基于輪廓線拼接中所出現(xiàn)的分支和對應(yīng)問題，分析了MC算法在實現(xiàn)輪廓線的表面建模中所出現(xiàn)的輪廓線重合度問題，并通過構(gòu)造外包棱臺模型、計算輪廓線投影有效區(qū)域、增大輪廓線點(diǎn)數(shù)目和網(wǎng)格規(guī)模等方法來解決該問題。最后本章對MP算法進(jìn)行了復(fù)雜度分析和實驗驗證，得出了較合理的結(jié)果。

碩士學(xué)位論文第四章分類處理輪廓線的漸近