When I started blogging about CSG I thought, how hard could it be to turn this into a full implementation?
Easy, right?
Boy was I wrong.
My old implementation only supported subtractive and additive brushes and didn't supporting any grouping of brushes. This made it possible to put all the brushes in a single list and let the brushes BE the CSG operation themselves.
In a full implementation things get way more complicated, mainly because of the grouping of brushes and the tree like CSG structure which results out of that.
The cool thing about CSG is that, except the brush splitting method, it actually works exactly the same in 3D as it does in 2D.
So I made a tool to perform CSG in 2D to build an CSG implementation which I could then, once I've got it to work, transfer to a 3D implementation.
After all, 2D is much much easier to debug and visualize.
Anyway, my theory to get a full real-time CSG implementation working is like this.
First of all, each brush is processed separately so we can not only perform these operations in parallel, but also update individual brushes without needing to reprocess everything.
Since in any CSG implementation the resulting mesh would only included portions of the original polygons created from the original brushes, no new polygons would be created.
This means we can use our brushes and operations as a sort of query over the polygons of these same brushes.
We 'just' pass our polygons through our CSG tree and determine which pieces are visible and which ones are removed.
At a higher level the CSG tree could be simplified on a per brush basis and some space partitioning data structure could be used to avoid unneeded calculations, but I haven't got to that point yet.
Our brush splitting method will tell us which lines are inside/outside or touching and if we make sure that at every stage in our tree we correctly determine if the given polygons is inside/outside or touching then we should end up with the correct polygons.
The inside/outside part is relatively easy, it gets hard with the touching part though.
Take for instance the following simple situation with an additive operation and two brushes:
In the left situation we want to treat the parts of the polygons that touch as being "inside" this particular branch of the CSG tree, on the right we want to keep the touching polygons.
Well we actually want to remove it for the left brush and keep it for the right brush, but this can be solved by detecting if surfaces on the left and right brush overlap, and then only keeping the polygons that belong to the last brush that overlaps.
We can solve this by taking the relative orientation of the polygons into account;
If they're opposites, remove them, if they're aligned, keep them.
For subtractive operations it gets more complicated:
In the left situation I'm doing something which may be debatable.
When the subtractive brush touching another brush on the outside, I keep that polygon part because I want the subtractive brush to be able to override the underlying brush.
In the right situation not only do we keep all the polygons of the subtractive brush that are inside (we remove all the polygons that are outside), but we need to change the orientation of the polygons too!
This brings me to the biggest problem with CSG trees; the number of polygons increase, because of splits, as you go down the tree!
This works fine as long as you work with a single list of nodes, like in my old algorithm, but when you have a tree like data structure this causes lots of problems.
Suppose I first categorize my polygons in the left branch into inside/outside/touching-inside/touching-outside categories, what happens if I then try to categorize those same polygons in the right branch?
The original polygons could actually be split into lots of new pieces, and I have no easy way to match them together! (Certainly not in a hierarchy that's x-levels deep)
Even if I find a good way to handle this, imagine what happens a polygon's orientation is changed in the right branch, it would've been categorized wrongly in the left!
This probably means I have to determine the orientation of a touching polygon at the very last moment, but that would require me to pass along additional information like which plane it was touching.
Right now I 'solve' this by going through the CSG tree and splitting functions several times, but to say that this is inefficient would be an understatement..
I'm playing with some ideas, like building some sort of categorization tree, but they're not fully gestated just yet.
I'm close, but I'm not there just yet.
Edit:
It's funny how writing things down often helps you find an answer to a problem!
This is my solution:
Categorize(branch.Left, ... );
//for each category
foreach(var polygon in myCategory)
{
Categorize(branch.Right, ... );
// now, even if the polygon has been split,
// we know the category of all polygons
// in both the left and right branch!
}