Introducing my Manifold Library

3 minute read.

Manifold is my computational geometry library - the beginnings of a CAD kernel of sorts. Its purpose is fast, reliable, topologically-sound operations on manifold triangle meshes. Reliability is really the key: I started this library because I was amazed at how unreliable the geometry kernels I had experienced (even high-end CAD) were in generating manifold - basically solid - output. The lack of reliability stems from the fact that Euclidean geometry is based on real numbers, but computers work in finite precision with rounding errors. This means it is entirely possible for a computer to find two points to be on the same side of a line, but their midpoint to be on the opposite side: Euclidean geometry does not hold. 

For this reason, many computational geometry libraries are proven correct for "general position" input, which means geometry where nothing is within rounding error of coincident, co-linear, or co-planar. This might be okay if the geometry were randomly distributed, but when dealing with human designs, "general position" is in fact the exception, not the rule. Modifying these algorithms to try to handle the "edge cases", which are in fact extremely common and widely varying, results in poor reliability. 

This library takes the approach of avoiding Euclidean assumptions to make a result that retains manifoldness for any input, with no special edge-case handling required. To properly verify this, I chose a very demanding test case: the Menger sponge.

This Menger sponge was created by cutting the same network of holes through a cube in the X, Y, and Z directions (a total of three Boolean difference operations) and is an ideal test case for several reasons. It is a fairly uniform and well-behaved solid with a genus (number of handles) that can be calculated analytically. It is fractal, so it can be built at a range of different complexities. It has complicated polygonal faces (many holes) that test triangulation. But most importantly, nearly every intersection is not in general position: instead of an edge intersecting a face, it nearly always intersects another edge or vertex. However it does not always intersect perfectly, since binary numbers cannot represent thirds exactly.

This test is also designed to showcase an important convenience aspect of this library: intuitive symbolic perturbation. Despite my focus on rounding error, it is still quite easy to create exact positions in a computer - for instance making the holes exactly the same length as the cube itself. If they were slightly too short, no holes would be visible as a thin membrane would cover the ends. But what if they are exactly aligned - membrane or no membrane? Either answer is a geometrically-valid solution, but it's clear that creating infinitely thin surfaces is not generally desirable. 

To easily create desirable results, this library uses intuitive symbolic perturbation to break ties for exactly equal coordinates, in the right direction so that infinitely thin surfaces and gaps are avoided. In so doing, the above fractal is properly created even though the set of subtracted holes is exactly the same length as the cube is. This avoids the need to pad dimensions with small tolerances, which can build up in complicated ways, as I often had to with OpenSCAD.

Of course if coordinates do accrue rounding error, then the symbolic perturbation no longer applies. An example is below: the difference of two identical cubes, except they are rotated in opposite directions and shifted to overlap, but not perfectly due to rounding error. 

Note all that's left is a surface with thickness of roughly the machine precision. These effectively random surfaces should be expected for any mesh Boolean algorithm where the shapes are nearly coincident. However, this library takes care to avoid introducing rounding error by using degrees instead of radians for rotations and ensuring that the most common rotations - those by multiples of 90 degrees - introduce zero rounding error. This feature is demonstrated by the Menger sponge above, since the same manifold was used to cut the holes in all three directions.

The above is a third-order Menger sponge, having a genus of 1,409 and 21,598 triangles. The test case that's part of my CI is fourth-order, having a genus of 26,433 and 396,896 triangles, but it's a bit of an eyesore and won't render very quickly on a cheap phone. 

Critically, the degenerate removal step has successfully removed every single degenerate triangle from these sponges and in so doing attained the correct genus by collapsing microscopic topological oddities. Although this step can take a significant fraction of the computation time, it in fact reduces total computation time in these examples because without it the result can have an orders of magnitude more triangles. 

Without even enabling GPU acceleration on my several-year-old Linux box, I can calculate the above third-order sponge in less than 0.7 seconds, and the fourth-order one in less than 30 seconds. However, these are very extreme examples that take much longer than their number of triangles would suggest. Performance of more representative examples will be the topic of my next post.