[發明專利]用于網格模型孔洞解除的數據處理方法及裝置

在審

• 申請號: 201410814479.2
• 申請日: 2014-12-23
• 公開（公告）號: CN104504660A
• 公開（公告）日: 2015-04-08
• 發明（設計）人: 王超;余強
• 申請（專利權）人: 北京數碼大方科技股份有限公司
• 主分類號: G06T5/00
• 分類號: G06T5/00
• 代理公司: 北京康信知識產權代理有限責任公司11240
• 代理人: 李志剛;吳貴明

技術領域

本發明涉及數據處理領域，具體而言，涉及一種用于網格模型孔洞解除的數據處理方法及裝置。

背景技術

隨著產品迭代速度與個性化需求的不斷提高，產品設計要求越來越迅速與準確，因此基于原型的改型設計被廣泛應用。逆向工程利用3D掃描技術獲得產品原型的點云數據，并進一步處理得到數字化產品網格模型，可以大大加快改型設計的速度。

但在3D掃描中，由于設備限制或產品自身特點，生成的點云常不能包含完整連續的原型特征，導致隨后的網格模型擁有大量孔洞。這些孔洞對基于網格模型的進一步改型設計有重大影響。為解決這個問題，逆向工程的建模引入了孔洞修補的概念。

在孔洞修補中，由于實際產品形狀常為復雜型面實體，3D掃描得到的三維點云數據常常在局部區域存在空間點分布不均勻以及曲率變化劇烈的情況。由這類點云數據生成的網格模型很容易出現孔洞缺陷，且孔洞本身形狀很不規則，出現諸如單點連多三角形孔洞)等復雜孔洞的情況，如圖1為單點連多三角形孔洞的示意圖。單點連多三角形孔洞形式多樣，可能是連環孔洞(如圖2為連環洞形式的單點連多三角形孔洞的示意圖)、島(如圖3為島形式的單點連多三角形孔洞的示意圖)、橋(如圖4為橋形式的單點連多三角形孔洞的示意圖)等多種情況，這種孔洞形式往往造成孔洞形狀變得崎嶇糾結，若未進行處理而直接修補可能導致孔洞修補算法產生畸形網格甚至無法建立拓撲結構。

為了修復單點連多三角形等復雜孔洞，需要解除復雜孔洞，將復雜孔洞分解為多個單連通環域，為后續的孔洞修補做好準備。

針對單點連多三角形孔洞，現有的解除方法是先找到連多孔洞的單點，從該點處開始對所有可能邊緣路徑進行遍歷，直到找到閉合的最小回路，再從下一個連多孔洞的單點開始遍歷查找，循環遞歸，直到所有子孔洞被分離。遍歷所有可能路徑的方法會耗費大量時間，主要原因在于：

(1)一個單點的遍歷需要耗費時間。

一個單點可能需要遍歷的次數較多，并且每個單點都要進行路徑回路長度比較，二者均會耗費時間。在某些情況下，這種時間耗費可能會加倍。如圖4所示，一個大孔洞內增加了一片橋狀懸浮片，導致此連環孔洞內有兩個單點需要循環，而且每個單點都有6條閉合路徑可供選擇，總共需要遍歷12次，外加比較回路長度和選取回路，若是大規模的孔洞，將耗費大量的時間。

(2)多點復雜環路的遍歷過程需要耗費時間。

當針對擁有多個單點的復雜環路時，路徑可能會急劇增加，對一個點的所有路徑進行遍歷，耗費了一定的時間；當解開一個孔洞后，再解下一個點的連環孔洞時，這種幾個點解環遍歷疊加在一起也會降低軟件運行的效率。

針對相關技術中對網格模型中的孔洞進行解除處理時執行效率低的問題，目前尚未提出有效的解決方案。

發明內容

本發明的主要目的在于提供一種用于網格模型孔洞解除的數據處理方法及裝置，以解決對網格模型中的孔洞進行解除處理時執行效率低的問題。

為了實現上述目的，根據本發明的一個方面，提供了一種用于網格模型孔洞解除的數據處理方法。

根據本發明的用于網格模型孔洞解除的數據處理方法包括：確定網格模型，其中，網格模型包括外邊，外邊為網格模型中僅存在于一個三角形中的邊，外邊包括第一外邊，第一外邊具有第一端點和第二端點，第一端點為非多邊點，非多邊點為僅被兩條外邊共用的端點；判斷第二端點是否為多邊點，其中，多邊點為被兩條以上外邊共用的端點；如果第二端點為多邊點，則確定與第二端點拓撲連續的端點為第三端點，其中，第三端點為第二外邊的端點，第二外邊和第一外邊共用第二端點；執行孔洞解除處理，其中，按照拓撲連續的方向對網格模型包括的外邊的端點進行遍歷，獲取網格模型中的單連通孔洞。

進一步地，確定與第二端點拓撲連續的端點為第三端點包括：確定第一拓撲結構，其中，第一拓撲結構為第一外邊所屬的拓撲結構，第一拓撲結構為一層拓撲結構；確定第二拓撲結構，其中，第二拓撲結構為與第一拓撲結構連續的拓撲結構，并且第二拓撲結構為包含第二端點的一層拓撲結構；確定第二拓撲結構包含的與第二端點共同屬于一條外邊的端點為第三端點。

進一步地，通過以下方法確定第一端點和第二端點：獲取外邊集合，其中，外邊集合為網格模型中包含的所有的外邊的集合；確定端點集合，其中，端點集合為網格模型中包含的所有的外邊的端點的集合；建立外邊集合和端點集合的映射關系，其中，映射關系為外邊和端點的對應關系；從端點集合中查找一個非多邊點作為第一端點；根據映射關系確定第二端點。