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.
In part 4 I wrote about cutting a brush with another brush.
When I started on writing about real time CSG, I had my original real time CSG algorithm in mind.
It's a simple enough algorithm, but a very simplistic subset of CSG.
I foolishly thought I could just figure our how to generalize it as I went along, it turned out to be a little bit harder than that.
Eventually I managed to get an algorithm to work, but it was complicated and un-intuitive.
The additive and common operations seemed coherent all right, I could rationalize every piece of it.
But the subtractive operation, my god, it was frankenstein as code..
It just didn't make any sense!
I managed to make it work, but only through trial and error.
And even though it seemed to work in all my tests, I didn't really trust it.
It definitely didn't feel right to unleash that piece of code into the wild, imagine what kind of damage that could do in the wrong hands!
And then, as I blogged about before, I read a post at filmic games and it hit me; not only can CSG operations be seen as logical operations (which makes it so much easier to express), but the subtractive operation is actually a combination of operations!
That's why it was so hard to get it to work coherently, I was trying to doing multiple things at the same time!
After that figuring out the lean and mean version of my previous algorithm was fairly easy.
Categorization
As I mentioned before, the final solution of the entire CSG tree consists of all the polygons of all the brushes MINUS all the pieces of these polygons that we reject.
We don't add any new polygons, at all.
Ever.
We just remove parts.
So the heart of this CSG algorithm is the categorization code, this code takes the polygons of a brush, goes through the CSG tree and categorizes each piece of the polygon as being inside, outside, or touching the shape that the entire CSG tree (or sub-tree) represents.
Well actually we have two types of "touch" categories, inside-touching (plane aligned) and outside-touching (aligned with the reverse of the plane).
We essentially do this for every left / right branch and then swizzle the categorization depending on the CSG operation and the results from the left and right branch.
First the code for the branches in the tree (pseudo code)
void CSGBranch.
Categorize( categorizationNode,
inputPolygons,
...,
inside,
touchInside,
touchOutside,
outside)
{
// Early out, check if the bounding box of
// the categorizingBrush intersects with
// the bounding box of this branch.
// If it doesn't, don't bother going any further
// (This effectively works as a, somewhat
// unbalanced, bounding volume hierarchy)
if (boundsOfPolygons
.IsOutside(this.Bounds))
{
// ... add all input polygons to outside
outside.AddRange(inputPolygons);
return;
}
switch (Operator)
{
case CSGOperator.Addition:
{
// (Left || Right)
LogicalOr(categorizationNode,
inputPolygons,
...,
inside, touchInside,
touchOutside, outside,
false,
false
);
break;
}
case CSGOperator.Common:
{
// !(!Left || !Right)
LogicalOr(categorizationNode,
inputPolygons,
...,
outside, touchOutside,
touchInside, inside,
true, // reverse Left
true // reverse Right
);
break;
}
case CSGOperator.Subtraction:
{
// !(!Left || Right)
LogicalOr(categorizationNode,
inputPolygons,
...,
outside, touchOutside,
touchInside, inside,
true, // reverse Left
false
);
break;
}
}
}Notice how elegant it is?The LogicalOr method is basically the CSG Addition operator.
The inside, touchInside, touchOutside, outside parameters are lists to which the polygon pieces are added.
Notice how the 'not operator' is basically nothing more but a reversal of the parameters!
The last two parameters are used to tell the LogicalOr method if the left and/or right branch need to have their parameters reversed.
So here's the LogicalOr method:
void CSGBranch.
LogicalOr( categorizationNode,
inputPolygons,
...,
inside,
leftTouchInside,
leftTouchOutside,
leftOutside)
{
// right
// inside | touch-I | touch-O | outside
// left | | |
// inside I | I | I | I
// touch-I I | tI | I | tI
// touch-O I | I | tO | tO
// outside I | tI | tO | O
... create some temp lists ...
// if anything is inside the left branch,
// we don't need to check it again for
// the right branch. Everything else is put
// in temporary lists whose contents we'll
// check against the right branch ...
if (!inverseLeft)
Left.
Categorize(categorizationNode,
inputPolygons,
...,
inside, leftTouchInside,
leftTouchOutside, leftOutside);
else
// .. same as above but with parameters
// reversed
if (!inverseRight)
{
// right
// inside | touch-I | touch-O | outside
// left | | |
// touch-I I | tI | I | tI
Right.
Categorize(categorizationNode,
leftTouchInside,
...,
inside, touchInside,
inside, touchInside);
// right
// inside | touch-I | touch-O | outside
// left | | |
// touch-O I | I | tO | tO
Right.
Categorize(categorizationNode,
leftTouchOutside,
...,
inside, inside,
touchOutside, touchOutside);
// right
// inside | touch-I | touch-O | outside
// left | | |
// outside I | tI | tO | O
Right.
Categorize(categorizationNode,
leftOutside,
...,
inside, touchInside,
touchOutside, outside);
} else
{
// .. same as above but with parameters
// reversed
}
}
Note that if a polygon is touching-inside on one branch, and touching-outside on the other branch, then it means the two branches are touching each other there.
Which means that any polygon in that area is essentially inside both, and therefore 'inside'.
And here's the code that handles the leafs in the tree; the brushes themselves:
void CSGBrush.
Categorize( categorizationNode,
inputPolygons,
...,
inside,
touchInside,
touchOutside,
outside)
{
// Early out, check if the polygons we're
// processing belong to the same brush as
// we're currently checking against
if (categorizingBrush == this)
{
// We're looking for the parts of
// 'categorizingBrush' that are visible
// and at this position in the tree, these
// polygons are definitely visible ...
foreach (var polygon in inputPolygons)
polygon.Visible = true;
// We know all polygons are interesecting
// with the brush they lie on
touchInside.AddRange(inputPolygons);
return;
}
// Early out, check if the bounding box of
// the categorizingBrush intersects with
// the bounding box of this brush.
// If it doesn't, don't bother going any further
if (boundsOfPolygons
.IsOutside(this.Bounds))
{
// ... add all input polygons to outside
outside.AddRange(inputPolygons);
return;
}
... create some temp lists ...
this.Split(inputPolygons,
...,
inside,
tempTouchingInside,
tempTouchingOutside,
outside);
// We know that the current brush
// is not the 'categorizingBrush'.
// We also know that any polygon liying
// on the surface of this brush cannot
// be lying on the surface of
// 'categorizingBrush' (well okay, it
// can, but one overrides the other
// depending on order, which is exactly
// what we want)
// So we set all the polygons lying on
// the surface of this brush to invisible.
// This solves overlapping polygon problems
foreach (var polygon in tempTouchingInside)
polygon.Visible = false;
foreach (var polygon in tempTouchingOutside)
polygon.Visible = false;
touchInside.AddRange(tempTouchingInside);
touchOutside.AddRange(tempTouchingOutside);
}And finally here's what we do at the top level:
void CSGTree.
ProcessBrush(categorizationNode,
inputPolygons)
{
.. create temporary lists ...
// Categorize the inputPolygons
// depending on their location in
// the tree ...
RootNode.
Categorize(categorizationNode,
inputPolygons,
...,
// Store results in
// temporary lists ..
invisiblePolygons,
visiblePolygons,
reversedPolygons,
invisiblePolygons);
// We set all polygons that are outside
// or inside the tree as being invisible ...
foreach (var polygon in invisiblePolygons)
polygon.Visible = false;
// We reverse the order of all the polygons
// that the tree categorized as having a
// reversed orientation ...
foreach (var polygon in reversedPolygons)
ReverseVertexOrder(polygon);
}
And that's it!
After you've build all the geometry, when a brush moves, simply reprocess it and all the brushes it touches.
to make it easier to see where there are any t-junctions,
or where multiple vertices lie on the same line
Note that I didn't describe the CSGBrush.Split method, I'm going to retroactively modify the previous posts to add more pseudo code (it belongs there), and update the repository as well.
(but not today)
I'll post about it when I've done that.
Limitations and Future work
When I use this algorithm on my test level which has 234 brushes and 467 nodes, I can generate a mesh with it within about 80ms.
Keep in mind that this algorithm was designed with dynamically updating a handful of brushes in mind, not so much with updating everything all the time.
The resulting mesh has not been optimized yet, there are T-junctions and polygons that should be joined together, but that's a different topic and really deserves a series on it's own.
If the polygons are optimized per brush, T-junctions should be a rarity considering that the cutting plane that split an edge, would've cut any aligned edges on another brush as well.
(Of course, there might still be T-junctions because of floating point errors, so don't completely rely on this)
As for performance, there is much room for improvement here:
- All brushes are processed independently, which makes them a prime candidate for parallelization.
(This is what I did in my editor) - This is the big elephant in the room; The algorithm should be rewritten with CPU cache usage in mind, this alone could make it an order of a magnitude faster. Half edges are the biggest problem here. The code would become more complex.
- A higher level bounding volume hierarchy, hashed grid, or sweep & prune phase could theoretically speed things up. Although when I tried it, it only slowed things down.
I'm guessing that this is because we're already doing some sort of (unbalanced) hierarchical culling while going through the CSG-tree, so perhaps there's not too much to be gained. Perhaps this only becomes a problem when the tree grows very large. - I'm convinced that it should be possible to figure out some short cuts when going through the tree. Perhaps it's even possible to work from the bottom-up, by starting at the leafs.
Perhaps that would allow getting rid of all the temporary lists, which is not so much a problem in a language such as C# where allocation is very cheap, but a bigger problem in languages such as C++. - There are a lot of lower level optimizations that can help a lot with performance too.
I'm using a lot of methods and enumerations in the example code for clarity and readability, and these hurt performance.
Once you understand the code, you should consider copying all the planar/vector methods code directly into the methods where they're used.
Also, you should consider not converting planar side calculations into enums, but using the floating point values instead.
This should help a lot in the inner loops and could seriously improve performance.
That's it for now, let me know if I need to explain something in more detail or if you use or improve on my algorithm!