The next iteration of the surface meshing algorithm from the previous post is surface remeshing. Surface meshing is the process of taking an existing mesh and generating a new mesh of the same surface. This can be useful in many scenarios — for example, we’re using a 3D modeling program to design a surface that we want to use in a simulation. Unfortunately, the mesh that the modeling software creates isn’t designed for simulation. It might have very big triangles, triangles with distorted shapes, way too many triangles, or other problems. You know, triangle problems. Surface meshing allows us to generate a new surface of roughly the same shape but with a uniform density of points and consistent elements.
The procedure is fairly straight forward:
- Begin with an existing mesh.
- Generate evenly spaced points on that surface. We do this by generating random points on the surface and discarding any that lie within a certain distance of a point that has already been added. We accelerate this process with a simple spatial partitioning data structure.
- Run the Ball Pivot Algorithm on that set of points. The points have no connection to the original surface once they are generated.
You can play with an initial implementation here. Warning: this is very buggy and likely to crash, generate meshes with holes, or create fairly ugly meshes, depending on the settings.