[發明專利]基于最遠點優化的藍噪聲網格生成方法

有效

• 申請號: 201410283442.1
• 申請日: 2014-06-23
• 公開（公告）號: CN104036552B
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 嚴冬明;郭建偉;張曉鵬
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06T17/30
• 分類號: G06T17/30
• 代理公司: 中科專利商標代理有限責任公司11021
• 代理人: 宋焰琴

技術領域

本發明屬于計算機圖形處理技術領域，具體涉及計算機圖形處理中的藍噪聲采樣技術和網格生成技術，特別涉及一種從隨機分布的采樣點集進行優化采樣點位置，并利用采樣點生成三角網格的方法。

背景技術

網格模型是三維形體在計算機中表示的主要方法之一。網格模型主要包括三角形，四邊形或者多邊形網格。其中，三角形網格由于結構簡單，易于操作從而受到了廣泛的關注。因此，高質量三角形網格的生成方法也成為了圖形學以及數字幾何處理領域的一個研究熱點。常見的三角形網格獲取有三種方法：(1)通過激光掃描儀掃描得到的粗糙網格數據；(2)通過離散連續曲面；以及(3)通過等值面提取得到的網格模型。通常，這些模型有數據量大，三角形網格質量差等缺點，不能直接用于比如有限元模擬，計算機動畫等高級應用。Yan等人(D.-M.Yan,B.Lévy,Y.Liu,F.Sun,and W.Wang,“Isotropic remeshing with fast and exact computation of restricted Voronoi diagram,”Computer Graphics Forum,vol.28,no.5,pp.1445–1454,2009)提出了提出一個在網格模型上計算準確的Voronoi圖的算法，在這個算法的基礎上，結合快速的重心Voronoi圖(Centroidal Voronoi Tessellation-CVT)計算框架，生成高質量的網格。這個算法效率高，可以處理帶噪聲的網格，是目前網格生成領域公認的最好的方法。

但是現有的曲面網格生成研究主要針對如何提高三角形的質量，而忽略了網格頂點的整體分部。在許多領域的應用中，都要求采樣點的分布既滿足隨機性又滿足均勻性，這些性質統稱為藍噪聲性質，藍噪聲性質和人類的視覺感知系統密切相關，在圖像合成，真實感繪制，機器人路徑規劃等領域有著大量應用。現有的藍噪聲采樣方法可以大致分成三類：(1)泊松圓盤采樣方法及其變種；(2)基于Lloyd迭代的優化方法；(3)基于樣本或者規則的生成方法。其中，等人(T.,HECK,D.,DEUSSEN,O.:Farthest-point optimized point sets with maximized minimum distance.In High Performance Graphics Proceedings(2011),pp.135–142.)提出利用最遠點采樣優化(Farthest Point Optimization-FPO)算法計算藍噪聲采樣點集。該方法的核心思想是最大化采樣點集中任意兩點的最小距離。FPO將采樣點集的藍噪聲性質進一步提高。但是，現有的FPO只能處理二維平面的等半徑采樣，不能處理變半徑和曲面上的采樣。

藍噪聲采樣以及網格生成分別都有幾十年的研究歷史，但是很少有工作將兩者結合起來同時研究。近年Ebeida等人(Ebeida,M.S.,Mitchell,S.A.,Davidson,A.A.,Patney,A.,Knupp,P.M.,and Owens,J.D.(2011).Efficient and good Delaunay meshes from random points.Computer-Aided Design,43(11):1506–1515.)提出一個有效的算法將具有藍噪聲性質的最大化泊松圓盤采樣點集(MPS)進行三角化，得到的網格具有很多良好的性質。Yan和Wonka(Yan,D.-M.and Wonka,P.(2013).Gap processing for adaptive maximal Poisson-disk sampling.ACM Trans.on Graphics,32(5):148:1–148:15.)首次提出網格曲面上的最大化泊松圓盤采樣(Maximal Poisson-disk Sampling-MPS)方法及重新網格化方法，推動了藍噪聲網格生成的發展。

發明內容

本發明提供一種在曲面網格上進行藍噪聲優化采樣，并利用優化的采樣點生成高質量三角網格的方法，以解決現有的網格生成方法生成的網格頂點分布差、不適于物理模擬、且不易控制最小角度的缺點。

為實現上述目的，本發明提供一種基于最遠點優化的藍噪聲網格生成方法，該方法包括以下步驟：

步驟S1、在輸入的三角網格上根據密度函數進行隨機采樣，產生初始采樣點集；

步驟S2、利用基于最短邊刪除的方法對初始的采樣點集進行預處理，以改善所述采樣點集的分布；