Smoothing Triangle Meshes

4 minute read.

My Manifold library operates on triangle meshes because they are a lowest common denominator representation of a solid that all others, from NURBS to SDFs, can be converted into. However, it can take a huge number of flat facets to adequately approximate the smooth curves of these other representations, particularly in manufacturing where graphics cheats like Phong shading are not available. Therefore, it would be convenient to be able to smoothly interpolate a triangle mesh so that fewer triangles could adequately approximate the desired curved surface. I have devised such a method which I will describe here, but first, a little background.

When I was working on the 3MF spec (3D manufacturing format), we were trying to avoid the pitfalls of AMF (additive manufacturing format), one of which was curved triangles. The idea was that faceted meshes could be refined to a smooth shape by interpolating each triangle's corner vertices and normal vectors; the problem was that no algorithm was given in the standard to define exactly how this interpolation should happen. It turns out to be a tricky problem with an infinite number of possible solutions. That was a non-starter for users, since the format did not specify precisely what shape a given file would represent. 

In building my interpolant I'm trying to solve the same problem, but precisely. I want the vertices to be on the final surface, in case they came from something like an SDF rather than an artist. I want the surface to be tangent-plane continuous everywhere, but with the option to add sharp creases. I want each triangle to be independently calculable, using only data from its own edges so it can be easily GPU-parallelized, and the computation should be fairly cheap.

What I realized was that normal vectors are not enough to parameterize the surface very well. Instead I opted to define a cubic Bezier curve for each edge, where the extra control points are given as weighted halfedge tangent vectors from each vertex. I have an algorithm to compute the surface normal along these edge curves based solely on the other halfedge tangents around the triangle, such that as long as the tangent vectors are coplanar at each vertex where two triangles join, then those triangles will calculate the same normals along the shared edge, and hence create a smooth juncture. However, if the tangents are not coplanar, then a crease will form. The surface of the curved triangle is filled using a side-vertex method, averaging three radial Bezier curves whose control points are interpolated from the edge Beziers. 

These curved triangles are not meant to replace NURBS or other curvature parameterizations: they cannot perfectly represent conics, and they are not curvature-continuous (G₂) at edges. However, they can smooth arbitrary topologies well, particularly when quad-meshing fails. And they can approximate other surfaces such as NURBS just like triangular facets can, but to higher precision with fewer points.

This low-level parameterization is ideal for flexibility and could be easily added as an extension to formats like 3MF or glTF. However, it is a lot of work to manually specify such a large number of control points, so higher-level APIs are called for. I have created one, but I believe there is much room for innovation in calculating "nice" control points based on a variety of possible input. 

My high-level smoothing API is designed to calculate normal vectors for a mesh and then create edge Beziers by projecting the edges up to the tangent planes. For symmetric cases, the edge curves become arcs of circles. To allow additional control, you can specify the smoothness (default one) of a sparse set of edges, which will cause chains of such edges to form a continuous curve and will concentrate the transverse curvature near this edge until it becomes a crease at a smoothness of zero. 

I've created a simple example below to demonstrate my two-level smoothing system. First I have the plain input mesh (blue), an intentionally difficult case with steep angles and long, narrow triangles, forming a very rough scallop shell shape. I have sharpened the perimeter from a smoothness of one at the back to 0.2 at the front. I've also included yellow polygons representing the halfedge tangents calculated at each vertex (their lengths have been scaled by their weight).

Next, I have the result of refining the above mesh, demonstrating the interpolated curvature. I have colored it according to the local mean curvature: blue is negative (concave) and red is positive (convex). Another feature of Manifold's API is that it can calculate the per-vertex mean curvature and Gaussian curvature. Note the red perimeter where the edges were intentionally sharpened, and how those sharpened edges form a smooth curve. 

Coloring:

You may note the wrinkles emanating from the sides of the top and bottom vertex, which are highlighted by the curvature coloring. If you uncheck Coloring, you can see what the shape looks like plain. The ripples are still visible, but reasonable considering the odd shape of the input mesh. The point of this example is to demonstrate that this API can produce decent results even when the input mesh is extremely low-resolution. 

As with any triangulation, an arbitrary surface can be approached by adding more vertices, but it happens much more rapidly using smooth interpolation. As an example, I meshed a sphere with different numbers of triangles and found the maximum deviation in radius for these curved triangles was one to two orders of magnitude smaller than for faceted triangles:

My goal for this high-level API was to minimize maximum absolute mean curvature, given the constraints of the vertices and intentionally sharpened edges. This was inspired by minimal surfaces, which have zero mean curvature everywhere. My system doesn't actually minimize this, as it's also designed to be simple and quick to calculate, but it makes a decent approximation. However, since the curvature can be easily calculated, it can be compared to other approaches that create these halfedge tangents differently. Do you have any ideas you'd like to try out?