Isaac's Blog

Mesh Smoothing

2018/01/26

Mesh smoothing, also known as mesh denoising, is an important and widely discussed topic in terms of geometry processing. Basically, a mesh smoothing method takes three steps: loading a mesh from a file; smoothing that mesh; outputting the mesh to a file. Recently, I implemented a few basic algorithms regarding mesh smoothing.

Selection of Mesh Library

There are a lot of mesh libraries that give us a data structure so that we can use to build a mesh for an object file. What I am using is the geometry-processing-js library. It is a library written in JavaScript which constructs a mesh based on half-edge. It also gives plenty of predefined functions regarding the components of a mesh e.g. half-edge, vertex, edge, face, etc. Besides, it also includes a linear algebra library which makes it handy for users to do matrix-vector operations.

Mesh Smoothing Algorithms

I implemented two algorithms for mesh smoothing, a mean filtering algorithm, and a weighted mean filtering algorithm.

Mean Filtering Algorithm

A most naïve mean filtering algorithm goes as follows:

Begin

Step 1: Create a Hash Map $positions$ mapping each index of vertex with its position to be updated;

Step 2: For each vertex $v$ in the mesh, calculate $positions[v]$ by the average position of the neighbor vertices in the one-ring of $v$;

Step 3: After the whole iteration, update the positions of vertices in the mesh by the Hash Map $positions$.

End

However, if the object has some holes on it, this algorithm could cause the holes to enlarge after times of iteration, which is shown in Figure 1.

Mesh Smoothing figure 1

Figure 1: Holes enlarge on the object, steps = 5.

Sometimes, we don’t like such distortion, so it is necessary to preserve the boundary of holes on the mesh. We can add a step to the algorithm to constrain the vertices of boundary edges:

Begin

Step1: Create a Hash Map $positions$ mapping each index of vertex with its position to be updated;

Step2: For each vertex $v$ in the mesh, calculate $positions[v]$ by the average position of the neighbor vertices in the one-ring of $v$;

Step3: To preserve the boundary of holes on the mesh, if vertex $v$ is on boundary, update $positions[v]$ to the original position of vertex $v$ in the mesh;

Step4: After the whole iteration, update the positions of vertices in the mesh by the Hash Map $positions$.

End

Weighted Mean Filtering Algorithm

The weighting method simply weights each neighboring vertex by the area of the two faces incident to it. The weighted mean filtering algorithm goes like this:

Begin

Step1: Create a Hash Map $positions$ that maps each index of vertex to its position to be updated;

Step2: For each vertex $v$ in the mesh, traverse its neighborhood vertices. And for each neighbor vertex $nv$ calculate the weight value on each neighborhood vertex $weightnv$ by adding area of the two incident faces together;

Step3: After the traversal of neighborhood vertices, calculate the total weight $weight$ on the vertex $v$ by accumulating every $weightnv$, and calculate $positions[v]=\frac{\sum_{} weightnv \cdot position\,of\,nv}{weight}$;

Step4: To preserve the boundary of holes on the mesh, if vertex $v$ is on boundary, update $positions[v]$ to the original position of vertex $v$ in the mesh;

Step5: After the whole iteration, update the positions of vertices in the mesh by the Hash Map $positions$.

End

However, in the implementation, I found this could cause the faces of the mesh overlapping one another after several times of iterations, because the position of vertex could fall outside its one-ring neighborhood. As shown in Figure 2, overlapping occurs after 5 times of iteration.

Mesh Smoothing figure 2

Figure 2: Overlapping of faces, steps = 5.

In order to prevent such thing from happening, I tried to find those vertices which could fall outside its neighborhood during an iteration. The one-ring neighborhood of one vertex is actually a star-shaped polygon so that we can use the left-turn/right-turn check to decide whether the vertex is inside it or not.

To find out the star-shaped neighborhood of a certain vertex $v$, we should first project all the neighbors onto the plane which is defined by vertex $v$ and its normal vector $n$. We can find the projection $q=(x^\prime,y^\prime,z^\prime)$ of vertex $p=(x,y,z)$ on the plane that defined by the normal $n=(a,b,c)$ and vertex $v=(x_0,y_0,z_0)$ in the way below.

There are following implicit geometric relationships between $p$, $q$, $n$ and $v$: $pq \parallel n$ and $vq \perp n$.

The following equation can be derived from $pq \parallel n$:

$$\begin{equation}
\frac{x^\prime-x}{a}=\frac{y^\prime-y}{b}=\frac{z^\prime-z}{c}=t \tag{1} \label{eq:1}
\end{equation}$$

And from $vq \perp n$, we can derive:

$$\begin{equation}
a(x^\prime-x_0)+b(y^\prime-y_0)+c(z^\prime-z_0)=0 \tag{2} \label{eq:2}
\end{equation}$$

Combining $\eqref{eq:1}$ and $\eqref{eq:2}$, we can solve for $t$:

$$\begin{equation}
t=\frac{ax_0+by_0+cz_0-(ax+by+cz)}{a^2+b^2+c^2} \tag{3} \label{eq:3}
\end{equation}$$

Then we can solve for the projection $q=(x^\prime,y^\prime,z^\prime)$ by combining $\eqref{eq:1}$ and $\eqref{eq:3}$.

As the data structure of mesh is based on half-edge, and all the faces are defined by half-edges in counter-clock-wise order. Thus, for each vertex $v$, we can simply get the boundary edges of a star-shaped neighborhood in counter-clock-wise order, project them along with the position to be updated $positions[v]$ onto the plane that is defined by vertex $v$ and its normal vector $n$. Then we can do the left-turn/right-turn check on that plane to see whether the new position for vertex $v$ $positions[v]$ is outside its neighborhood polygon or not.

So the modified algorithm goes as follows:

Begin

Step1: Create a Hash Map $positions$ that maps each index of vertex to its position to be updated;

Step2: For each vertex $v$ in the mesh, traverse its neighborhood vertices. And for each neighbor vertex $nv$ calculate the weight value on each neighborhood vertex $weightnv$ by adding area of the two incident faces together;

Step3: After the traversal of neighborhood vertices, calculate the total weight $weight$ on the vertex $v$ by accumulating every $weightnv$, and calculate $positions[v]=\frac{\sum_{} weightnv \cdot position\,of\,nv}{weight}$;

Step4: Check whether $positions[v]$ falls outside its one-ring neighborhood, if so, use the mean filtering algorithm to update the new position;

Step5: To preserve the boundary of holes on the mesh, if vertex $v$ is on boundary, update $positions[v]$ to the original position of vertex $v$ in the mesh;

Step6: After the whole iteration, update the positions of vertices in the mesh by the Hash Map $positions$.

End

Results and Conclusions

As for the mean filtering algorithm, Figure 3 shows the results for after applying it on different objects with different step numbers.

Mesh Smoothing figure 3

Figure 3: Results of mean filtering algorithm.

As for the weighted mean filtering algorithm, Figure 4 shows the results for after applying it on different objects with different step numbers.

Mesh Smoothing figure 4

Figure 4: Results of weighted mean filtering algorithm.

We can conclude that the results of both algorithms basically look alike, and both of them could cause the volume of object to shrink if we apply too many times.

I have also uploaded the project to this blog: /projects/mesh-smoothing, we can go there to see how exactly the algorithms work.

CATALOG
  1. 1. Selection of Mesh Library
  2. 2. Mesh Smoothing Algorithms
    1. 2.1. Mean Filtering Algorithm
    2. 2.2. Weighted Mean Filtering Algorithm
  3. 3. Results and Conclusions