A Practical Guide to Boolean Operations on Triangle Meshes
The allure of generic set operations applied to your triangle meshes has led you here at last. You want subtractions, intersections and unions for your latest project, ideally supporting chained operations and — of course — be blazing fast. It's gotta handle huge meshes. It must be reliable.
Bright-eyed, you set out armed with your raw wits and Möller's triangle intersection algorithm. Your BVH skills are pretty good, and you've already been thinking ahead to some interesting cases, like if a vertex from one mesh lies on a vertex from the other mesh. Floating point error hasn't escaped your notice, and you're careful to keep track of how reliable your geometric comparisons are.
It takes you weeks to produce results.
Initial tests look good, but there's a few cases that you forgot to consider.
Complexity increases.
Your test suite gets larger.
Complexity continues to increase.
It slowly dawns on you that fundamental mistakes have been made, but the real truth is that almost every choice you made was flawed.
It is a beautiful but very inconvenient fact that the technicalities of boolean operations dominate implementation. You can't fly a plane without wings (even if you refuse to call them "wings"), and you can't do boolean operations on triangle meshes without a better floating-point philosophy than the various flavors of compare-with-epsilon. The boolean operations problem is even difficult to define properly, with any assumption almost sure to bite you down the line. You might think, for example, that a triangle mesh separates an "inside" from an "outside", and that this is good enough for your use case. Not so. Think you can get away with using an existing library for 2D triangulation? Think again! You're going to have to toss most of your favorite geometry algorithms (including Möller's, unfortunately) and start rebuilding from the ground up.
I almost recommend YOLO-ing it once (as I did above) for purely educational value, but your time is worthwhile, and what is the point of literacy if not to communicate what we need not experience?
This post is the landing page for sub-posts of considerable length, each dealing with a particular facet of the boolean operations problem. This is meant to be an educational experience for you, the reader, but also permanent documentation for me, who will be reimplementing the entire algorithm from scratch. Math experience is a bonus, of course, but I'll try to keep extensive math digressions as optional as possible.
Sub-pages