一種跟蹤隱式曲面交線的算法
2008-12-31 00:00:00余正生楚廣琳
計算機應用研究 2008年7期
摘 要：傳統的跟蹤方法在求下一個跟蹤點時一般是采用迭代法，而迭代法會出現初始值的選取和迭代收斂的問題。為此提出一種跟蹤隱式曲面交線的算法。該方法最主要的優點是：在跟蹤隱式曲面的交線時，在前一個跟蹤交點已經求得的情況下，利用正方形與兩個隱式曲面的交點，即可快速有效地求出下一個跟蹤點，而不用涉及迭代收斂的判斷。
關鍵詞：隱式曲面；交線；初始交點；跟蹤
中圖分類號：TP391．72 文獻標志碼：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
在許多計算機圖形學應用中，如建模、生成有限元網格、指定工具路徑、科學視覺、界面和特征檢測等，經常遇到曲面與曲面相交的問題（SSI）。在邊界表示幾何建模應用中，曲面與曲面相交問題顯得尤為重要。
在過去幾十年中，有大量的工作研究曲面和曲面相交的相關問題。曲面和曲面相交算法一般可劃分為四種類型[1]；
a）細分方法。其核心思想是（遞歸地）將問題分解為更小和更簡單的問題。一個簡單的例子是遞歸地將曲面分解為雙線性小片，然后再處理這些小片的相交；不斷進行細分，直到滿足某些判斷條件。滿足這些條件的點拼接在一起，形成一條或多條相鄰的曲線。Kevin等人[2]就是采用細分的方法來繪制隱式曲面的交線。一般地，細分控制是基于控制多邊形的幾何性質來進行的，如不斷縮小的性質、凸包等。在有限范圍內，細分方法收斂于實際的相交曲線，但是會產生大量的數據并且運行速度很慢的問題。通過限制細分的層次來減少這些問題，但是這樣會存在可能丟失一些小特征的風險，如環或者被丟失或者錯誤地連接孤立體。
b）格子評測。它是將曲面相交問題簡化成一系列更低階的幾何形狀的相交問題。與細分方法一樣，格子方法速度很慢，也存在關于丟失環和孤立體的問題。解析方法試圖找到交線的一種明確表示，只有在有限的情形中這種方法才可行。Miller等人[3，4]使用一種幾何方法來實現這種方法。
c）步進方法。它也稱為曲線跟蹤法，由Faux等人[5]和Barnhill等人[6~8]等人開發。其基本思想如下[9]：在相交的一個點P處構建一條局部的近似曲線。例如，該曲線相切于P。通過沿著該近似曲線步進一段指定的距離，得到下一個曲線點的估計為止。傳統的跟蹤方法是基于該位置利用迭代方法來優化結果。而迭代方法會出現初始值的選取和迭代收斂問題。
d）跟蹤方法。它是用得最廣泛的方法[6]。其原因[10]是跟蹤法（相對地）易于實現并具有通用性，這類情形對CAD應用來說特別重要。由于使用單一的方法無法適應復雜情況的求交，Koparkar等人[11~15]提出結合多種方法去解決曲面求交的問題。王華等人[16] 將區間算術與退火遺傳算法相結合，提出了區間退火遺傳算法的曲面求交。許曉革等人[17]改進了曲面離散跟蹤求交算法。
本文中采用的是跟蹤法。與傳統跟蹤算法不同的是，本算法不是采用迭代法以一個近似交點迭代獲得一個精確交點，而是采用作正方形與兩隱式曲面求交的算法計算出兩隱式曲面交線上的點。在跟蹤隱式曲面的交線時，在前一個跟蹤交點已經求得的情況下，利用正方形與兩個隱式曲面的交點，即可快速有效地求出下個跟蹤點。
1 兩隱式曲面交線的跟蹤
兩隱式曲面的交線方程如式(1)
F(x，y，z)=0G(x，y，z)=0
(1)
其中：xl ≤x ≤ xr ， yb ≤ y ≤ yt， zf ≤ z ≤ zn。
接下來介紹如何采用本算法跟蹤繪制出該交線。跟蹤隱式曲面交線的算法核心思想是：對于給定的兩個隱式曲面，用兩組分別平行于x軸和y軸的平面與兩張隱式曲面求交，將求出的一組交點作為初始交點輸入初始交點序列(P0，P1，…，Pn)中。其次，從已知的交點Pi（i=0，1，2，… ，n）出發，沿著該交點的切線方向，按給定的步長，前進到一點Pti，再以點Pti為中心，以給定的邊長作與切線垂直的正方形，計算這個正方形與兩個隱式曲面的交點Qi（i=0，1，2，…，m），以交點Qi為新的起始點進行跟蹤……依此產生一組離散的交點序列(Pi，Q0， Q1，…，Qm)，用直線段連接這些交點。直到初始交點序列中的所有點都跟蹤完畢，隱式曲面交線的跟蹤也就完成了。
跟蹤法主要包括三個步驟：求初始交點；計算后繼跟蹤交點；將所求的交點序列連接起來形成交線。
1．1 求初始交點
在交線的每個獨立分支上都必須有一個交點作為初始交點；否則，這支分支在跟蹤的過程中就很容易被遺漏。用兩組分別平行于x軸和y軸的平面與兩張隱式曲面求交，將求出的交點存入初始交點序列(P0P1…Pn)中。
1．2 跟蹤
從1．1節所求的初始交點序列(P0P1…Pn)中取出首節點P0，從該初始交點P0出發，用本文中所提出的跟蹤方法在切線方向上進行跟蹤（圖1），按給定的步長d，前進到一點Pt0，再以點Pt0為中心，以給定的邊長a作與切線垂直的正方形ABCD，計算正方形ABCD與兩個隱式曲面的交點Q0，再以交點Q0為初始點，依此求得下個交點Q1。
當遇到下列情況之一時停止跟蹤：
a)跟蹤到兩曲面任意一曲面的邊界。
b)跟蹤到初始點序列中的任一點。
c)無法確定跟蹤方向(如兩平面的法向量方向比較接近時)。
d)當無法確定跟蹤方向時，跟蹤過程停止，則從跟蹤起點切向量的反方向重新開始跟蹤。
本文跟蹤法主要分為以下三個步驟：
a)計算切向量。切向量方向是兩曲面在交點處的切平面的交線方向，即兩切平面法向量的叉積。該方向即為交線在該點的切向量方向。以下具體來說明切向量的求法。
兩隱式曲面的交線方程如式
其中：xl ≤x ≤ xr ， yb ≤ y ≤ yt， zf ≤ z ≤ zn。
如圖2所示，設P(x0， y0， z0)點在兩曲面的交線上，在曲面F(x，y，z)=0
上，P(x0， y0， z0)點處切平面的法向量為nF=(Fx， Fy ， Fz)|P，在曲面G(x，y，z)=0上，P(x0， y0， z0)點處切平面的法向量為
b)構造正方形，并求出正方形四個頂點的坐標。
如圖1所示，從P0點步進到Pt0點，現在以Pt0點為中心，垂直于P0Pt0作一個給定邊長的正方形，正方形的四個點分別記為A、B、C、D。在構造正方形的過程中，邊長的選取不能過大，否則計算出的下個交點精確度不高。
正方形四個頂點的計算如下：
如圖3所示，正方形ABCD，邊長為a，給定的相互垂直的兩個方向矢量U、V，分別為U=(Ux， Uy ， U
c）求正方形與兩個隱式曲面的交點。
它是整個跟蹤方法的重點。采用正方形四個頂點在隱式曲面上劃分正負的方法來求交點。以正方形ABCD為一個小的網格，求該正方形與兩曲面的交線。首先求正方形與隱式曲面F(x，y，z)=0的交線。如圖4，設點Si(i=0，1，2，3)依此表示正方形四個頂點A、B、C、D，將點Si(i=0，1，2，3)的坐標代入F(x，y，z)的表達式，然后計算F(Si)。如果 F(Si) ≥0，則標記為 Si(+)(i=0，1，…，n-1)；如果F(Si) ≤0，則標記為Si(-)(i=0，1，…，n-1)。如果SiSi+1(i=0，1，…，n-2) 符號不同，說明在SiSi+1之間必定存在一點，該點處的坐標值（通過線性插值法求出）使得F(x，y，z)=0成立，如果S0S3 符號不同，則在 S0S3之間必定存在一點，該點處的坐標值（其中該點坐標通過線性插值法求出）使得F(x，y，z)=0成立。從而得出正方形ABCD與隱式曲面F(x，y，z)的交點J(Jx，Jy，Jz)、K(Kx，Ky，Kz)，交點的連線JK近似為正方形ABCD與隱式曲面F(x，y，z)=0的交線。同理，可以求出正方形ABCD與隱式曲面 F(x，y，z)=0的近似交線MN。設M(Mx，My，Mz)、N(Nx，Ny，Nz)，交線JK和MN的交點T即為兩隱式曲面的交點。
在跟蹤過程中，步長和邊長的選取很重要。為了能較好地處理任意尺寸的曲面求交問題，本文使用固定步長法。固定步長的選擇尚無完善的理論依據，目前還是根據經驗確定。步長選擇不當會引起嚴重的后果。步長的選取應該適當地小，而正方形邊長的選取應該適當地大。如果步長選得過大的話，正方形ABCD與兩隱式曲面的交點存在誤差，這樣所得到的近似曲線段與實際兩隱式曲面的交線存在較大的誤差；如果正方形的邊長選取過小的話，正方形ABCD與兩隱式曲面有可能不存在交點。
1．3 連接交點序列
由1．1節得出了一組初始交點序列(P0P1…Pn)，然后取初始交點序列中的第一個交點P0進行跟蹤，得出了正方形與兩隱式曲面的交點Q0，將交點Q0作為新的跟蹤起點再次進行跟蹤，直到交點Qi (i=0，1，…，m) 滿足停止條件為止。這時得到一組交點序列(P0Q0 Q1…Qm)來繪制隱式曲面的一段交線。再從初始交點序列(P0P1…Pn)中取出第二個交點P1進行跟蹤。依此類推跟蹤完初始交點序列中的所有交點為止。此時，隱式曲面交線也就相應地跟蹤完畢。
2 跟蹤算法
算法大致流程如下：
a)輸入兩隱式曲面方程F(x，y，z)=0和 G(x，y，z)=0，跟蹤的步長d，誤差ε，正方形的邊長a以及x、y、z的范圍(xl ≤x ≤ xr ， yb ≤ y ≤ yt， zf ≤ z ≤ zn)。
b)根據一組平面與兩隱式曲面求交的方法求出初始交點，輸入初始交點序列(P0P1…Pn)。
c)取初始交點序列中的第一個交點P0，P0P。
(a)將該點P入鏈表PT中。根據式（3）求出P點的切向量，在切向量上前進一個步長d到達點Pt，以Pt點為中心作一個正方形ABCD，根據式（4）求出正方形的四個頂點坐標。
(b)以正方形ABCD作為一個網格求出其與隱式曲面F(x，y，z)=0的交線JK，其與隱式曲面 G(x，y，z)=0的交線MN。
(c)根據式(7)求出交線JK和MN的交點Q。將點Q入鏈表PT中。
(d)判斷是否滿足跟蹤停止條件。
如果滿足停止條件，則將鏈表PT中的點畫出，判斷跟蹤方向是否能夠確定；如果不能確定跟蹤方向(即兩個平面的法向量方向非常接近時)，將鏈表PT中首節點取出，執行(a)，但沿著切向量反方向上跟蹤，否則，執行(d)。
如果不滿足停止條件，則以交點Q為新的跟蹤起點，執行(a)。
(e)取出初始交點序列中的第二個交點P1，P1P。執行(a)。
(f)直到取出最后一個交點Pn，執行(a)。
此時，隱式曲面的交線已經跟蹤完畢。
3 實例
按照本文所提出的算法繪制出該隱式曲面的交線。其中，兩個曲面分別用不同的顏色表示，交線用紅色表示。圖5表示兩橢圓曲面交線的跟蹤圖；圖6表示環面和圓錐曲面交線的跟蹤圖；圖7(a)表示從圓錐的側面看時，橢圓和圓錐曲面交線的跟蹤圖；圖7(b)表示從圓錐頂尖往下看時，橢圓和圓錐曲面交線的跟蹤圖。
4 結束語
在本文中提出了在梯度方向上繪制正方形，利用正方形和兩隱式曲面求交的算法來繪制隱式曲面的交線的方法。這對求隱式曲面的交線來說是一種新的嘗試方法。傳統的跟蹤法采用迭代法計算精確交點時會遇到初始值的選取和迭代收斂問題。本文只使用簡單的線性插值就可以計算出正方形與隱式曲面的交點。當然本方法也有不足，當用定步長進行跟蹤隱式曲面交線時，如果曲面形狀不規則，且跟蹤步長過大時，所繪制出的交線就會出現少許失真現象；但當步長過小時，又會導致計算量過大。為了能夠更好地解決這些問題，今后將嘗試一些新的方法。例如當利用定步長進行跟蹤時，如何根據曲線的形狀給出相應適當的步長，或者根據曲線的曲率大小來設定變步長、利用變步長跟蹤等。
參考文獻：
[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:OxfordUniversity Press， 1986:117-142.
[16] 王華， 董金祥. 結合區間算術和退火遺傳算法的曲面求交[J]. 數值計算與計算機應用， 2004(4): 3-13.
[17] 許曉革， 冀陽峰， 楊蕾. 曲面離散跟蹤求交算法的研究[J]. 工程圖學學報， 2005(1): 66-69.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>
