Every once in a while the topic of CSG comes up. For those of you who don’t know, CSG stands for Constructive Solid Geometry. It essentially refers to making solids from boolean combinations of other solids. This is a problem from a past life when I was working on CSG with Jarek Rossignac at Georgia Tech.

Anyways, I was perusing the graphics blogs and saw a CSG post on Sander’s blog. The fundamental question is if you have a CSG object, how do you extract the watertight mesh surrounding it. This post is going to be a lightning course in CSG. Disclaimer: I haven’t dealt with CSG in several years so there may be mistakes.

Btw, as a warning, there is lots of programmer art ahead. If your eyes hurt easily, consider yourself warned.

CSG Intro
Suppose that we have two spheres.

The first operation that we have is the union. The union of A and B means that a point is either in A or B, possibly both. The notation is either A+B or A∪B. Both are valid. Here is the solid:

The next operation is the intersection. There are three ways to write it: A*B, A∩B, and AB. The intersection looks like so:

Another simple operation is not, and I’ll use !. It’s also called the complement. The most common notation is to use a line over it, which is a pain in HTML. You could also use ~. !B looks like this:

The last operation I’ll talk about is subtraction. It’s written as A-B. Easy.

De Morgan’s Laws
You probably know of these. The operations for union and intersection are the same as addition and multiplication respectively. Note that A-B is the same as A intersected with the complement of B.

Union
A+B=B+A
!(A+B)=!A*!B

Intersection
A*B=B*A
!(A*B)=!A+!B

Subtraction
A-B=A*!B

Distribution
A*(B+C)=A*B+A*C

Positive Normalized Form
A tree is in this form when it is just unions and intersections. Subtractions are not allowed. You can get rid of subtractions by changing them to intersections and complementing the right-hand side. For all these examples, I’m assuming the tree is in Positive Normalized Form.

Active Zones
With the preliminaries out of the way, here is the real meat of this post. Suppose that we have two spheres, and we want to figure out the watertight shell of A+B. Like this:

At first you would think that we would want to take every point on A and B, evaluate them, and everything that passes that expression would be considered in. Unfortunately, if we did that, then we would get lot’s of junk in the middle, like this.

Here’s the top image from this post. It’s made of about 20 or so CSG primitives.

To render this transparent image properly, you have to remove all the middle stuff and only render the watertight surface surrounding the theoretical solid.

That’s where Active Zones come in. The active zone of a primitive P is the area of the universe where a point on the surface of P will be on the border of the CSG solid. In this case, the active zone of A is just !B. For A, any point that is inside B will not be on the border of the resulting solid because it is, well, inside B. Simple.

Any point on the edge of A that is also in !B will be on a watertight edge of A+B. Here is A “trimmed” by !B.

If we then also trim B by !A, then we get the final solid.

So how is this done for more generic surfaces? Let’s try a more complicated example. Here are the primitives:

And we’ll extract the edges for the expression ((A+B)*C)+(D*E). That solid looks like this:

The solution is to trim each primitive by it’s active zone. We’ll start with A. Here is the expression:

To find the active zone of A, we will first make A the left-most node in the tree. Since the tree is in positive normalized form, we can do this by going up the tree from A and swapping if A is on the right side. Once that step is finished, we need to look at all nodes on the path from A to the root.

For those nodes along that path, you need to change the + operators to – operators.

Intuitively, we are saying that for a point on A to be on the surface, it must be inside any of the subtrees that it intersects with and must not be inside any of the subtrees that it unions with. That’s because if that point is inside a subtree that it unions with, it is by definition inside the solid, and therefore not on the surface.

The next step is to bring the tree back into positive normalized form by changing the subtractions to unions and applying De Morgan’s laws on the way down.

That leaves us with this expression.

The last step is to remove A, since we don’t need check it against itself.

So that’s the process for finding the active zone. In summary, to find the active zone of a primitive P:

1. Make P the left-most node.
2. Go up the tree from P, turning all union nodes into subtractions.
3. Apply De Morgan’s laws to make the tree positive normalized again.
4. Remove P.

So what does this active zone look like. Here are the primitives with A removed.

And here is the active zone of A, (!B*C)*(!D+!E):

Here we can see what A looks like with the area outside of its active zone grayed out. Now, we want to render A, but only the parts of A that fall inside its active zone.

Here are the active zones for each primitive. Please check my work!

A: (!B*C)*(!D+!E)
B: (!A*C)*(!D+!E)
C: (A+B)*(!D+!E)
D: E*((!A*!B)+!C)
E: D*((!A*!B)+!C)

If you render each surface trimmed by it’s active zone, you get this watertight mesh:

Of course, there are a lot more details depending on what you are doing. Happy CSG!

Filed under: CSG by admin