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

有效

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

1.一種三角網格數據的布爾運算的方法，其特征在于，所述方法包括如下步驟：

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

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

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

2.根據權利要求1所述的方法，其特征在于，所述步驟A包括：

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

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

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

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

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

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

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

3.根據權利要求2所述的方法，其特征在于，所述步驟A1包括：

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

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

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

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

4.根據權利要求2所述的方法，其特征在于，所述步驟B包括：

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

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

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

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

5.根據權利要求4所述的方法，其特征在于，所述步驟C包括：

C1、采用層次包圍盒樹碰撞檢測方法，計算出所述新規整化的兩個三角網格的局部三角網格的相交三角形對，以及所述相交三角形對中的每一個三角形上的交線；

C2、將所述相交三角形對標記為應刪除狀態，對每一個相交三角形使用三角化方法根據其交點和三角形頂點重新生成三角形；

C3、動態構建一個或者多個新局部三角網格的頂點數組、三角形數組和相鄰關系數組，以所述交線為邊界，將未標記為應刪除狀態的所述新規整化的兩個三角網格的局部三角網格數據，以及使用所述三角化方法生成的三角形寫入所述新局部三角網格的數組中；

C4、判斷每一個新局部三角網格與所述新規整化的兩個三角網格的局部三角網格的內外關系；

C5、根據判斷后的所述每一個新局部三角網格與所述新規整化的兩個三角網格的局部三角網格的內外關系和布爾運算類型，標記需要輸出的新局部三角網格的組合，并輸出對應的三角網格。