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