[發明專利]一種三維圖形自動簡化生成方法

有效

• 申請號: 201711071200.6
• 申請日: 2017-11-03
• 公開（公告）號: CN107945258B
• 公開（公告）日: 2021-01-12
• 發明（設計）人: 鄭家祥;栗韶遠;唐睿;王銳
• 申請（專利權）人: 杭州群核信息技術有限公司
• 主分類號: G06T15/00
• 分類號: G06T15/00;G06T7/13
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

1.一種三維圖形自動簡化生成方法，包括以下步驟：

在預處理三維圖形的基礎上，通過對三維圖形中幾何變化顯著的位置引入虛擬邊界，并將所述虛擬邊界的邊界約束添加至對應頂點的二次誤差矩陣中，具體過程為：

對于面片f，計算所述面片f對應的二次誤差矩陣Q^f，計算公式為：Q^f＝(A,b,c)＝(n·n^T,d·n,d²)，其中，面片f的平面方程為n·(x-v)＝0，n為面片f的法向量，v為平面上任一點，d為-n·v；

當面片f中的邊e＝(v₀,v₁)對應的兩個面片的法向差超過預設閾值時，對邊e增加邊界約束Q^e，所述邊界約束Q^e的定義與Q^f相同，僅是邊界約束Q^e中定義中的(n，b)表示通過邊e并垂直于面片f的一個面；將Q^e和Q^f按權重疊加至面片f對應頂點的二次誤差矩陣vQ；

當面片f中的邊e＝(v₀,v₁)對應的兩個面片的法向差沒超過預設閾值時，將Q^f增加至面片f對應頂點的二次誤差矩陣vQ；

對邊進行預檢查以確定所述邊對應面片的法向變化程度，并根據所述法向變化程度與所述邊的二次誤差矩陣確定邊的簡化優先級，具體過程為：

定義簡化優先級priority＝f(qerror)/g(cosin)；

qerror為邊的二次誤差；

cosin為所述邊對應面片的法向變化程度；

當qerror大于0時，函數f(qerror)與函數g(cosin)均為單位函數；

當qerror接近0時，加大cosin對簡化優先級的影響程度；

當cosin小于變化閾值時，定義函數f(qerror)為邊長度的負反比，g(cosin)為1–cosin；

當cosin大于變化閾值時，直接將簡化優先級設為Inf；

按照簡化優先級，迭代收縮最小二次誤差對應的邊，并更新所有關聯面片對應的邊的二次誤差矩陣和簡化優先級，滿足迭代終止條件后，輸出自動簡化生成的三維圖形。

2.如權利要求1所述的三維圖形自動簡化生成方法，其特征在于，所述預處理三維圖形，包括：

根據所述三維圖形對應包圍盒的大小，歸一化處理所述三維圖形；

對歸一化處理后的三維圖形，構建頂點與邊的連接關系；

在構建頂點與邊的連接關系時，增加一條虛擬邊于沒有連接關系且靠得非常近的頂點之間，具體為：

對每個頂點的幾何坐標(x,y,z)，以一個步長對三個維度分量進行離散化以變換到整數空間上，并哈希處理三個整數以確定每個頂點的哈希值；創建哈希值一致的頂點之間的連接關系。

3.如權利要求1所述的三維圖形自動簡化生成方法，其特征在于，所述按照簡化優先級，迭代收縮最小二次誤差對應的邊，并更新所有關聯面片對應的邊的二次誤差矩陣和簡化優選級，包括：

迭代簡化過程為：

在確定邊的簡化優先級后，將包含邊、邊對應的最優頂點、邊對應的二次誤差矩陣、邊的簡化優先級的四元組按照簡化優先級順序排列，形成簡化優先隊列；

按照簡化優先級，選擇簡化優先隊列中最小二次誤差對應的邊e＝(v₀,v₁)，在v₀和v₁的標志位均不為0，且不滿足迭代終止條件下，將邊e合并成其對應的最優頂點，并更新該最優頂點影響的邊的邊的二次誤差矩陣和簡化優選級。