在計算機圖形應用中，為了盡可能真實呈現(xiàn)虛擬物體，往往需要高精度的三維模型。然而，模型的復雜性直接關系到它的計算成本，因此高精度的模型在幾何運算時并不是必須的，取而代之的是一個相對簡化的三維模型，那么如何自動計算生成這些三維簡化模型就是網(wǎng)格精簡算法所關注的目標。

　　[Garland et al. 1997]提出了一種基于二次誤差作為度量代價的邊收縮算法，其計算速度快并且簡化質(zhì)量較高。該方法在選擇一條合適的邊進行迭代收縮時，定義了一個描述邊收縮代價的變量Δ，具體如下：對于網(wǎng)格中的每個頂點v，我們預先定義一個4×4的對稱誤差矩陣Q，那么頂點v = [v_x v_y v_z 1]^T的誤差為其二次項形式Δ(v) = v^TQv。假設對于一條收縮邊(v₁, v₂)，其收縮后頂點變?yōu)関_bar，我們定義頂點v_bar的誤差矩陣Q_bar為Q_bar = Q₁ + Q₂，對于如何計算頂點v_bar的位置有兩種策略：一種簡單的策略就是在v₁, v₂和(v₁+ v₂)/2中選擇一個使得收縮代價Δ(v_bar)最小的位置。另一種策略就是數(shù)值計算頂點v_bar位置使得Δ(v_bar)最小，由于Δ的表達式是一個二次項形式，因此令一階導數(shù)為0，即，該式等價于求解：

其中q_ij為矩陣Q_bar中對應的元素。如果系數(shù)矩陣可逆，那么通過求解上述方程就可以得到新頂點v_bar的位置，如果系數(shù)矩陣不可逆，就通過第一種簡單策略來得到新頂點v_bar的位置。根據(jù)以上描述，算法流程如下：

　　那么剩下的問題就是如何計算每個頂點的初始誤差矩陣Q，在原始網(wǎng)格模型中，每個頂點可以認為是其周圍三角片所在平面的交集，也就是這些平面的交點就是頂點位置，我們定義頂點的誤差為頂點到這些平面的距離平方和：

其中p = [a b c d]^T代表平面方程ax + by + cz + d = 0(a² + b² + c² = 1)的系數(shù)，K_p為二次基本誤差矩陣：

因此原始網(wǎng)格中頂點v的初始誤差為Δ(v) = 0，當邊收縮后，新頂點誤差為Δ(v_bar) = v_bar^TQ_barv_bar，我們依次選取收縮后新頂點誤差最小的邊進行迭代收縮直到滿足要求為止。

View Code

本文為原創(chuàng)，轉(zhuǎn)載請注明出處：http://www.cnblogs.com/shushen

參考文獻：

[1] Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (SIGGRAPH '97). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 209-216.