Realtime CSG - Optimizations

The last time I blogged about realtime CSG, I mentioned that in my test scene if I performed CSG on the entire scene it would take about 80ms.
(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.