© 2023 无名玩家X
Diffusing / smoothing weight map over a triangular mesh.
在三角形网格上扩散/平滑权重分布
Diffuse per vertex weights/scalar map/scalar function over an irregular triangle mesh (laplacian diffusion) - 05/2018 - #Geometry 在不规则三角形网格上扩散每个顶点权重/标量映射/标量函数（拉普拉斯扩散）
Showcasing simple procedures with C++ code to smooth / diffuse per vertex weights over a triangle mesh. 用C++代码展示在三角形网格上平滑/扩散每个顶点权重的简单过程。
Say you associate each vertex of a mesh ($ v_i $) with a real value ($ w_i $), it is possible to diffuse or smooth this per vertex weight map over the surface of the mesh. 假设您将网格的每个顶点($ v_i $)与实数值($ w_i $)关联，那么就有可能在网格表面上扩散或平滑每个顶点的权重分布。
Uniform diffusion
均匀扩散
Let’s consider the direct neighbors of the weight ($ w_i $), namely the weights ($ {\cdots, w_{j}, \cdots } $):
我们考虑权值($ w_i $)的直接邻域，即权值($ {\cdots, w_{j}, \cdots } $)：
让我们考虑权重 $ w_i $ 的直接相邻，即权重 $ {\cdots, w_{j}, \cdots } $:
For every vertices we can average the values (${\cdots, w_{j}, \cdots } $) surrounding vertex ($i $):
\[w_i' = \sum\limits_ { \frac{w_{j}}{|\mathcal N(i)|} }\]| Where ($ \mathcal N(i) $) is the set of vertices adjacent to ($ i $) and ($ | \mathcal N(i) | $) the number of vertices connected to ($ i $) (i.e. its valence). Notice here we ignore altogether the old value ($ w_i $) and directly replace it with its new value ($ w_i’ $). You need two buffers ($ \mathbf w = {w_1, \cdots, w_n } $) and ($ \mathbf w’ = {w_1’, \cdots, w_n’ } $). Once all the new values ($ \mathbf w’ $) are computed you can swap the buffers and repeat the process to further smooth out the results. |
Here we set constant values on the left (=0) and right side (=1) of the plane and diffuse the interior values. After diffusion the values will smoothly progress in the interval ($[0, 1] $).
If you wish to slow down the diffusion process this is easily performed by linearly interpolating the old value ($ w_i $) with the new one:
\[w_i' = w_i . (1-t) + \left ( \sum\limits_ { \frac{w_{j}}{|\mathcal N(i)|} } \right ) . t\]Where ($ t \in [0, 1] $) is your interpolation factor.
While values are effectively smoothed out you can notice the result is not symmetrical. This is because we completely ignore the fact triangles have different size and shape. Intuitively a neighbor ($ v_{j} $) far from ($ v_i $) should contribute less than a closer neighbor when we average the values.
Weighted diffusion
To take into account the mesh irregularities we need to introduce barycentric weights ($ \mathbf \beta $). For every vertices ($ v_i $) we associate a set of weights ($ { \cdots, \beta_{ij}, \cdots } $) corresponding to each direct neighbor:
We now do a weighted average of the neighboring values: \(w_i' = w_i (1-t) + \left ( \frac{ \sum\limits_ w_{ij} \beta_{ij} }{ \sum\limits_ { \beta_{ij} } } \right ) . t\)
Notice that if we set ($ \beta_{ij} = 1 $) the formula simplifies to the uniform case. Carefully setting up the weights ($ \beta_{ij} $) will allow us to take into account irregular triangle distribution and we can obtain perfectly symmetrical results:
This result was obtain with the so called cotangent weights quite popular in geometry processing. If you iterate the process enough times the values will be all equal on the vertical axis ($y $). On the horizontal axis ($x $) from the right to the left side values will increase linearly i.e. ($ f(x) = x . (1 / hlength) $).
As a simpler alternative you could use edge length but it will produce more irregular results:
\[\beta_{ij} = \frac{\sum\limits_{k \in \mathcal N(i)} {\|v_i - v_k\| } }\]Code
You will also need to take a look at my blog post on cotangent weights to fully take advantage of the code below.
C++ code
Notes:
- you can apply the process to the whole mesh or sub part of the mesh.
- It’s possible to use a brush to locally smooth the weight map.
- Notice that when ($ t >= 1 $) it will sometimes output erroneous results, in particular for the cotangent weights it is recommended to set something strictly inferior to one to stabilize the convergence.
Going further
What we are actually doing here is computing an harmonic function ($ f:\mathbb R^2 \rightarrow \mathbb R $) defined over the surface of a irregular triangle mesh. At each smoothing iteration we are actually computing one Jacobi iteration to solve the linear system of equations ($ \Delta f = 0 $). If you set values to form a closed region and iterate enough times you will effectively solve the system completely and compute an harmonic weight map (it is however the slowest way to do so).
If this does not make any sens to you but feel the irrepressible need to know, take a look at my tutorials on harmonic weights. You will see that you can easily smooth weights on regular 2D grids (i.e. a texture) or 3D grids (voxels).
To directly solve ($ \Delta f = 0 $) without diffusion, see my article to compute harmonic weights by directly solving the linear system of equation .