(And I should mention again that this algorithm is intended for fast updates, not necessarily doing this faster for the entire CSG tree. Even though that would be a nice bonus)

I also mentioned a couple of things that could be done to improve performance, and that there are a lot of ways to improve performance.

Today I had a simple idea to improve performance.

By checking the bounds for each left and right branch separately at a higher level, so that we know what operation we're performing, we can handle some common situations in a more simplified, and faster, way.

Here's the updated pseudo code for the CSGBranch.Categorize method.

void CSGBranch. Categorize( categorizationNode, inputPolygons, ..., inside, touchInside, touchOutside, outside) { switch (Operator) { case CSGOperator.Addition: { // Check if the given polygons // are possibly touching the // left branch if (boundsOfPolygons .IsOutside(Left.Bounds)) { // Polygons are not touching // the left branch. // Check if the given polygons // are possibly touching the // right branch if (boundsOfPolygons .IsOutside(Right.Bounds)) { // Nope, all of them are // categorized as 'outside' outside.AddRange( inputPolygons); } else { // We only need to check // with the right branch Right. Categorize(...); } } else // Polygons are touching // the left branch. // Check if the given polygons // are possibly touching the // right branch if (boundsOfPolygons .IsOutside(Right.Bounds)) { // We only need to check // with the left branch Left. Categorize(...); } else { // Polygons are touching // both branches // same as before ... // (Left || Right) LogicalOr(categorizationNode, inputPolygons, ..., inside, touchInside, touchOutside, outside, false, false ); } break; } case CSGOperator.Common: { // Check if polygons are outside // either left or right branch if (boundsOfPolygons .IsOutside(Left.Bounds) || boundsOfPolygons .IsOutside(Right.Bounds)) { // Considering that in a // 'common' operation we need // to find the parts that are // shared with both branches, // we know that if the polygons // are outside just one branch // that they are categorized as // 'outside' outside.AddRange( inputPolygons); } else { // Polygons are touching // both branches // same as before ... // !(!Left || !Right) LogicalOr(categorizationNode, inputPolygons, ..., outside, touchOutside, touchInside, inside, true, // reverse Left true // reverse Right ); } break; } case CSGOperator.Subtraction: { // Check if the polygons are // touching the left branch if (boundsOfPolygons .IsOutside(Left.Bounds)) { // The right branch removes // and the left branch keeps // whatever is inside it. // If all the polygons are // outside the left branch // then we know they're all // categorized as 'outside' // this branch. outside.AddRange( inputPolygons); } else // Polygons are touching // the left branch. // Check if the given polygons // are possibly touching the // right branch if (boundsOfPolygons .IsOutside(Right.Bounds)) { // If we're only touching the // left branch, we don't need // to do a more complicated // operation, and just // categorize the left branch. Left. Categorize(...); } else { // Polygons are touching // both branches // same as before ... // !(!Left || Right) LogicalOr(categorizationNode, inputPolygons, ..., outside, touchOutside, touchInside, inside, true, // reverse Left false ); } break; } } }

This alone increased the speed from about 80ms to 25-30ms for the entire test scene.

I'm going to use a much bigger scene in the future,

because it really is too small to properly test for scalability.