I spent some time playing around with CSGJS over the weekend. It’s a great library. I thought it might be interesting to port it to C++.
After quite a lot of googling I found that someone had already done most of the hard work here which was nice and they had kept the MIT license which was even better.
I decided I’d take their work and see if I could improve it a little and learn how it worked.
The fundamental algorithm used is to take two sets of convex polygons that make up a 3D model, create separate BSP trees and then perform union, subtract or difference algorithms upon the target BSP tree. The algorithm is actually very nice and well documented here Constructive Solid Geometry Using BSP Tree - Christian Segura1, Taylor Stine2, Jackie Yang.
The code I took worked pretty well but I managed to optimize making it about 40% faster and removed the memory leaks.
Here are some examples of the output.
A gourd with a cylinder subtracted
The same gourd with the cylinder added (union)
Cube with a sphere union and cylinder subtracted along x, y and z axis
The good thing about the algorithm is that it’s recursive nature and simple testable stages make it pretty easy to implement and test. The downside is that the creation of BSP trees both at the initial “list of polygons to BSP” stage and the processing stage cause a lot of allocations making this unsuitable for real time operations.
Anyway, all my changes and test harness are available on git hub for people to play with.
Comments