[gorb314]

Constructive Solid Geometry using BSP trees.

There is a javascript implementation [0] which is where I saw it the first time, it is about 500 lines of fully commented code. The algorithm is so simple, I absolutely love it.

Basically, when performing a union on two meshes, we determine the 3d BSP trees from both meshes, then simply clip each mesh using the other's tree. The output is the union of the two leftover meshes.

And since both intersection and difference can be written as a combination of inversion and union, they are simply composed from those.

I can't find a good paper on the algorithm though, not sure where exactly it originated.

[0] https://github.com/evanw/csg.js/blob/master/csg.js

[solidr53]

Nice! I studied the library by porting it to TypeScript.

https://github.com/birkir/csg.js/blob/patch-1/csg.ts

[gorb314]

Nice work...

I've ported this algorithm to Python, but mine is nowhere as succinct as yours (or the original). For my needs, I require the meshes to remain watertight (if the inputs are watertight), and this specific implementation doesn't preserve it. But I still love the algorithm due to its conceptual simplicity.