[發明專利]基于邊收縮的網格參數化方法

在審

• 申請號: 201410382276.0
• 申請日: 2014-08-06
• 公開（公告）號: CN104157012A
• 公開（公告）日: 2014-11-19
• 發明（設計）人: 葉修梓;陳志楊;錢江;方萃浩
• 申請（專利權）人: 杭州新迪數字工程系統有限公司
• 主分類號: G06T17/20
• 分類號: G06T17/20
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 王桂名

技術領域

本發明涉及一種三角網格模型的參數化方法，尤其是涉及一種基于邊收縮的網格參數化方法。

背景技術

網格參數化是一種非常重要的數字幾何處理工具，它適用于計算機圖形、計算機輔助幾何設計、數字幾何處理等學科及其交叉研究領域，廣泛應用于紋理映射，網格編輯，網格變形，網格數據壓縮等方面。

網格參數化的分類有以下幾種：(1)根據參數域的不同，可以分為平面參數化、球面參數化和基于簡化網格的參數化；(2)根據參數化保留內在不同幾何變量的變形，可以分為保面積參數化、保角參數化和等距參數化；(3)根據算法的計算復雜度可以分為線性方法和非線性方法等。

網格參數化有很大的差異，各種方法涉及的算法和技術也差別很大。但目前的研究主要集中于基于簡化網格的參數化，即參數域是原網格的簡化網格。基于簡化網格的參數化，在構建簡化網格的過程中，建立起原網格頂點和簡化網格面之間的參數映射關系。這和一般的參數化，通過求解方程組，建立參數域和原網格的同胚關系有很大的差別。概括起來說，這類參數化算法有這些特點：(1)單純的構建頂點的映射關系，參數化無需求解線性方程組；(2)簡化網格多分辨率的特性，也賦予這類參數化算法多分辨率的優點；(3)簡化網格若在簡化過程中，保持和原網格同胚而不退化(即和原網格有相同的虧格)，它無需考慮原網格是否封閉或有界的問題。

基于簡化網格參數化的思想來源于Hoppe的漸近網格算法(Progressive?Meshes)，其經過一系列簡化操作后獲得簡化網格序列；Lee基于Dobkin－Kirkpatrick算法，一個時間和存儲空間復雜度都大的算法，構建層次化的簡化網格系列；在此基礎上，構造了一個光順的參數化算法(Multiresolution?Adaptive?Parameterization?of?Surfaces，MAPS算法)；在MAPS構建基域的算法基礎上，提出了各種參數化方法，如Wood等采用類似于氣球膨脹的相關方法；Guskov等利用遞歸穿刺的方法構建“Normal?Meshes”；這一類算法都是全局的，即整個網格的參數化被一次建立起來。相對的，也有大量的工作對參數化的局部進行改進，如Guskov等在每個分片上進行局部調整，特別是對分片的邊界，分片頂點的參數化結果，來獲得參數化結果的全局光順。而Khodakovsky等提出了全局光順參數化算法(Globally?Smooth?Parameterization，GSP)，利用新的判別準則構建網格基域，并在構建基域過程中，提出邊穿越(Edge?Classification)算法來構建全局參數化方程組。但是，上述算法對于復雜模型的處理過程比較復雜，而且網格變形容易因為空間臨近關系而造成的變形錯誤，得到的效果還不一定能符合需求。作為構建參數化基域的網格簡化技術，是一個被深入研究的課題。

發明內容

本發明所要解決的技術問題在于提供了一種對復雜三角網格模型的快速、有效、新穎的基于邊收縮的網格參數化方法。

一種基于邊收縮的網格參數化方法，包括下述步驟：

(1)用邊收縮簡化算法計算所有網格邊收縮的權重，按照權重建立起收縮邊堆棧；

(2)依次取堆棧中最優的收縮邊，對網格模型進行邊收縮操作以簡化模型；

(3)在確定收縮邊后，根據收縮邊、收縮邊的頂點、收縮邊的相關邊，構建參數化基域、映射被移除的原網格頂點；

(4)在一個層次的簡化完成后，在最新簡化的網格上重新執行(1)～(3)步驟，當簡化后的三角形個數達到指定的數目時結束。

作為優選，步驟(1)的具體操作為：

(A)進行權重設計，計算每條網格邊的收縮權重和收縮點位置；

(B)采用QEM方法，改變網格拓撲和構建收縮邊堆棧。

Garland的QEM方法既可以保證原簡化網格有良好形態，同時也保證簡化網格基域的三角形形態和均勻性，這對于參數化算法的效果有更重要的作用。

作為優選，步驟(2)采用遞歸的邊收縮方法簡化三角網格模型，具體操作為：