OpenCASCADE曲面求交之追蹤法

eryar@163.com

1 Introduction

朱心雄等著《自由曲線曲面造型技術》書中對曲面求交的追蹤法（Marching method）有詳細介紹，首先曲面求交追蹤法的提出是1990年R.E. BARNHILL和S.N. KERSEY的一篇論文：A marching method for parametric surface/surface intersection感興趣的可以下載來看看原文：

1990年我才幾歲，那時家里有黑白電視機已經算不錯的。對于一般NURBS曲面的求交，先用分割離散法求得交線的拓樸結構和交點的估計值，然后再應用迭代法根據估計值求得精確交點。如果認為交點分布不夠細密，可以對網格進行加密，再應用迭代法得到新的精確交點，由此可以獲得完整、致密的精確交線，而無需應用追蹤法。

2 追蹤法的原理

追蹤法的原理：假設兩曲面間共有N個交線環，先通過某種求交方法確定各交線環上的一個交點，然后以該交點為初始交點，根據交線的幾何性質，按照一定步長計算該條交線上下一交點的近似值，再應用迭代法求得精確交點。沿交線走向不斷前進，直到遍歷整條交線。追蹤法的優點是在求得首交點后搜索交線其余交點的速度非常快，且適用范圍廣。不論何種參數曲面，只要曲面不存在非正則點，并可以求得曲面上任意點的坐標位置、法矢、切矢等幾何信息，就可以用追蹤法求交。追蹤法的問題是目前尚無非常有效的方法來求得所有交線環的起始點。在有些情況下尋求初始點所花費的時間遠大于追蹤法過程中所節省的時間，而為了節省尋求初始點的時間，又可能漏掉某些交線，當在孤立交點和比較小的交線環時尤甚。

3 追蹤法的實現

OpenCASCADE實現曲面求交追蹤法的類是IntWalk_PWalking，注意看類注釋中的單詞marching:

追蹤法中需要解決兩個問題：

• 如何確定追蹤方向：目前常用切線法確定追蹤方向，即估計真實交線在該點的切線方向，并以此作為追蹤方向。當曲面間存在切點時，由于在切點附近兩曲面的法矢非常接近，無法確定追蹤方向，這也就是所謂的“迷向”問題（Tangent tracks）。在類IntWalk_PWalking中，追蹤方向作為成員變量tgdir，將迭代法計算的交線的切向量保存起來，當有“迷向”問題時，調用函數RepartirOuDiviser來修復。
• 如何確定追蹤步長：追蹤步長的選擇通常有兩種方法：1）固定步長和2）變步長也稱為自適應步長法Adaptive Step。因為迭代法是根據估計點的參數來計算精確交點，為了避免根據點反求參數，直接根據切線方向的X,Y分量來確定參數的步長。雖然有些變化，總體上看使用的是固定步長法。若直接根據交線切線方向tgdir乘以步長得到點，是需要反求點在曲面上的參數。步長主要與精度設置有關，精度設置高，步長越小，則會導致計算速度慢，求出的交點過密，還可能帶來不穩定因素。如步長過大，可能 會導致迭代不收斂或者跳到另外 一條交線上。

使用默認精度設置，追蹤法得到的交點數量就很大。若設置精度低，交點數量會明顯減少，提高計算速度。

如上圖所示，若兩個曲面只有一個交線，使用有追蹤法時只需要指定交線的初始交點，即可以得到整個交線。當兩曲面有多個交線或有孤立交點時，就需要找出多個交線的起始交點：

上圖所示位置交線斷開生成兩條交線，一個是綠色一個是紅色，這種情況就需要分別指出兩個交線起始點。

4 Conclusion

綜上所述，曲面求交追蹤法的優點是在求得首交點后搜索交線其余交點的速度非常快，且適用范圍廣。追蹤法的問題是目前尚無非常有效的方法來求得所有交線環的起始點。曲面求交一般會采用通用性較好的網格法-迭代法-追蹤法三者相結合的方法。應用網格法求得交點的初始估計值，再用迭代法求得精確交點，并以其為起點進行追蹤，直到得到整條精確交線。

IntWalk_PWalking追蹤法的步長與精度密切相關，選擇合適的精度，可以使交線的交點數量少，提高計算速度。因為精度越高追蹤過程中得到的追蹤點越多，對于每個追蹤點都需要使用迭代法計算精確交點。