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

3 追蹤法的實現

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

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

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

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

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

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

4 Conclusion

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

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