Quadric-error-metric网格简化
1.推导
(以下向量均为列向量)
设平面
p
i
p_i
pi的法向量为
n
i
n_i
ni,
x
i
x_i
xi为该平面上任一点，则其在齐次坐标下的方程为：
n
ˉ
i
=
(
n
i
,
−
n
i
⋅
x
i
)
\bar n_i=(n_i,-n_i \cdot x_i)
nˉi=(ni,−ni⋅xi)
设空间中任意一点
x
x
x的齐次坐标为
x
ˉ
=
(
x
,
1
)
\bar x=(x, 1)
xˉ=(x,1)
由几何关系可知
x
x
x到
p
i
p_i
pi的距离的平方
d
(
x
,
p
i
)
d(x,p_i)
d(x,pi)为：
d
(
x
,
p
i
)
=
(
(
x
−
x
i
)
⋅
n
i
)
2
=
(
[
n
i
,
−
n
i
⋅
x
i
]
[
x
1
]
)
2
=
(
n
ˉ
i
T
x
ˉ
)
2
=
x
ˉ
T
(
n
ˉ
i
n
ˉ
i
T
)
x
ˉ
=
x
ˉ
T
Q
i
x
ˉ
\begin{aligned} d(x,p_i)&=((x-x_i)\cdot n_i)^2\\ &=(\begin{bmatrix}n_i,-n_i\cdot x_i\end{bmatrix}\begin{bmatrix}x\\1\end{bmatrix})^2\\ &=(\bar n_i^T\bar x)^2\\ &=\bar x^T(\bar n_i\bar n_i^T) \bar x\\ &=\bar x^TQ_i\bar x \end{aligned}
d(x,pi)=((x−xi)⋅ni)2=([ni,−ni⋅xi][x1])2=(nˉiTxˉ)2=xˉT(nˉinˉiT)xˉ=xˉTQixˉ
其中
Q
i
Q_i
Qi称为Quadratic error Matrix,注意到这个
Q
i
Q_i
Qi由于是法向量生成的，所以是定义面上的，现在分别定义顶点和边上的Quadratic error Matrix
Q
i
v
Q_i^v
Qiv和
Q
e
Q^e
Qe:
Q
i
v
=
∑
j
∈
Ω
(
i
)
Q
j
Q
e
=
Q
1
v
+
Q
2
v
\begin{aligned} Q_i^v&=\sum_{j\in \Omega(i)}Q_j\\ Q^e&=Q_1^v+Q_2^v \end{aligned}
QivQe=j∈Ω(i)∑Qj=Q1v+Q2v
所以每条边上的
v
ˉ
\bar v
vˉ要满足
v
ˉ
=
m
i
n
(
v
T
Q
e
v
)
\bar v=min(v^TQ^ev)
vˉ=min(vTQev)
若
Q
e
Q^e
Qe可逆，记
Δ
=
v
T
Q
e
v
\Delta=v^TQ^ev
Δ=vTQev,当取最小值时，应该满足
∂
Δ
∂
x
=
0
\frac{\partial \Delta}{\partial x}=0
∂x∂Δ=0，
∂
Δ
∂
y
=
0
\frac{\partial \Delta}{\partial y}=0
∂y∂Δ=0，
∂
Δ
∂
z
=
0
\frac{\partial \Delta}{\partial z}=0
∂z∂Δ=0，即：
[
q
11
q
12
q
13
q
14
q
12
q
22
q
23
q
24
q
13
q
23
q
33
q
34
0
0
0
1
]
v
ˉ
=
[
0
0
0
1
]
\left[\begin{array}{cccc} q_{11} & q_{12} & q_{13} & q_{14} \\ q_{12} & q_{22} & q_{23} & q_{24} \\ q_{13} & q_{23} & q_{33} & q_{34} \\ 0 & 0 & 0 & 1 \end{array}\right] \mathbf{\mathbf { \bar v }}=\left[\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right]
⎣⎢⎢⎡q11q12q130q12q22q230q13q23q330q14q24q341⎦⎥⎥⎤vˉ=⎣⎢⎢⎡0001⎦⎥⎥⎤
（ps:如果
Q
e
Q^e
Qe不满秩，则可取
v
ˉ
=
v
1
+
v
2
2
\bar v=\frac{v_1+v_2}{2}
vˉ=2v1+v2,即为两顶点中点）
2. 算法流程
输入：网格，目标定点数n，cost阈值t
输出：简化后的网格
-
计算每条边的 Q e Q^e Qe
-
计算每条边上的新的 v ˉ \bar v vˉ
-
while N v N_v Nv >n and C o s t m i n Cost_{min} Costmin<t:
3.1 将每条边的 c o s t = v ˉ T Q e v ˉ cost=\bar v^TQ^e\bar v cost=vˉTQevˉ放入最小堆；
3.2 删除堆顶的cost,并且塌陷该条边（即将该边的两个顶点并到 v ˉ \bar v vˉ上去，该新点上的Quadratic error Matrix则更新为刚才的 Q e Q^e Qe）；
3.3 更新堆(更新相邻的 Q e Q^e Qe和cost)；
end;