The Heart of the Matter - Polygonica's Boolean Engine

Why are 3D Boolean operations so difficult?

Well, often they aren’t. In a polygonal Boolean engine, you are performing lots of polygon-polygon or triangle-triangle intersections, and let’s face it, this isn’t the most difficult problem to solve within the field of computational geometry. So performing the cylinder/sphere Boolean operations shown above is not straightforward, but neither should it be too much of a challenge.

Of course, you’ve still got to consider things such as sensible performance optimisations on a single core, efficiently exploiting multiple cores and ensuring memory efficiency, but generally speaking a simple case is, well, ‘quite simple’. 

The problems with 3D Booleans arise because there are many – possibly an infinite number – of geometric cases that are not ‘quite simple’. 

Let’s explore some examples.

I’m sorry Dave, I’m afraid my floating-point isn't quite exact.

Firstly, an important digression about floating point numbers. Please skip if this is old news for you.

In most systems used in computational geometry and 3D graphics, calculations relating to coordinates are performed using the floating point representation. However, floating point numbers cannot be stored exactly in the data representations used by computers i.e. binary.

I’m not going to explain this here. There truly are an infinite number of explanations out there on the web e.g. this short video. 

The lack of exactness of binary floating point representations is a pretty critical fact of life that you have to deal with when working with any 3D geometric representation on a computer.

One of the common ways to deal with this issue is to set a precision below which two bits of geometry in your model, most commonly vertices, are deemed to be at the same location in space. If you wish to compare two vertices to check if they are at the same location, you could perform an equality test on each pair of coordinates, such as:

if ((x1 == x2) && (y1 == y2) && (z1 == z2)) 
{
    // Vertices are equal
}

However, as it is impossible to represent floating point numbers exactly in computer memory, the probability of that condition being satisfied for a particular pair of supposedly identical vertices occupying supposedly the same location in space is much lower than you’d expect.

So what can you do? Well typically you might do something like

const VERTEX_TOL = 1.e-9;
if ((fabs(x1 – x2) < VERTEX_TOL)&& 
    (fabs(y1 – y2) < VERTEX_TOL)&&
    (fabs(z1 – z2) < VERTEX_TOL))
{
    // Vertices are equal
}

// fabs makes the sign positive in all cases

Or perhaps compute the distance between the two vertices and test if that is below whatever tolerance your system uses.

Almost Normal

If you think of a Boolean operation as a bunch of polygon intersections, followed by connecting the results in an orderly manner, then it doesn’t seem like it should be too challenging. What’s all the fuss about? 

Well one of the really difficult situations a Boolean has to handle are when polygons or triangles (faces) on the two bodies involved in the Boolean operation are almost, but not quite, coplanar. 

As you can imagine from the description of floating-point numbers given above, this situation can occur surprisingly often. But why is it such a problem?

A standard way to compute the direction of the line of intersection of two planes is to use the vector cross product of the normals to each of those planes. I’m not going to go into details of how that works here – there are plenty of blogs and videos that explain it. 

In the images left and centre we see the standard case. It’s easy to calculate the normals from the cross product of the vectors along two of the edges, and then the cross product of the normals gives a vector parallel to the direction of the intersection.

What happens though when those two polygons are almost coplanar? Well, the plane normals can become very close to being identical. Variations in floating-point precision can start to have an effect on the results of the cross product calculation, which in turn can lead to variations in the direction of the computed intersection vector, as shown in an exaggerated form in the image on the right. 

If such variations occur across several adjacent polygons then the line of intersection that is computed may not actually meet at the polygon boundaries. It’s easy to imagine the kinds of problems this can lead to, particularly when you wish to create a watertight, manifold result.

Supermassive Black Hole

Alas, the problems don’t stop there. Black holes and the effects of general relativity aren’t common in polygon mesh modelling, but it seems they can occur. 

Consider the two n-sided polygons in the sketches below. The orange polygon is almost coplanar to the blue polygon - the sketch accentuates the difference. Based on the floating point tolerances in use, the vertices A1 and A2 lie in the plane of the blue polygon, whilst the vertices C1 and C2 are slightly above that plane. What of vertex B? The geometry suggests that if vertex B doesn’t lie on the plane of the blue polygon, it should lie above it. However …

Remember from the section on floating-point numbers above that we aren’t comparing coordinates exactly. We are treating vertices that are within a given distance of the computed surface – in this case the plane - as being on it. 

In the second diagram, looking side-on, we see the two planes computed from the vertex coordinates, plus the tolerance bands either side of this computed result. If a vertex from one polygon lies within the tolerance region of the plane of the other it is regarded as lying ‘on’ that plane. 

So what of vertex B? Where does that lie with respect to the blue plane? 

In fact, as shown in the second diagram, situations can occur where the floating point calculations result in vertex B being placed slightly below the blue plane rather than above it. So the intersection line of the two polygons passes through A1 and A2 but in between vertices B and C. We’ve got a planar polygon that is in fact curved, and our hunt for black holes is on.

Alas, this effect isn’t due to curvature in space-time. It’s most likely to occur due to the far more mundane lack of exactness in the storage of floating point numbers using a fixed binary representation as described above.

If the Boolean algorithm doesn’t detect this and handle it reasonably elegantly, then all kinds of problems can result. 

Of course if the concave polygon was triangulated there would be no non-planar planar polygon. But there would be other issues, including extra tiny triangles which need to be sorted into meaningful geometry, leading to tiny ‘noise’ solids or voids which both increase memory usage and can cause issues with downstream algorithms, or even cause problems in manufacturing processes, if not removed. 

In this case the extra information provided by using n-sided polygons rather than simple triangles gives the algorithm the opportunity to recognise the problem and deal with it in a more elegant way, creating a cleaner, more coherent result.

This is just one simple example to help explain why 3D Boolean operations quickly become very difficult, particularly when encountering real data from the wild. 

Sure, if you are using double precision floating point, the chances of this particular example occurring may be fairly small, but if you are performing many operations, or have badly formed input, then the chances quickly increase.

Why must it always rain on me?

I hope this example gives you some insight into why one of the very common stress tests for 3D Booleans involves surfaces that nearly match, but don’t quite. 

Such situations are common, and can arise in:

• models from CAD designs in which freeform surfaces are intended to be identical but don’t quite match
• models combined from different sources that have been tessellated in different ways to different tolerances
• models arising from scan data, where there are many small polygons and a lot of randomised vertex noise
• models that have been moved between different systems that use different coordinate precisions e.g. 3MF and STL store coordinates in single-precision whereas most CAD BREP representations and engines use double-precision.

Almost coplanar faces aren’t the only challenging geometric conditions faced by Boolean algorithms, but they are perhaps one of the most common. And difficult geometric edge cases don’t just arise in polygonal representations. They can arise in all geometric forms used in computational geometry, be they freeform mathematical surfaces such as NURBS/splines and implicits/signed-distance-fields, or sample-based representations such as voxels. 

In the end, if you want your algorithm to produce a quality result – connected, watertight and manifold – then you need to pay close attention to those tricksy floating point numbers, whatever geometric representation you are working with.

Don’t stress me now

The video below shows a simple stress test of the Polygonica Boolean. In each case there are two identical meshes – two spheres, two remeshed cuboids and two teeth scans. One mesh is being rotated and/or transformed randomly by a tiny amount, and then a Boolean operation performed. 

As you can see, after more than thirty years of continuous development, the Polygonica Boolean is very robust with respect to nearly but not quite matching surfaces.

Key Features of the Polygonica Boolean

Supported operations: 

• Union, Subtract, Intersect.
• Create intersection curve.
• Multiple Boolean union e.g. union entire scene or assembly in a single optimised operation.
• Sectioning by a plane.
• Splitting using a tool solid - intersection and subtract combined in a single operation.
• Gluing – union of surfaces that should meet exactly but don’t quite.

Speed:

• As described in the history section above, the Polygonica Boolean was designed to be performant, due to its original target use of CNC material removal simulation.
• The Boolean is fully multi-threaded.
• The Boolean has been designed so that performance scales well with data size.

Robustness:

• The Boolean has been in active use for over thirty years. In that time many edge cases have been dealt with.
• Customer bugs are fixed and added to regression suites, which are run continuously. Each new fix must pass all regression tests, which include all customer reported bugs from over three decades of regular usage in the CAM industry.

Support:

• Polygonica is fully supported. Customer reported bugs are fixed and between eight and twelve patch releases are issued each year.
• Polygonica includes an API journaling mechanism. If a customer encounters a problem they can reproduce in their software then send the API journal to the Polygonica support team. This can be replayed, on any supported platform in both debug and optimised flavours, to quickly reproduce the bug. New customer journals are added to the regression test suites.
• Both Polygonica and MachineWorks are subject to rigorous QA and regression testing, with tests built up over thirty years.

Open non-manifold data:

• The Polygonica Boolean supports and works on non-manifold geometry.
• The Polygonica Boolean works on both watertight and open data. However it is required that the geometry in the region of the intersection be watertight and free from self-intersections.

Options to keep, transfer or discard faces:

• The Boolean offers control over whether polygons are transferred from the tool to the target, or discarded. This is more relevant for Boolean operations on open surfaces.

Notifier callbacks:

• Both the Polygonica Boolean and Polygonica’s offsetting allow the application to specify callbacks which are called when individual vertices, edges and faces are created or discarded. This allows the application to closely track changes in the mesh and maintain associativity between the applications’ domain representation and the mesh inside Polygonica. Typically though such associations are regenerated each time a modified mesh is extracted from Polygonica.

Poor quality data and healing

Poor quality mesh data is common, for many reasons. If you are developing a mesh-based 3D Boolean algorithm, you can attempt to deal with the problems during the Boolean operation itself, or you can apply a pre-processing step which fixes a known subset of the problems.

Due to the requirements for high performance, the Polygonica Boolean places restrictions on mesh quality such that the parts must be watertight along the intersection region, and free from self-intersections everywhere. Apart from these stipulations, non-manifold geometry is supported.

Polygonica also provides best-in-class automatic mesh healing that will make a part or assembly watertight and remove all self-intersections. Healing greatly helps all downstream mesh operations, not just Booleans, to be faster and more robust, as they don’t continually need to check and handle tricky geometric situations that were removed by the healing process.

Conclusion

Robust, accurate and performant 3D Boolean operations that work correctly on a wide range of input data are amongst the more difficult algorithms to develop and maintain in the field of computational geometry. 

Polygonica’s 3D mesh Boolean is the result of several decades of continuous software development and bug fixing, and is protected by an extensive regression test suite managed by a full time QA team. 

If you want to test it for yourselves, please don’t hesitate to get in touch.