GDC talk

I did a GDC talk on the latest CSG algorithm I developed!

You can watch it here

Realtime CSG Level Editor for Unity released!

Whoohoo!

Finally after years of working on it, I released my real-time CSG asset on the Unity asset store!

The project page can be found here!

CSG Unity plugin update 9

Yes, I'm still working on my real-time CSG plugin!

Here is some progress on CSG brush editing.
I decided I'll keep brush editing convex only for now, I really need to finish this plugin!
There's nothing that stops me from adding non-convex editing later on, it just means I need to handle a lot of of edge cases and that takes too much time right now.
As you can see in the video I also improved the grid rendering.

There are only some minor technical issues that I need to fix and then a list of trivial issues + polish.

CSG Unity plugin update 8

I guess I never posted this on my blog, oops!

Here's a video showing some WIP brush editing I've been working on.
It handles non-planar non-convex self-intersecting polygons.

Half-Life Black Mesa in Unity / CSG Unity plugin update 7

Hi! It's been a while since the last update and this is mainly because I spend 2 months in Copenhagen for my Unity onboarding and I didn't really have much time to work on CSG then or after.

Since I can't work on it full time anymore the pace is a lot slower, it doesn't help that I need to spend a lot of time & energy on the eventual move to Copenhagen at the end of January.

But don't worry, I'm committed to finishing this plugin and it will get done!

In the meantime, here's some eye candy for you to enjoy :)

Yes your eyes are not deceiving you, this is a Half-Life Black mesa level running in Unity.
I wrote an importer that imports all the brushes from black mesa maps and turn them into the CSG brushes that my plugin uses. I also wrote an importer for the meshes (which was a huge time-sink, maybe I shouldn't have done that!)

After I got the importer working to a point where it was good enough (for my purposes at least), I did some performance testing .. and at first it was much slower than I suspected. It was interactive, but definitely not as fast as I thought it would be. It took me a while to figure out that I was actually, accidentally, updating all the >3000 brushes in the level every time I moved a single brush!

CSG Unity plugin progress update 6

Just came back from vacation from sunny Turkey and in half a day fixed a bug that I spend a couple of days trying to fix before I left. Funny how that works some time.

The bug had to do with several brushes having a surface that lie on the same plane and where sometimes the wrong surface would be categorized as being visible, such as a surface that should actually not exist anymore because it was removed by another brush.

Now I can finally focus on merging brushes on the edges where they intersect, this should fix all the problems I'm having with gaps between brushes. I already have a good idea on how to do this, so hopefully this shouldn't take too long.

CSG Unity plugin progress update 5

So the last few weeks I've been busy fixing lots of issues here and there, making sure things work like they should etc. I still need to implement a couple of important pieces but I'm making good progress.

Here's a video that shows some of the things that the plugin can already do (one of these days I'm going to show something more interesting than a couple of simple shapes)

Finally, I've been offered a job at Unity! So pretty soon now I'll start working there and do my best to help make Unity even better than it is :)

(and this is one of the reasons why I've had so many distractions lately)

CSG Unity plugin progress update 4 - C++ / smoothing

The last couple of weeks where really busy, once again I had lots of distractions which made it hard for me to work on the plugin. I probably have something to announce soon!
I've done a couple of things however.

First of all I've moved the actual CSG code from Unity/C# to C++. The reason for this is because the more low level optimizations I did the more it felt like C# was actively resisting me trying to optimize everything.

The more you do low level optimizations, the more it starts to feel like C++ but without all the helpful syntax such as 'inline' and with pointer juggling without all the unsafe nonsense. I was actually already working with lots of big C# arrays + indices so I was effectively already doing memory management. Moving everything to C++ actually made it possible for me to clean up the code and make it MORE readable. Not something you usually hear when you compare C++ to C#!

The whole plugin was always intended as an editor only plugin anyway, so fortunately I won't condemn myself to supporting a gazillion platforms by moving everything to C++!
Other big benefits are that I have a clear separation between the Unity part and the CSG part, I can use good quality low level profilers to find bottlenecks and I have way more low level control over memory and performance now.

While I was moving everything to C++ it also gave me a chance to revisit some parts of the CSG process and fix some issues. One improvement I made, for instance, is normal smoothing, which at the moment can only be used on polygons that share the same texture coordinate surface.

Here you can see the normals in unity's 'normal' debug view.

Another, internal, improvement is that the CSG representation is now an n-tree internally instead of a binary tree. This matches the unity hierarchy better and allows me to have shallower hierarchies which should perform better.

My focus now is to get something out there, so I'm going to fix the remaining bugs and implement only what really needs to implemented for the first version.

Subdivision surfaces

Just got back from the states, so I still have a bit of jetlag (man I hate that). But anyway, someone suggested I should take a look at Mesh Fusion, which is a really interesting tool that does approximate CSG with subdivision surfaces.

This made me want to try to see if I can get my CSG algorithm to work with subdivision surfaces, which I never tried out. So here's my first attempt at performing subdivision surfaces on a cube mesh, about half a days work.

Next on my list of things to do is fix some t-junction issues on the final mesh that pops out of the CSG process. I need to get the whole plugin in a shippable status, after that I'll continue my research on subdiv.

CSG Unity plugin progress update 3 - Leaking Light

Until now I had a mesh per brush because I figured that would make it easier for the user to do whatever they want with the meshes they generate. They could use individual brushes for navigation, occlusion culling or give individual brushes different physics materials. I figured I would combine the meshes just before the game is played in the editor, or before the game is published to any particular platform.

Finally I hit a situation that clearly shows that I need to combine all meshes somewhere in the editor in real-time. This is unfortunate because I'd have to force the user to create parent objects for brushes that hold the meshes and I'm afraid this could be confusing to users when they create a brush (without a parent object) and nothing shows up.

The problems I bumped up against all have to do with Unity's lighting. 

Unity doesn't seem to like meshes being split into multiple different objects. For some reason, even when vertices of 2 objects align exactly (I checked this in the debugger), it'll cause leaks in the lighting. Maybe Unity introduces some minor floating point errors somewhere, I have no idea. Still, the light leakage is huge for seams that must be incredibly tiny (no matter how I orientate the camera I cannot see any seams, not even tiny flickering pixels). 

It is possible to get the lighting to not have seams by messing around with the light's bias parameters, but that doesn't seem like a long term solution to me. I don't want users to be force the users to spend hours messing around with lighting parameters just to make this work.

Another, much bigger problem, is that light-mapping using individual brushes is problematic to say the least. Technically it might be possible to join all brushes and force a re-bake of all the lighting when the game is published to a platform. It would cause changes in the appearance of the game between the editor and the run-time, and it would be SLOW to publish. So I'm pretty sure all I would accomplish is that I'd receive tons of hate mail and assassination attempts.

So now I'm rewriting some code so that there are these higher level components that capture all the meshes of it's child brushes and combine them in the editor in real-time. One problem is that unity would show this combined mesh as a single mesh in the editor. Select it and you select all the meshes of all the brushes that are combined in it at the same time. 

Fortunately I was already rendering brush outlines with custom code and was forced to implement my own ray-brush intersection / drag & drop code in the editor anyway, so I can actually work around Unity's limitations. It won't be pretty, but it'll work.

The silver lining is that doing things this way means that there won't be a gazillion MeshFilters, MeshColliders and MeshRenderes in the scene anymore. The brush components can also be changed into relatively simple classes that can safely be removed at run-time without side-effects. All that will remain at run-time are the meshes that have been generated by the brushes.

Update: 

I was wrong! Light leakage had to do with mesh size (not the size of the mesh in world-space). Apparently the shadow bias is calculated in the mesh's object-space, but then applied in world-space? So very large mesh + reasonable bias + downscale of mesh in world space = HUGE shadow bias that causes light leakage.

I (mostly) implemented the part where all CSG generated meshes are joined into one unity mesh and got a nice speed boost as well. I guess in retrospect, uploading all these tiny unity meshes was kind of slow. (which makes sense)

... now to fix a weird bug that causes all the brushes to be re-CSG-ed every frame, non-stop. *sigh*

(good thing it's still fast enough)

CSG Unity plugin progress update 2 - drag & drop materials

Another CSG update! Now it's possible to drag & drop materials onto the brushes, either on one surface or multiple surfaces at the same time. The video also shows procedural brushes (that can be turned into regular brushes). Meshes are generated in real-time, this is not some rendering trick.

CSG Unity plugin progress update - vertex editing

Just a quick update on my Unity CSG plugin (now in Unity 5). I implemented a WIP vertex editing tool to edit brushes (convex polytopes) with. I also implemented a WIP tool to edit the translation of textures on surfaces by just dragging it across the surface. Also my first 60hz youtube. yay!

Realtime CSG in Unity3D (video)

Just showing the progress on getting realtime CSG to work in Unity3D.

In the video you can see a worst case scenario for the CSG algorithm. The performance of the CSG algorithm is determined by how many brushes intersect with a brush, In this case 128 brushes intersect with a single brush.

Try doing this scenario in UE4! You will give up long before you actually get to 128 brushes. I'm not saying this to bash UE4, but it's the fastest realtime CSG out there in the wild.

There's still a lot of work to be done, not the very least I need to implement a way to easily build and edit the brushes themselves. I also still have lots of ideas to improve performance even further and some ideas on how to bound floating point errors no matter how many times edges get split.

Mesh optimizations

The last couple of (work)days I've been working on some code to optimize meshes generated by my CSG algorithm, which now works in Unity. 

Before

After

I'm quite pleased with the results. From 2073 vertices and 6951 triangles to 536 vertices and 2340 triangles. A pain to debug though :)

It's actually a heavily updated version of the CSG algorithm I blogged about/written articles on.. the new version is much faster.

Game Development Tools source code went up

The source code for the book "Game Development Tools" went up,
and you can find all the source code, including my CSG article, here!

Busy busy busy

For a long time me & Matthew have been working on an article on "real-time constructive solid geometry" (CSG) for the Game Development Tools book. We finished the article somewhere at the end of march, and last week we finished the demo. It's been a really interesting experience, writing an article, but it sure was a lot more work than I thought it would be! It really gives me a renewed respect for authors in general! Anyway, the source is going to be put on the book's website eventually, I'll post a link here when it's up, and eventually put it on git (when I can find time in my way too busy schedule). The article itself is basically a better written version of what I already wrote down on my blog, but with a couple of additional details, improvements and discoveries that we've made along the way!



While making the CSG demo I had a bug in my polygon splitting code (obviously fixed now), which looked kinda funny :)

Other than that I've been really busy with my regular projects, and a super secret IOS game which I've been working on with my friends at Limbic and Hidden Elephant. Can't wait to show some stuff from the game!

Unfortunately, all this means that I haven't had much time to work on my other experiments :(

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.

Realtime CSG - Part 5

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.
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.


The result:

Points are vertices moved towards the center of the polygon
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!

CSG operations update

In my last post I mentioned that I suddenly realized that all popular CSG operations (Addition, Subtraction & common) can be expressed as logical operations.
Using that knowledge it was trivial to rewrite all operations as a mix of logical OR (the simplest of operations) and logical NOT operations.

To reiterate:

•  ( A ||  B) = CSG Addition
• !(!A ||  B) = CSG Subtraction
• !(!A || !B) = CSG Union

Now the way my CSG code iterated over the CSG tree was basically to tell each child-node in which list to store the polygons that are inside, outside or touching (I actually have 2 categories of touching polygons, depending on the alignment of the plane that touches it).

Performing a logical NOT comes down to just swizzle the lists I'm passing on, so it's essentially free.
Leaving me with code for just 1 CSG operation that needed to work perfectly!

Although I got everything working with the more complicated code before, it had some really scary parts because of the CSG subtraction operation which was really hard to get right because I flipped the orientation of the polygons to get it working.
This caused a cascading effect which complicated all the other operations as well.

So when I rewrote it today I found a much more elegant solution which allows me to flip the orientation of the polygons at the very end, again simplifying everything even more.

It's pretty clean and easy to read now, I still need to test it.
I'm way more confident now about it working in all test cases compared to before because of it's reduced complexity.

CSG operations

Lately I've been posting a lot of random thoughts, and this is one of them.
Today I read a post at filmic games about CSG, and for one reason or another a thought popped up in my head:

CSG operations can be expressed more intuitively as logical operations!

Technically, bitwise operations would work too, at least from a programming pov, but would make less sense (we're not working with bits here, aren't we).

• A CSG complement operation would behave like a logical NOT operation (! in C languages), where the shape becomes "everything outside of the shape" (which is only useful as an intermediate step, not so much as an actual operation).
  
  
• A CSG common (also known as 'intersection') operation behaves like a logical AND operation (&& in C languages) because only the parts that are kept are the ones shared between the two shapes.
  
  
• A CSG addition (also known as 'union') operation behaves like a logical OR operation (|| in C languages) because all the parts of both shapes in this operation are kept afterwards.
  
  
• A CSG subtraction operation would actually be a combination of AND and NOT (A&&!B).
  
  

The pictures have shamelessly been taken from wikipedia on the topic of logical operators which interestingly enough showed CSG like pictures!
(They're actually Venn diagrams)

Which shows that these things are, in fact, the very same thing!
(Hmm ... I wonder why I never noticed that before)

Note that logical OR (CSG union) operations can also be expressed as !(!A && !B), and that I've already shown that CSG subtraction can be expressed as (A && !B), meaning that all popular CSG operations can be implemented using only NOT and AND operations.

Now consider that a NOT operation would effectively not change the mesh at all, but would only invert the classification of triangles being inside or outside, there would effectively only be one kind of mesh modifying operation left..

Interesting!