Instant-Meshes-标架场方法
在顶点
V
i
V_i
Vi定义n-Rosy标架场,定义
R
s
o
(
o
,
n
,
k
)
:
=
r
o
t
(
n
,
k
2
π
s
o
)
,
k
∈
Z
R
s
o
(
o
,
n
)
:
=
{
R
s
o
(
o
,
n
,
0
)
,
R
s
o
(
o
,
n
,
1
)
,
…
,
R
s
o
(
o
,
n
,
s
o
−
1
)
}
\begin{aligned}&\mathcal{R_{s_o}}(\mathbf{o},\mathbf{n},k):=rot(\mathbf{n},k\frac{2\pi}{s_o}),k \in \mathbb{Z} \\&\mathcal{R_{s_o}}(\mathbf{o},\mathbf{n}):=\{\mathcal{R_{s_o}}(\mathbf{o},\mathbf{n},0),\mathcal{R_{s_o}}(\mathbf{o},\mathbf{n},1),\dots,\mathcal{R_{s_o}}(\mathbf{o},\mathbf{n},s_o-1)\}\end{aligned}
Rso(o,n,k):=rot(n,kso2π),k∈ZRso(o,n):={Rso(o,n,0),Rso(o,n,1),…,Rso(o,n,so−1)}
第一个式子是将
o
⃗
\vec{o}
o
绕法向量
n
⃗
\vec{n}
n
旋转
k
2
π
s
o
k\frac{2\pi}{s_o}
kso2π角度,第二个式子即是在顶点处用
o
⃗
\vec{o}
o
对称旋转
n
n
n次构成一个n-Rosy标架场
1.Intrinsic smoothness
该方法为将顶点 V i V_i Vi的相邻顶点 V j V_j Vj旋转到 V i V_i Vi的切平面上,然后寻找 o i ⃗ \vec{o_i} oi 与 o j ⃗ \vec{o_j} oj 的最小旋转角度,并用高斯赛德尔方法进行迭代求解。
定义能量函数:
E
(
O
,
k
)
:
=
∑
i
∈
V
∑
j
∈
N
(
i
)
∠
(
o
i
,
R
s
o
(
o
j
i
,
n
i
,
k
i
j
)
)
2
E(O, \mathbf{k}):=\sum_{i \in \mathcal{V}} \sum_{j \in \mathcal{N}(i)} \angle\left(\mathbf{o}_{i}, \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j i}, \mathbf{n}_{i}, k_{i j}\right)\right)^{2}
E(O,k):=i∈V∑j∈N(i)∑∠(oi,Rso(oji,ni,kij))2
其中
o
j
i
:
=
rot
(
n
j
×
n
i
,
∠
(
n
j
,
n
i
)
)
o
j
\mathbf{o}_{j i}:=\operatorname{rot}\left(\mathbf{n}_{j} \times \mathbf{n}_{i}, \angle\left(\mathbf{n}_{j}, \mathbf{n}_{i}\right)\right) \mathbf{o}_{j}
oji:=rot(nj×ni,∠(nj,ni))oj,即
o
j
o_j
oj旋转到
V
i
V_i
Vi切平面上后的向量。
k
i
j
k_{ij}
kij为旋转次数,要求解该能量函数,可通过以下方法
k
i
j
:
=
arg
min
0
≤
k
<
s
o
∠
(
o
i
,
R
s
o
(
o
j
i
,
n
i
,
k
)
)
o
i
←
∑
j
∈
N
(
i
)
w
i
j
R
s
o
(
o
j
i
,
n
i
,
k
i
j
)
,
o
i
←
o
i
/
∥
o
i
∥
\begin{aligned} &k_{i j}:=\underset{0 \leq k<s_{o}}{\arg \min } \angle\left(\mathbf{o}_{i}, \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j i}, \mathbf{n}_{i}, k\right)\right)\\ &\mathbf{o}_{i} \leftarrow \sum_{j \in \mathcal{N}(i)} w_{i j} \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j i}, \mathbf{n}_{i}, k_{i j}\right), \quad \mathbf{o}_{i} \leftarrow \mathbf{o}_{i} /\left\|\mathbf{o}_{i}\right\| \end{aligned}
kij:=0≤k<soargmin∠(oi,Rso(oji,ni,k))oi←j∈N(i)∑wijRso(oji,ni,kij),oi←oi/∥oi∥
即先寻找最佳旋转次数,然后通过拉普拉斯权重归一化,由于搜寻空间是很小的(
s
o
s_o
so,如果是n-Rosy,也就是n,而n通常是很小的一个常数),可用暴力方法,若顶点
V
i
V_i
Vi周围有
m
m
m个点,那迭代一次的搜索空间大小也只有
m
n
mn
mn
然后通过高斯赛德尔迭代:
o
i
′
←
w
i
j
1
R
s
o
(
o
j
1
i
,
n
i
,
k
i
j
1
)
,
o
i
←
o
i
′
/
∥
o
i
′
∥
o
i
′
←
o
i
′
+
w
i
j
2
R
s
o
(
o
j
2
i
,
n
i
,
k
i
j
2
)
,
o
i
←
o
i
′
/
∥
o
i
′
∥
\begin{array}{ll} \mathbf{o}_{i}^{\prime} \leftarrow w_{i j_{1}} \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j_{1} i}, \mathbf{n}_{i}, k_{i j_{1}}\right), & \mathbf{o}_{i} \leftarrow \mathbf{o}_{i}^{\prime} /\left\|\mathbf{o}_{i}^{\prime}\right\| \\ \mathbf{o}_{i}^{\prime} \leftarrow \mathbf{o}_{i}^{\prime}+w_{i j_{2}} \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j_{2} i}, \mathbf{n}_{i}, k_{i j_{2}}\right), & \mathbf{o}_{i} \leftarrow \mathbf{o}_{i}^{\prime} /\left\|\mathbf{o}_{i}^{\prime}\right\| \end{array}
oi′←wij1Rso(oj1i,ni,kij1),oi′←oi′+wij2Rso(oj2i,ni,kij2),oi←oi′/∥oi′∥oi←oi′/∥oi′∥
2.Extrinsic smoothness
该方法区别于上面的方法为直接在三维空间里求解能量函数,即不再旋转到切平面,则能量函数改为:
E
e
(
O
,
k
)
:
=
∑
i
∈
V
∑
j
∈
N
(
i
)
∠
(
R
s
o
(
o
i
,
n
i
,
k
i
j
)
,
R
s
o
(
o
j
,
n
j
,
k
j
i
)
)
2
E_{\mathrm{e}}(O, k):=\sum_{i \in \mathcal{V}} \sum_{j \in \mathcal{N}(i)} \angle\left(\mathcal{R}_{s_{o}}\left(\mathbf{o}_{i}, \mathbf{n}_{i}, k_{i j}\right), \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j}, \mathbf{n}_{j}, k_{j i}\right)\right)^{2}
Ee(O,k):=i∈V∑j∈N(i)∑∠(Rso(oi,ni,kij),Rso(oj,nj,kji))2
则
k
i
j
k_{ij}
kij的最优解为
(
k
i
j
,
k
j
i
)
:
=
arg
min
0
≤
k
,
l
<
s
o
∠
(
R
s
o
(
o
i
,
n
i
,
k
)
,
R
s
o
(
o
j
,
n
j
,
l
)
)
2
\left(k_{i j}, k_{j i}\right):=\underset{0 \leq k, l<s_{o}}{\arg \min } \angle\left(\mathcal{R}_{s_{o}}\left(\mathbf{o}_{i}, \mathbf{n}_{i}, k\right), \mathcal{R}_{s_{o}}\left(\mathbf{o}_{j}, \mathbf{n}_{j}, l\right)\right)^{2}
(kij,kji):=0≤k,l<soargmin∠(Rso(oi,ni,k),Rso(oj,nj,l))2
可以看到搜索空间变为
n
2
n^2
n2,其实它还是很小的,也是可以暴力求的。下一步则依然还是高斯赛德尔迭代。
3.说明
- 上述算法有解的条件是收敛,而事实就是它就是收敛的。
- 上述算法因为它是基于局部的,所以可以支持并行。
- 初始标架场被设置为随机的切向量,锐利特征则通过二面角阈值来判断,锐利边上顶点的法向量为任一面的法向量,而其余的可用角度权重等来定义。
- Gauss–Seidel method可能陷入局部最小解,可通过随机法避免,而该文提出了另一种**多分辨率层次法(Multiresolution hierarchy)**来避免这种情况,如下。