Realtime CSG - Part 2

This is part 2, you can find part 1 here.

Last time I told a bit about numerical stability, and the importance of consistency when dealing with geometry.
I also mentioned that in my CSG algorithm I represent my geometry in half-edges and described an algorithm that cuts a polygon using another plane.

Now I'm going to explain how to build the geometry of a brush, which is the most basic primitive in my CSG algorithm.


Brushes

A brush is a Convex Polytope, which is essentially a list of planes.
You create geometry from a brush by calculating all the intersections (which will be our vertices) of these planes, and creating our half-edges and polygons from these.

But before we begin, a word of advise.
You have to make sure that your data is clean otherwise you'll run into all kinds of wonderfully weird bugs.
What you really need to check for, and you should write some code to do this, that you don't have any duplicate planes, or planes that are -almost- the same.


So how do we build geometry and half-edges from this set of planes?
There are two methods that I know of.


The "standard" way

The first one is the most commonly used in game engines:

• You create a big polygon by projecting an axis-aligned rectangle onto each plane, which is aligned by the most major axis of the normal of the plane.
• You then cut this polygon up, using the polygon split method i described in my previous post, using all the other planes in your brush.
• You then merge all the half-edges and turn it into a proper mesh.

Now the problem I have with this method is that first of all, it works the best when your brush is at the center in worldspace, the moment your brush is placed beyond the size of your axis-aligned rectangle it'll fall apart.
You can of course make that rectangle really large, but the problem with that is that when you mix numbers that are both very large and very small that your floating point errors will end up getting worse.
Another problem is that at the end you need to start to merge your vertices, which means comparing coordinates which is dangerous because floating point calculations are not exact, and you might end up either merging vertices that shouldn't be merged, or end up not merging vertices that should.


The "precise" way

The above method might very well be good enough for some applications, but I prefer a different, more complicated method.
It's a complicated SOB, so if I'm too fuzzy about some details, please let me know.
Keep in mind that you need to understand half-edges before you can comprehend this algorithm!

In the first step we calculate all the intersections of all the planes, and we make sure those intersections also lie on the inside or on all the other planes, because some planes also intersect somewhere outside the brush.

So at this moment you might be thinking "How can we possibly create polygons out of that??", "And how can that possibly be more accurate than the above method?" or "Maybe I should get some coffee..."
Now, I can't help you with the coffee, but bear with me, all will be revealed.
(Good thing I didn't accidentally write down "bare with me, all will be revealed"!)

Let's go over what information we have at every intersection:

• We have the location of the intersection
• We know which planes intersect at each vertex
• We know that each plane will create 1 polygon
• We know that where two planes intersect, we'll have an edge
• We know that each edge will have two vertices

(Well actually a plane may actually only intersect at 0, 1 or 2 vertices, in which case you should just drop the plane.)

So now if you visualize this, you'll have multiple edges (defined by a pair of planes) ending at your vertex.
So, at this moment in time we only know one side of the edge.
Hmm... that sounds familiar.. that almost sounds like.. a half-edge!

Now look at this picture:

The green arrows are the half-edges we can build for every vertex.
The Red arrows are the half-edges that we know would be build for other vertices, but we don't know them yet.
However, we know that the edge formed by a pair of red/green arrows would share the same pair of planes (A/B , B/C and A/C in this case), so we can use that information to link both sides together!

The next issue is then, how to put the half-edges in order?
If you look at the picture, what do we know about our edges:

• We now know both half-edges on each full-edge
• We know that we'll have two full-edges on each plane (let's call them E & F)
• We know that E will go to F -OR- F will go to E.
• We know both full-edges on a plane share one vertex, but only one of these full-edges will be on that plane/polygon, so either E or F will not have this vertex.
• We know that the order of half-edges or vertices in a polygons are consistent (clockwise or anti-clockwise)

So if we check the orientation of E going to F and F going to E, one of them will have the 'correct' orientation (which depends on how you define the order of your polygons).
After that it's a just matter of setting a pointer from one to the other.

Theoretically you could probably get away with only checking the orientation of 2 edges, and then using that information to iteratively build the edges around the edges with known orientation, it would probably be pretty complex and I haven't tried this.
It would, however, be more accurate.

Keep in mind that if you can't find 2 full-edges on the same plane, then you're dealing with a plane that only intersects at an edge and needs to be dropped.

Once you've done that, the mesh will be done.

In part 3 I'll start explaining the CSG algorithm itself.