[發明專利]一種流形曲面模型有序邊緣鏈快速求解方法

在審

• 申請號: 202310550114.2
• 申請日: 2023-05-16
• 公開（公告）號: CN116630574A
• 公開（公告）日: 2023-08-22
• 發明（設計）人: 宋小文;趙曉陽;單巖;陳曉坤
• 申請（專利權）人: 浙江大學
• 主分類號: G06T17/20
• 分類號: G06T17/20;G06T17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 鄭海峰

本發明公開一種流形曲面模型有序邊緣鏈快速求解方法，對象為基于三角面元的流形曲面所表示的三維模型；主要內容為：創新邊緣鏈求解思路，通過優先判斷流形曲面模型在±X、±Y、±Z六個方向的最值端點結合奇偶分別遍歷的方式，快速求解第一邊緣點，有效提高求解速度；提出精準邊緣點判據，結合第一邊緣點與其他邊緣點的鄰近關系，依次遞推，直接確定邊緣鏈，規避了完全遍歷的時間與算力浪費問題，提高求解速度的同時所求邊緣鏈自帶先后順序，無需額外整理順序；提出非半邊數據結構下的邊緣鏈獲取方法，基于多數組代替半邊數據結構，徹底解決半邊數據結構帶來的信息冗余和算力浪費問題，增廣了可解模型范圍，也為算法跨語言部署提供前提條件。

技術領域

本發明屬于三維圖形技術領域，具體涉及一種流形曲面模型有序邊緣鏈快速求解方法。該方法適用于提取流形曲面模型邊緣鏈，用于模型展平、貼圖、渲染等。

背景技術

隨著硬件能提供更高的算力，計算機圖形學技術得到了極大的發展，催生了一系列模型處理的方法。

由于足夠多的三角面元組成的流形曲面可逼近任意復雜的曲面，數據結構精簡，從而被廣泛應用于模型的表示，隨之衍生出模型展平、貼圖、渲染等技術。

其中，模型展平技術在醫學觀察、模型外觀繪制、計算機輔助設計領域均有應用，而獲取模型邊緣，以識別內外頂點，是模型展平操作前的必要步驟。

獲取模型邊緣鏈需要訪問模型點、線、面元之間的相鄰關系，一般的做法是，將模型轉化為半邊數據結構，半邊數據結構按照指針變量的方式儲存了上述關系，可直接通過指針變量訪問，但對于無指針概念的計算機語言，如JavaScript、TypeScript等，構建和訪問半邊數據結構并不靈活，即此方法有局限性；

與此同時，將模型轉化為半邊數據結構的過程將浪費算力；對于獲取邊緣鏈的任務而言，不會使用到半邊數據結構的中的半邊信息，故而浪費儲存。此外，一般的做法按照“先全部識別，再排序整理”的方式先通過遍歷的方式識別出全部邊緣頂點，再將邊緣頂點進行整理排序，顯然此過程繁瑣，且浪費計算資源；故需要一種通用、高效的模型邊緣獲取方法。

發明內容

為了解決格式如.stl、.obj、.babylon等由三角面元構成的流形曲面所表示的模型邊緣鏈提取的任務中，傳統做法僅單一地完全遍歷分析所有點，得到的邊緣點缺少先后秩序的問題、使用無指針概念的編程語言，如JavaScript、TypeScript等構造半邊數據結構不靈活的問題、以及半邊數據結構造成的信息冗余問題、構造半邊數據結構造成的算力浪費問題、非半邊數據結構下難以求出帶順序的邊緣鏈的問題等，本發明提出了一種流形曲面模型有序邊緣鏈快速求解方法。本發明提供了跨語言編程的基礎、高效、快速、求出的邊緣鏈自帶順序，無需整理。

為解決上述技術問題，本發明所采用的技術方案是：

本發明提供了一種流形曲面模型有序邊緣鏈快速求解方法，包括以下步驟：

步驟S01:導入流形曲面模型數據；

步驟S02:分別解析出模型的頂點、面元數據集合，并儲存為頂點數組P、面元數組F；

步驟S03:解析并形成所有頂點相接面元集合，并儲存為數組Wheel；

步驟S04:分別解析出對應±X、±Y、±Z六個方向的最值端點，判斷其中是否有邊緣點，若有，則將發現的第一個邊緣點儲存為數組predge的第一個元素predge(1,1)，并執行步驟S06；若沒有，則執行步驟S05；

步驟S05:此時，步驟S04中的點均被判斷為內部頂點，內部頂點即流形曲面上被邊緣鏈所圍區域中的點，內部點和邊緣點成對立關系；按編號先奇數再偶數依次遍歷分析各點，直到解析出第一個邊緣點為止，并儲存為數組predge的第一個元素predge(1,1)；