OpenCASCADE曲面求交之迭代法
eryar@163.com
1 Introduction
朱心雄等著《自由曲線曲面造型技術》書中對曲面求交的迭代法有詳細介紹，其中關于曲面迭代求交的原理介紹如下：為求得兩個曲面精確的交點，Newton-Raphson迭代法得到廣泛應用，該法的優點為
- 計算精度高，速度快，在初值選擇比較合理的情況下，一般僅需要迭代二到三次就可以使交點的精度從百分之幾提高到萬分之幾甚至百萬分之一的數量級。
- 適用范圍廣，只要能獲得曲面的幾何位置、切矢、法矢等信息，不論什么類型的曲面都可以使用迭代法。
其缺點是對初始值要求較嚴格，初始值選擇不當，可能導致迭代不收斂，也就無法得到精確的交點。
在曲面求交等問題中，一般可根據參與變化的參數數量將迭代法分為三參數迭代法和四參數迭代法兩種類型。我們知道，一張參數曲面有兩個參數，兩張參數曲面共有四個參數變量。采用三參數迭代法時，兩個曲面的四個參數中只有三個參數參與迭代過程，而保持另一個參數固定不變，這實際上就是計算不變參數的等參數線與另一張曲面的交點。采用四參數迭代法時，兩張曲面的四個參數變量都參與迭代過程，四者都可能變化。兩種迭代法各有其優缺點。在下述情況下以應用三參數迭代法為宜：
- 要求將交點迭代至某參數線上，以利于后繼追蹤求交法中濾除無效初值點；
- 當交線接近于參數邊界時，希望將交點迭代至準確的邊界上，以便進行裁剪等操作。
但對于一般交點，三參數法則未必適用。首先遇到的問題是在四個參數中選擇何者作為不變參數，固定參數選擇不當可能降低迭代收斂速度以至根本不收斂，或者破壞交線拓樸結構的正確性。迭代法本身不能夠成獨立的求交方法，主要在追蹤法中使用，OpenCASCADE中曲面求交追蹤法的類是IntWalk_PWalking。本文主要介紹OpenCASCADE曲面求交迭代法的類IntWalk_TheInt2S的用法及原理。
2 Newton迭代求交
OpenCASCADE中兩曲面求交迭代法由類IntWalk_TheInt2S實現，其類中主要函數有：
給定兩個曲面，和初始估計點在兩個曲面上的參數(u1, v1), (u2,v2)，迭代計算出精確交點。固定三參數的方式總共分四種類型IntImp_ConstIsoparametric：
IntImp_UIsoparametricOnCaro1：是固定估計點在曲面1上的參數u；
IntImp_VIsoparametricOnCaro1：是固定估計點在曲面1上的參數v；
IntImp_UIsoparametricOnCaro2：是固定估計點在曲面2上的參數u；
IntImp_VIsoparametricOnCaro2：是固定估計點在曲面2上的參數v；
為了避免三參數迭代法找不到交點的情況，會在四個方向上分別進行計算，總有一個方向上會找到交點，并將找到交點的參數固定情況返回：
在函數Perform()中通用求解迭代方程組，得到精確交點：
其中迭代方程組為成員變量myZerParFunc，方程組求解使用類math_FunctionSetRoot。由方程組求解類注釋可知，需要方程組的一階偏導數即梯度Gradient，采用的是Newton迭代法。若方程組有解Root且滿足精度要求，則保存下精確交點的坐標值及在兩個曲面上的參數值等數據。
3 三參數迭代方程組
三參數迭代方程類為GeomInt_TheFunctionOfTheInt2SOfThePrmPrmSvSurfacesOfWLApprox,
是從類math_FunctionSetWithDerivatives派生的，即三參數迭代方程是個方程組(Function Set)。其定義在文件IntImp_ZerParFunc中，先使用函數ComputeParameters()根據固定參數類型來確定估計點的固定參數及另外三個參數變量的初始值：
設兩個參數曲面S1(u1,v1)，S2(u2,v2)，并已知一交點的初估計點P0，P0點在兩張曲面上對應的投影點分別為P1=S1(u0,v0)和P2=S2(s0,t0)。由于P0點為一估計點，所以P1和P2并不重合。設以s0作為固定參數，即當固定參數類型為IntImp_UIsoparametricOnCaro1時，則問題轉化為求u*,v*,t*，使兩曲面片上的點S1(u*,v*)和S2(s0,t*)重合。建立方程組：
R(u,v,t)=S1(u,v) - S2(s0, t)
通過函數計算兩個曲面上的點pntsol1和pntsol2，得到三個變量的方程組的值。
因為要使用Newton迭代法，需要提供方程組的一階偏導數，即Jacobian矩陣：
函數Derivatives()用來計算一階偏導數：
4 Conclusion
綜上所述，迭代法本身不能構成一個獨立的求交方法，與所有不動點迭代法一樣，應用迭代法求交線之前，首先必須給出交點的初始估計值，而交點的初始值必須通過其他求交方法得到。因此，迭代交交常同其它求交方法結合使用，作為交點精化的一種手段。迭代法的主要過程是根據初始估計點的幾何性質（如坐標位置、切矢、法矢、曲率等）運用Newton方法得到一個較原估計點更接近于目標點（即精確交點）的估計點。如此反復進行，直到求得的交點滿足所要求的精度。該法的優點是在初值比較好時其收斂速度非常快，而且能應用于任意參數曲面包括Coons曲面和等距曲面，因此應用非常廣泛，其主要缺點是對初始值要求比較苛刻，初始值 選擇不當有可能導致迭代不收斂。
OpenCASCADE中曲面求交的迭代法也不是獨立的方法，與之配合的有離散網格求交得到初值，在追蹤中作用迭代法。迭代求交使用的是三參數迭代法，根據三參數迭代法的數學方程可知，需要計算曲面上參數對應的點和切矢。