Solve Less General Problems

Two decades ago when I first started working at Avid, one of the tasks I was assigned was porting our product (a consumer video editor - think iMovie before it was cool) from the PCI-card-based video capture we first shipped with to digital video vie 1394/Firewire.

Being the fresh-out-of-school programmer was, I looked at this and said "what we need is a hardware abstraction layer!" I dutifully designed and wrote a HAL and parameterized more or less everything so that the product could potentially use any video input source we could come up with a plugin for.

This seemed at the time like really good design, and it did get the job done - we finished DV support.

After we shipped DV support, the product was canceled, I was moved to a different group, and the HAL was never used again.

In case it is not obvious from this story:

• The decision to build a HAL was a totally stupid one. There was no indication in any of the product road maps that we had the legs to do a lot of video formats.
• The fully generalized HAL design had a much larger scope than parameterizing only the stuff that actually had to change for DV.
• We never were able to leverage any of the theoretical upsides of generalizing the problem.
• I'm pretty embarrassed by the entire thing - especially the part where I told my engineering manager about how great this was going to be.

I would add to this that had the product not been canned, I'd bet a good bottle of scotch that the next hardware option that would have come along probably would have broken the abstraction (based only on the data points of PCI and DV video) and we would have had to rewrite the HAL anyway.

There's been plenty of written by lots of software developers about not 'future-proofing' a design speculatively. The short version is that it's more valuable to have a smaller design that's easy to refactor than to have a larger design with abstractions that you don't use; the abstractions are a maintenance tax.

It's Okay To Be Less General

One way I view my growth as a programmer over the last two decades is by tracking my becoming okay with being less general. At the time I wrote the HAL, if someone more senior had told me "just go special-case DV", I almost certainly would have explained how this was terrible design, and probably have gone and pouted about it if required to do the fast thing. I certainly wouldn't have appreciated the value to the business of getting the feature done in a fraction of the time.

In my next model I started learning from the school of hard knocks. I started with a templated data model ("hey, I'm going to reuse this and it'll be glorious") and about part way through recognized that I was being killed by an abstraction tax that wasn't paying me back. (At the time templates tended to crash the compiler, so going fully templated was really expensive.)  I made the right decision, after trying all of the other ones first - very American.

Being Less General Makes the Problem Solvable

I wrote about this previously, but Fedor Pikus is pretty much saying the same thing - in the very hard problem of lock-free programming, a fully general design might be impossible. Better to do something more specific to your design and have it actually work.

Here's another way to put this: every solution has strengths and weaknesses. You're better off with a solution where the weaknesses are the part of the solution you don't need.

Don't Solve Every Problem

Turns out Mike Acton is kind of saying the same thing. The mantra of the Data-Oriented-Design nerds is "know your data". The idea here is to solve the specific problem that your specific data presents. Don't come up with a general solution that works for your data and other data that your program will literally never see. General solutions are more expensive to develop and probably have down-sides you don't need to pay for.

Better to Not Leak

I haven't had a stupid pithy quote on the blog in a while, so here's some parental wisdom: it's better not to leak.

Prefer specific solutions that don't leak to general but leaky abstractions.

It can be hard to make a really general non-leaky abstraction. Better to solve a more specific problem and plug the leaks in the areas that really matter.

Interval Sets With the STL

I spent some time today working on an interval set. The basic idea of an interval set is to record a set of disjoint ranges that partition a number space into a finite "included" area and an infinite "excluded" area. Or to put it more simply, [3, 6) is an interval, and [3, 6) [8, 10) is an interval set.

Googling around for this I found a few ideas based on using a sorted map, with the interval beginning as the key and the interval end as the value. My approach is different, and is closer to the original implementation of Macintosh regions: a vector of beginning and ending pairs, e.g. { 3, 6, 8, 10 }.

I'm not sure whether this approach is superior to a map-based approach; I think I'd have to code each one all the way to completion. The vector does have a few advantages:

• Compact storage, with minimal overhead.
• Reading the sorted array can usually be done in linear or log-N time.

The basic rules for the interval set are:

• Intervals are inclusive at the bottom and exclusive at the top. So the interval 3,6 includes the number 3 but excludes the number 6. (Thus given two intervals [3,6) and [6,9) the number 6 is included in exactly one of them.)
• Intervals must have non-zero length (so [3,3) is illegal).
• Intervals are finite - there is no notation to say "everything below 3" is included.

The heart of the algorithm is a "merge" operation. In a merge, the sequence of interval edges from two interval sets are traversed together (think of a merge sort) and each new smallest sub-interval is evaluated for inclusion by a boolean operation. This lets us perform a union, difference, intersection, or symmetric difference in linear time O(N+M) where N and M are the lengths of the vectors.

(The actual time is actually slightly worse because vector will need to periodically reallocate its memory during the creation of the new resulting vector. We could use a heuristic to pre-allocate some space at a loss of memory efficiency. If we used a set we could avoid memory costs, but we'd end up with O(NlogN) time to build the set anyway, and we'd pay node overhead, which is almost certainly worse than any extra on a vector of 32-bit floats or integers.)

When we search for an interval (using lower_bounds) we can tell whether we are "in" or "out" of the region by looking at whether the index of the returned region is even or odd - even regions are in the set and odd ones are outside of it.

The interval class is also heavily special cased for a number of optimizations:

• Separate operators on pair allow for the processing of a single interval (rather than a set). When we know the single interval, we can take a number of short-cuts, and we can perform "in-place editing" using log-N searches into the original interval set.
• Operations on sets can identify short cuts. For example, the intersection of two sets whose range is disjoint is always empty. (In other words, if the last value in A is less than the first value in B, intersecting A and B is an empty set.)

I haven't used the interval set class enough to profile it; real measurement will tell which of these optimizations is a win. One tricky aspect of the code is that vector is a leaky abstraction - it makes mid-vector insertion look cheap when really it is a linear operation (because all subsequent elements must be copied to their new locations).

As an example of why this might matter: consider symmetric difference (XOR) of an interval set and a single range. This operation can be computed simply by: deleting the range bounds from the set if they exist, otherwise inserting them. In other words, given the interval set [0,3) [6,9) [12,15) we can XOR this with the interval [6,8) by deleting 6 and inserting 8 - the new XOR is [0,3) [8,9) [12,15). This is a relatively fast operation: two log-N searches (for 6 and 8) and one delete and one insert.

Despite the simplicity of the algorithm, vector is going to require two mid-vector editing operations, so our average time complexity is O(N) - linear! (On average half the elements of the vector are after us, and we do two editing ops.)

For this reason, the special case of a disjoint XOR is special cased. If we XOR [-10, -8) into the above region, we can observe that -8 < 0, therefore the regions don't intersect, and -10, -8 simply needs to be pre-pended. This can be done with a single insert, and thus should run about twice as fast as a pair of individual inserts.

CGAL Performance - Work In Bulk

A performance tip when using CGAL 2D Boolean Operations: you'll get much better performance if you can perform multiple operations at once.

I wrote code that did something like this:

for each polygon
my_area.difference(polygon)

That snippet took 36 minutes to run. So I rewrote it like this:

vector all;
for each polygon
all.push_back(polygon)
Polygon_set_2 sub_area.join(all.begin(),all.end());
my_area.difference(sub_area);

New running time: 3 minutes. Why the huge speedup? Well, every time you do a boolean operation between two polygons, the underlying arrangements are merged using a "sweep" algorithm, which is an efficient way to merge two big piles of lines. The sweep operation's time is O(NlogN) which is very good for this kind of thing, but N is the sum of the edges in both polygon sets.

If the area we are subtracting from is very complex, this means that for each subtraction we do an operation based on the big polygon's area. Ouch!

The second snippet wins in two ways:

• We do only one operation against "my_area", so if my_area is complex we eat the cost of going through the area only once.
• A "join" on a range of polygons is very fast because CGAL will divide and conquer in groups, to minimize the total number of operations. That is, a join on a range is faster than a join on each individual item.

If you run a profiler like Shark on CGAL and see "sweep_line_2" taking all the time, use techniques like the one above to cut down the total number of merges. It can make a huge difference!

Trust No One

Here is my "new" approach to topological integration of the planar map for X-Plane scenery.  (I say new because it's new to the code, not because this is a new approach.)

Trust no one.

Basically:

• Topological data is never read from disk.  It is never imported.  We don't trust TIGER or VMAP0 to be correctly integrated.  In the case of VMAP0, I can tell you for a fact that it has errors.  (I've never caught TIGER, but the older code wasn't very sensitive.
• Instead, all data is imported and sanitized on input by CGAL.
• Once CGAL has the data, we are home free; the 3.3.1 Planar map with an exact numeric type is rock solid.

Of course, this means integrating the data every time we use it, which means my big bad new workstation isn't as big and bad as you'd think, relative to a much more expensive problem.

The advantages of this are:

• It's as good as CGAL is (and CGAL is very, very good). Bad data can't ruin the party.
• Because bad data can't ruin the party, it's safe for third party use - that is, the tools can handle third party data that hasn't been "degunked".

Animation and Bounding Sheres

X-Plane uses transform animation - that is, 3-d models are animated by applying rotations and translations to parts of their geometry.  This makes calculating the bounding sphere tricky.

In attempting to find the smallest static bounding sphere that accounted for all animation, I first tried transforming the bounding sphere by the animation.  Translations would move the sphere half-way to the extrema of the translation and increase the radius by half the translation distance. Rotations around the origin would move the sphere to the origin and increase the sphere size by its original distance from the origin.  (This is like convolving the sphere around a sphere.)

This didn't work very well - consider a rotating beacon on top of a tall pole.  This object has only one animation - a rotate around the Y axis.  If we convolve around a sphere, we end up rotating the rotating beacon around the arm of the pole (e.g. its very tall height) when in fact it only rotates around the Y axis, which it is not far from at all.

So take two was to take the axis into account, convolving the sphere correctly around the axis. This helped a lot, but for some models the sphere was still really huge.

Then a modeler pointed the problem out to me: some authors will rotate an object a tiny bit around a very long arm to create a not-quite-linear translation.  Convolving around 360 degrees for this tiny rotation means picking up a ton of area that would never be in the object.

So take three is to explicitly convolve the rotated geometry along the real rotated arc at a few degrees spacing, with the spacing decided by whether we need to be faster or more accurate. This seems to work pretty well.

The most accurate thing I can image would be to actually convolve all of the points to create a finalized point cloud and then take the bounding sphere.  We get false area by convolving a larger volume than we need to.  The problem with the point cloud approach is that the number of points increases exponentially as we nest animations - to truly get it right, assuming 36 convolve steps, each point is multiplied up to 36 times for each rotation.

Assuming we could afford that cost, to be even more correct, we would want to convolve taking into account aligned animation variables - that is, if two animations happen in lock-step, we should not multiply out all possibilities because they cannot animate separately.

But at some point, the bounding sphere is a heuristic, and in practice the three refinements above make a huge improvement and don't leave a lot of slop on the table.

Randomized Bounding Spheres

X-Plane uses bounding spheres to cull our meshes.  So having the smallest possible bounding spheres matters - the quality of the bounding sphere calculator affects all culling, which affects all drawing.

But calculating a minimum bounding sphere for a point cloud is not a fast operation - it's worse than linear time (which matters for huge meshes that are loaded while the simulator is running) and algorithms usually require robust mathematical operators.

Instead I use a bit of a heuristic - an incremental grow algorithm:

Initialize the sphere to size 0 and center of the first point.
For each point until there are none left.
If the point is inside the bounding sphere, ignore it.
Otherwise, grow the bounding sphere to just barely include this point.

This algorithm is pretty good but not optimal.  The reason that it's not optimal is that when we grow to encompass a new point P, the opposite point that is "growing" (and not moving) the sphere is the farthest point on the sphere from P.  This farthest point may not actually be an input point at all - it could just be an artifact of the fact that we are using the sphere instead of the original data to grow.

(A slower but more comprehensive algorithm would have us go back over the original point data to find the far-side point limits, giving us O(N^2) - plus we'd start to have floating point robustness issues.)

The quality of the bounding sphere has a lot to do with the order in which we grow it - the earliest points establish the size of a sphere, effectively inducing "phantom" points around the temporary (smaller) sphere.

So my first idea was to find the longest axis between any two points in my cloud and insert them first, in the hope that by establishing the long axis we could avoid growing the sphere in false directions.  This option probably means fewer grow operations (since more points will be inside the long axis) but the cost of finding the longest axis is O(N^2) so it's not really a speed win.

What surprised me is that using the longest axis vs. the native submit order coming out of the host program, the longest axis was better sometimes but worse in others.  The "natural" order of the points seemed to produce pretty good results a lot of the time too.

What I then tried was a randomized approach:

For each of N trials
Shuffle the data
Calculate the bounding sphere
If the sphere is smaller than our previous best
(or this is the first trial)
Save this as our best

Now the quality of these bounding spheres are random (and some are quite poor) but as we increase N, we are more and more likely to randomly find an order that is superior to any pre-determined heuristic.  The shuffle takes linear time, and the number of trials is constant (and quite possibly a lot smaller than the number of points).

For N = 256, this produces better results than either the natural or long-axis-based sphere perhaps 90% of the time.  And when it doesn't produce the best sphere, it is very close to optimal, usually within a few percent.

Minkowksi Sums and Buffering

As usual, a concept which I struggled with for years is implemented cleanly and elegantly in CGAL.  I've spent more hours than I can think of fighting with buffering algorithms - the one I finally came up with is very similar in approach to the GEOS buffering algorithm.

Buffering is the process of making a polygon bigger or smaller - a trivial operation unless something ugly happens, like the polygon bumping into its new bloated self.

GEOS solves the problem the same way CGAL does: using the winding rule.  Basically, as long as your offset polygon segments always turn in the same direction as the original, you can count the number of edges you cross - each time you go from the right side of the edge to the left, you increase the winding count (for counter-clockwise polygons) - and vice versa.  If the winding count is positive, you're inside.

Why this works, I don't know - I couldn't prove it to you.  But it does seem to work, and it seems to produce robust results even with fairly smashed up offset polygons, which is important to me, because often my offsets are larger than the polygons themselves.

If I had to prove it, I'd probably try to demonstrate that certain overlapping cases of similarly wound polygons form "union" operations, thus the results are always adding or always subtracting (depending on which kind of buffer you use).

So could I have used CGAL?  Actually no -- I needed something that's not easy to find in the GIS world: a buffer that varies its width per segment.  I buffer polygons to remove the road's width from the area I use to place buildings - sometimes the road width changes mid-polygon!

Compressed Vectors - Part 2

My last post introduced an STL vector that uses RLE to save space and an index for reasonably fast random access.

But that's not the whole story.  We're trying to compress the "snapshot structure".  Those familiar with the lowest level of X-Plane multiplayer networking know that X-Plane uses a packed structure to describe one "frame" of the sim - that is, plane location, control surface deflections, needles, etc.  It is very heavily packed (both with and without loss, depending on the parameter).

The flight replay is essentially a giant vector of these structures.  So...how to utilize our compressed vector (which only compresses identical data)?

The answer is the plane_old_data compressed vector.  Basically this vector relies on the fact that its items are plain old data (POD) and stores each struct across many vectors (each usually containing 4-byte int or 8-byte long longs for items).  Call each of these vectors that covers a sequence of cross sections of our struct "track".  (Those who have used ProTools will understand why I say this.)

Now we can use our compressed vector for each track.  The result is that consecutive values over time at the same offset in our struct get compressed.  If the struct is filled with parameters (some of which vary, some of which don't), we get to compress the ones that do.

Once we get this structure integrated, we'll see what kind of packing efficiency we get.

Transform Normals Directly

EDIT: Technique 2 (origin differencing) is, besides a terrible idea, not the fastest way to transform normals. See this post for a much better treatment of the subject!

There are two ways to transform a normal vector N given a matrix M:

1. Compute the inverse of M, transpose it, and use that new M' to transform the normal vector.
2. Transform M directly, and transpose the origin (0,0,0) then subtract the transformed origin form the transformed normal. This is like transforming the two end points of the normal.

Which is better? Well, I'd say it depends.

• If you are transforming a lot of normals, calculate the inverse and transpose it once. Now you can invert normals directly.
• If you are transforming only one normal, it might be cheaper to transform two points rather than invert a 4x4 matrix.

But...there is a danger to the "transform the points" technique: loss of precision!

If your matrix contains a large translation, then the result of transforming the normal and origin will be two points that are close together, but far the origin. This means that you have lost some precision, and subtracting won't get it back!

The inverse/transpose method does not have this problem; the transpose moves the translation part of the matrix off into the bottom row where we don't really care about it - the remaining matrix terms should have fairly small magnitudes and not lose precision.

Pinching Cascading Shadow Maps

The battle with cascading shadow maps (CSM) is always one for resolution.  We could use 25 layers of CSM, but that would defeat the whole purpose of CSM.  Ad-Hoc shadow maps deliver really good, precise shadows, but with two draw-backs:

• They are horribly dependent on the size of the objects in your world.  For small objects they produce crisp shadows - for big ones they produce muck.
• Odds are the number of objects floating around (cars, buildings, etc.) is several orders of magnitude larger than the number of CSM layers you might use.  I get good results with 8 CSM layers, and can probably reduce that with careful optimization.  I usually have more than 8 buildings on screen.  (That means a lot of thrash as we create, then use each shadow map, with GL setup each time.)

Yesterday I found (by misunderstanding the NVidia White Paper) a way to squeeze a little bit more detail out of my CSM layers.

For each "layer" (that is, a distance-wise partition of the user's frustum that gets a separate shadow map) we normally calculate the shadow map's bounding cube around the corners of the user's view sub-frustum (for that layer).

But that's really a much bigger bounding box than we need.  For the price of an iteration over the scene graph* we can calculate a smaller bounding box that is "pinched in" to the edge of the content we need to draw.

Is this a win?  Well, it depends...on...

• The size of your scenery content.  You won't get a pinch in that's much smaller than the smallest indivisible entities in your world.
• The overall shape of your scenery content - if it really fills the frustum, no win.

Evaluating this on scenery, I am seeing:

• Very little benefit for the nearest layers...they are usually so small (a few dozen meters) that they include much larger scenery entities.  (Our ground patches can be several kilometers, so no win.)  But for the far layers, we might reduce the bounding box by 25-50% in some dimensions...that's almost like doubling your texture!
• The shape of our content is a win.  Since the world is sort of flat and 2-dimensional, usually at least one axis of the bounding box (depending on the sun's angle) is horribly wasted.  That's where we get a win.

Example: the user's camera is on the ground, facing north.  The sun is directly overhead.  Now the user's frustum indicates that, in the farther layers, content that is significantly below or above the ground would be visible.  (We don't have occlusion culling here.)

But in practice, there is no scenery below the ground.  So we can "pinch in" the far clip plane of the sun's camera (which is really far from the sun, just in case anything below the surface of the earth is visible), bringing that far clip plane all the way up to the lowest ground point. Similarly, if we're not shadowing clouds (they are handled separately) the near clip plane can be pushed down to the tallest building.

This makes the far layers much, much more useful.  Normally if the layer is 10 km away at 60 degrees FOV, the bounding box for the shadow map is going to have 10000 meters from its near to far plane.  If we "pinch in", we can reduce this "depth of field" to the difference between the lowest and highest scenery items, which might only be 100 or 200 meters.

(This is of course a best-case scenario...put a mountain in there and angle the sun a bit and the win is much more modest.)

As a side effect, the scene graph traversal lets us completely eliminate layers that contain no content - I am finding I drop at least one layer that way.

EDIT: all of the above data is totally misleading - for shadowing 3-d content, the above is true. But if the terrain mesh is included (it is much larger, and its granularity is larger), the savings all vanish.

* Lazy evaluation can make this a lot faster - simply skip whole sub-trees of the scene graph that are already entirely inside the "pinched" cube)

Oblique Frustum Culling is Cool

Every now and then I come across a graphics algorithm so out there that it just blows my mind - it feels like cheating the laws of physics or something.  Oblique Frustum Culling is one of those algorithms.

Here's the situation: to make a pretty water reflection, you need to reflect the camera position around the water plane - take a picture, and then use that projected texture later to draw the water reflections.  There's one hitch: you have to clip out everything below the water.  If you don't, you get this.

The inset picture is the "from-the-water" view...note that the pillars of the bridge go way below the water (so one art asset can be used at many elevations).  But since they are not obscured by the water (when viewed from below the water), they show up in the reflection texture as the dark areas behind the bridges.  (This is because the reflection texture's projection doesn't know what "forward" and "backward" are along the projected light ray.)

You can't fix this using depth buffering or by drawing the water - the water would occlude everything you do want.  So you need a user-specified clip plane.  Clip everything below the water and go home happy, like this.

As I have blogged before, clip planes and shaders don't always work well together.  (And by don't always, I mean never.)  If I remember correctly, one vendor requires you write the clip vertex while the other requires you don't.  To make it more fun, the latest GLSL specs will deprecate the clip vertex entirely in terms of gl_ClipDistance (which makes more sense actually).  Mix that with drivers for OS X and for Win/Lin, and users who aren't on the latest GLSL compilers, and you have enough anarchy to want to kill yourself.

That's where oblique frustum culling comes in.  Basically it's an algorithm that takes the near clip plane of the view frustum and distorts/bends/twists/performs voodoo on it so that it is your user clip plane.  Quite literally everything below water is now "too close" to the camera.

What I really love about this algorithm is: no extra state - we don't have to have conditionals in our shaders for the (rare) time we need our user clip plane - we just bend the frustum and move on with life.  How cool is that?!!

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.

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<.