一種跟蹤隱式曲面交線的算法

摘 要：傳統(tǒng)的跟蹤方法在求下一個跟蹤點(diǎn)時一般是采用迭代法，而迭代法會出現(xiàn)初始值的選取和迭代收斂的問題。為此提出一種跟蹤隱式曲面交線的算法。該方法最主要的優(yōu)點(diǎn)是：在跟蹤隱式曲面的交線時，在前一個跟蹤交點(diǎn)已經(jīng)求得的情況下，利用正方形與兩個隱式曲面的交點(diǎn)，即可快速有效地求出下一個跟蹤點(diǎn)，而不用涉及迭代收斂的判斷。

關(guān)鍵詞：隱式曲面；交線；初始交點(diǎn)；跟蹤

中圖分類號：TP391．72 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)07-2235-03

Efficient method for tracing intersections of two implicit surfaces

YU Zheng-sheng， CHU Guang-lin

(Institute of Graphics Image， Hangzhou Dianzi University， Hangzhou 310018， China)

Abstract:When computing the next tracing point， the traditional tracing method generally used the iterative method. But the iterative method had to face the following problems. How to select the initial value? Whether the iteration converges or not?This paper presented a method for tracing the intersections of two implicit surfaces.The most obvious advantage of this method is: when tracing the intersections， it could quickly get the next tracing point by intersecting this square plane with the two implicit surfaces.

Key words：implicit surface; intersections; initial point; tracing



在許多計(jì)算機(jī)圖形學(xué)應(yīng)用中，如建模、生成有限元網(wǎng)格、指定工具路徑、科學(xué)視覺、界面和特征檢測等，經(jīng)常遇到曲面與曲面相交的問題（SSI）。在邊界表示幾何建模應(yīng)用中，曲面與曲面相交問題顯得尤為重要。

在過去幾十年中，有大量的工作研究曲面和曲面相交的相關(guān)問題。曲面和曲面相交算法一般可劃分為四種類型^[1]；

a）細(xì)分方法。其核心思想是（遞歸地）將問題分解為更小和更簡單的問題。一個簡單的例子是遞歸地將曲面分解為雙線性小片，然后再處理這些小片的相交；不斷進(jìn)行細(xì)分，直到滿足某些判斷條件。滿足這些條件的點(diǎn)拼接在一起，形成一條或多條相鄰的曲線。Kevin等人^[2]就是采用細(xì)分的方法來繪制隱式曲面的交線。一般地，細(xì)分控制是基于控制多邊形的幾何性質(zhì)來進(jìn)行的，如不斷縮小的性質(zhì)、凸包等。在有限范圍內(nèi)，細(xì)分方法收斂于實(shí)際的相交曲線，但是會產(chǎn)生大量的數(shù)據(jù)并且運(yùn)行速度很慢的問題。通過限制細(xì)分的層次來減少這些問題，但是這樣會存在可能丟失一些小特征的風(fēng)險，如環(huán)或者被丟失或者錯誤地連接孤立體。

b）格子評測。它是將曲面相交問題簡化成一系列更低階的幾何形狀的相交問題。與細(xì)分方法一樣，格子方法速度很慢，也存在關(guān)于丟失環(huán)和孤立體的問題。解析方法試圖找到交線的一種明確表示，只有在有限的情形中這種方法才可行。Miller等人^[3，4]使用一種幾何方法來實(shí)現(xiàn)這種方法。

c）步進(jìn)方法。它也稱為曲線跟蹤法，由Faux等人^[5]和Barnhill等人^[6~8]等人開發(fā)。其基本思想如下^[9]：在相交的一個點(diǎn)P處構(gòu)建一條局部的近似曲線。例如，該曲線相切于P。通過沿著該近似曲線步進(jìn)一段指定的距離，得到下一個曲線點(diǎn)的估計(jì)為止。傳統(tǒng)的跟蹤方法是基于該位置利用迭代方法來優(yōu)化結(jié)果。而迭代方法會出現(xiàn)初始值的選取和迭代收斂問題。

d）跟蹤方法。它是用得最廣泛的方法^[6]。其原因^[10]是跟蹤法（相對地）易于實(shí)現(xiàn)并具有通用性，這類情形對CAD應(yīng)用來說特別重要。由于使用單一的方法無法適應(yīng)復(fù)雜情況的求交，Koparkar等人^[11~15]提出結(jié)合多種方法去解決曲面求交的問題。王華等人^[16] 將區(qū)間算術(shù)與退火遺傳算法相結(jié)合，提出了區(qū)間退火遺傳算法的曲面求交。許曉革等人^[17]改進(jìn)了曲面離散跟蹤求交算法。

本文中采用的是跟蹤法。與傳統(tǒng)跟蹤算法不同的是，本算法不是采用迭代法以一個近似交點(diǎn)迭代獲得一個精確交點(diǎn)，而是采用作正方形與兩隱式曲面求交的算法計(jì)算出兩隱式曲面交線上的點(diǎn)。在跟蹤隱式曲面的交線時，在前一個跟蹤交點(diǎn)已經(jīng)求得的情況下，利用正方形與兩個隱式曲面的交點(diǎn)，即可快速有效地求出下個跟蹤點(diǎn)。

1 兩隱式曲面交線的跟蹤

兩隱式曲面的交線方程如式(1)

F(x，y，z)=0G(x，y，z)=0

(1)

其中：xl ≤x ≤ xr ， yb ≤ y ≤ yt， zf ≤ z ≤ zn。

接下來介紹如何采用本算法跟蹤繪制出該交線。跟蹤隱式曲面交線的算法核心思想是：對于給定的兩個隱式曲面，用兩組分別平行于x軸和y軸的平面與兩張隱式曲面求交，將求出的一組交點(diǎn)作為初始交點(diǎn)輸入初始交點(diǎn)序列(P0，P1，…，Pn)中。其次，從已知的交點(diǎn)Pi（i=0，1，2，… ，n）出發(fā)，沿著該交點(diǎn)的切線方向，按給定的步長，前進(jìn)到一點(diǎn)Pti，再以點(diǎn)Pti為中心，以給定的邊長作與切線垂直的正方形，計(jì)算這個正方形與兩個隱式曲面的交點(diǎn)Qi（i=0，1，2，…，m），以交點(diǎn)Qi為新的起始點(diǎn)進(jìn)行跟蹤……依此產(chǎn)生一組離散的交點(diǎn)序列(Pi，Q0， Q1，…，Qm)，用直線段連接這些交點(diǎn)。直到初始交點(diǎn)序列中的所有點(diǎn)都跟蹤完畢，隱式曲面交線的跟蹤也就完成了。

跟蹤法主要包括三個步驟：求初始交點(diǎn)；計(jì)算后繼跟蹤交點(diǎn)；將所求的交點(diǎn)序列連接起來形成交線。

1．1 求初始交點(diǎn)

在交線的每個獨(dú)立分支上都必須有一個交點(diǎn)作為初始交點(diǎn)；否則，這支分支在跟蹤的過程中就很容易被遺漏。用兩組分別平行于x軸和y軸的平面與兩張隱式曲面求交，將求出的交點(diǎn)存入初始交點(diǎn)序列(P0P1…Pn)中。

1．2 跟蹤

從1．1節(jié)所求的初始交點(diǎn)序列(P0P1…Pn)中取出首節(jié)點(diǎn)P0，從該初始交點(diǎn)P0出發(fā)，用本文中所提出的跟蹤方法在切線方向上進(jìn)行跟蹤（圖1），按給定的步長d，前進(jìn)到一點(diǎn)Pt0，再以點(diǎn)Pt0為中心，以給定的邊長a作與切線垂直的正方形ABCD，計(jì)算正方形ABCD與兩個隱式曲面的交點(diǎn)Q0，再以交點(diǎn)Q0為初始點(diǎn)，依此求得下個交點(diǎn)Q1。

當(dāng)遇到下列情況之一時停止跟蹤：

a)跟蹤到兩曲面任意一曲面的邊界。

b)跟蹤到初始點(diǎn)序列中的任一點(diǎn)。

c)無法確定跟蹤方向(如兩平面的法向量方向比較接近時)。

d)當(dāng)無法確定跟蹤方向時，跟蹤過程停止，則從跟蹤起點(diǎn)切向量的反方向重新開始跟蹤。

本文跟蹤法主要分為以下三個步驟：

a)計(jì)算切向量。切向量方向是兩曲面在交點(diǎn)處的切平面的交線方向，即兩切平面法向量的叉積。該方向即為交線在該點(diǎn)的切向量方向。以下具體來說明切向量的求法。

兩隱式曲面的交線方程如式

其中：xl ≤x ≤ xr ， yb ≤ y ≤ yt， zf ≤ z ≤ zn。

如圖2所示，設(shè)P(x0， y0， z0)點(diǎn)在兩曲面的交線上，在曲面F(x，y，z)=0

上，P(x0， y0， z0)點(diǎn)處切平面的法向量為nF=(Fx， Fy ， Fz)|P，在曲面G(x，y，z)=0上，P(x0， y0， z0)點(diǎn)處切平面的法向量為

b)構(gòu)造正方形，并求出正方形四個頂點(diǎn)的坐標(biāo)。

如圖1所示，從P0點(diǎn)步進(jìn)到Pt0點(diǎn)，現(xiàn)在以Pt0點(diǎn)為中心，垂直于P0Pt0作一個給定邊長的正方形，正方形的四個點(diǎn)分別記為A、B、C、D。在構(gòu)造正方形的過程中，邊長的選取不能過大，否則計(jì)算出的下個交點(diǎn)精確度不高。



正方形四個頂點(diǎn)的計(jì)算如下：

如圖3所示，正方形ABCD，邊長為a，給定的相互垂直的兩個方向矢量U、V，分別為U=(Ux， Uy ， U

c）求正方形與兩個隱式曲面的交點(diǎn)。

它是整個跟蹤方法的重點(diǎn)。采用正方形四個頂點(diǎn)在隱式曲面上劃分正負(fù)的方法來求交點(diǎn)。以正方形ABCD為一個小的網(wǎng)格，求該正方形與兩曲面的交線。首先求正方形與隱式曲面F(x，y，z)=0的交線。如圖4，設(shè)點(diǎn)Si(i=0，1，2，3)依此表示正方形四個頂點(diǎn)A、B、C、D，將點(diǎn)Si(i=0，1，2，3)的坐標(biāo)代入F(x，y，z)的表達(dá)式，然后計(jì)算F(Si)。如果 F(Si) ≥0，則標(biāo)記為 Si(+)(i=0，1，…，n-1)；如果F(Si) ≤0，則標(biāo)記為Si(-)(i=0，1，…，n-1)。如果SiSi+1(i=0，1，…，n-2) 符號不同，說明在SiSi+1之間必定存在一點(diǎn)，該點(diǎn)處的坐標(biāo)值（通過線性插值法求出）使得F(x，y，z)=0成立，如果S0S3 符號不同，則在 S0S3之間必定存在一點(diǎn)，該點(diǎn)處的坐標(biāo)值（其中該點(diǎn)坐標(biāo)通過線性插值法求出）使得F(x，y，z)=0成立。從而得出正方形ABCD與隱式曲面F(x，y，z)的交點(diǎn)J(Jx，Jy，Jz)、K(Kx，Ky，Kz)，交點(diǎn)的連線JK近似為正方形ABCD與隱式曲面F(x，y，z)=0的交線。同理，可以求出正方形ABCD與隱式曲面 F(x，y，z)=0的近似交線MN。設(shè)M(Mx，My，Mz)、N(Nx，Ny，Nz)，交線JK和MN的交點(diǎn)T即為兩隱式曲面的交點(diǎn)。



在跟蹤過程中，步長和邊長的選取很重要。為了能較好地處理任意尺寸的曲面求交問題，本文使用固定步長法。固定步長的選擇尚無完善的理論依據(jù)，目前還是根據(jù)經(jīng)驗(yàn)確定。步長選擇不當(dāng)會引起嚴(yán)重的后果。步長的選取應(yīng)該適當(dāng)?shù)匦。叫芜呴L的選取應(yīng)該適當(dāng)?shù)卮蟆Ｈ绻介L選得過大的話，正方形ABCD與兩隱式曲面的交點(diǎn)存在誤差，這樣所得到的近似曲線段與實(shí)際兩隱式曲面的交線存在較大的誤差；如果正方形的邊長選取過小的話，正方形ABCD與兩隱式曲面有可能不存在交點(diǎn)。

1．3 連接交點(diǎn)序列

由1．1節(jié)得出了一組初始交點(diǎn)序列(P0P1…Pn)，然后取初始交點(diǎn)序列中的第一個交點(diǎn)P0進(jìn)行跟蹤，得出了正方形與兩隱式曲面的交點(diǎn)Q0，將交點(diǎn)Q0作為新的跟蹤起點(diǎn)再次進(jìn)行跟蹤，直到交點(diǎn)Qi (i=0，1，…，m) 滿足停止條件為止。這時得到一組交點(diǎn)序列(P0Q0 Q1…Qm)來繪制隱式曲面的一段交線。再從初始交點(diǎn)序列(P0P1…Pn)中取出第二個交點(diǎn)P1進(jìn)行跟蹤。依此類推跟蹤完初始交點(diǎn)序列中的所有交點(diǎn)為止。此時，隱式曲面交線也就相應(yīng)地跟蹤完畢。

2 跟蹤算法

算法大致流程如下：

a)輸入兩隱式曲面方程F(x，y，z)=0和 G(x，y，z)=0，跟蹤的步長d，誤差ε，正方形的邊長a以及x、y、z的范圍(xl ≤x ≤ xr ， yb ≤ y ≤ yt， zf ≤ z ≤ zn)。

b)根據(jù)一組平面與兩隱式曲面求交的方法求出初始交點(diǎn)，輸入初始交點(diǎn)序列(P0P1…Pn)。

c)取初始交點(diǎn)序列中的第一個交點(diǎn)P0，P0P。

(a)將該點(diǎn)P入鏈表PT中。根據(jù)式（3）求出P點(diǎn)的切向量，在切向量上前進(jìn)一個步長d到達(dá)點(diǎn)Pt，以Pt點(diǎn)為中心作一個正方形ABCD，根據(jù)式（4）求出正方形的四個頂點(diǎn)坐標(biāo)。

(b)以正方形ABCD作為一個網(wǎng)格求出其與隱式曲面F(x，y，z)=0的交線JK，其與隱式曲面 G(x，y，z)=0的交線MN。

(c)根據(jù)式(7)求出交線JK和MN的交點(diǎn)Q。將點(diǎn)Q入鏈表PT中。

(d)判斷是否滿足跟蹤停止條件。

如果滿足停止條件，則將鏈表PT中的點(diǎn)畫出，判斷跟蹤方向是否能夠確定；如果不能確定跟蹤方向(即兩個平面的法向量方向非常接近時)，將鏈表PT中首節(jié)點(diǎn)取出，執(zhí)行(a)，但沿著切向量反方向上跟蹤，否則，執(zhí)行(d)。

如果不滿足停止條件，則以交點(diǎn)Q為新的跟蹤起點(diǎn)，執(zhí)行(a)。

(e)取出初始交點(diǎn)序列中的第二個交點(diǎn)P1，P1P。執(zhí)行(a)。

(f)直到取出最后一個交點(diǎn)Pn，執(zhí)行(a)。

此時，隱式曲面的交線已經(jīng)跟蹤完畢。

3 實(shí)例

按照本文所提出的算法繪制出該隱式曲面的交線。其中，兩個曲面分別用不同的顏色表示，交線用紅色表示。圖5表示兩橢圓曲面交線的跟蹤圖；圖6表示環(huán)面和圓錐曲面交線的跟蹤圖；圖7(a)表示從圓錐的側(cè)面看時，橢圓和圓錐曲面交線的跟蹤圖；圖7(b)表示從圓錐頂尖往下看時，橢圓和圓錐曲面交線的跟蹤圖。



4 結(jié)束語

在本文中提出了在梯度方向上繪制正方形，利用正方形和兩隱式曲面求交的算法來繪制隱式曲面的交線的方法。這對求隱式曲面的交線來說是一種新的嘗試方法。傳統(tǒng)的跟蹤法采用迭代法計(jì)算精確交點(diǎn)時會遇到初始值的選取和迭代收斂問題。本文只使用簡單的線性插值就可以計(jì)算出正方形與隱式曲面的交點(diǎn)。當(dāng)然本方法也有不足，當(dāng)用定步長進(jìn)行跟蹤隱式曲面交線時，如果曲面形狀不規(guī)則，且跟蹤步長過大時，所繪制出的交線就會出現(xiàn)少許失真現(xiàn)象；但當(dāng)步長過小時，又會導(dǎo)致計(jì)算量過大。為了能夠更好地解決這些問題，今后將嘗試一些新的方法。例如當(dāng)利用定步長進(jìn)行跟蹤時，如何根據(jù)曲線的形狀給出相應(yīng)適當(dāng)?shù)牟介L，或者根據(jù)曲線的曲率大小來設(shè)定變步長、利用變步長跟蹤等。

參考文獻(xiàn)：

[1]PHILIP J， SCHNEIDER D，EBERLY H. Geometric tools for compu-ter graphics[M].[S.l.]: Industry and Electric Press， 2005: 437-448.

[2]KEVIN G， RONALD S，BALSYS J. Rendering the intersections of implicit surfaces[J]. IEEE Computer Graphics and Applications， 2003， 23(5):70-77.

[3]MILLER J R， RONALD N G. Using tangent balls to find plane sections of natural quadrics[J]. IEEE Computer Graphics and Applications， 1992， 16(2):68-82.

[4]MILLER J R， RONALD G . Geometric algorithms for detecting and calculating all comic sections in intersection of any two natural quadric surfaces[J]. Computer Vision， Graphics， and Image Processing， 1995， 57(1):55-66.

[5]FAUX O D ， PRATT M J. Computational geometry for design and manufacture[M].Chichester: Ellis Horwood Limited，1979.

[6]BARNHILL R E， KERSEY S N. A marching method for parametric surface/surface intersection[J]. Computer Aided Geometric Design， 1990， 7(1-4): 257-280.



[7]AZIZ N M， BATA R. Bezier surface/surface intersection[J]. IEEE Computer Graphics and Application， 1990， 10(1): 50-58.

[8]MARKOT R P， MAGEDSOON R L. Solution of tangential surface and curve intersection[J]. Computer Aided Design， 1989， 21(7): 421-429.

[9]BAJAJ C L， HOFFMAN CM， LYNCH R E， et al. Tracing surface intersections[J]. Computer Aided Geometric Design， 1988， 5(4):285-307.

[10]KRISHNAN S， DINESH M. An efficient surface intersection algorithm based on lower dimensional formulation[J]. ACM Trans on Graphics， 1997， 16(1):74-106.

[11]CHOI B K. Surface modeling for CAD/CAM[M].[S.l.]:Elsevier Science Publisher ， 1991.

[12]KOPARKAR P. Surface intersection by switch from recursive subdivision to interactive refinement[J]. The Visual Computer，1991，8（1）.47-63.

[13]LASSER D. Intersection of parametric surfaces in the bernstein bezier representation[J]. Computer Aided Design， 1986，18(4)：186-192.

[14]TIMMER H G. A solution to the surface intersection problem，Report MDC 17789[R].[S.l]: Douglas Aircraft Company，1977.

[15]PRATT M J， GEISOW A D. Surface/surface intersection problems.[M]//GREGORY J A.The Mathematics of Surfaces. Oxford:OxfordUniversity Press， 1986:117-142.

[16] 王華， 董金祥. 結(jié)合區(qū)間算術(shù)和退火遺傳算法的曲面求交[J]. 數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用， 2004(4): 3-13.

[17] 許曉革， 冀陽峰， 楊蕾. 曲面離散跟蹤求交算法的研究[J]. 工程圖學(xué)學(xué)報， 2005(1): 66-69.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”