In part 2 I described how to build a brush, which is the basic building block of the algorithm I'm describing.
This time I'll start explaining some parts of my CSG algorithm.
CSG Operations
Now that we've created our brushes, we want to build larger meshes with them.
We do that by performing certain operations between them, these are similar
to regular algebra because their order matters greatly and you really want
to be able to group them together.
Formally there are 3 types of CSG operations:
- Addition, sometimes called 'Union' or 'Merge'.
- Subtraction, sometimes called 'Difference'.
- Common, sometimes called 'Intersection' or, confusingly 'Union'.
At each operation we determine which pieces of each mesh is inside, outside or is touches the other mesh. (Something I'll be blogging about eventually)
(A brush 'touches' another brush when one of it's polygons lies exactly on the plane of the other brush)
Depending on the type of operation these polygon pieces are either discarded or kept.
Since you almost never would want to perform a 'common' CSG operation on anything but a small number of brushes, you really need to group brushes together.
This is also, to a lesser degree, true for subtractive brushes.
This means you'll need some sort of tree structure so you can determine what operation to perform on and with which brushes.
Divide and conquer
So do we need to perform those operations on all brushes for each brush?
Fortunately not!
The trick is that for each brush, using some sort of bounding volume hierarchy, you determine which brushes intersect or touch your brush, and then put them into a list (let's call it an operations list) which is also sorted by the order in which they appear in your CSG tree.
So now that you have a list of operations to perform on each brush, on a per brush granularity.
This means that when a brush is added, deleted, moved or is modified, only that brush and the brushes it touches need to be rebuild, this is the part that makes this algorithm real-time.
This also makes it easier to perform each brush update in parallel, which will make this algorithm faster and faster the more cores a CPU has!
Early outs
Keep in mind that you can drastically shorten your operations list by having some intelligent early-outs.
For example, if the brush your working on is inside another additive brush, which is further on in your CSG-tree, then you know that you can just discard the entire brush (because anything you do will be deleted further on in the tree anyway).
In the reverse you can also just ignore the smaller brush when processing the larger brush because it'll never have any effect on this brush.
There are many cases like this, but be careful with this, I've tried a lot of early-outs which seemed to work most of the time but then broke down on a rare situation!
User interface limitations
In my editor I never implemented the CSG-grouping of brushes because it's really hard from an user-interface point of view.
In an editor you really want to group brushes semantically (for example all the brushes that form a 'door' or 'window') instead based on operation (artists aren't programmers after all, nor should we burden them with technicalities; they need to focus on their art, not their editor!).
If you try to implement this sort of functionality in an editor, you'll get an extra level of complexity which will really make your editor harder to use and understand.
That said, it shouldn't be too hard to implement because from the algorithms' point of view, it only effects the building of that operations list I was talking about earlier.
Nothing is stopping you from implementing a full implementation and not necessarily exposing all the functionality (all the time) in your editor, if you're building something which doesn't require an editor this is not so much of a problem obviously.
Processing a brush
To process each brush, we need to traverse the operations list.
Both parts of it.
The thing is, all the brushes that are ahead of our brush in the hierarchy, need to be handled differently than the brushes that come after it.
Which is exactly what I'll be blogging about next time!