劉坤良，黃金明

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

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

劉坤良1，黃金明2

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

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

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

1 引言

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

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

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

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

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

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

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

Figure 1 Incorrect splicing resulting in cones

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

(1)

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

(2)

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

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

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

(3)

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

Figure 2 Calculate deflection angles sum

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

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

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

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

voidCalConvexHull(V,n,S)

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

output:輪廓線的凸包所包含的所有點集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ū)頂點;

b=S[Top];

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

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個頂點)

for(i=1;i

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

}

Pop(S);

}

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

3 輪廓線的拼接

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

Figure 3 Connecting control points

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

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

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

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

Figure 4 The shortest diagonal algorithm

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

4 分支問題

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

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

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

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

4.2 按照周長比率解決分支問題(分支數(shù)≥3)

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

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

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

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

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

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

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

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

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

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

Figure 5 Splitting when one line corresponds to multil-line

5 末端輪廓線的閉合處理

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

Figure 6 Triangulating contour line

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

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

Figure 7 Contour lines splicing and triangulation result

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

7 結(jié)束語

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

附中文參考文獻：

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

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

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

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

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

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

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

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

[9] 蘇安，冉蜀陽，吳章文，等． 基于相鄰層輪廓線幾何形狀匹配的三維重建[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基金項目：中國地質(zhì)調(diào)查局發(fā)展研究中心承擔的“華南地區(qū)深部巖體圈定與形態(tài)研究”工作項目([2011]02-22-14)通信作者：黃金明(hjm89211@163.com)

TP391.4

A

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

劉坤良(1976-),男,山東金鄉(xiāng)人，碩士，講師，研究方向為算法設(shè)計與分析、三維可視化。E-mail:2003_asecliu@126.com

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

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