[發明專利]一種基于GPU加速的維諾圖三維網格重構方法

在審

• 申請號: 201711071102.2
• 申請日: 2017-11-03
• 公開（公告）號: CN108053483A
• 公開（公告）日: 2018-05-18
• 發明（設計）人: 王莉莉;韓嘉偉;蘇濤
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06T17/30
• 分類號: G06T17/30;G06T1/20
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

本發明涉及一種基于GPU加速的維諾圖三維網格重構方法，包括以下步驟：利用k?dtree查找三角網格與輸入點數據的空間鄰近關系并將鄰近關系解釋為點數據的維諾圖，利用空間切割算法計算維諾圖和三角網格的交集并以此計算點數據的能量，更新點位置，多次迭代直至能量函數收斂，并通過Delaunay三角化算法構造新的網格。本發明借助GPU強大的并行計算能力，大大提高了算法的計算速度和效率。

技術領域

本發明屬于三維網格重構技術領域，具體涉及基于維諾圖特性和GPU的通用計算加速的網格重構方法。

背景技術

三維網格模型作為三維媒體的一個重要載體得到了越來越廣泛的關注與應用，在工業制造、數字娛樂、數字文化遺產、智能城市等方面發揮了重要的作用。近年來，隨著計算機處理能力的提高和三維掃描技術以及視覺重建技術的發展，三維網格模型的獲取變得更加容易和快捷。但是，初始獲得的粗糙模型通常存在各種缺陷，很難直接用于各種計算，通常需要進行去噪，修補，簡化，以及重采樣等處理以滿足應用需求。

目前三維網格模型主要由如下幾種方式獲得：(1)通過激光掃描儀掃描得到粗糙點云數據并進行重建；(2)通過對連續曲面離散化；(3)通過對體數據或者隱函數的等值面提??；(4)通過計算機視覺方法獲得(比如通過多角度圖像重建，或者通過三維模型的輪廓線重建等)，如圖1所示。通常情況下，這些模型往往存在數據量大、網格質量差等缺點，不能直接用于比如有限元模擬、計算機動畫、三維打印等對網格質量要求很高的應用中。重新網格化(Remeshing)，是在輸入網格的基礎上，在保持拓撲信息不變的前提下對網格進行重采樣并且網格化，以滿足不同應用的各種需求。

Voronoi cells方法是生成非結構網格的常用方法之一，通常的文獻都稱之為Delaunay triangulation方法，這是因為人們一般都采用與Voronoi cells等價的Delaunay triangles的數據結構和算法?；赩oronoi本身結構的特性，將普通的三角網格結構轉化為有Delaunay triangles，能大大的增強復雜模型在解決問題的時候的健壯性。同時維諾圖生成網格時還使用了樹狀搜尋方法，本身就具有高效性，為之后實時重構鋪下了基礎。

此外，在巨大的游戲市場的驅動下，圖形處理器GPU(Graphics Processing Unit)正在快速地發展。GPU的運算能力已經高于CPU。GPU與CPU相比，在浮點運算能力，內存帶寬，價格上都體現了極大的優勢。然而由于GPU的硬件構造是為圖形顯示而設計，并不適合完成CPU所進行的通用計算任務。隨著今年來對于GPU通用計算的研究，以及GPU廠商的推動，現在出現了較為完善的通用計算編程語言和GPU的驅動。在支持通用計算的GPU中，頂點著色器，幾何著色器，以及像素著色器都是高度可編程的。對于用戶來說這些著色器統一成為流處理器。

當前主要的GPU通用計算語言包括CUDA和OpenCL(Open Computing Language)。英偉達公司提出CUDA并行計算架構。CUDA利用GPU的浮點計算能力，可大幅度提升計算性能。CUDA是針對NVIDIA顯卡架構進行特別設計和優化的GPU通用計算語言。OpenCL則是由蘋果公司提出的，多家公司共同聯合開發的，跨平臺異構系統的通用計算語言。OpenGL是可以運行在不同廠商GPU，CPU，DSP，等處理器上而不需要進行代碼改寫的異構平臺的通用計算語言。