Surface meshing in the browser

reset

A common problem we come across is needing to make meshes of complex surfaces. This can be done with many different approaches, but regardless of the method, it is often quite difficult. Especially when doing simulations on surfaces, you need a well-behaved triangle mesh, that is one with a controllable density of elements and nicely shaped triangles. This can be done by generating a set of points on that surface and then triangulating them. But triangulating surfaces embedded in 3-space is no simple task. Recently, I came across an interesting approach to this problem which works especially well with generated point clouds called the Ball-Pivot Algorithm. I implemented it in javascript (you should see it running above).

Let’s start with the basic idea of triangulation in 2D. A triangulation of a set of points is just a set of triangles that covers all those points and don’t overlap.

Now not all triangulations are created equal. We want to make triangulations whose triangles are nicely shaped, as close to equilateral as possible. This leads to better numerical stability and convergence in simulations.

This leads to something called the Delaunay triangulation. This is a really neat triangulation defined such that circumcircle of any triangle in the triangulation does not contain any other points. The circumcircle is the smallest circle enclosing the triangle. One thing that’s not entirely obvious is that this triangulation always exists. And the thing that is great about this triangulation is that it maximizes the minimum angle of the triangles. This means it gives us the best shaped triangles we can get with the points we have.

The problem comes when we make the jump from 2D to 3D. We can generalize the idea of Delaunay triangulations to 3D, giving us tetrahedron instead of triangles and circumspheres instead of circumcircles. However, what we want is surface of triangles embedded in 3-space, not a 3 dimensional solid. One way to get around this is called alpha shapes. This is a subset of the 3D Delaunay triangulation but only including faces of a certain size. Alpha shapes can create good surface triangulations; however, it is necessary to compute the full 3D Delaunay, which is complex in computation and implementation as well as numerically unstable.

So in comes the Ball-Pivot algorithm. This algorithm is nice because it works in linear time for points of a constant density, and it is exceptionally cute conceptually. The idea is you have a ball of a certain radius sitting in a triangle. This ball rolls over the edge of the triangle and keeps rolling until it hits another point. Then, that edge and the point it hits make a new triangle which is added to the triangulation, and the ball rolls over a new edge. If you start with a good triangle, such that the ball contains no other points, then the new triangle the ball rolls onto won’t contain any other points either because any point would have been hit before hand. This maintains the Delaunay property! In fact, the ball pivot algorithm produces a subset of an alpha shape.

There are a few caveats. If the curvature and density of the surface points is too high, a larger ball won’t be able to fit in the necessary crevices, missing some points. If the ball is too small, it can fall through large triangles and leave holes. While these issues can worked around, the ball pivot algorithm works best for surfaces with a consistent density of points.

Feel free to look at the code inside, but it is not optimized and not pretty. This was thrown together in 2-3 days, so it definitely lacks polish.