In part 1 I explained the basics you'll need to know to understand how to perform real-time CSG.
In part 2 I described how to build a brush, which is the basic building block of the algorithm I'm describing.
In part 3 I wrote about CSG operations.
As I mentioned in my first post of the year; The most important thing to realize is that when you're performing CSG with multiple brushes, no matter which operations you perform, or how you group your brushes, the final mesh you'll end up with will always consist out of (parts of) the original polygons, which where made out of our brushes.
Only parts of these original polygons are removed, no new polygons need to be created, ever.
So in the end, we basically need to manage which parts will be visible or invisible depending on the situation.
At the end of part 3 I said that in the next blog post I would write about how to traverse the operations list.
Well, before I we get to that part I need to explain how to cut up a brush into the right pieces.
Cutting the brush
In part 1 I wrote about cutting polygons.
Cutting a brush is a natural extension to that.
The algorithm is pretty straight forward; for every brush you intersect with, cut each polygon of your brush with the planes of the intersecting brush.
All the pieces that are on the outside of the polygon are classified as "outside".
At the end, if there's anything left of the original polygon, then that's either "inside" or "touching-inside" or "touching-outside".
The polygon is "touching" when all the points of the polygon lie on one of the planes of the intersecting brush.
By comparing the normal of the polygon and the touching plane you can determine if it's "touching-inside" (normals are pointing in the same direction) or "touching-outside" (normals point in opposite directions).
You can use a dot product between the normals for this.
If the result of the dot product is positive, they're pointing in the same direction, if it's negative they're opposites.
Obviously if it's not touching, it's "inside".
Depending on the situation you'd need to discard your polygon pieces if it's inside/touching-inside/touching-outside or 'just' outside.
Next time
That's all I have time for today, the next time I'll go through the algorithm for general CSG.