[發明專利]三角網格數據的布爾運算方法及其系統

有效

• 申請號: 201210149907.5
• 申請日: 2012-05-15
• 公開（公告）號: CN102682476A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 葉建平;張吉帥;郭李云;張磊
• 申請（專利權）人: 深圳市旭東數字醫學影像技術有限公司
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 黃韌敏

技術領域

本發明涉及幾何建模技術領域，尤其涉及一種三角網格數據的布爾運算方法及其系統。

背景技術

幾何建模技術是指計算機里組織數據類型和數據結構以表示物體在空間的形狀、尺寸及位置信息。目前大量使用在3D游戲和動畫，計算機輔助設計，電影特效，數字城市，地質建模，分子生物學，數字醫學等領域。三維空間的幾何模型簡稱為三維模型，主要有線框模型、表面模型和實體模型三種表示方法，其中表面模型運用最為廣泛，三角網格數據是表面模型的一種常用形式。幾何模型布爾運算是指對兩個模型的空間信息進行并、交、差等操作以得到新的模型。在建立和處理復雜模型時，可運用布爾運算對模型進行靈活的加工和修改。

現有的商用幾何建模軟件有AutoCAD,SolidWorks,Maya,3dMax,UG等，都集成了三維模型布爾運算功能，但目前的布爾運算方法要求參與布爾運算的模型必須是封閉的，而且在處理大規模的模型數據時速度較慢，存在多次運算導致軟件速度下降甚至出錯的問題。

綜上可知，現有的幾何建模技術在實際使用上，顯然存在不便與缺陷，所以有必要加以改進。

發明內容

針對上述的缺陷，本發明的目的在于提供一種三角網格數據的布爾運算的方法，以降低了三角網格數據的布爾運算出錯的概率，提高了布爾運算的計算速度；

為了實現上述目的，本發明提供一種三角網格數據的布爾運算的方法，所述方法包括如下步驟：

A、對采用三角網格表示的三維模型進行懸邊、懸點消除和重合點歸并處理，獲得新規整化的兩個三角網格；

B、提取包含所述新規整化的兩個三角網格的相交區域的局部三角網格；

C、將所述局部三角網格進行碰撞檢測計算、三角剖分、網格重構、內外關系判斷以及布爾運算，拼接且輸出新的三角網格表示的三維模型。

根據所述的方法，所述步驟A包括：

A1、分別獲取所述三角網格中的每個三角形的頂點數組、三角形數組以及相鄰關系數組，并且分別構建兩個新的三角網格；

A2、順序訪問每個所述三角形的三角形數組的拓撲單元，若已經完成全部所述三角形訪問，則執行步驟A5；

若沒有完成全部所述三角形訪問，則取出每個所述三角形的三個頂點索引；若所述三個頂點索引中的兩個或者三個頂點索引相同時，則所述拓撲單元為退化單元三角形，丟棄所述退化單元三角形,并重新開始執行所述步驟A2，順序取出下一個拓撲單元；在所述三個頂點索引中的三個頂點索引均不相同時，則執行步驟A3；

A3、根據所述三個頂點索引在所述頂點數組獲取頂點坐標，并以不重合的方式插入到新構建的頂點數組中；

A4、將所述三個頂點索引作為一個拓撲單元插入新構建的三角形數組中，并且返回所述步驟A2，順序取出下一個拓撲單元，重新開始執行所述步驟A2；

A5、順序訪問所述新構建的三角形數組，根據每個拓撲單元的三個頂點索引將三角形索引寫入頂點對應的相鄰關系數組行中；

A6、查看所述三角網格中的所有相鄰關系數組，將所述相鄰關系數組中沒有數據的行所對應的頂點標記為不可用狀態。

根據所述的方法，所述步驟A1包括：

A11、使用線性浮點型數組保存所述三角網格中的每個三角形的頂點坐標，獲得所述三角網格的頂點數組；

A12、使用線性整數型數組保存所述三角網格的頂點索引，獲得所述三角網格的三角形數組；

A13、使用二維整型數組保存所述三角網格中的每個三角形的頂點所屬的三角形索引，獲得所述三角網格的相鄰關系數組；

A14、根據所述三角網格的頂點數組、三角形數組以及相鄰關系數組分別構建兩個新的三角網格。

根據所述的方法，所述步驟B包括：

B1、分別查看所述新規整化的兩個三角網格的頂點數組，計算所述新規整化的兩個三角網格的X、Y、Z坐標的最大值和最小值，構成兩個包圍盒；

B2、分別構建所述新規整化的兩個三角網格的局部三角網格的頂點數組、三角形數組和相鄰關系數組；

B3、分別查看所述新規整化的兩個三角網格的局部三角網格的三角形數組，若其中一個所述新規整化的三角網格的三角形有一個頂點處于另一個所述新規整化的三角網格的包圍盒范圍內，則將所述三角形標記為應刪除狀態；

B4、將在所述包圍盒范圍內的新規整化的三角網格的三角形的頂點、拓撲單元以及相鄰關系寫入所述新規整化的兩個三角網格的局部三角網格的頂點數據、三角形數組以及相鄰關系數組中。

根據所述的方法，所述步驟C包括：