結合邊分割的改進二次誤差測度算法①

張悠然

(長春大學 網絡安全學院, 長春 130022)

三維網格模型在計算機圖形學、計算機動畫、虛擬現實等領域有著廣泛應用, 然而復雜場景的三維模型極大地消耗了帶寬資源、增加了處理時間, 不利于模型的存儲、計算、渲染等. 因此, 通過使用相對簡單的模型代替原始的高細節模型, 即對網格模型進行簡化成為當前的主流方案[1]. 網格簡化指通過刪除或修改對視覺影響不大的點、邊、面來減少網格面片數量[2],對幾何模型在各領域的應用有著重要意義.

自Clark[3]于1976 年提出網格簡化思想以來, 國內外學者對簡化算法進行了廣泛而深入的研究. 其中,1997 年由Garland 和Heckbert 提出的二次誤差測度(QEM)算法是目前使用最廣泛的網格簡化算法之一.QEM 算法運算速度快, 簡化后的模型質量較高, 是一種兼顧速度、質量和通用性的較理想的算法[4]. 然而,該算法僅以點到相關平面距離的二次方作為誤差測度,容易使簡化后的模型失去局部特征和幾何結構, 并且易產生狹長三角面, 導致渲染效果差. 針對上述問題,很多學者提出改進方案. Kim 等人[5]將離散曲率范數與距離度量結合共同作為邊折疊代價, 保留了原始網格的高曲率區域. Tang 等人[6]選擇引入反向成本概念增加高、低曲率差異, 并選擇中點作為新頂點使算法更簡單、直觀. 王繼東等人[7]把三角形法向量約束因子嵌入誤差矩陣中, 讓體積變化平方作為誤差度量, 并自動分配網格疏密, 保留模型局部特征. Li 等人[8]提出考慮紋理的邊緣折疊改進方法, 并提前計算模型邊界以保留模型基本拓撲結構. Mao 等人[9]利用平均二次誤差代替累積誤差作為折疊代價. Tang 等人[10]引入高斯曲率作為簡化因子, 以此保留網格細節特征.

綜上所述, QEM 算法的改進方向多是通過優化誤差度量來保持三維網格模型特征, 沒有重點解決簡化后模型的三角面異常問題. 基于此, 本文提出一種結合邊分割的網格簡化算法. 實驗表明, 該算法簡化后的模型視覺效果更好, 高簡化率下的模型精度更高.

1 QEM 網格簡化算法

QEM 算法實際上是一種基于邊折疊的網格簡化算法. 算法通過頂點對的迭代收縮來簡化三維模型, 即選擇合適的邊進行折疊, 而邊折疊順序依賴于誤差.

1.1 邊折疊操作

邊折疊是一種基于網格邊代價的迭代收縮算法.該算法具有可逆性且折疊代價的計算和更新僅依靠局部信息, 使得算法效率較高.

邊折疊操作前提是計算三角網格邊的折疊代價,每次操作取出隊列最頂端的邊(即折疊代價最小的邊),進行邊折疊操作[11]. 如圖1 所示, 邊v1v2為選中的折疊代價最小的邊.

圖1 邊折疊示意圖

根據邊v1v2的兩個端點v1、v2和局部信息計算出誤差最小的新頂點v0的位置. 刪除頂點v1、v2及兩點所在三角網格v1v2v3和v1v2v6, 刪除相應的邊v1v3、v2v3、v1v6、v2v6. 添加新頂點v0和新生成的邊v0v3、v0v6, 更新頂點v0的局部頂點信息、邊信息的拓撲結構. 重復上述步驟, 直至三角網格數量達到要求.

1.2 QEM 算法

QEM 算法中的頂點對迭代收縮是邊折疊的擴展,頂點對的折疊代價即為邊折疊代價. Garland 等人[4]將頂點誤差定義為點到點所在平面集距離的二次方和,并用二次矩陣保留當前模型的每個頂點近似誤差.

故預先對網格中的每一個頂點定義一個4×4 的誤差矩陣Q, 則頂點v=[vx vy vz1]T的誤差形式確定為其二次項(v)=vTQv. 將空間中的每個頂點與其所在平面相關聯, 定義誤差為點與平面集距離的二次方和, 如式(1)所示:

其中,planes(v)是包含頂點v的所有三角平面集;p=[a bcd]T表示由方程ax+by+cz+d=0所定義的平面, 且a2+b2+c2=1. 由式(1)中的誤差度量可重寫為二次形式:

其中,Kp表示平面p的基本二次誤差矩陣, 如式(3)所示:

通過Kp計算空間中任意頂點到該三角面的距離平方, 則頂點的二次誤差矩陣Q可表示為:

通過計算v誤差的局部最小值得到新頂點的最佳位置, 當Qv可逆時, 計算新頂點v最佳位置的公式如下所示:

綜上, QEM 算法邊折疊代價實則為頂點對(v1v2)收縮后產生的新頂點v的近似誤差,v近似誤差的取決于v1、v2的近似誤差, 即點到與其相關的三角面距離的平方和. 這種僅依靠距離度量作為近似誤差的簡化算法會使簡化后的模型過于均勻, 難以保留局部特征, 不適合高精度、高細節模型的簡化需求. 此外, 頂點對的迭代收縮在消除一些三角面的同時會使新頂點所在三角形的邊長拉長, 容易產生細長三角面, 導致簡化效果差. 因此, 根據上述分析將對QEM 算法進行改進, 改進后的ESQEM 算法能較好解決QEM 算法所存在的問題.

2 改進QEM 網格簡化算法

針對原始QEM 網格簡化算法所存在的問題引入高斯曲率算子和邊緣分割操作, 提出結合邊分割的二次誤差測度(ESQEM)算法.

首先, 只考慮距離度量的QEM 算法會使簡化后的網格和頂點均勻分布, 不利于邊緣特征保留. 因此將能反應頂點尖銳度的頂點高斯曲率加入二次誤差度量中,并提取和保留網格模型邊界點, 以此維護高曲率區域特征和幾何結構. 其次, 在簡化過程中添加邊長查詢機制, 根據網格模型平均邊長設置目標長度、邊中點作為分割點, 對異常三角形進行邊分割操作, 以此消除不規則的邊.

2.1 添加高斯曲率算子

高斯曲率反應了曲面局部彎曲程度, 三角網格上某點的高斯曲率反應該點的尖銳程度, 因而不均勻區域和特征邊緣的高斯曲率較大. 本文采用Kim 等人[12]提出的方法來計算網格中內頂點和邊界頂點的高斯曲率, 頂點高斯曲率與其相連的角度和面積有關, 如圖2.

圖2 頂點高斯曲率

圖2 中θi是三角形fi的內角, 三角形面積用Si表示,n表示與頂點v相連的三角形個數. 則三角網格中內頂點和邊界頂點的高斯曲率計算公式如式(8)、式(9)所示:

若邊e由頂點v1和頂點v2組成,而邊的高斯曲率與邊上的頂點相關[13], 則e的高斯曲率可通過式(10)計算:

其中,K(v1)和K(v2)分別代表邊e兩個端點v1和v2的高斯曲率, 且權重ωi可通過式(11)計算:

在QEM 算法中, 選擇最小的邊代價進行邊緣折疊操作, 以獲得最佳近似結果. 當在邊折疊代價中加入高斯曲率算子后, 便能有效規避具有顯著特征的邊被折疊. 將二次誤差和高斯曲率結合, 獲得新的邊塌陷成本,如式(12)所示:

其中, 權重ω用來平衡高斯曲率K(e)和二次誤差Q(e),且ω可通過式(13)計算:

其中,Qavg和Kavg分別是所有邊的平均二次誤差和平均高斯曲率, 而參數a用于調整K(e)和Q(e)的數量級關系, 通常將高斯曲率設為比二次誤差小兩個數量級.

2.2 邊分割策略

邊分割是三角剖分的一種經典操作. 實質是將離散的點集連接成一定大小的三角形, 而Delaunay 三角剖分的應用最為廣泛. Dyer 等人[14]定義非Delaunay 邊為兩個對角之和大于π的邊, 并通過遞歸分割非Delaunay邊將任意一個流形三角網格轉化為Delaunay 網格;Liu 等人[15]考慮到非Delaunay 邊的蝴蝶形區域提出了一種計算最優分割點的方法. 張順嵐等人[16]利用Delaunay 三角形剖分技術實現了戰場仿真模型的局部三角化. 若對已知三維網格中進行邊分割操作需要確定要分割的邊及分割點的位置.

因此, 為了消除由QEM 算法產生的狹長三角面,提出一種基于網格邊長的邊分割方法. 該方法對簡化后網格的邊進行遍歷以獲取邊長信息, 根據網格平均邊長求出目標長度, 并將目標邊的中點作為分割點進行邊緣分割操作, 邊分割流程如圖3 所示.

圖3 基于網格邊長的邊分割流程圖

Step 1. 讀取三維網格模型;

Step 2. 計算網格平均邊長AvgLength, 令目標長度TargetLength 為b倍AvgLength. 其中, 倍數b可根據實際模型做適當調整;

Step 3. 遍歷網格中的每條邊, 獲取每條邊的長度EdgeLength;

Step 4. 判斷邊長是否大于目標長度, 若EdgeLength大于TargetLength, 進入Step 5, 否則跳至Step 8;

Step 5. 計算當前邊的中點位置, 設中點為分割點vertex_split;

Step 6. 獲取當前邊所在三角面的頂點坐標v[0]、v[1]、v[2]、v[3];

Step 7. 刪除以點v[0]、v[1]、v[2]和v[0]、v[2]、v[3] 組成的2 個舊三角面, 添加由點v[0]、v[1]、vertex_split, 點v[1]、v[2]、vertex_split, 點v[2]、v[3]、vertex_split 和點v[3]、v[0]、vertex_split 組成的4 個新三角面;

Step 8. 判斷當前邊是否為最后一條邊, 如果是則進入Step 9, 否則跳至Step 3;

Step 9. 保存邊分割后的網格信息;

Step 10. 輸出模型.

2.3 算法描述

綜上所述, 改進的二次誤差測度算法描述如算法1.

算法1. ESQEM 算法1) 讀取網格文件, 獲取原始三維網格信息.2) 遍歷網格中的每個頂點, 計算每個頂點的二次誤差矩陣Q.3) 區分網格內頂點和邊界頂點, 根據式(8)和式(9)計算內定點和邊界頂點的高斯曲率, 并根據式(10)計算每條邊的高斯曲率.Q 4) 計算 并判斷是否可逆. 如果 可逆, 求新頂點 的最佳位置, 設置參數ω, 根據式(12)計算當前邊的最小代價并插入最小堆中; 如果不可逆, 分別把v1、v2 和(v1+v2)/2 作為新頂點 計算邊折疊代價,找出3 種情況的最小邊代價, 插入最小堆中.v Q v v Q v v 5) 邊折疊操作. 從堆頂刪除代價最小的邊, 添加新頂點合并最小代價邊的兩個端點, 更新及近鄰邊的誤差矩陣和高斯曲率, 并返回步驟4).6) 邊分割操作. 遍歷網格的每條邊, 當EdgeLength 大于TargetLength時, 刪除兩個舊的三角面, 同時根據頂點和中點位置添加4 個新的三角面; 當EdgeLength 小于TargetLength 時, 繼續判斷下一條邊, 直至循環結束.7) 保存簡化后的網格模型.v v

算法1 不但可以通過參數ω調整網格特征保留情況, 還能通過邊長判斷異常三角面. TargetLength 通常為AvgLength 的4/3 倍, 也可以根據原始網格模型調整最佳TargetLength 值, 使簡化后的三角面更均勻.

3 實驗分析

實驗分別采用QEM 算法和ESQEM 算法對Cow模型和Dinosaur 模型進行簡化, 通過對比兩種算法的簡化效果及簡化前后的Hausdorff 距離來驗證ESQEM算法在維持模型邊緣、避免異常三角面和保留局部特征方面比原始算法更有效.

3.1 簡化效果對比

ESQEM 算法是基于VS 2019 開發平臺在QEM算法源碼基礎上進行改進的. 為增加可信度, 實驗所測試機相同(Intel(R) Core(TM) i5-8265U CPU 1.60 GHz,RAM 8 GB), 輸入數據相同, 控制參數相同, 且未對改進算法做任何加速處理. 為保證在相同簡化率的情況下進行比較, 參數ω允許的最大誤差不超過0.01 個精度, 參數b為固定值. 簡化后模型以白模和網格兩種形式進行整體和局部對比展示, 隨著簡化率增高, 網格模型信息不斷變動, 表1 為實驗過程中的網格數據.

表1 實驗模型數據基本信息

Cow 的原始模型如圖4 所示. 采用兩種算法對Cow 模型進行簡化, 結果見圖5 和圖6. 由圖4 可知,簡化后的模型邊緣始終保持完整, 從圖5(a)到圖5(c)簡化率由58.03%升到82.77%, 此過程中模型逐漸變得棱角分明, 卻并無異常面和異常拓撲產生. 當簡化率超過90%時, 圖5(d)中牛的腳部和面部特征出現模糊,但曲率更高的牛角處仍然清晰可見, 且未產生細長三角面. 對比圖6(d), 當使用QEM 算法簡化率超過90%時, 牛的腳部及面部特征退化, 而牛角的上半部分直接消失, 此外還產生了多個細長三角面. 而圖6(c)中, 雖然邊緣特征仍在, 但出現孔洞及異常三角面.

圖4 Cow 原始模型

圖5 Cow 模型ESQEM 算法簡化結果

圖6 Cow 模型QEM 算法簡化結果

為了更清晰的觀察兩種算法的簡化效果, 將Cow模型的局部位置進行放大比較. 如圖7、圖8 所示,圖7(a) 和圖7(b) 為Cow 模型在簡化率為58.03%時的背部對比圖, 圖8(a)和圖8(b)為Cow 模型在簡化率為92.69% 時的頭部對比圖. 可以看出, ESQEM算法能消除異常三角面和保留高曲率特征.

圖7 Cow 模型背部對比圖

圖8 Cow 模型頭部對比圖

Dinosaur 的原始模型如圖9 所示. 圖10 為ESQEM算法對Dinosaur 模型的簡化效果圖, 圖10(a)到圖10(c)的簡化率從58.09%到89.28%, 在此過程中模型外表逐漸鋒利, 但幾何結構與局部特征依舊清晰可辨. 而當簡化率超過90%時, 從圖10(d)可以看出模型面部、手部等輪廓依舊清晰, 且三角面和拓撲也并無異常. 圖11為QEM 算法對Dinosaur 模型的簡化效果圖, 從圖11(a)到圖11(d)的模型輪廓無顯著變化, 但在簡化過程中產生了細長三角面. 并且當簡化率超過90%時, 由圖11(d)明顯看到, 模型部分手部特征消失, 恐龍的爪子由3 個退化成2 個.

圖9 Dinosaur 原始模型

圖10 Dinosaur 模型ESQEM 算法簡化結果

圖11 Dinosaur 模型QEM 算法簡化結果

為了更清晰的對比兩種算法的不同效果, 將Dinosaur 模型的局部位置進行放大比較. 圖12 和圖13是簡化率為93.10%時, Dinosaur 模型的背部和手部對比圖, 從紅圈標注的位置可以看出, ESQEM 算法不僅能更多地保留模型局部特征, 還能將較大的三角面進行分割.

圖12 Dinosaur 模型背部對比圖

圖13 Dinosaur 模型手部對比圖

3.2 Hausdorff 距離對比

Hausdorff 距離是用來測量歐氏空間中兩個點集之間距離的一種量度. 在三維網格模型簡化過程中, 通常使用Hausdorff 距離來比較簡化前和簡化后模型的相似程度, Hausdorff 距離越小, 則簡化前后的模型就越相似, 精度就越高, 反之, 簡化模型的精度就越低. 因此,在使用兩種不同算法的情況下, 計算簡化前后模型的Hausdorff 距離, 能有效對比ESQEM 算法和QEM 算法簡化后的模型精度. 圖14 和圖15 為兩種算法簡化Cow 模型和Dinosaur 模型的Hausdorff 距離值. 其中,橫坐標代表模型簡化率, 縱坐標代表Hausdorff 距離.

由圖14 可知, 當簡化率低于75%時, 使用ESQEM算法得到的模型精度整體略低于QEM 算法.尤其當簡化率在35%–75%時, Hausdorff 距離相差較大. 然而,當到簡化率超過75%時, ESQEM 算法的精度開始高于QEM 算法, 且簡化率越大, 精度越高.

圖14 Cow 的Hausdorff 距離

圖15 反映了相似的情況, 前期簡化率較低時, 兩種算法的Hausdorff 距離值相差不大. 簡化率在50%左右時, 使用ESQEM 算法所得的Hausdorff 距離值出現波動, 模型精度不夠穩定. 當簡化率超過70%時, 使用ESQEM 算法所得模型精度開始高于QEM 算法. 綜上所述, ESQEM 算法更適合高簡化率的簡化需求, 模型所需面數越少, ESQEM 算法較QEM算法的優勢就越大.

圖15 Dinosaur 的Hausdorff 距離

4 結論與展望

針對QEM 算法難以保留簡化后模型的細節特征、幾何結構和容易產生異常三角面等缺點, 提出一種結合邊分割操作的改進算法(ESQEM). 該算法加入了高斯曲率算子和長邊分割操作, 在維持幾何結構的基礎上, 通過調整參數保留模型局部特征、優化異常三角面. 實驗證明ESQEM 算法具有更好的簡化效果,能更多的保留模型細節、均勻三角面, 并在高簡化率的條件下, 簡化后的模型精度比QEM 算法更高. 在接下來的研究中, 將會考慮重新計算邊的分割點. 如第3.2 小節所示, 僅以邊中點作為分割點無法在低簡化率條件下保證模型精度. 為了在簡化過程中始終能得到較高精度的模型, 后續會考慮引入邊分割代價, 以保證新的分割點與原始模型相同位置的點最接近.