Just a quick update

Deferred Virtual Texture Shading

I've blogged about this idea before, using a virtual texture cache as a sort of g-buffer, and this has some advantages (I'm not going to re-iterate these again, just read my older posts if you want to know more).

Frankly it's simply a dynamic form of surface caching, so I decided I'll start calling this idea "dynamic surface caching" instead of "deferred virtual texture shading", which is a horrible name for it anyway.

Anyway, today I read a blog post about an idea where a light pre-pass renderer is implemented using spherical harmonics.
This made me realize that with my dynamic surface caching idea, the lighting of the surfaces could be stored as SH coefficients as well, de-coupling it from the view direction, which would make the cache idea more useful.

Realtime CSG

When I implemented the realtime CSG algorithm I've been blogging about, I was mainly concerned with getting it to work, getting it stable and making it perform fast, not so much with code readability (it was a prototype anyway).
Since I needed to explain it in a coherent way (or at least I try to) I needed to figure out all the peculiar details I put in code a year ago, and figure out how to communicate all this in an effective way.

This actually gave me some new insights and ideas.
My original implementation only had additive and subtractive brushes, no 'common' brushes, and the CSG operation was tied with the brush, making a complete CSG hierarchy impossible.

It worked really well for it's purpose (seriously, you probably wouldn't want to directly expose this kind of functionality in an editor anyway), but I have some ideas on how to generalize it, possibly make it more efficient, and definitely make it more readable and accessible.
So I need to do some tests and get some code working before I can continue with the blog posts about it.


Unfortunately this is a very busy time for me at the moment.
Clients with lot's of deadlines (meaning I need to do some work at home as well), a top secret project I'm working on with some friends of mine, preparing for Christmas, wife wanting me to do all kinds of home improvement stuff, and my daughter obviously wanting some attention between all this as well ..

But I should have more time to code around Christmas itself!

Realtime CSG - Part 3

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.

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!

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.

Realtime CSG - Part 1

Yesterday I got an email asking if I could explain my real-time CSG algorithm.
So I figured I might as well blog about it.

(CSG stands for Constructive Solid Geometry by the way)


I'm doing this from memory, so hopefully i'm not missing anything, please don't hesitate to tell me if something isn't clear to you.

About Numerical Stability

Before I begin, I need to stress that with these kinds of things you
really have to worry about floating point errors.
As you might know, floating point numbers have limited precision and
cannot possible hold a number with infinite precision.
If you divide 1 by 3, you won't get 0.3333333 with 3's into infinity,
instead you'll just get 0.333333343 (single precision).

Above all, consistency is more important than accuracy with geometry
on a computer. Otherwise you always end up with coordinates that are
almost the same, but never quite the same.
You'll need to use 'epsilon values', which is a small bias
(for example 0.01), when comparing coordinates or distances.
This is because you cannot assume that two calculations that are
equal from a mathematical sense, will produce the same result.

For example:
a/b does not (necessarily) give the same result as a * (1/b)
a*(b*c) does not (necessarily) give the same result as (a*b)*c
etc.

So, for example, when you determine the distance of a point to a plane you need to define for yourself that a point will be:

• on the negative side of a plane when it's distance is < -epsilon.
• on the positive side if it's distance is > epsilon.
• on the plane itself if it's distance is between >= -epsilon and <= epsilon.

Make sure that you don't mix up, for example, > with >=, or you'll get all kinds of weird hard to track down bugs!
Be consistent!


Half-edges

I use a half-edge data structure to represent my geometry, you can find a basic explanation of the half-edge data structure here.

For my CSG algorithm you'll need a couple of basic methods.

First of all you'll need a method to create a pair of half-edges (with a new vertex) in between two other half-edges, which essentially splits a full edge in two and inserts the new vertex in between.


Polygon cutting

Another thing you'll need is a method to cut a polygon with a plane.

It works like this:
You cut a polygon by looping trough all your vertices, and for every vertex determine if it's on the positive side (outside), the negative side (inside) or -on- the plane you're currently cutting with. (using epsilon values like I mentioned before)

• If all vertices are on the plane, then you've got a duplicate plane and you'll need to remove that plane (quite frankly, you should've detected that before you start cutting)
• If all your vertices are on the 'outside' or are on the plane then you need to treat the entire polygon as being cut.
• If all your vertices are on the 'inside' or are on the plane then your entire polygon wasn't cut by the plane.
• In all other situations you'll need to cut your polygon into two pieces.

You do this by finding the two vertices where the polygon was intersected by the plane.
If the vertices you find just happen to lie on the cutting plane you won't need to calculate any intersection, but often you'll need to calculate the intersection point of an edge with the cutting plane, and then use the half-edge insert method I mentioned earlier.


The big advantage of half-edges here is that when you split the half-edge, you automatically do it for both polygons on both sides of the edge.
And since you won't be calculating an intersection when a point is already on the plane, you won't be splitting it twice and everything will be nice and consistent!

When you have an edge to split, you may have an edge that goes from the inside to the outside, or an edge that goes from the outside to the inside.
Now what is -really- important is that you always calculate the intersection point in the same direction.
What this means is that if you do:

myNewVertex = myCuttingPlane.Intersect(myInsideVertex, myOutsideVertex);

Then you don't mix it with:

myNewVertex = myCuttingPlane.Intersect(myOutsideVertex, myInsideVertex);

When you calculate your intersection point, stick with one direction!
Otherwise you'll end up with some vertices that are biased towards one side of the plane, and other vertices that are biased at the other side of the plane.
So make sure you're, once again, consistent here.


In the part 2 I'll explain how to build geometry from
brushes (convex polytopes), which are the building blocks of my CSG algorithm.

Update:
Created a repository for the code.