Mesh Generation
Given a fixed point set, Delaunay triangulation will try to make the triangulation more shape regular and thus is considered as a “good” structured mesh.
如果点集的位置本身就不好？
👆 The distribution of points is more important for a good mesh.
How to sample points to generate high‐quality meshes?
Centroidal Voronoi Tessellation
定义
定义: The VT is a centroidal Voronoi tessellation (CVT) , if each seed coincides with the centroid of its Voronoi cell
👆 CVT:满是“点与所在区域的重心重合”的 Voronoi 图。
方法
• Construct the VT associated with the points
• Compute the centroids of the Voronoi regions
• Move the points to the centroids
• Iterate until convergent
效果
CVT理论
CVT energy function:
$$ F(X)=\sum_{i=1}^{N} \int _{V_i}\rho (X)||X-X_i||^2dX $$
CVT is a critical point of \(F(X)\), an optimal CVT is a global minimizer of \(F(X)\)
Geometric interpretation
The CVT energy with \(\rho (X)\) identical to 1, is the volume difference between the circumscribed polytope and the araboloid.
\(\rho (x)\)是种加权，用于内容相关。
当 \(\rho =I 时， X为 V_i \)的重心时能量最小。
The gradient of \(F(X)\) is [Iri et al. 1984; Asami 1991; Du et al. 1999]:
$$ \frac{\partial F}{\partial \chi _i} =2m_i(\chi _i-C_i), $$ where $$ m_i=\int _{\chi\in \Omega _i }\rho (\chi )d\sigma $$
Lloyd’s method is a gradient descent method, thus has linear convergence
Smoothness of F(X)
Can BFGS method be applied to computing CVT? Or does CVT energy F(X) have required \(C^2\) smoothness?
Results:
- It has been noted that F(X) is non‐smooth [Iri et al. 1984], but without proof
- It has been proved that F(X) is \(C^1\) [Cortes et al. 2005]
- F(X) is \(C^2\) in a convex domain in 2D and 3D [Liu et al. 2009]
C2 Continuity of F(X)
Figure: Illustration of \(C^2\) smoothness of CVT energy in 2D
CVT的应用
- CVT on Surface
- CVT for Remeshing
[1:20:59]
把 CVT 算法推广到曲面，可以把距离改为测地线度量
连续曲面测地距离：表面上的孤长
离散网格的测地距离：可参数化到平面再计算
Optimal Delaunay Triangulation
ODT energy function:
$$ E(X)=||f-f_{I,T }||L^1(\Omega) $$
$$ =\sum _{\tau \in T}\int _\tau f_I(X)dX-\int _\Omega f(X)dX $$
CVT VS ODT Energy
• CVT energy
$$ F(X)=\sum _{i=1}^N\int _{V_i}||X-X_i||^2dX $$
• ODT energy
$$ E(X)=\sum _{\tau \in T}\int _\tau f_I(X)dX-\int _\Omega f(X)dX $$
比较：
本文出自CaterpillarStudyGroup，转载请注明出处。 https://caterpillarstudygroup.github.io/GAMES102_mdbook/