基于二次誤差測度的車身網格簡化算法研究

李 旭， 周 卓， 時艷茹， 尹鵬舉

（山東理工大學交通與車輛工程學院，山東 淄博 255049）

近年來，逆向工程在企業的新車型設計中得到了廣泛的應用。由于ATOS等非接觸式掃描設備的出現，人們很容易獲取大量點云數據，三角化以后具有數百萬的三角網格，數據如此龐大而計算機工具本身計算能力的限制使得車身模型構建較慢而且效率低下[1]。尋求一種能夠減少三角網格數量而盡量不損失原模型拓撲形狀的簡化算法對車身曲面重構具有重要的意義。

目前對網格簡化的主要方法有刪減法和頂點聚類算法。刪減法[2,6]通過重復依次刪除對模型特征影響較小的幾何元素并重新三角化來達到簡化模型的目的；根據刪除的幾何元素的不同，通常又可以分成頂點刪除法、邊折疊法和三角面片折疊法等。刪減法具有編碼簡單和運行速度快的特點，但在需要保持拓撲關系的應用中簡化效率會受到一定的影響。頂點聚類算法[3]根據一定的規則，將原始網格模型中的兩個或多個頂點合并成一個頂點，并刪除合并頂點后的退化三角形，從而到達簡化網格面片數量，實現網格模型的簡化的目的。頂點聚類法能處理任意拓撲類型的網格模型，算法簡單，速度較快。但由于簡化誤差控制困難，容易丟失較小結構的細節，因此通常簡化模型的質量不高。

本文對基于二次誤差測度的邊折疊簡化算法進行了研究，綜合考慮了車身逆向工程對網格簡化的精確性與快速性的要求，使之保留了車身曲面中邊界，孔洞和棱線等特征，并通過合理的數據結構的構建提高了算法簡化的速度。本文對某轎車測量點云局部區域進行了簡化和分析，并與三維造型軟件imageware中簡化效果進行了比較，結果表明，基于二次測度算法不僅更快速，而且可達到更好的簡化效果，很適合于海量車身拓撲網格的簡化。

1 二次誤差測度邊折疊簡化算法

1.1 邊折疊簡化算法[4-5]

（1）將頂點vi移到位置；

（2）將出現vj的所有地方用vi代替，即將所有關聯至vj的邊關聯至vi；

（3）刪除vj，刪除所有的退化邊和退化三

邊折疊簡化算法的基本思想是：在每一次簡化操作中以邊作為被刪除的基本幾何元素，并增加一個新點，所有與被刪除邊相連的點都與該新點相連，使模型仍保持是三角形網格。在進行多次的選擇性邊折疊后，模型就可簡化到任何程度。角形（圖中灰色三角片）。

如圖1所示，每折疊一條非邊界邊，模型減少2個三角形，1個頂點，3條邊；折疊一條邊界邊，模型減少1個三角形，1個頂點，2條邊。邊折疊簡化模型網格必須與原網格盡量相似，這取決于邊折疊的順序和邊折疊后生成的新頂點的位置。

圖1 邊折疊示意圖

1.2 二次誤差測度

如何選擇合適的邊進行收縮及如何生成新的頂點，有一個選擇誤差測度標準的問題。本文采用二次誤差測度準則。

二次誤差測度最早由Garland提出，該方法將點到相關平面的距離的平方和作為誤差測度。它的優點是具有極高的計算速度，較小的內存消耗，而且得到的簡化網格具有較高的質量。雖然該方法不是全局優化的，但得到的簡化網格的質量可以和全局優化方法相媲美。

設對邊(vi, vj)進行折疊，則與邊(vi, vj)相關聯的三角形集合 Planes(i, j)構成了原模型上的一個區域。設邊折疊后生成的新位置v為[x, y, z,1]T，定義這次邊折疊帶來的新誤差Δ ()為到三角形集合Planes(i, j)中每個三角形所在面的距離的平方和，即

其中 p =[a, b, c, d ]T表示三角形集合Planes(i, j)中的每個三角形所在面的平面方程ax + b y + c z + d =0 ，且有 a2+b2+c2=1。式(1)可變換如下

其中 Kp是4×4的對稱矩陣，稱為三角形的誤差矩陣，它的定義如下

Q稱為本次邊折疊的誤差矩陣，定義如下

算法中為了快速、簡單地計算邊收縮的誤差，首先，將Planes(i)中的所有三角形的誤差矩陣求和，得到了關于頂點vi的誤差矩陣Qi，同樣可以得到頂點vj的誤差矩陣Qj；然后，將頂點vi和頂點vj的誤差矩陣Qi、Qj相加，近似成該邊折疊的誤差矩陣Q，即Q=Qi+Qj；最后求出邊折疊的誤差Δ)=TQ，則新頂點v的誤差矩陣為Q。

2 算法的實現

2.1 數據結構

（1）頂點信息

采用數組表示頂點信息列表。頂點列表除了記錄每個頂點的坐標位置，還記錄了每個頂點的誤差矩陣，頂點相關的面，頂點相關的頂點。由于每個頂點關聯面的個數不定，所以關聯面采用動態鏈表來表示。

（2）三角面信息

三角面片信息表記錄了模型中三角面片的構成信息、狀態信息。構成信息包括了三角形三個頂點的序號，并且要保證這3個頂點是按逆時針排列。在簡化過程中，由于算法要對邊進行折疊，一些三角形會發生變形，退化成點或線段，在以后的簡化階段和模型繪制階段將不對這些三角形進行處理，因此設置一個標志字段記錄三角形面片中各頂點的狀態，只有當3個頂點均未褪化時，能夠連接為三角形，可以繼續處理。三角形面片信息也采用數組表示。

（3）比較誤差測度的堆

折疊誤差堆的排序采用最小堆排序。該最小堆以邊折疊誤差值作為關鍵字。堆是邏輯上具有完全二叉樹形式的數組，數組中每個元素除了記錄折疊誤差外，還記錄了每條邊折疊后的新位置，邊關聯的兩個頂點的序號。

2.2 算法流程圖

基于二次測度的簡化算法主要步驟包括：判斷各邊是否為邊界邊，如果為邊界邊，要作出與此邊垂直并包含此邊的輔助面計算每個三角形和輔助面的誤差矩陣，并將各個頂點關聯的三角形或輔助面誤差矩陣求加和，得到該頂點誤差矩陣；對折疊誤差堆進行排序；進行邊折疊；更新簡化圖形；如果網格數目達到簡化要求，則結束壓縮。基于二次誤差測度的簡化算法詳細流程圖如圖2所示。

3 在車身逆向工程中的應用算例

本文使用 VC++6.0編程實現了基于二次誤差測度的簡化算法，并通過opengl應用接口實現了曲面或實體模型的顯示。圖3是編程所實現的用戶界面，可以進行文件的讀入，圖形的簡化，放大縮小，旋轉等交互處理。以及便于保存簡化后，符合用戶需求的圖形文件，可同時保存為obj文本格式和 stl格式，該文件格式可以導入Imageware和UG中進行后續處理，這樣也為以此兩個軟件為主的逆向工程提供了大大的方便。

圖2 算法流程圖

如圖4為某轎車發動機罩初始模型及本文算法與imageware中簡化算法對其簡化的結果?？梢钥吹剑舅惴ㄔ?.2秒的時間之內將6萬個點簡化成 5000個三角形，如圖4(b)所示，通過局部放大可以看到，簡化模型的邊界與初始模型的邊界是基本相同的，而過渡處的棱線處仍然保持了原有的特征，而在圖4(c)中， imageware使用了3秒鐘將同一模型簡化成5000個三角形，同樣經過局部放大，可以看到所生成的網格邊界參差不齊與初始網格的邊界已經完全不同，棱線特征基本已經消失。由此比較可見，imageware中簡化速度慢，而且丟失了大量重要的信息，效果很差?；诙握`差的簡化方法能夠快速實現網格的簡化，且很好的保持了原始網格的重要特征。

圖3 圖形顯示界面

4 結束語

從實驗結果來看，本文采用的二次誤差測度邊壓縮簡化算法比imageware三角形壓縮算法計算速度快而且能夠更好的保持初始網格特征信息，逆向工程對點云的處理階段即要求能夠盡可能的減少點云的數量以加快運算速度而且要盡可能的保持點云信息，本算法快速而精確很適合應用于車身曲面的逆向工程。

圖4 對轎車發動機罩點云的簡化

[1]王建勇, 賀 煒, 劉言松. 逆向工程技術及其實物反求應用[J]. 機床與液壓, 2005, (5): 34-36.

[2]Schroder W, Zarge J, Lorensen W. Decimation of triangle meshes [J]. Computer Graphics, 1992, 26(2):65-70.

[3]Low K-L, Tan T-S. Model simplification using vertex-clustering [C]//Proceedings of the 1997 Symposium on Interactive 3D Graphics, ACM SIGGRAPH’97, 1997: 156-163.

[4]Garland M. Simplification using quadric error metrics [J].Computer Graphics, 1997, 31(3): 209-216.

[5]Hoppe H. Progressive meshes [J]. Computer Graphics,1996, 30(1): 99-108.

[6]周 昆, 潘志庚, 石教英. 基于三角形折疊的網格簡化算法[J]. 計算機學報, 1998, 21(6): 506-513.