Fixing Shadow Maps

In the old days of stencil shadow volumes, the code to draw the scene might look something like this:

1. For each light source
2. Clear the stencil buffer
3. For each shadow caster
4. Draw its shadow volume
5. Draw the scene

The big problem here is the "shadow volumes" - that's geometry that may be as complex as the scene, but isn't the scene, and changes as the sun moves. We can get clever and try to write a geometry shader, but in the old day you had to build your shadow volumes. Ouch.

Another problem with stenciled shadow volumes is that "fake" geometry shaped by transparency is ignored.

Shadow Maps

Shadow maps bake distance calculations into a texture, from the light source's point of view. But we have two ways to code this, both pretty painful:

1. For each light source
2. Draw the scene (depth only) from the light's 3.perspective
3. For the scene
4. Draw the scene with a shader that knows about the shadow maps

Of course while that looks nice and fast, that shader features one shadow calculation per light source.

An alternative is to build the scene in passes:

1. For each light source
2. Draw the scene (depth only) from the light's perspective
3. Draw the scene with a shader to accumulate that light's contribution

The first option uses a huge shader and a lot of VRAM; the second one hits the scene graph a lot. The second case might be a win if we can use our scene graph culling code to draw only the part of the scene that could be affected by the light (assuming the culling works that well).

It should be noted that for one directional light (e.g. the sun) the shadow map case is great: we need one texture, one extra pass, and we automatically get shadows on everything. Transparent geometry is not shadowed, and we don't have to ask "how do I make a stencil volume" for everything that might show up in the scene graph. Render time for the shadow pass can be very fast because we can skip texturing and color write-out.

The Problem With Shadow Maps

The problem with shadow maps is shadow resolution. You lose resolution in 3 dimensions: the width/height of the shadow map (which shows up as big blocky pixels in the shadow) and "depth" - if the precision of depth values isn't good enough, "close calls" between the occluder and occludee are not resolved correctly due to rounding errors.

Depth precision is less of a factor now that modern hardware supports formats like R32F (a single 32-bit floating point channel) but horizontal resolution is limited by texture size; even a 2048x2048 texture doesn't provide much detail over more than about 500 meters of "world". For a flight simulator, that's not enough.

To make matters worse, the shadow texture's position is based on the light source, not the viewer's camera. This means that often the most detailed part of the shadow map is somewhere useless (like far away), while the ugly crude part is right in front of the user. There are a number of algorithms, like trapezoidal shadow maps (TSM) that try to reshape the shadow map to use the pixels better, but if your scene graph is huge, this isn't an improvement of the right magnitude.

Splitting the Lights

One way to solve the resolution problem is to break the light source into multiple "lights", each shadowing a different part of the scene. (Think of a directional light as really bounded by a cube, because this is the area the shadow map casts a shadow for. We are making many small cubes that cover the volume of the original light cube, which had to be big enough to cover the whole scene.)

This approach gives us a potentially arbitrary improvement in resolution, but it puts us on the "multiple light" scenario - two passes over (at least part) of the scene graph per light. If you have efficient culling there might be a win, but shadows are cast, so a small light volume can end up shadowing a large area at some light source angles.

Stenciled Shadow Maps With GBuffers

I'm not sure if anyone has done this before - for all I know it is a known production technique and I just haven't found the paper. The technique I describe here uses a G-Buffer to save on iterations over the scene graph, and the stencil buffer to save on shadow map memory. If you already have a G-Buffer for deferred shading, this works well.

What Is a G-Buffer

A G-Buffer is a series of frame buffers which encode everything you could want to know about a given pixel. Typically for a given pixel X, at a minimum you would know the XYZ position in eye space, the normal vector, and the unlit ("raw") color of the source point on the source geometry that filled pixel X.

In other words, a G-Buffer is sort of a spatial index, giving you constant time access to your scene graph, given screen-coordinate X & Y as an input. With deferred shading, you can now create light effects - for a given screen-space pixel, you know what a given light would have done to that pixel, because you still have its normal, position, original color, etc.

G-Buffering is a win for lighting because we can radically reduce the number of pixels for which per-pixel lighting is applied.

• Because we will apply lights later in screen space (by reading the G-Buffer to get the normals, positions, etc. of the pixls involved) there is never any overdraw. If your scene was created by drawing the screen 4x over, the G-Buffer contains the final result, only the pixels that showed up. So if you have 4x overdraw, G-Buffering represents a 4x reduction in lighting calculations.
• If a light has limited scope (e.g. it is directional or attenuated), you only have to apply the lighting calculation to the small set of pixels that it could affect. With traditional lights, every pixel in the scene must consider every light (or you must turn the lights off and on very carefully). With G-Buffering, the "second-pass" of accumulating lighting can be done for small screen areas by drawing a trivial bounding volume for the light. This means that small lights are much, much cheaper in terms of pixel fill rate.

Be warned that G-Buffering also has three weaknesses that you have to eat just to get started:

• To draw the scene itself, you have to fill a huge amount of data - perhaps 12 to 16 floating point values per pixel. That's a much higher fill rate to the framebuffer than you'd have with conventional texturing (or even HDR). So you'll pay a price just to have a G-Buffer. You only win if you save enough lighting calculations later to justify the G-Buffer now.
• FSAA is not an option; the G-Buffer needs exact values from precisely one scene graph element for each pixel. So you may need to render at a higher res (ouch) or apply post-processing to smooth out geometry. (Post processing is recommended in GPU Gems 2.)
• Alpha-blending works, um, badly. Basically you only get the final values of the front-most pixel. So you will have to compromise and accept a hack...for example, the front-most pixel's lighting calculations applies to the blend of the texture colors of all contributing pixels. If this hack ruins your content, your only alternative is to fully render the scene before blending, then do a second pass - at that point the G-Buffer is probably not a win.

G-Buffering and Shadow Maps

G-Buffering works well with shadow maps; you can "project" a shadow map onto a scene using only the contents of the G-Buffer, not the original scene itself. (To project the shadow you really only need object position, which is in the G-Buffer.)

But what about shadow map resolution? We can use the stencil buffer to accumulate the shape of the shadow cast by each shadowing element in the scene graph, and then bake the light. The full rendering loop would look like this:

1. Draw the entire scene to the G-Buffer
2. For each light source
3. Clear the stencil buffer
4. For each shadow-casting object (for this source)
5. Draw shadow map for this object
6. Project shadow map into stencil buffer using G-Buffer
7. Accumulate contribution of light, using stencil buffer

Note that for the sun-light case, our time complexity is relatively similar to the original shadow-map algorithm: step 5 at the worst case involves drawing a shadow map for the entire scene. (I'm waiving my hands - we'll be filling a lot more pixels, because we've got a full-sized shadow map for individual elements. It's the equivalent of being allowed to have a truly enormous shadow map.)

But what's interesting about this is that the cost of the steps aren't necessarily as high as you'd think in terms of fill rate.

• Step 5 (drawing the shadow map for one object) can use as many or as few pixels as we want -- we can choose our shadow map size based on the position of the object in eye space! That is, we can finally spend our shadow fill rate budget on things that are close to us. Since each object gets its own shadow map, our max resolution can be relatively high.
• Step 6 requires us to draw some kind of "shadow casting volume" onto the screen - that is, to cover the pixels that could be shadowed by a given occluder. This has the potential to be a lot less than the entire screen, if we can draw relatively sane volumes. (But the only penalty for a cruder, larger volume is a few more shader ops.)
• Step 7 requires us to burn in the light, which (as with all G-Buffering) only requires touching the pixels that the light could illuminate; so we get a win for lights with limited range or tight focuses.

This algorithm has some nice scalability properties too:

• Because we know where in the final scene's eye space we are working, we can tune quality on a per-shadow basis to spend our computation budget where we need it. (E.g. turn off PCF for far-away shadows, use smaller maps, don't shadow at all.)
• We can even make content-level decisions about shadows (e.g. shadow only buildings).
• The algorithm trades quality for time. Traditional shadow maps are limited by maximum texture size, which is a painful way to scale. This lets us simply trade a faster CPU/GPU combo for better results, with no maximum limit.
  

Future Parallelization

If we ever get GPUs that can dispatch multiple command streams, the inner loop (4,5,6) could be parallelized. Essentially you'd have a few shadow map textures, and you'd pipeline steps 5 on multiple cores, feeding them to step 6. So a few GPUs would be prepping shadow maps, while one would be baking them into the stencil map. This would let us scale up the number of shadow-casting elements.

Perspective Correct Texturing in OpenGL

99.9% of the time, you don't have to worry about perspective correct texturing in OpenGL. If you draw a textured rectangle, it will look correct from any angle. But there are a few cases where you need to manage perspective yourself.

I blogged here on what perspective vs. non-perspective texturing looks like when a rectangle is deformed into another shape. This blog doesn't mention a minor detail: OpenGL will never give you that middle image - instead what you get is something like this. (What you see is the two triangles that OpenGL decomposes the quad into.)

Creating Perspective with the Q Coordinate

If you can easily identify the amount of "squishing" you have applied to one end of a quad, you can use the "Q" coordinate to produce perspective correct textures. We do this in X-Plane: the snow effect is a cylinder that wraps around the plane. In order to assure that the entire screen is covered, we close up one end to make a cone in some cases. When we do this, the quads that make the sides of the cylinders become trapezoids, then triangles. By using the Q coordinate technique, we keep our texture perspective correct.

There are two caveats of this technique:

1. You can't really make the texture go to infinite distance (that would be a Q coordinate of zero). If you do, all texture coordinates are zero and some of your texture information is lost. To hack around this, we clamp to a very small minimum Q. Don't tell anyone!
2. This technique will produce perspective changes in both directions of the texture! This is the "correct" perspective thing to do, but may be surprising. In particular, as we make the far end of our cylinder into a cone, because visually this is the equivalent of making it stretch out to much further away, the texture is stretched along the cylinder, making snow flakes that are close to us very tall and ones that are far away very short.

Why does this technique work? Well, basically texture coordinates are 4-component vectors, with the S & T coordinates you are used to divided by the Q coordinate (the 4th component). By having a smaller Q component, the division makes the S & T effectively larger, which means more texture in a small area, which looks "farther away".

But the real magic is in how interpolation happens. When you specify a per-vertex variable that is "varying", it is interpolated across the polygon. In our case, the Q coordinate is interpolated, creating a pattern of shrinking Q's that stretches the texture dynamically. The Y=1/X shape of this curve creates "perspective".

Creating Perspective Via Matrices

This snippet of code is the nuclear weapon of perspective. You simply give it a trapezoid (four corners) in 2-d and it calculates a matrix that applies the texture in a manner that looks like the appropriate perspective. In other words, it's effectively calculating the vanishing points.

We use this in X-Plane for the skewed instruments - when the user drags the instrument corners, we simply calculate a matrix that creates the correct perspective.

The snippet of code contains comments with the derivation - one interesting property: given 8 variables in a 2-d perspective matrix and 8 variables (four 2-d corners) there can exist only one perspective matrix for any given trapezoid.

One warning if you decide to use this with OpenGL: make sure your computed transform matrix doesn't produce negative W coordinates! (To do this, simply apply the resulting matrix to one of your input corners and check the resulting W. If it is negative, negate the entire matrix.)

I use LAPACK to solve the matrix in my version of this code, and LAPACK doesn't make a lot of guarantees for the "constant" term (a constant factor applied to all matrix values). If that constant is negative, you will get output coordinates where X, Y, Z and W are all negative - the perspective division would cancel this negation, but at least on the machines I've used, the negative "W" causes anarchy long before we get that far.

The reason you can use a projection matrix anywhere in OpenGL is because projection fundamentally relies on storing information in the "W" coordinate (the 4th coordinate) to be divided later - the "W" just gets carried along for the ride and then later produces the correct perspective effect.

Sound and the 24" iMac

I finally found info on how to make it happen here.

Here's the short version:

• I used Ubuntu 7.10, which has Alsa 1.14, which is a little different.
• Make sure

  options snd-hda-intel model=bbp3

  is somewhere in your modprobe.d files, like in alsa-base.
• Turn on a lot of goo in the mixer.
• Surprisingly the built-in Mic is the digital input!

I now know that XSquawkBox Linux sound does work (but only if X-pane itself is run with --no_sound to allow OSS to open).

I Love CGAL

Because CGAL does many magic geometry operations for me that (having tried to code myself) are a PITA to implement.

But every now and then you end up with a link error like this:

"CCBToPolygon(CGAL::I_Filtered_const_iterator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face >, std::allocator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face > > >, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::_Is_valid_halfedge, CGAL::CGALi::In_place_list_iterator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face >, std::allocator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face > > >, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::Halfedge, int, std::bidirectional_iterator_tag>, Polygon2&, std::vector >*, double (*)(CGAL::I_Filtered_iterator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face >, std::allocator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face > > >, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::_Is_valid_halfedge, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::Halfedge, int, std::bidirectional_iterator_tag>), Bbox2*)", referenced from:
FaceToComplexPolygon(CGAL::I_Filtered_const_iterator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face >, std::allocator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face > > >, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::_Is_valid_face, CGAL::CGALi::In_place_list_iterator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face >, std::allocator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face > > >, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::Face, int, std::bidirectional_iterator_tag>, std::vector >&, std::vector >, std::allocator > > >*, double (*)(CGAL::I_Filtered_iterator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face >, std::allocator > > > >, GIS_vertex_data>, CGAL::Arr_extended_halfedge > > > >, GIS_halfedge_data>, CGAL::Arr_extended_face > > >, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::_Is_valid_halfedge, CGAL::Arrangement_2 > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, CGAL::Arr_extended_dcel > >, std::vector > > >, std::allocator > > > > >, CGAL::Arr_segment_traits_2 > > > >, GIS_vertex_data, GIS_halfedge_data, GIS_face_data, CGAL::Arr_vertex_base > > > >, CGAL::Arr_halfedge_base > > > >, CGAL::Gps_face_base> >::Halfedge, int, std::bidirectional_iterator_tag>), Bbox2*)in MapAlgs.o

How To Drive CVS Totally Insane

Okay, I do have to admit: posting on why CVS sucks or how to make it slow is the lamest thing ever.  I mean, duh!  Everyone knows that CVS is 1970's technology, 3 parts dope to 1 part disco, and there are better alternatives.

But...I think the performance situation I found is interesting because of when it happens.  (In particular, this performance problem has been with us for months and I only noticed now.)

The airport database is a 40 MB, 800,000 line text file.  We checked it into CVS

Hey, stop laughing...it seemed like a good idea at the time!

What's interesting is that CVS can (or at least could) check revisions onto the main branch fast enough that we didn't realize we were getting into trouble, and check out the head branch at linear speeds, limited only by net connection.

Poking into the repository, it turns out that this is because the head-branch revision is stored in its entirety with diff instructions to move back a step each way toward the first revision. 

This goes a ways toward explaining why CVS doesn't become incrementally slower at getting code as you use it: in truth it does, but the cost is born on the older versions of the repository, not the newer ones!

Where we got into trouble was when I checked data into a branch.  The branch cannot be the head revision, so it is stored as a delta off the version it came from.  With a huge file, the cost of applying even one diff on the fly is quite large.

In our case, getting the head revision takes less than a minute; getting either the previous revision of this file or the branched latest version take over 45 minutes!

I am not yet sure what we can do about this - the fact that historical check-outs will be slow is annoying, but clearly we don't use that feature very often.  (Fortunately this is a rarely-changing file.)

Pitfalls of Performance-Tuning OpenGL

Performance-profiling OpenGL is more difficult than performing a non-OpenGL application because:

1. OpenGL uses a pipelined architecture; the slowest component will slow performance while other parts of the system go idle and
2. You don't always have good insight into what's going on inside the OpenGL pipeline.

(Toward this second point there are tools like NVidia's PerfHUD and GLExpert that can tell you this, but your regular adaptive sampling profiler won't help you much.)

Pitfall 1: Not Being Opportunistic

The key to opportunistic performance tuning is to look at your whole application - creating a specialized "test case" to isolate performance problems can be misleading. For example, in X-Plane our break-down of main-thread CPU use might be roughly this:

• Flight model/physics: 10%.
• 2-d Panel: 5%.
• 3-d World Rendering: 85%.

This is telling us: the panel doesn't matter much - it's a drop in the bucket. Let's say I make the panel code twice as fast (a huge win). I get a 2.5% performance boost. Not worth much. But if I make the world rendering twice as fast I get a 73% performance boost.

The naive mistake is to stub out the physics and world rendering to "drill down" into panel. What the profiler is saying is: don't even bother with the panel, there are bigger fish to fry.

Pitfall 2: Non-Realistic Usage and the Pipeline

The first pitfall is not OpenGL specific - any app can have that problem. But drill-down gets a lot weirder when we have a pipeline.

The key point here is: the OpenGL pipeline is as slow as the slowest stage - all other stages will go idle and wait. (Your bucket brigade is as slow as the slowest member.)

Therefore when you stub out a section of code to "focus" on another and OpenGL is in the equation, you do more than distort your optimization potential; you distort the actual problem at hand.

For example, imagine that the sum of the pane and scenery code use up all of the GPU's command buffers (one phase of the pipeline) but pixel fill rate is not used up. When you comment out the scenery code, we use less command buffers, the panel runs faster, and all of a sudden the panel bottlenecks on fill rate.

We look at our profiler and go "huh - we're fill rate bound" and try to optimize fill rate in the panel through tricks like stenciling.

When we turn the scenery engine back on, our fill rate use is even lower, but since we are now bottlenecked on command-buffers, our fill rate optimization gets us nothing. We were mislead because we optimized the wrong bottleneck. We saw the wrong bottleneck because the bottleneck changed when we removed a part of real use code.

One non-obvious case of this is framerate itself; high frame-rate can cause the GPU to bottle-neck on memory bandwidth and fill rate, as it spends time simply "flipping" the screen over and over again. It's as if there's an implicit full-screen quad drawn per frame; that's a lot of fill for very little vertex processing - as the ratio of work per frame to number of frames changes, that "hidden quad" starts to matter.

So as a general rule, load up your program and profile graphics in real-world scenario, not at 300 fps with too little work (or 3 fps with too much work).

Pitfall 3: Revealing New Bottlenecks

There's another way you can get in trouble profiling OpenGL: once you make the application faster, OpenGL load shifts again and new bottlenecks are revealed.

As an example, imagine that we are bottlenecked on the CPU (typical) but pixel fill rate is at 90% capacity, and other GPU resources are relatively idle. We go to improve CPU peformance (becaues it's the bottleneck) but as a result, we optimize too far and as a result we bottleneck completely on fill rate; we get to see only a fraction of our CPU work.

Now this isn't the worst thing; there will always be "one worst problem" and you can then optimize fill rate. But it's good to know how much benefit you'll get for an optimization; some optimizations are time consuming or have a real cost in code complexity, so knowing in advance that you won't get a big win is useful.

Therefore there is a case of stubbing that I do recommend: stubbing old code to emulate the performance profile of new code. This can be difficult -- for example, if you're optimizing CPU that emits geometry, you can't just stub the code or geometry goes down. But when you can find this case, you can get a real measurement of what kind of performance win is possible.

Musings on Weird UI Designs

I've written too many UI frameworks (where by "too many" I mean more than zero). You could shout at me that I should use a library, but the calculus that has led me to do this over and over is pretty inescapable:

• An existing old huge code base uses an existing, old UI framework.
• The whole UI framework is perhaps 100 kloc and will probably be about the same when renovations are done.
• The application itself is 500 kloc, or maybe 3 mloc...applications get big.
• The interface between the UI framework and application is "wide" because all of the app UI behavior code has to talk to the UI framework.

So given the choice of recoding 100 kloc of UI or touching a huge chunk of a 500 kloc app, what do you do? You go rework the UI framework so that you can preserve the existing UI.

That decision has been true in X-Plane twice now (and was true in previous, more conventional companies too). But with X-Plane I hit a particular, strange situation: no objects!

In a traditional user interface some kind of persistent data structure represents the on-screen constructs; typically this data structure might be an object hierarchy, so that message passing between objects can be used to resolve how user input is handled; polymorphic object behavior specializes the actions of each "widget" in the user interface.

X-Plane's normal user interface code, which derives from a more game-like approach, is quite a different beast.

• Every user interface widget is implemented by a "function", called every frame, that both draws the widget and processes any user input events (that are essentially stored globally, e.g. "is the mouse down now", "what is the currently pressed key").
• A dialog box is simply a series of function calls.
• The function calls take as arguments layout information and what to do with the data, e.g. what floating point variable is "edited" by this UI element.

This creates very terse code, but a difficult problem when it comes to adding "state". There are no objects to add member variables to!

Working with such a weird construct has certainly made me "think different" about UI...it turns out that every feature I've wanted to add to X-Plane has been pretty straight forward, once I purged myself of the notion of objects.

State Without State

For X-Plane 9 I did some work on keyboard handling, providing real text editing in text widgets, keyboard focus, etc. The solution to implementing these features without state is:

• A UI "widget function" (that is, the code drawing a particular instance of a widget) can calculate a unique ID for the widget on the fly based on the input data. Thus the function can tell "which" widget we are at any one time.
• It turns out that usually the only state needed is state for a widget with focus, and which widget is focus. That is...all the variables turn out to be class-wide. (Remember, the data storage for the values of the widgets are already being passed into the functions.)
• Some global infrastructure is needed to maintain the notion of focus, but that's true of any system, whether it's global or on the root window. (Since X-Plane has only one root window, the two are basically the same.)

I went into the project thinking that I was going to have to visit every single call sight of every single UI function...after working at this technique for about a day I realized that the scope of the problem was much bigger than I thought, went back, and did the above "dynamic identity" scheme.

This is sort of like the "fly-weighting" technique suggested in the Gang Of Four book, but the motivation is different. GoF suggest fly weighting for performance (e.g. 2 million objects are too slow). To me this is ludicrous...while I do think you need to optimize performance based on real profiling data, data organization for performance is fundamental for design. If you need to fly-weight your design to fix a performance problem, you screwed your design up pretty bad.

This is different - it's fly-weighting out of desperation - that is, to avoid rewriting a huge chunk of code.

Should that code later be refactored? I'm not sure. (The above design does make it possible though - you just make a new API on top of the old API that looks more like a conventional OOP system; once you've entirely migrated to the new API you can reimplement your widgets in a more conventional manner.) The conventional wisdom would be: yes, refactor, but in our case, I just don't see the win. I'm a strong advocate of continuous refactoring to improve future productivity. X-Plane's strange UI design scheme has not been a problem; Austin is exceedingly fast at writing new UI code and I wouldn't want to get in the way of that!

Wedge This In

WorldEditor and the scenery code come with a UI framework that's as close to my current thinking on how UI should be done as I'm ever going to get...some of the quirks include: all coordinates are window-relative (I believe that widget-relative coordinates don't save client code and make debugging harder) and course refreshes (on today's hardware it's not worth spending a lot of brain power trying to figure out what needs to be redrawn, especially when your artist is going to give you translucent elements that require the background to be redrawn anyway).

I am reworking the PlaneMaker panel editor right now; the code had reached a point of complexity where it needed to be refactored for future work, so I built a cheap & dirty version of the WED UI hierarchy to live inside X-Plane.

I tried something even stranger than the WED UI framework: the widget code in PlaneMaker doesn't persist the location of objects in any way! All of the hierarchy calls pass the location into the widget when it is called.

The initial coding of this was a little bit weird, but it actually has a strange silver lining: no resize-refresh problems!

When I wrote WED, I had to deal with a whole category of bugs where something has changed in the data model, and the right set of messages wasn't set up to tickle the UI to resize itself and redo the layout. With the PlaneMaker code this is never an issue because the data model is examined any time we do anything - our location decisions are always current.

The down-side of this is of course performance; a lot of code is getting called a lot more often than needed. I figure if this turns out to be a problem, I'll add caching on an as-needed basis and add notifications to match. One of the reasons this may be a non-issue is that PlaneMaker's panel editor edits a very small set of data; a single panel can have at most 400 instruments. WED can open 20,000 airports at once (um, don't try this at home), so the caching code had to be very carefully written to not have slow paths in hot loops.