Friday, May 14, 2010

CSG operations update

In my last post I mentioned that I suddenly realized that all popular CSG operations (Addition, Subtraction & common) can be expressed as logical operations.
Using that knowledge it was trivial to rewrite all operations as a mix of logical OR (the simplest of operations) and logical NOT operations.

To reiterate:
  •  ( A ||  B) = CSG Addition
  • !(!A ||  B) = CSG Subtraction
  • !(!A || !B) = CSG Union

Now the way my CSG code iterated over the CSG tree was basically to tell each child-node in which list to store the polygons that are inside, outside or touching (I actually have 2 categories of touching polygons, depending on the alignment of the plane that touches it).

Performing a logical NOT comes down to just swizzle the lists I'm passing on, so it's essentially free.
Leaving me with code for just 1 CSG operation that needed to work perfectly!

Although I got everything working with the more complicated code before, it had some really scary parts because of the CSG subtraction operation which was really hard to get right because I flipped the orientation of the polygons to get it working.
This caused a cascading effect which complicated all the other operations as well.

So when I rewrote it today I found a much more elegant solution which allows me to flip the orientation of the polygons at the very end, again simplifying everything even more.

It's pretty clean and easy to read now, I still need to test it.
I'm way more confident now about it working in all test cases compared to before because of it's reduced complexity.