1、 CAD 模型修復的結構維護摘要有兩種主要方法轉換鑲嵌的 CAD 模型,它們所包含的不一致就像存在于流形封閉三角形網格中的縫隙或自交叉。面向表面算法通過擾亂部分輸入嘗試修復不一致，但他們往往不能處理特殊情況。另一方面體積算法產生有保證的流形網格，但由于全球重采樣大多輸入鑲嵌結構被破壞。在本文中，我們將結合這兩種方法的優點： 我們利用素網格拓撲的簡潔性在自交叉和縫隙附近重建一個已清理的表面，但在遠離這些不一致的區域保留了輸入的鑲嵌性。因此，我們能夠保留可能存在于輸入鑲嵌結構的任何特征（即 iso 參數或曲率線）。我們的算法縮小縫隙至用戶定義的最大直徑，解決自交叉、處理不兼容的補丁取向并生成保持在

2、輸入模型容錯范圍內功能敏感的流行輸出。簡介今天CAM生產環境的一個共同難題具有不同的幾何表現，它一方面采用CAD系統，另一方面采用下游應用程序。 而CAD系統通常代表一個模型通過一套被整理的NURBS補丁或其他表面基元（可能是從CSG代表提取的），下游應用程序如計算流體或結構仿真，快速原型和依靠封閉一致的流形三角形網格作為輸入流的數控加工。從一個到另一個表示的轉換不僅要考慮時間是一個主要瓶頸,而且也要考慮輸出的準確性和質量,這直接影響所有后續生產階段。常見的鑲嵌算法可以有效準確地將單一表面基元轉換成三角形網格，但通常不能處理不同原語之間連續性限制或檢測和解決交叉幾何。這導致工件像縫隙、重疊、交

3、叉或方向不一致的鑲嵌補丁一樣，往往不得不進行手動修復和繁瑣的后處理步驟。由于這個原因，已投入相當的努力使算法能夠自動修復這種模型。有兩種主要方法轉換鑲嵌的CAD模型，它們所包含的不一致就像存在于干凈流形三角形網格中的縫隙或自交叉。面向表面算法設法明確地計算或識別(子-)補丁，它們是通過臨時邊界元素縫合在一起的。這些算法輸入補丁變化很小，但由于數值問題不能保證輸出網格的一致性，因此通常需要用戶交互。另一方面體積算法使用一個標志距離網格作為中間表示，能夠保證流形重建。不幸的是，由于全球重采樣這些算法破壞了輸入鑲嵌結構。此外，該決議的基礎網格限制了重建質量。 在本文中，我們結合這兩種方法的優點：我們

4、利用素網格拓撲的簡潔性在自交叉和縫隙附近重建一個已清理的表面，但在遠離這些不一致的區域保留了輸入的鑲嵌性。因此，我們是能夠保留可能存在于輸入鑲嵌結構的任何特征（即 iso 參數或曲率線）。我們的算法縮小縫隙至用戶定義的最大直徑，解決自交叉、處理不兼容的補丁取向并生成保持在輸入模型容錯范圍內功能敏感的流行輸出。 其基本思路是，首先確定包含像文物一樣的縫隙和重疊的關鍵區域，然后有選擇地在這些地區運用體積重建算法，最后將未修改外部元件加入重建。由于其選擇性我們的算法一方面能達到較高的網格分辨率和文物附近的較高的重建質量，另一方面也不會引發全球重建算法的輸入的性能開銷。圖1：我們的算法將鑲嵌的 CAD

5、 模型轉換成一個無交集和封閉三角形網格，它涵蓋所有的差距達到一定規模。左：輸入補丁被創建通過由385個修剪NURBS曲面組成的鑲嵌CAD模型。中：一個標準體積重建算法在全球重新取樣并銷毀鑲嵌結構。右：我們的算法僅在本地文物附近重新取樣比如缺口和交叉點，因此保留了大部分輸入鑲嵌。2.前期工作基于表面算法直接在輸入鑲嵌上工作并使用大量技術來檢測和解決文物。這些技術包括，例如：相互捕捉邊界元素，投影和插入邊界邊成面，明確計算面之間的交叉，補丁之間正常領域的傳播BW92，BS95，BDK98，GTLH01，MD93，小塊補丁拼接縫隙TL94，Lie03，通過識別和切割處理GW01解決拓撲噪聲等。 基于

6、表面的方法只能在文物附近小范圍地區修改輸入的幾何形狀。因此，盡可能保留輸入鑲嵌。然而，這些方法通常不能提供任何輸出質量擔保：有可能沒有全球一致的定位輸入補丁，一些文物比如重疊幾何或“雙墻”很難處理; 交叉點是很難發現和解決的; 這是由于一個健全和有效實施的數值問題是一項挑戰。 面向體積的方法轉換成輸入體積的表示，即一個標志距離領域或定向網格的距離 NT03，Ju04，FPRJ00。從這個立方體表示提取表面使用類似移動立方體LC87，KBSS01或雙輪廓Gib98，JLSW02，Ju04技術。體積技術生產保證流形輸出。此外，拓撲文物和孔可以使用不同的過濾器操作輕松刪除ABA02，DMGL02，N

7、T03。算法 我們算法的輸入是一個鑲嵌的CAD模型M0 = P1,Pn它由n個元素Pi組成。每個元素Pi是一個流形三角形網格,并通過元素的ID i唯一識別。此外,規定誤差極限e0和最大直徑誤差g0。輸出是一個無交集的封閉三角形網格 T，它接近M0達到最大誤差e0并且所有縫隙的直徑 < = g0。我們的算法進行幾個階段 （見圖 2）：轉換 M0 到封閉網格 M （第 3.1）確定一個關鍵點的集合封閉所有的交叉點和所有直徑縫隙 (第 3.2）使C削減至一個最小的集合（第3.3）將 C0 轉變為關鍵頂點集合 D ，它封閉所有縫隙和所有交叉 （第 3.4 ）對D削減M（第3.4）在D 內幾何模型

8、的重建（第3.5）7. 后處理，以減少輸出的復雜性（第3.6） 1.輸入修補程序 2關鍵點 3.關鍵的單元格 4.剪輯 5.初試. 重建 6.結果圖 2：我們算法的階段。 輸入修補程序通常像展覽文物的縫隙和交叉 （1）我們確定一 (較大)關鍵點，在附近圍繞這些文物 (2)然后將這些頂點轉換為一組（較小）的關鍵單元格(3) 輸入被剪切的關鍵單元格的修補程序(4)，單元格的內部重新構造使用變量行進的立方體算法 (5)初步重建，然后將之簡化，獲得最后的結果 (6)請注意，請注意幾何模型遠離文物不受我們的重建算法的影響，因此任何結構中，輸入修補程序是完好的。 下面我們假定二不失一般性，對輸入模型進行縮

9、放和翻譯，這樣的錯誤誤差e0= 1，并且一個整數網格的范圍使M0對于某些 k是封閉的。注意:格子的大小就等于誤差差值e0。我們還假設給出最大差距直徑g0 = 2g, g為正整數。我們經常通過網格頂點或網格單元格的小的集合將數據相關聯。為提高內存效率，這些數據被存儲為深度為k的八叉樹的最優結點。八叉樹是自適應改進需求的，例如當我們訪問網格頂點或網格單元格時。對于每一個修補程序，通過復制Pi和扭轉每個三角形的方向設定一個鏡像修補程序。然后我們沿著三角形的交界的共同邊Si合并Pi和。增量是一個新的封閉的修補程序Qi它通過共同邊表示Pi。我們在新模型中集合新的修補程序。注意：M是封閉的，但對于 M0仍

10、包含在的同一文物中。還要注意的是，以此構筑的算法輸入的修補程序方向不變。如果事實證明，由此產生的“雙墻“沒有必要保證主結構的重建，他們將在后處理階段被刪除，見第3.6節。接著我們計算一個關鍵網格頂點的集合Cg。我們認為，這些關鍵點作為顆粒填充兩個或多個修補程序M的空區域使之更接近2g。這些關鍵的地區包括所有直徑<=2g的縫隙，特別是所有不同修補程序的交點。該算法的后期將提取面之間的關鍵和非關鍵頂點來創建表面修補程序，實際上縮小了縫隙并解決了交叉。 如果是由兩個或多個修補程序M 相交的我們認為網格頂點是模糊的。如果 v 是一個模糊頂點，我們設置所有關鍵頂點 即。圖 3 顯示了M的一些配置和

11、相應的模糊關鍵頂點。圖 3： 示例配置。 一些修補程序的配置如上顯示。請注意，每個修補程序是一個封閉的三角形網格。這些關鍵點作為顆粒填充兩個或多個修補程序M的空區域使之更接近2g。切口有效提供附近子像素的準確性。模糊頂點利用一個深度為k的(臨時)八叉樹能夠有效地定位。我們通過類似最優級八叉樹節點的中心的整數坐標轉移的八叉樹的起點，即它們對應的網格頂點。如果n是八叉樹的一個節點，我們通過表示八叉樹的中點，表示八叉樹的深度。因此，如果 n 是一個 最優級節點 （dn = k) 我們要檢查是否通過兩個或多個不同修補程序的相交。我們的想法是建立一個和八叉樹層次結構相匹配的盒子嵌套層次結構。因此，如果

12、n 是一個內部八叉樹節點，那么包含所有子節點n的盒子Box(n)會被選定。一個簡短的計算表明，通過讓該屬性是滿足的。特別注意，一個三角形相交框中的一個最優級節點 n 也會和所有祖先 n 的框相交。我們現在以遞歸方式向每個三角形M插入八叉樹用一個類似Ju Ju04的算法。從根節點開始，一個三角形被插入一個節點n如果它與Box(n)相交。這可以使用分離軸定理GLM96有效地進行測試。如果一個節點 n 包括的三角形屬于不同的修補程序，n被拆分，三角形被分發給其子節點。最后，中心的 每個屬于兩個或多個修補程序的三角形的最優級節點n表示一個模糊頂點。 為了提高附近關鍵區域的解決方案，我們還計算

13、出每個關鍵頂點從拍攝光線M沿著坐標軸的直線距離（圖3）。幸運的是，我們建立了上面的臨時八叉樹已經提供了一個空間搜索結構來加快射線模型相交測試。如果我們發現一個單位距離內的交叉點，我們用頂點v組成三元組，以為方向，以為距離作為切口。這些切口將在以后用于幾何結構體中所有點的重采樣。數字顯示，切口用小箭頭附加到v并指向方向 d來舉例說明，請參見圖 3。 在前一階段我們計算一個集 的關鍵頂點，我們認為是填補所有縫隙的粒子。算法的后期將提取邊界C 創建表面修補程序，實際上縮小這些縫隙并解決了交叉。由于這些填充應盡可能少的改變M，所以C應該盡可能的小。因此我們通過填充所有空隙的最小集 替換 C。我們通過對

14、 C應用拓撲維護侵蝕算子得到 ，即我們從簡單的 C開始先后刪除關鍵頂點。（請注意我們只能刪除關鍵頂點但不是切口）。直觀地，一個頂點稱為簡單點，如果刪除不會更改拓撲結構 C，即如果它不創建或處理新的連接組件。簡單點的確切定義，以一種有效的方法確定一個頂點是否簡單是從其 26 個鄰居BK03 中確定的。然而,我們必須考慮,在我們的例子中切口代表物質,而在BK03切口代表空白區域。我們的過程如下：對于每個關鍵頂點V，我們計算它到邊界的距離d(v)。如果v有一個非關鍵鄰域，我們令d(v) = 0。其他關鍵點距離的計算是通過在代表切口的上距離變換實現的，即距離不會在一個切點上傳送。然后，我們刪除層簡單關

15、鍵點來得到一個新的關鍵點集合（圖4（左）和圖5）：層= 0,1 ,., 對于所有d(v)=層的頂點v，如果V是簡單的那么設置V為非關鍵的。正如下面的重建工作將沿著切點發生，切點應在非關鍵點和關鍵點之間。此外，切點不在頂點 和 M之間（圖 4(右)和圖 5）。因此，如果V是一個關鍵點，我們會刪除所有切點和而不是向所有關于V的非關鍵的6個鄰域W中插入切點。在這里，來表達重建算法的 是一個特殊值， 對應于一個填充并且相應的頂點在后處理階段應該是平滑的。圖 4：侵蝕。左圖，我們看到集合的關鍵頂點填補了兩個修補程序之間的空隙。綠色頂點已被拓撲維護侵蝕算子刪除。沒有斷開的兩個修補程序不能刪除紅色頂點。右圖

16、：每個剩余（藍色）頂點被替換通過指向頂點的切點。現在所有的切點形成面，在算法的后階段被提取用來填補表面修補程序的縫隙。關鍵單元格 屬于的關鍵點 刪除切口 額外切口圖5：示例配置 （續），拓撲維護侵蝕算子（3.3 節）縮小到對于一個由額外切點包圍的較小集合。網格單元格是與屬于的關鍵頂點相鄰的或和被標記為關鍵的多個修補程序相交的（3.4節）。 在這一階段，我們將一個關鍵的網格單元格D集合將 M剪切成一個內部和一個外部組件，內部組件包含所有組件的模型。然后丟棄內部組件，取而代之的是一個如3.5節所描述的完好重建。 首先，我們要確定關鍵網格單元格 D的集合。D應包括M的所有組件，即所有的交叉點和所有的

17、縫隙，我們設定這個網格單元為關鍵的，如果它包含M的兩個或多個修補程序 (交叉點) 或如果其事件頂點之一是關鍵的 (縫隙) 圖 5 顯示了M的某些示例配置和它們相應的關鍵網格單元格。下面，我們將表示一個網格面為關鍵，如果它共享一個非關鍵和關鍵的單元格。網格邊稱為關鍵事件，如果事件是一個關鍵面。 其基本思想是分裂沿著關鍵面M的 所有三角形為子三角形，這樣每個子三角形要么完全在關鍵區域D的內部要么完全在關鍵區域D的外部。然后，我們簡單地拋棄那些完全位于內部的三角形。 雖然相交平面的數學問題簡單，而實際執行一個有效的數值模擬的裁剪算法是一個困難的問題。下面我們將提出一個專門為我們設置的新的算法。在運行

18、算法的所有時期內，網格將保留在三角形網格中。我們沒有處理任意價的一般多邊形，包括孔等。實際上，我們僅僅使用歐拉操作拆分 1-3 和拆分 2-4 （邊緣剝離）來修改網格，并提供大多數網庫的基本操作。通過使用一個混合定點/自適應精度表示頂點的位置，我們獲得沒有健壯性和準確性的相對加速比。這三個階段中的剪切收益在圖 6 中說明。在第一階段，關鍵邊相交、模型面和插入交叉點到該模型使用1至3或2至4拆分。在第二階段，相交的關鍵面和模型邊緣，再次插入相交點使用 2-4 拆分。這個過程會自動產生邊，這些邊是由所有包含關鍵網格面的三角形模型相交產生的。因此每個三角形現在不是完全位于關鍵單元格的內部就是完全位于

19、關鍵單元格的外部。在第三階段我們則只是丟棄那些重心在關鍵單元格中的三角形。 為了有效地枚舉關鍵邊和關鍵面，我們使用由朱報 JLSW02提出的遞歸八叉樹遍歷技術。然而，為了加快算法，在下降到八叉樹單元格之前，我們首先測試是否當前三角形真的與使用分離軸定理的單元格相交。 初始配置 第一階段 第二階段 第三階段圖 6： 初始配置：三角形網格就是對一組關鍵網格單元格進行裁剪。第一階段：通過1到3次拆分或2到4次拆分三角形網格的交叉邊被插入到網格。第二階段：通過2到4次拆分邊緣網格和網格面的交集被插入到網格。現在每個三角形不是完全位于關鍵單元格集合的內部就是完全位于關鍵單元格集合的外部。第三階段：內部三

20、角形將被刪除。執行 如果交叉點被可靠地檢測并正確地計算上述算法才能執行。然而，切換到精確算法，算法會緩慢下來。出于這個原因，我們使用混合形式表示。將該模型輸入頂點的位置量化到N位。對于每個頂點 v，我們將存儲 其確切位置 使用一種自適應精度表示Pri91 ,She97。 及其近似位置 使用一個固定的點表示N位寬度。例如，（請記住，網格的度為）：當計算交點時我們可以使用近似位置評價“易排斥“。考慮例如一個邊e 和網格面f = fmin，fmax的交集。我們首先檢查是否與框相交。這個測試使用最大只有3N 位的Ju04方法準確地評價定點算法。只有這次測試成功，我們才能使用精確算法計算真正的相交點。類

21、似的考慮也適用于三角形邊相交、 邊邊相交、 三角形單元格相交等。現在，我們提出了一個算法來重構內部關鍵單元格的表面。這種算法使用特征元素的敏感性移動立方體和由Kobbelt等人提出的雙輪廓算法。但是，除了要功能敏感外，我們的算法可以處理每個邊的多個切點和外部幾何在關鍵單元格內部重建的無縫連接。我們首先枚舉所有內部網格的面，再次使用八叉樹的遞歸遍歷技術。對于每個內部網格的面，我們收集位于這些面邊緣的切點。請注意網格邊緣可能存在兩個以上的切點，如果一個修補程序與該邊緣相交多次。通過構造，切點的數量總是偶數。此外，切點指向順時針（CW）方向與切點指向逆時針（CCW）方向相互交替。我們現在通過邊連接這

22、些切點： 順時針切點連接到下一個逆時針切點以逆時針方式圍繞網格表面 （圖 7，左)，也可以看。如果我們連接來自同一網格邊緣的兩個切點，我們在面的中心處插入一個輔助點來防止拓撲退化。請注意，通過構造，邊不相交。 然后我們依次訪問每個關鍵單元格。創建如上所述的單元格表面的邊或者是外部幾何邊界的邊。在任何情況下，這些邊緣在單元格周圍形成一個或多個連接循環。每一個循環通過三角形扇形成三角形（圖7，右）。由于邊不相交，循環不會交叉所以是三角形風扇。 圖 7：我們通過邊連接切口到一個網格面上（左）。對于每個網格單元格，外部幾何體的邊和邊界邊在單元格周圍形成循環。每一個循環通過三角形扇形成三角形（右）。風扇

23、的中心頂點位置 p的計算是取相交網格單元格中 Lin00的三角形平面距離的最小值。注意如果該單元格包含一個特征邊或角，這種結構將確定 p。如果計算出點p 碰巧超出該單元格，或如果它不在所有的支撐平面內，它將被設置為無效。無效的頂點在后處理階段是平滑的。最后，我們翻轉內部網格面的邊，使中心頂點相連接。這可以保證鄰近單元格的特征頂點通過一個（特征）邊連接（圖8）。采樣頂點 平滑頂點圖8：示例配置（續）。在關鍵網格單元格中的幾何體替換一個重建表面R，R是從切點通過使用變種移動立方體算法提取的。R 的一些頂點可以直接從M中進行采樣。不過，其他對應于R的那些部分覆蓋M的縫隙。這些頂點的位置是由一個迭代的

24、平滑篩選器決定的。平滑 之后的重建階段處理以下類型的頂點的位置尚未確定。對應于重建部分的頂點跨越 M 的縫隙，因此沒有確定的位置。這些頂點要么從切點分離出來要么在三角形扇的中心創建一個空的網格單元格。在網格單元中的三角形風扇中心的頂點包含沖突幾何通常由于一個不足細化深度 k 。在這兩種情況下我們通過應用迭代平滑過濾器 Tau95平滑頂點位置。 抽取 重建算法的輸出是一個封閉的流形三角形網格T，它接近輸入模型M并已解決所有項目。然而，由于縫隙附近的人工細化T通常比M0包含更多的頂點和面。這可以歸因于兩方面因素：每個修補程序的輸入模型通過共同邊T表示。基礎網格的分辨率越高，在關鍵區域重建模型就需要

25、越多的三角形。因此，我們有兩個選擇減少輸出的復雜性。首先，網格T通常包括多個相關連的組件，只有少數幾個對M的外部有真正的作用。其他組件只是從內部被分成三角形M，因此可以很容易地確定并丟棄。該標識可以通過洪水手動或自動填充過程如Ju04。第二，我們應用一個標準功能敏感網格抽取算法到 T GH97。然而，為了保持M的輸入鑲嵌，我們只能在重建地區這么做。4結果 在大量不同復雜性的CAD 模型中我們評價了我們的方法（圖 9，10，11)。所有的節點被送到一個 2 GB，3.2 GHz 的奔騰 4 電腦上。輸入參數的選擇 我們的算法只重構文物附近的地區和本地重建在后加工階段進一步被消滅，輸出復雜性的典型增長通過次級線性體現網格決議。因此，我們可以使用高網格決議來提高三角形重建質量而不會產生不必要的開銷。如果輸入修補程序的鑲嵌是足夠準確地，我們可以設置 即使對于高決議也不會錯過任何縫隙。漸近行為 如果工件形成一維子空間例如沿著兩個相交表面或沿兩個毗鄰補丁，關鍵頂點和單元格的數量關于網格決議對常數在理論上呈線性增長。我們的實驗結果與理論描述相吻合，只有相機模型（圖10）是個例外因為它包括許多內部幾何和“雙墻”。這些工件不能有效地得到解決，因此，關鍵點和單元格實際上形成了一個二維或三維子空間。在這些地區八叉樹不得不細化到最大深度，這會導致內存使用量顯著增加。 圖9 直升機 圖