CSG booleans

A cube, a sphere and three cylinders. Four boolean cuts on plain triangle meshes, each one a BSP tree clipping another BSP tree.

The problem

Two meshes that overlap are still two meshes. Draw a cube and a sphere in the same spot and you get a cube with a sphere poking out of it, with every hidden face still there. To carve a hole, merge two shapes or keep only the shared volume, you need new geometry: the faces of A that sit outside B, the faces of B that sit inside A, and every triangle cut where the two surfaces cross.

How it works

Each mesh becomes a BSP tree. A node takes the first polygon of its list as its split plane, keeps the polygons that lie on that plane, and sends the rest to a front child or a back child. A polygon that crosses the plane is cut into a front piece and a back piece.
Clipping is the core move: push A's polygons down B's tree and drop whatever ends up in solid space. Invert flips every polygon and swaps front and back, which turns solid into empty.
Union clips A by B, B by A, then once more on the inverted B so coplanar faces are not kept twice. Subtract inverts A first and back at the end. Intersect inverts both. Every vertex test uses a 0.00001 tolerance.

What I hit

My first port flipped vertices in place. Split pieces share vertices, so a shared one could get flipped twice, and the result came out striped with wrong normals. In the C# source a vertex is a struct and is copied by value. Copying on flip fixed it.
The sphere has 960 triangles and its BSP tree has 480 nodes in a single chain, 480 deep. A convex shape has every other face behind each face plane, so the tree never branches.

My build

Ported the BSP node, plane split, polygon and vertex code to JavaScript and drew the results with three.js.
Inputs: cube 12 triangles, sphere 960, each cylinder 128.
Union 2,266 triangles. Cube minus sphere 1,754. Intersect 724.
Against the cube face at x = 0.8, the sphere's triangles sort into 66 front, 844 back and 50 spanning. The 50 spanning ones split into 50 front and 50 back pieces.
Chained: intersect 724, minus cylinder X 1,544, minus Y 4,878, minus Z 8,645.

Trade-offs

Every cut adds triangles, and long thin slivers pile up along each seam. There is no split heuristic, so tree shape depends on polygon order. The output is not welded: each triangle gets its own three vertices. The tolerance is applied to an unnormalised plane, so its real size changes with triangle area.

When to use it

Editor tools, level blockouts and one-off cuts at load time, where a few thousand triangles of output is fine. For repeated cuts on dense meshes every frame, plan for cleanup, or reach for a different method.