多輪廓線的三維形體重構(gòu)技術(shù)研究與實(shí)現(xiàn)*

劉坤良，黃金明

(1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387;2.中國(guó)地質(zhì)調(diào)查局發(fā)展研究中心，北京 100037)

多輪廓線的三維形體重構(gòu)技術(shù)研究與實(shí)現(xiàn)*

劉坤良1，黃金明2

(1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387;2.中國(guó)地質(zhì)調(diào)查局發(fā)展研究中心，北京 100037)

實(shí)際應(yīng)用中，三維重構(gòu)經(jīng)常面對(duì)的不是直接的體數(shù)據(jù)信息，而是一序列的二維輪廓線數(shù)據(jù)，因此基于輪廓線的三維重構(gòu)研究有著極其重要的實(shí)用價(jià)值。在多輪廓線的三維形體重構(gòu)中，輪廓對(duì)應(yīng)、輪廓拼接、分叉處理和末端輪廓線的封閉處理等是其關(guān)鍵技術(shù)。提出了三維重構(gòu)中每一個(gè)實(shí)現(xiàn)步驟具體的解決方案。針對(duì)輪廓線繞向問(wèn)題提出了夾角和檢測(cè)法，有效避免了輪廓多邊形的繞向誤判；對(duì)輪廓線一對(duì)多分叉問(wèn)題提出了按周長(zhǎng)比率解決問(wèn)題的思路；在末端輪廓線的三角剖分算法中提出了最大張角三角形方法，減少了三角剖分的計(jì)算量，達(dá)到了在各種形態(tài)輪廓線條件下能夠?qū)崿F(xiàn)正確的拼接。實(shí)現(xiàn)結(jié)果表明，輪廓線拼接過(guò)程中每個(gè)步驟的解決方法是正確有效的，相較于其他實(shí)現(xiàn)方法通用性更強(qiáng)。

輪廓線；三維重構(gòu)；Delaunay三角剖分；凸包

1 引言

在實(shí)際應(yīng)用中，我們可能常常面對(duì)的不是直接的體數(shù)據(jù)信息，而是一序列的二維輪廓線數(shù)據(jù)。從一組有序的平面輪廓線重建三維形體是一個(gè)具有普遍意義的研究課題, 在醫(yī)學(xué)、地質(zhì)、生物等領(lǐng)域有著非常廣泛的應(yīng)用。例如，在醫(yī)學(xué)數(shù)據(jù)的可視化中，如果CT或者M(jìn)RI圖像兩層切片之間的距離遠(yuǎn)遠(yuǎn)大于圖像的分辨率，也就是Z方向的采樣十分稀疏，這時(shí)需要在每層圖像上就感興趣的區(qū)域勾畫(huà)出輪廓線，并由一序列的二維輪廓線重構(gòu)出由面模型表示的三維形體。又如，在醫(yī)學(xué)圖像的三維數(shù)據(jù)場(chǎng)可視化中，盡管相鄰斷層圖像之間的距離很小，但是目前的物質(zhì)分類(lèi)技術(shù)尚不能將共存的多種不同物質(zhì)加以分類(lèi)，需要人工干預(yù)，由醫(yī)學(xué)專(zhuān)家手工勾劃出感興趣的區(qū)域，如在醫(yī)學(xué)的治療系統(tǒng)中，為了保證治療的準(zhǔn)確性和可靠性，先勾畫(huà)出器官(血管、神經(jīng)等)的輪廓線，再由這些輪廓線重建組織表面。如此，由器官輪廓線重建的組織表面可以極大限度地輔助醫(yī)學(xué)診斷，為擬定最佳手術(shù)方案提供可靠的依據(jù)，從而提高手術(shù)質(zhì)量，減少醫(yī)療事故[1]。因此，基于以上實(shí)際應(yīng)用的需要，對(duì)三維重構(gòu)的研究有著及其重要的實(shí)用價(jià)值。

基于輪廓線的三維形體重構(gòu)需要解決輪廓線質(zhì)心計(jì)算、輪廓線繞向調(diào)整、輪廓線對(duì)應(yīng)、輪廓線拼接、輪廓線分叉以及末端輪廓線的封堵等相關(guān)問(wèn)題。李運(yùn)鋒等[2]提出的基于方向包圍盒投影轉(zhuǎn)換的輪廓線拼接方案，首先判斷多邊形的頂點(diǎn)凹凸性，對(duì)于凹頂點(diǎn)，將其轉(zhuǎn)換到對(duì)應(yīng)的凸包上；然后計(jì)算凸包的方向包圍盒，旋轉(zhuǎn)平移矩形包圍盒，并求包圍盒內(nèi)接橢圓，將每個(gè)頂點(diǎn)都按比例投影此橢圓上；基于投影后的點(diǎn)進(jìn)行輪廓線拼接，尋找相鄰輪廓線頂點(diǎn)之間的對(duì)應(yīng)關(guān)系；最后還原實(shí)際坐標(biāo)，進(jìn)行原始模型的三維重構(gòu)。該方案較之最短對(duì)角線方法，能比較好地解決最短對(duì)角線方法中出現(xiàn)拼接交叉的現(xiàn)象，但是由于該方案沒(méi)有考慮輪廓線中心對(duì)齊問(wèn)題以及輪廓線的尺寸變化，在一定情況下，也會(huì)發(fā)生扭曲現(xiàn)象，甚至投影轉(zhuǎn)換后的模型，較投影之前，模型效果會(huì)更差，而且該方案也沒(méi)解決輪廓線的分支問(wèn)題。毛先成等[3]提出的復(fù)雜輪廓線三角面片的重構(gòu)算法，雖然考慮了中心對(duì)齊以及輪廓線的尺寸變化，并提出了輪廓線分支的解決方案，但是，其處理分支問(wèn)題時(shí)需要人工干預(yù)，降低了算法的自動(dòng)性而且其沒(méi)有處理末端輪廓線的封堵問(wèn)題，在輪廓線末端出現(xiàn)空洞，使拼接結(jié)果不能形成封閉曲面。目前相關(guān)論文實(shí)現(xiàn)的輪廓線拼接方案，重點(diǎn)實(shí)現(xiàn)了輪廓線拼接過(guò)程中的某幾個(gè)步驟，解決其中的幾個(gè)問(wèn)題，在其解決方案所面對(duì)的具體問(wèn)題上能得到正確的解，但適用范圍有限，通用性不強(qiáng)。

本文從輪廓線重構(gòu)所需解決的問(wèn)題出發(fā)，有效地解決了輪廓線拼接過(guò)程中出現(xiàn)的拼接交叉問(wèn)題，實(shí)現(xiàn)了分支輪廓的自動(dòng)處理以及末端輪廓線的封堵，多輪廓線的拼接結(jié)果滿足工程需求。

2 輪廓線的預(yù)處理

對(duì)于中心點(diǎn)對(duì)齊、形狀相近、繞向一致的相鄰輪廓線，拼接結(jié)果一般不會(huì)出錯(cuò)。實(shí)際上，三維形體重構(gòu)的輪廓線形態(tài)各異，為了提高重構(gòu)的效果，避免錯(cuò)誤的連接，有必要在輪廓線拼接之前進(jìn)行輪廓線的處理。

2.1 輪廓線中心點(diǎn)對(duì)齊及尺寸調(diào)整

相鄰輪廓線的形狀和中心位置可能相差較大，必須通過(guò)坐標(biāo)的平移和放縮，使相鄰輪廓線轉(zhuǎn)換成中心點(diǎn)重合、大小比例一致的輪廓線，才能正確地拼接處理[4]，否則會(huì)產(chǎn)生錐體現(xiàn)象，如圖1所示。

Figure 1 Incorrect splicing resulting in cones

假設(shè)相鄰兩輪廓線分別為Contour1和Contour2，其包圍矩形的中心點(diǎn)坐標(biāo)分別為center1(x1,y1)和center2(x2,y2),寬和高分別為(width1,height1)和(width2,height2)，其中PanFactor和ZoomFactor分別表示輪廓線的平移距離和放縮因子，則有如下等式成立：

(1)

輪廓線Contour1各頂點(diǎn)坐標(biāo)保持不變，Contour2各頂點(diǎn)的坐標(biāo)作如下調(diào)整：

(2)

2.2 輪廓線繞向一致性調(diào)整

對(duì)于相鄰的輪廓線在位置和尺寸調(diào)整以后，還需要判斷輪廓線的繞向，如果輪廓線繞向不一致，要對(duì)其中一個(gè)輪廓線進(jìn)行逆序處理。這些判斷和處理是計(jì)算機(jī)圖形學(xué)、模式識(shí)別、CAD等領(lǐng)域經(jīng)常碰到的問(wèn)題。大多數(shù)情況下，需要計(jì)算輪廓線的法向量，如果相鄰輪廓線的法向量不一致，則輪廓線繞向不同，從而對(duì)其中一輪廓線進(jìn)行繞向反向處理，這可以通過(guò)使輪廓線上控制點(diǎn)的順序逆序來(lái)實(shí)現(xiàn)。由于輪廓線形態(tài)各異，輪廓線所形成的多邊形有可能是凸多邊形也可能是凹多邊形，簡(jiǎn)單地計(jì)算輪廓線的法向量適用于凸多邊形，當(dāng)輪廓線是凹多邊形時(shí)可能會(huì)得到錯(cuò)誤的結(jié)果，其中一種解決辦法是首先把凹多邊形投影到其凸包上，然后計(jì)算其凸包的法向量，但這種方法增加了計(jì)算量。

本文采用夾角之和檢測(cè)法檢測(cè)輪廓線多邊形的繞向問(wèn)題，該方法對(duì)各種形態(tài)的輪廓線都能得到正確的結(jié)果，不需要計(jì)算凹多邊形的凸包。輪廓線多邊形的所有邊均可看作有向邊，邊的方向與頂點(diǎn)的串連方向相一致。計(jì)算多邊形每一條邊與下一條邊所形成的旋轉(zhuǎn)角度之和，如果相鄰兩輪廓線的所有邊形成的角度之和的值符號(hào)一致，那么它們繞向一致，否則繞向不一致。首先要確保輪廓線所在平面的法線向量方向一致，分別計(jì)算多邊形前后兩條邊的叉乘和點(diǎn)乘，根據(jù)點(diǎn)乘結(jié)果可以得到兩邊的夾角，根據(jù)邊叉乘后的向量與輪廓線所在平面的法向量比較結(jié)果取夾角值的符號(hào)，如果方向相同，夾角取正值，否則取負(fù)值，如圖2所示。不管是凸多邊形還是凹多邊形，所有邊形成的角度累積和或者接近2π或者接近-2π。其對(duì)應(yīng)公式如下：

(3)

其中,Mi為兩條邊點(diǎn)乘結(jié)果，Ni為兩條邊叉乘矢量，Nface為輪廓線所在平面法向量。當(dāng)Ni與輪廓線所在平面的法線Nface同向時(shí)Angle(i)取正，否則取負(fù)。0≤i

Figure 2 Calculate deflection angles sum

2.3 輪廓線凸包計(jì)算及坐標(biāo)到凸包的投影轉(zhuǎn)換

對(duì)于凸輪廓線,可以采用輪廓線拼接技術(shù)直接拼接，而對(duì)于凹輪廓線，要先求其凸包，然后將凹頂點(diǎn)投影到其所在的凸包上。在礦體圈定的連接面積或者地層剖面中，輪廓線多邊形通常都是凹多邊形，因此必須進(jìn)行凹多邊形的凸化處理。

凸包是物體形狀描述、特征抽取的一個(gè)重要工具，已被廣泛地應(yīng)用于模式識(shí)別、圖像處理等研究領(lǐng)域。凸包的定義很簡(jiǎn)單，對(duì)于平面上的任意一個(gè)點(diǎn)集S，或者一個(gè)多邊形P，其凸包是指包含S或P的最小的凸多邊形[5]。

本文設(shè)計(jì)實(shí)現(xiàn)了輪廓線多邊形的凸化處理算法，偽代碼如下：

voidCalConvexHull(V,n,S)

input:輪廓線頂點(diǎn)集合V，頂點(diǎn)個(gè)數(shù)n

output:輪廓線的凸包所包含的所有點(diǎn)集S

{

InitStack(S);

Push(S,v0);Push(S,v1);

k=2;

a=v0;b=v1;c=vk;

while(k!=1){

while(ConvexDeg(a,b,c)≤0&&(Top≥1)){

Pop(S);

}

a=S[Top]在V中的前驅(qū)頂點(diǎn);

b=S[Top];

c=S[Top]在V中的后續(xù)頂點(diǎn);

while(ConvexDeg(a,b,c)<0&&(Top≥1)){

V=V-vk;

k=(k+1)%n;

a=S[Top-1];b=S[Top];c=vk;

while(ConvexDeg(a,b,c)>0){

V=V-vk;

k=(k+1)%n;

c=vk;

}

Pop(S);

}

Push(S,vk);

}

a=S[Top-1];b=S[Top];c=v1;

if(ConvexDeg(a,b,c)<0)

Pop(S);

a=S[Top];b=S[1];c=S[2];

if(ConvexDeg(a,b,c)<0&&S[1]為V的第1個(gè)頂點(diǎn))

for(i=1;i

s[i]=s[i+1];

}

Pop(S);

}

計(jì)算出凹輪廓線的凸包以后，對(duì)于輪廓線上的凹點(diǎn)，通過(guò)投影到最近的兩個(gè)凸點(diǎn)的線段上，從而實(shí)現(xiàn)將一個(gè)任意形狀的輪廓線映射為一個(gè)凸輪廓線。投影方式可以選擇按比例投影或者垂直投影，由于垂直投影，投影后存在線段折回的現(xiàn)象，故本文中根據(jù)凹點(diǎn)到前一凸點(diǎn)的距離相對(duì)前后兩個(gè)凸點(diǎn)在輪廓線上的距離之和的比值，選擇按長(zhǎng)度比例投影。該投影方法相較于垂直投影避免了線段折回造成的拼接交叉問(wèn)題。

3 輪廓線的拼接

假設(shè)兩相鄰平行平面上各有一輪廓線，上輪廓線上的點(diǎn)列為p0,p1,…,pm-1，pm(其中pm與p0為同一點(diǎn))，下輪廓線上的點(diǎn)列為q0,q1,…,qn-1,qn(其中q0與qn為同一點(diǎn))，點(diǎn)列均按逆時(shí)針?lè)较蚺帕?。每一個(gè)線段pipi+1或qiqi+1稱(chēng)為輪廓線線段。用一條輪廓線線段的兩端點(diǎn)與相鄰輪廓線上的一點(diǎn)相連接，可以構(gòu)成一個(gè)三角面片，如圖3所示。

Figure 3 Connecting control points

連接上輪廓線中的一點(diǎn)與下輪廓線中的一點(diǎn)的線段稱(chēng)為跨距。很顯然，一條輪廓線線段，以及將該線段兩端點(diǎn)與相鄰輪廓線上的一點(diǎn)相連的兩段跨距構(gòu)成了一個(gè)三角面片，稱(chēng)為基本三角面片。而該兩段跨距則分別稱(chēng)為左跨距和右跨距。實(shí)現(xiàn)兩條凸輪廓線之間的三維形體重構(gòu)就是要用一系列相互連接的三角面片將上、下兩條輪廓線連接起來(lái)。但是，怎樣保證連接起來(lái)的三維形體是合理的且具有良好的性質(zhì)是需要認(rèn)真研究的問(wèn)題。連接上、下兩條輪廓線上各點(diǎn)所形成的眾多基本三角面片，應(yīng)該構(gòu)成相互連接的三維形體表面，而且相互之間不能在三角面片的內(nèi)部相交。因此，只有同時(shí)滿足下列兩個(gè)條件的三角面片集合才是合理的:

(1) 一個(gè)輪廓線線段必須在而且只能在一個(gè)基本三角面片中出現(xiàn)。因此，如果上、下兩層輪廓線各有m和n條輪廓線線段，那么，合理的三維形體表將包含m+n個(gè)基本三角面片。

(2) 若一個(gè)跨距在某一基本三角面片中為左跨距，則該跨距必須是而且僅是另一個(gè)基本三角面片的右跨距。

將符合上述條件的三角面片集合稱(chēng)為可接受的形體表面。對(duì)于相鄰兩條輪廓線及其上的點(diǎn)列而言，符合上述條件的可接受的形體表面可以有多種不同的組合。在如此眾多的可接受表面的組合中，為了確定所需要的一種組合，許多學(xué)者都通過(guò)制定不同的優(yōu)化目標(biāo)函數(shù)，提出了不同的優(yōu)化方法。例如：FuchS H提出的表面面積最小法；Kepple E提出的體積最大法；Ehristiansen提出的最短對(duì)角線法；Ganapathy提出的相鄰輪廓線同步前進(jìn)法等[6]。其中，最大體積法、最短對(duì)角線法和相鄰輪廓線同步前進(jìn)法都屬于啟發(fā)式算法。表面面積最小法和體積最大法都屬于全局最優(yōu)的表面重構(gòu)方法，計(jì)算量較大且較費(fèi)時(shí)；而最短對(duì)角線法和相鄰輪廓線同步前進(jìn)法是屬于局部最優(yōu)的判定方法，計(jì)算量較小，可以提高計(jì)算速度。最短對(duì)角線法適用于上下輪廓線大小和形狀相近，對(duì)中情況比較好的情況。該方法就是在四邊形p1p2q1q2中的兩條對(duì)角線p1q2和p2q1中選擇較短的一條作為下一三角面片的邊，生成三角面片，如圖4所示。相鄰輪廓線經(jīng)過(guò)預(yù)處理后，大小、形狀比較接近，對(duì)中情況也比較好，所以適合最短對(duì)角線法拼接。

Figure 4 The shortest diagonal algorithm

采用最短對(duì)角線法拼接相鄰輪廓線時(shí)，從兩輪廓線中控制點(diǎn)較少的輪廓線的第一個(gè)控制點(diǎn)p0開(kāi)始，在對(duì)應(yīng)輪廓線中查找離點(diǎn)p0距離最近的一點(diǎn)qi，以線段p0qi為起始邊，執(zhí)行最短對(duì)角線算法。

4 分支問(wèn)題

當(dāng)相鄰斷層的輪廓線數(shù)目不等時(shí)要解決分支問(wèn)題。對(duì)于多個(gè)不重疊的輪廓線而產(chǎn)生的分支問(wèn)題，需要把多分支轉(zhuǎn)化成一組單分支。輪廓線合并和輪廓線分裂是兩個(gè)解決分支問(wèn)題的方式，輪廓線合并是采用一定的方式把多條輪廓線合并為一條，再進(jìn)行一對(duì)一的輪廓線拼接。而輪廓線分裂是采用一定的方式把單輪廓線分成多條輪廓線，再進(jìn)行多個(gè)一對(duì)一的輪廓線的拼接。

4.1 內(nèi)插邊解決分支問(wèn)題(分支數(shù)=2)

引入內(nèi)插邊來(lái)解決相鄰輪廓線的分支問(wèn)題屬于輪廓線的分裂方法，它適用于獨(dú)立分叉問(wèn)題，該方法利用兩輪廓線之間的垂直平分線將一斷層的單輪廓線分成兩條輪廓線，與另一斷層兩條輪廓線對(duì)應(yīng)。

當(dāng)多輪廓線間最短距離較大、上下輪廓線大小有較大的差別時(shí)，該方法會(huì)出現(xiàn)單輪廓線的大部分區(qū)域與相鄰斷層的一個(gè)較小的輪廓線相連，從而影響構(gòu)造的精度，而且當(dāng)分支過(guò)多時(shí)，該方法實(shí)現(xiàn)比較困難[7]。

4.2 按照周長(zhǎng)比率解決分支問(wèn)題(分支數(shù)≥3)

由于相鄰斷層距離較小，上下輪廓線的大小應(yīng)該具有一定的相似性，可按照多輪廓線周長(zhǎng)的比率把多分支問(wèn)題轉(zhuǎn)化成若干個(gè)單分支問(wèn)題。設(shè)下層包含一條輪廓線，上層包含多條封閉輪廓線，需要把下層的單輪廓線按照上層多個(gè)輪廓線的周長(zhǎng)的比率分裂成與上層輪廓線數(shù)目相同的多條輪廓線，然后按照上述步驟，進(jìn)行輪廓線拼接[8]。設(shè)上層有三條輪廓線C1、C2、C3，下層有一條輪廓線C0。如圖5所示，則實(shí)現(xiàn)輪廓線分裂的具體算法如下:

Step 1 計(jì)算輪廓線C1、C2、C3的質(zhì)點(diǎn)坐標(biāo)，假設(shè)分別為B1、B2、B3，計(jì)算輪廓線C0的質(zhì)點(diǎn)，假設(shè)為A0。

Step 2 計(jì)算以質(zhì)點(diǎn)B1、B2、B3為頂點(diǎn)的多邊形的質(zhì)點(diǎn)，假設(shè)為B0。

Step 3 連接線段B0B1、B0B2、B0B3。

Step 4 輪廓線C0中做線段A0A1、A0A2、A0A3，分別平行于線段B0B1、B0B2、B0B3。

Step 5 計(jì)算輪廓線C1、C2、C3的周長(zhǎng)，假設(shè)分別為P1、P2、P3。

Step 6 在輪廓線C0中計(jì)算點(diǎn)M1，使點(diǎn)M1把輪廓線C0中A1、M1、A2部分按照輪廓線C1、C2周長(zhǎng)的比例分成兩部分，即A1M1∶M1A2=P1∶P2。用同樣的方法分別按照輪廓線C1、C3和C2、C3的周長(zhǎng)的比率,把A1、M3、A3和A3、M2、A2各自分成兩部分。

Step 7 把輪廓線C1、C2、C3分別和輪廓線C0分割后的三部分M1A0M3A1M1、M1A0M2A2M1、M2A0M3A3M2對(duì)應(yīng)。

Step 8 按照單輪廓線的重構(gòu)方法構(gòu)建三維實(shí)體。

分裂之后的輪廓線在拼接前也要進(jìn)行輪廓線數(shù)據(jù)的預(yù)處理。

Figure 5 Splitting when one line corresponds to multil-line

5 末端輪廓線的閉合處理

為了實(shí)現(xiàn)末端輪廓線的閉合處理，本文設(shè)計(jì)實(shí)現(xiàn)了任意多邊形的三角剖分算法。該算法把輪廓線作為任意多邊形，通過(guò)任意多邊形的三角剖分算法，實(shí)現(xiàn)輪廓線的三角剖分。在實(shí)現(xiàn)任意多邊形三角形剖分算法時(shí)，為了減少計(jì)算量,本文在搜索最小外接圓半徑三角形時(shí)，采用最大張角三角形方法，即與當(dāng)前邊形成的夾角最大的點(diǎn)為待選點(diǎn)。如圖6a所示，對(duì)于線段AB，輪廓線上其他頂點(diǎn)與該線段所形成的夾角分別為α1α2α3α4，其中α4值最大，故選取C點(diǎn)與線段AB組成一個(gè)剖分三角形。

Figure 6 Triangulating contour line

6 實(shí)現(xiàn)結(jié)果

本文以VisualC++6.0和開(kāi)放式3D圖形編程接口OpenGL為開(kāi)發(fā)工具。使用固體礦產(chǎn)資源開(kāi)發(fā)領(lǐng)域中，二維反演生成的一系列二維輪廓線數(shù)據(jù)，進(jìn)行輪廓線預(yù)處理、輪廓線拼接、分叉和末端輪廓線的封閉處理生成封閉的三維形體模型，如圖7所示。

Figure 7 Contour lines splicing and triangulation result

從圖7可以看出，各種形態(tài)的輪廓線所形成的三維模型拼接正確，有效避免了模型交叉等錯(cuò)誤拼接現(xiàn)象。單對(duì)多輪廓線對(duì)應(yīng)的情況，如圖7b、圖7c所示，對(duì)于一個(gè)輪廓線對(duì)應(yīng)超過(guò)三個(gè)以上的輪廓線情況，該方法同樣有效，能夠自動(dòng)實(shí)現(xiàn)單輪廓線按周長(zhǎng)比例分割，完全避免了人工干預(yù)且分割結(jié)果符合工程需求。各種形態(tài)的末端輪廓線被看作任意形狀的多邊形，采用本文介紹的任意多邊形剖分算法，其剖分結(jié)果如圖7a、圖7c、圖7d所示，實(shí)現(xiàn)了末端輪廓線的閉合處理，不會(huì)出現(xiàn)空洞或剖分后三角形面的相交情況，其算法時(shí)間復(fù)雜度與文獻(xiàn)[7]實(shí)現(xiàn)的三角剖分算法相同，約為O(N2)[9]。但是，在搜索最小外接圓半徑三角形時(shí)采用本文的方法，可以減少計(jì)算量，因?yàn)橛?jì)算半徑需要開(kāi)方，其計(jì)算量大，而最大張角三角形方法只需要乘除運(yùn)算，并且在搜索候選點(diǎn)時(shí)，最小外接圓半徑法由于計(jì)算精度問(wèn)題，對(duì)工程中控制點(diǎn)坐標(biāo)絕對(duì)值很大、相對(duì)值較小的情況，會(huì)造成剖分錯(cuò)誤，出現(xiàn)空洞或剖分后的三角形面相交。

7 結(jié)束語(yǔ)

本文研究了多輪廓線三維形體重構(gòu)中，輪廓對(duì)應(yīng)、輪廓拼接、分叉和末端輪廓線的封閉等關(guān)鍵技術(shù)，提出了三維重構(gòu)中每一個(gè)實(shí)現(xiàn)步驟具體的解決方案。針對(duì)輪廓線繞向問(wèn)題，提出了夾角之和檢測(cè)法檢測(cè)輪廓線多邊形的繞向問(wèn)題，有效避免了繞向誤判；輪廓線拼接過(guò)程中，首先把凹多邊形投影于凸包上，然后進(jìn)行輪廓線的拼接；對(duì)于輪廓線一對(duì)多分叉問(wèn)題提出了按周長(zhǎng)比率解決問(wèn)題的思路；對(duì)末端輪廓線通過(guò)任意多邊形的三角剖分算法實(shí)現(xiàn)曲面的封閉，三角剖分中，搜索具有最小外接圓半徑三角形時(shí)，采用最大張角三角形方法，減少了三角剖分的計(jì)算量。實(shí)驗(yàn)結(jié)果表明，這些實(shí)現(xiàn)方法切實(shí)可行，相較于其他輪廓線拼接方法，過(guò)程直觀易懂、速度快、通用性強(qiáng)。當(dāng)輪廓線不平行時(shí)，可以在輪廓線預(yù)處理階段相對(duì)某個(gè)參考點(diǎn)或者參考面轉(zhuǎn)換為平行或近似平行的輪廓線[10]，采用上述方法拼接完成后再轉(zhuǎn)換為原始坐標(biāo)獲得正確的重構(gòu)結(jié)果。今后，我們將研究不平行輪廓線間的三維形體重構(gòu)及三維重構(gòu)結(jié)果的平滑處理，使輪廓線重構(gòu)算法更通用，重構(gòu)結(jié)果更自然、美觀。

[1]HuangYong-li.Theoryandtechnologyresearchof3Dreconstructionbasedonslice-imagesdata[D].Zhengzhou:ZhengzhouUniversity, 2004.(inChinese)

[2]LiYun-feng,LiuXiu-guo．AlgorithmofcontourssplicingbasedonOBBprojectiontransformation[J]．JournalofComputerApplications， 2011,31(12):3353-3356．(inChinese)

[3]MaoXian-cheng,LuXiao-qin,XuZhi-qiang．Triangletilesreconstructionfromdrilldata-basedcomplexcontours[J]．ComputerEngineeringandApplications，2009,45(23):179-181．(inChinese)

[4]MaHong-bin,GuoJia-teng.Cut-and-sewalgorithm:Anewmulti-contourreconstructionalgorithm[J]．JournalofNortheasternUniversity,2007, 28(1):111-114．(inChinese)

[5]WuZhong-hai,YeCheng-qing,PanYun-he．AnImprovedalgorithmofconvexhullcomputing[J]．JournalofComputer-AidedDesign&ComputerGraphics，1997,9(1):9-13．(inChinese)

[6]TangZhe-sheng.Visualizationof3dspatialdatasets[M].Beijing:TsinghuaUniversityPress,1992.(inChinese)

[7]TuZhi-hong,SangNong．DelaunaytriangulationalgorithmofarbitrarypolygonswithvisualClanguage[J]．Computer&DigitalEngineering，2005，33(1):34-36．(inChinese)

[8]LiMei，MaoShan-jun，MaAi-nai．Buildingorebodysolidmodelfromplanarcontours[J]．JournalofComputer-AidedDesign&ComputerGraphics，2006，18(7):1017-1021．(inChinese)

[9]ShuAn，RanShu-yang，WuZhang-wen，etal．Threedimensionalsurfacesreconstructionbasedonshapeofadjacentlayercontours[J]．JournalofComputerApplictions，2009，29(2):450-452．(inChinese)

[10]SeungWonShin,DamirJuric.Modelingthree-dimensionalmultiphaseflowusingalevelcontourreconstructionmethodforfronttrackingwithoutconnectivity[J].JournalofComputationalPhysics, 2002,180:427-470.

附中文參考文獻(xiàn)：

[1] 黃永麗. 基于斷層數(shù)據(jù)的三維重建理論與技術(shù)的研究[D].鄭州：鄭州大學(xué), 2004.

[2] 李運(yùn)峰，劉修國(guó)．基于方向包圍盒投影轉(zhuǎn)換的輪廓線拼接算法[J]． 計(jì)算機(jī)應(yīng)用， 2011,31(12):3353-3356．

[3] 毛先成，盧曉琴，徐志強(qiáng)．基于鉆孔數(shù)據(jù)的復(fù)雜輪廓線三角面片的重構(gòu)[J]．計(jì)算機(jī)工程與應(yīng)用，2009,45(23):179-181．

[4] 馬洪濱，郭甲騰．一種新的多輪廓線重構(gòu)三維形體算法：切開(kāi)-縫合法[J]．東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007, 28(1):111-114．

[5] 吳中海，葉澄清，潘云鶴．一個(gè)改進(jìn)的簡(jiǎn)單多邊形凸包算法[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1997,9(1):9-13．

[6] 唐澤圣. 三維數(shù)據(jù)場(chǎng)可視化[M]. 北京:清華大學(xué)出版社,1992.

[7] 涂治紅，桑農(nóng)．用VC語(yǔ)言實(shí)現(xiàn)任意多邊形的Delaunay完全三角剖分[J]．計(jì)算機(jī)與數(shù)字工程，2005，33(1):34-36．

[8] 李梅，毛善君，馬藹乃． 平行輪廓線三維礦體重建算法[J]． 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18(7):1017 -1021．

[9] 蘇安，冉蜀陽(yáng)，吳章文，等． 基于相鄰層輪廓線幾何形狀匹配的三維重建[J]． 計(jì)算機(jī)應(yīng)用，2009，29(2):450-452．

LIU Kun-liang,born in 1976,MS,lecturer,his research interests include algorithms analysis and design, and 3D data visualization.

Study and implementation of multi-contour 3D reconstruction

LIU Kun-liang1，HUANG Jin-ming2

(1.School of Computer Science & Software Engineering,Tianjin Polytechnic University,Tianjin 300387;2.Development and Research Center,China Geological Survey,Beijing 100037,China)

In practical applications, 3D reconstruction often faces a series of 2D contour lines rather than the volume data we often process, so studying 3D reconstruction based on contours has important practical values. The key technologies of 3D-reconstruction based on multiple contours include contours corresponding, contours splicing, crotched contours handling, and terminal contours closing . The concrete solutions to each step of 3D construction of contours are given. According to the winding direction issue of contours, we propose a method of gauging the sum of angles, avoiding error judgment of the winding direction of contours. For the crotching issue of one contour corresponding to multiple contours, we give a way of splitting contours based on the circumference ratio of corresponding contours. We also give the means of maximum angle in order to reduce the calculation time on triangulating terminal contours. The proposed solutions can achieve correct contours splicing of any contours, guarantee that each step of the solution is correct and effective, and they are more universal compared to other solutions.

contour;3D reconstruction;Delaunay triangulate;convex hull

1007-130X(2015)01-0133-06

2013-04-10;

2013-07-04基金項(xiàng)目：中國(guó)地質(zhì)調(diào)查局發(fā)展研究中心承擔(dān)的“華南地區(qū)深部巖體圈定與形態(tài)研究”工作項(xiàng)目([2011]02-22-14)通信作者：黃金明(hjm89211@163.com)

TP391.4

A

10.3969/j.issn.1007-130X.2015.01.020

劉坤良(1976-),男,山東金鄉(xiāng)人，碩士，講師，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析、三維可視化。E-mail:2003_asecliu@126.com

通信地址：300387 天津市天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院

Address:School of Computer Science & Software Engineering,Tianjin Polytechnic University,Tianjin 300387,P.R.China