CSM vs. Ad Hoc Shadows - Quality

Comparing the quality of ad-hoc shadows vs. CSM...there are some cases where ad-hoc does a lot better.  In particular, given a character or vehicle near the camera, ad-hoc usually looks better, because a lot of shadow map res is dedicated to a relatively small area.

Where CSM excels is in very large models or very large terrains where there is no good scene-graph based decomposition.  For example, ad-hoc shadows on terrain by decomposing sub-parts of the mesh works rather poorly - decompositions really need to be based around view frustums (which is exactly what CSM does), not based on world coordinates.

One thing I haven't been able to quantify yet is the cost in triangle count to CSM.  If you look carefully at the CSM scheme, you'll see that at certain camera vs. sun angles, there can be significant overlap between the shadow volumes, and that means multiple iterations over the scene graph content that is in the "shared" location.  If the model in that location is expensive, this can be a potential performance problem.  

(For example, if you work on, oh I don't know, a flight simulator, there is a chance that the user's airplane is significantly more expensive than anything else in the universe...if it spans several CSM volumes, you're going to feel the pain.)

Finally, from what I can tell, while it is more efficient (fill-rate wise) to apply all CSM volumes at once, it is not strictly necessary from a quality standpoint - I'm not seeing a ton of artifacting from applying CSM volumes separately via stenciling.  

(The artifacts would be from the overlap of low and higher res shadow maps..what I have found is that if the CSM scheme uses enough splits to really look good, the overlap regions are small and don't differ that much in quality between the lower and higher res shadow map that overlap.)

nVidia's CSM demo uses four shadow maps -- my tests required six at first, but upon examination, it looks like the closest and farthest map are too close and too far to be useful, and could be dropped.

Ad-Hoc Stenciled Shadow Maps

Previously I blogged a design for combining G-Buffering with shadow mapping using the stencil buffer. I doubt that this is an original idea; the GPU Gems 2 chapter on G-Buffering (a la CRYSIS) mentions that G-Buffering and shadow mapping work well together.

I would describe the G-Buffering + stencil + shadow mapping approach as "ad-hoc" shadow mapping because the approach lets you compute any number of arbitrary shadow volumes and apply them to screen-space areas.  Because we are using the stencil buffer, it doesn't matter if the shadow volumes overlap.  We can simply pick out the most important parts of the scene (closest to camera, biggest, important to user, flagged by artist) and shadow those.  We can shadow fewer models or all models, determined by runtime settings.

Wait, what do I mean by "shadow volume"?  Well, a shadow map is a 2-d texture, but the value of a pixel in that 2-d texture is the "nearest occluder" from the sun.  Since the minimum and maximum gray-scale value correspond to distances from the sun, we can think of the shadow map effectively specifying occluder information within a cube that is aligned such that the sun sees exactly one square face of the cube.

Cascading Shadow Maps (CSM) uses a similar approach to fix some of the weaknesses of shadow mapping, namely:

1. That shadow volume is very much resolution limited - both by texture dimension (X and Y axes) and texture precision (Z axis).  For very large scenes, you run out of res long before you get a nice looking shadow.
2. Often the alignment of the sun and user's viewpoint are such that your pixels are being spent where the user can't see them, which is wasteful.

CSM solves both of these problems by using multiple shadow volumes in multiple maps, using a smaller volume for the near part of the view frustum (which is naturally smaller since the view frustum gets larger as it goes away from your eyeball).

Typical CSM designs will simply use 2, 3, or 4 shadow maps simultaneously, looking up the shadow per pixel in each one.  But this design can be adapted to ad-hoc shadow mapping -- with ad-hoc shadow mapping, we simply build each shadow map (near, far, very far away) in series, and apply each one to the stencil buffer.

Since there is no penalty for overlapping shadow volumes, we can even combine ad-hoc and CSM approaches - we can run several shadow volumes along the view frustum (a CSM-like approach), excluding "high value" content - and then separately shadow that "high value" content, each with its own shadow map.  The result is generally good shadow precision, and arbitrarily precise shadows for models that require extra res.

CGLA: Abusing merge_edge

The CGAL arrangement_2 operation "merge_edge" takes two connected half-edges (connected by a vertex of degree 2) and makes them one. Useful! But there is some fine print:

merge_edge is only meant to be used when the new combined curve covers the exact same path as the old curve. If you are using line segments as your curves, this means the three vertices involved (the middle vertex is the one to be deleted) are collinear.

Can merge_edge be abused to remove edges that bend? Yes, sort of, if you are very careful:

1. You must verify that the new combined edge does not cross any other edges, and will be in the same face as the existing two edges. This limits how much you can move an edge by combining. Basically merge_edge can't change topology!
2. The two half-edges being merged must go in the same direction! Otherwise, the half-edge direction flag could be wrong after the merge.

None of this is very safe - safer (but slower) is to simply add the new edge and delete the two old ones.

STL Priority Queue

The STL on my Mac seems to have a "priority queue", but it's not quite what I want - it's just a wrapper around a heap.  What I want in a priority queue is:

1. log-time insertion of elements.
   
2. Constant time popping of the front.  (Actually, I can live with log-time here.)
   
3. The ability to reprioritize a single item in log time, based on the item itself.
   
4. Priorities stored with the elements (rather than calculated by a comparator).
   
5. Ability to put items into the queue without adding special "helper" fields.

Those last two points aren't critical, but they are very convenient.

Item 3 is what makes things interesting...for a lot of priority queue algorithms, the algorithm is only fast if you can reprioritize just a few affected other items without going over the entire queue.  (Doing an entire-queue operation will typically give you N-squared time, because you hit the entire queue to reprioritize every time you process a single item.)

There are two ways I've used to do this:

1. If I store the priority in the item itself (violates the last two points), I can just insert the items into an STL multi-map by priority.  To reprioritize an item, I find it by doing an equal_range query on its current priority, erase it, then reinsert it at the new priority.
2. To meet all the point, I use a map from priority to item, but then maintain a separate "back-link" map from items to iterators into the original map.  This gives me the ability to find an item by value and remove it from the priority queue and reinsert it.

The system can be made more efficient by using a hash map instead of a regular map for the back links, but it requires a hashing operator to be defined for the values, rather than just operator<.

User Clip Planes and GLSL

To combine a GLSL shader and user clip planes, you need to do two things:

1. Set up your clip plane normally using glClipPlane and glEnable(GL_CLIP_PLANEx).
2. Make sure to write the eye-space transformed vertex position to gl_ClipVertex in your vertex shader.

You do not have to do the clipping yourself - you just need to output an eye space vertex from your vertex shader so that the GPU can do it for you.  (Remember, normally your shader outputs only clip-space coordinates, potentially skipping eye-space entirely.)

And this should make sense - the shape of a clipped triangle may not be a triangle - it could be a quadrilateral which must then be decomposed into two triangles for the setup-engine.  So clipping needs to be done by dedicated hardware - your shader just has to give it access to eye-space coordinates.

(Clip planes are similar to eye-space tex-gen and lights in that you specify your input in object space, but the clip plane is then transformed to eye space at input time.  This means that the clip plane is stored "camera relative" and will not move as you move the model view matrix. This is a good thing - clip planes are typically global in nature, so we don't want them to move each time we move the original to draw a car or some other moving mesh.)

EDIT: of course, you'll get software render if you touch gl_ClipVertex on most hardware.  Your options:

• Use fixed function pipeline.
• Use pre-writing the Z buffer if you can.
• Case this out by card.

CGAL Arrangements - How Do You Find Your Edges?

A fundamental client problem with the CGAL arrangement_2 class: how do you recover handles to the edges you insert?  Note that the insertion APIs do not return halfedge handles unless you use very specialized (read: limited) functions.

I have found basically two strategies:

If you can afford to iterate across every single half-edge in the arrangement, use Arr_consolidated_curve_data_traits_2 to tag your input curves with an index number back to the original source data.  

After the insert (and you can use any kind of bulk insert you want), simply iterate across all edges (remember, a single curve is shared between two halfedges), pull out your key, and you now have a link from half-edge to original curve.  This is a many-to-many relationship - the consolidated cure traits will make sure that multiple keys make it to a half-edge if needed.

If you are doing a small amount of incremental work, attach an observer.  You will need to override the following observer messages:

• after_create_edge to detect new half-edges induced for your insertion.
• after_modify_edge to detect cases where your edge completely overlaps an existing half-edge.
• after_split_edge to detect the case where your edge partly overlaps an existing edge.  (The existing edge will be split so that there is a vertex at the end of your inserted curve.)
• If the curves you are inserting intersect with each other, after_split_edge also needs to detect the case where an edge you previously inserted and care about is split in two.

I use the former strategy for the bulk creation of a map from source data - I'm going to have to apply traits to every edge, so I might as well let the bulk insertion run without a ton of individual callbacks, then go through later.

I use the latter strategy to detect induced rings when I am adding small areas and not using the sweep-line algorithm.

Future work: I have not had time to analyze whether incremental observation is better/worse for performance than bulk insertion with consolidated data keys.

To Sweep or Not To Sweep

I've spent the week porting the X-Plane scenery generation code back to CGAL.  I will describe the history of this code and its constant battle with robustness in another post, but for now I will just mention that credit goes (besides obviously to the authors of CGAL, who are geniuses of the Nth degree) to Andrew McGregor for a lot of the ideas on how to use CGAL with the scenery generation code - the final design is really just a refinement of his work.

The X-Plane scenery generation code (which we just call "the render farm") is the code that turns hundreds of GB of GIS data into scenery.  At its heart is a topologically integrated planar map of all vector features in a given tile - every road, river, coastline, change of terrain type, etc. is baked into one map.  A typical map might have half a million edges, covering a 1 x 1 degree area.

For X-Plane 8.20 and 9.0 we shipped using a planar map I wrote myself.  While the planar map didn't work very well, it had a few special cases that were highly optimized.  In particular, given two sub-regions of two maps, with an identical ring of half-edges identifying them (identical meaning identical coordinates) you could swap the interiors of the two regions in time proportional to only the number of elements inside the ring.

It turns out that this is a really useful trick for a few things:

• If you have a huge map you want to tile, you simply induce the cut lines, and swap each single tile with an empty map.
• If you want to "overlay" a polygon, or even a sub-map (destroying what is below) you simply induce a border ring in both polygons and swap.
• You can crop a map's interior or exterior by inducing a ring and swapping with a blank map.

This was an operation where the devil is in the details - because components are swapped "in-place" the swap doesn't have to copy, allocate, or deallocate the map, so it turns out to be fast in pracatice.  In terms of time complexity, it's very fast for very small operations on a huge map, which turns out to be an important case for us.

Now CGAL's arrangement_2 gives me some power tools* that are very useful - in particular, sweep-line algorithms.  The link shows a good explanation.  Basically the power of the link is to process a set of line segments in a lot less than O(N^2).

But there's a slight problem with sweep-line - it has to iterate over the entire set of edges in a map, including the ones already in the map.  That means that inserting a small number of edges into a complex map is surprisingly slow.

So in some cases I now have two implementations of various map operations:

• Sweep-based implementations, which are good when we're inserting a lot of data at once.
• Incremental implementations - theoretically much worse, but acceptable to keep the size of our data set down.

So far, incremental operations are proving to be a big win when "burning airports" - that is, merging or overlaying very small airport boundary areas into a full map.

* Of course, the real advantage of CGAL is that it is robust and doesn't randomly blow up during operations!