OpenCASCADE-曲面求交
eryar@163.com
Abstract: 曲面求交是幾何造型內核最為重要也最為復雜的問題之一，求交算法的質量（穩定、準確、快速）直接影響到幾何內核的穩定性和實用程度，故具有十分重要的意義。求交問題包括曲線與曲線求交、曲線與曲面求交和曲面與曲面求交，其中最重要難度最大的當屬曲面與曲面求交問題，其他求交問題可以應用曲面與曲面求交的思想予以解決。本文主要介紹opencascade中曲面與曲面求交的實現原理。
Key Words: Face Face Intersection, Intersection
1. Introduction
如果說理解opencascade中面的構造原理（即理解BRepBuilderAPI_MakeFace的源碼），我覺得算是理解了BRep表示法的數據結構Modeling Data。如果說理解了曲面與曲面求交的實現原理，我覺得算是對幾何內核中的核心算法布爾操作有了一定的認識。曲面與曲面求交過程（Intersection Algorithm）中主要依賴三大工具：擬合（Approximation Algorithm）、投影（Projection Algorithm）和定位（Classification Algorithm）。下面結合布爾操作TKBO中的曲面與曲面求交類IntTools_FaceFace源碼實現分別介紹這三大工具的應用場景。opencascade中的算法類一般的使用套路和把大象裝冰箱類似總共分三步：
第一步，初始化；通過構造函數或Init()等函數將算法類需要的參數輸入進去；IntTools_FaceFace中通過SetParameters()函數設置算法的參數
第二步：計算；使用函數Build()， Perform()函數來執行計算；IntTools_FaceFace中的主要實現邏輯在Perform()中。
第三步：輸出；將計算結果輸出。IntTools_FaceFace通過Lines()和Points()函數輸出計算結果即交線和交點。
2. Approximation Algorithm 擬合
opencascade中曲面的表示有兩種方式，一種是參數方程S(u,v)表示，一種是二次曲面的代數方程f(x,y,z)=0表示。因此也將曲面求交問題分為：
- 代數/代數曲面求交；
- 代數/參數曲面求交；
- 參數/參數曲面求交；
opencascade中計算曲面求交更底層的類是IntPatch_Intersection，其中也是分這三種類型來處理：
GeomGeomPerfom()對應的是代數/代數曲面求交；
GeomParamPerform()對應的是代數/參數曲面求交；
ParamParamPerform()對應的是參數/參數曲面求交；
其中代數/代數曲面求交函數GeomGeomPerform()中使用類IntPatch_ImpImpIntersection來計算兩個二次代數曲面的求交，其實這是Imp縮寫就是隱式代數方程Implicit Equation的意思。
二次代數曲面的求交使用包IntAna來實現，這在早期文章中分析了其實現原理，主要思想是將一個二次曲面的參數表示代入隱式方程變成一元方程，然后對這個一元方程進行求解。例如圓柱面與二次代數曲面求交：
其中代數/參數曲面求交函數GeomParamPerform()中使用類IntPatch_ImpPrmIntersection來計算代數曲面和參數曲面的求交，這里Prm為Parametric equation參數方程的縮寫。其代碼注釋中寫到bi-parametrised surface意思雙參數曲面S(u, v)。
其中代數/參數曲面求交函數ParamParamPerform()中使用類IntPatch_PrmPrmIntersection來計算參數數曲面和參數曲面的求交。
參數/參數曲面求交的基本方法有以下五種：
- 代數法，也稱解析法；
- 網格離散法；
- 分割法；
- 迭代法；
- 追蹤法；
相關原理介紹可以參考朱心雄等著《自由曲線曲面造型技術》。大家可以結合源碼，看看opencascade中使用了哪些方法。曲面交線的表達涉及三個問題，交點信息表示，交線組織及交線中交點的刪除策略。交線的表達使用類IntPatch_Line：
在類IntTools_FaceFace中函數SetParameters()中可以指定交線中交點的刪除策略。通過參數ApproxCurves和ApproximationTolerance來指定交線中交點是否擬合及擬合精度。求交過程中得到的交點往往非常致密，這樣雖然可以保證交線的精度，但保存的數據量太大，在實際應用中需要刪除部分交點。Pratt提出使用最小二乘法對交線逼近，以刪除不必要的交點。這里就需要使用到擬合算法Approximation Algorithm。
在opencascade中擬合問題被抽象成非線性方程組的求解問題，當然最小二乘法也是其中方法之一。擬合算法是造型內核中最基礎最重要的算法，除了簡單的點擬合成線以外，還要處理帶約束的情況，如加上交點通過曲面的位置約束等。幾何約束求解器中核心也是如此。法國、俄羅斯數學厲害，我想應該是已經形成理論+應用的良性循環。數學是創新的基礎，是用最簡單的語言來精確描述自然中的規律，雖然我們理工科一直學數學，但工作后很大一部分人很少使用高等數學中的工具，感覺數學沒什么用。學而不思則罔，思而不學則殆。我總結的學習規律就是要有實踐，上學時實踐就是通過做題，數學理論的一種實踐就是開發出軟件程序。
現在國家提倡自主我覺得是大好事，什么時候我們出一個幾何內核，出一個PDE偏微方程求解器等，形成理論加實踐的良性循環，以我們的人數和勤勞，離科技強國就不會太遠。
3. Projection Algorithm 投影
投影主要用來計算曲面上的曲線對應到曲面參數空間的曲線PCurve，生成FACE面時如果邊EDGE中沒有PCurve，得到的面是不正確的。投影算法的實現原理在早期的文章中已經詳細介紹過，投影算法依賴擬合算法。投影算法用在生成交線的函數中MakeCurve()：
當不對交線進行擬合時，生成交線及PCurve主要使用類GeomInt_SS的靜態函數來得到交線：
這樣生成的交線是B樣條曲線且控制頂點數量很大。當通過擬合可以生成更簡化的B樣條交線。
4. Classification Algorithm 定位
定位工具主要用于判斷點和一個區域的狀態，是在區域內、外還是上。在早期的文章中有一些介紹：https://www.cnblogs.com/opencascade/p/Point_Classifier.html
點定位在曲面求交中的應用就是處理拓樸面的情況，對于幾何曲面，其實參數域就是其參數S(u,v)的取值范圍。對于拓樸面，其參數域是通過邊界Wire來限定的，而且還會有面上開孔的情況需要處理。其實IntTools_FaceFace主要是用來計算FACE中幾何曲面求交的，沒有正確處理定位問題，即生成的交線沒有處理面的邊界問題。相信看懂源碼的同學可以解決這個問題。
定位問題是個幾何問題，在《計算幾何及應用》一書中有對點的定位問題有詳細算法。一般的處理方法是通過點作一條半射線，計算半射線與多邊形交點的個數，若交點數為奇數，則點在內部，否則在外部。還有一種方法是通過計算點與多邊形各頂點的角度來判斷。這兩種方式時間復雜度均為O(n)。opencascade中使用的第一種方法。書中提到幾種效率更高的算法，如點定位問題的分層方法，可以將查詢時間提高到O(logn)。點定位問題的單調鏈方法用O(nlogn)時間和O(n)空間作預處理，查詢時間可以O((logn)^2)完成。點定位的三角形細分方法(Triangulation refinement method)只用O(n)空間存放預處理結果，用O(logn)時間回答點在哪個區域，完成預處理的時間是O(nlogn)。由此可見，opencascade的定位算法還有一些改進空間。
5. Conclusion
幾何內核中曲面和曲面求交是最重要最復雜的問題，處理曲面和曲面求交需要擬合Approximation Algorithm、投影Projection Algorithm和定位Classification Algorithm工具。其中擬合和投影主要是數學問題，定位主要是個幾何問題，理解問題就能找到相應的解決工具。慶幸有opencascade這個功能相對完備的開源的幾何內核，提供了一個理論聯系實踐的平臺。理解數學理論后可以去閱讀源碼，甚至是參與和貢獻，求交、擬合、投影和定位工具都有一些改進空間。
最近關注的朋友說文章發得少了，主要原因是有點忙，不是因為保守不想分享，當然有些朋友也提醒要留一手。對于opencascade的技術分享我是沒有保留的，因為opencascade是開源的，如果通過這些文章分享能幫助別人解決一些問題，就是創造價值，是有意義的。時不時收到網友的感謝，收獲的感動不是用金錢可以衡量的。