Wednesday, September 02, 2009

OpenGL Matrix Tricks: Camera Properties

In my last post I pointed out that:
  • Planes have vectors "embedded" in them (the normal vector).
  • We can quite cheaply backward-transform a plane, because planes are transformed by a transposed inverted matrix - if we want to go "backward" the two matrix inversions cancel each other out.
Knowing this, we can play some fun camera tricks using OpenGL's model-view and projection matrices.

Finding The Clip Planes

To cull a sphere, we can transform the sphere's center into eye space, then test it's distance to each of the 6 viewing clip planes (in eye space). If we are outside the clip planes by more than the sphere radius, it is out of camera view.

(We don't want to do this in clip space because clip-space's scale is non-uniform - comparing a distance to the radius of the sphere would be very wrong.)

But where do we get our culling planes? Well, the clip planes in clip space are very simple, because clip space is just a 2-unit cube centered on the origin. The clip planes are therefore:
  • Left clip: (1,0,0,1) - that is 1x + 0y + 0z + 1 = 0, also known as X + 1 = 0.
  • Right clip: (-1,0,0,1)
  • Bottom clip: (0,1,0,1)
etc. etc.

So all we need to do is multiply these planes by the transposed projection matrix and we have our clip planes not in clip space but in eye space. In practice, we can "multiply out" the transpose and the multiply and get a code snippet that looks like this.

Basically the cost of finding our clip planes in eye space from the projection matrix is just a bunch of adds and subtracts. Cheap! I should also note that this works for any projection matrix - ortho, frustum, oblique frustum, or Dr. Demento's totally insane deformed matrix.

Finding Billboard Vectors

A billboard is a quad whose points are entirely within the XY plane in eye space. That is, it always faces the camera. To calculate a billboard, we need to find vectors in model-view space that map to "right" and "up" in eye space.

It turns out that this is a lot like the clip-plane problem above. Consider the YZ plane, facing "right" (that is, a plane whose plane coefficients are 1,0,0,0). We can transform that from eye to model-view space, then recover our normal vector and that's which way "right" is.

Once again we're taking a few static plane equations, running them through a transposed matrix, and out comes our answers. Here's a code snippet.

Another Way To Look At Billboarding

It turns out there's an even easier way to understand how the billboarding example works than transforming plane equations by a transposed matrix.

An affine transformation matrix consists of rows of basis vectors - that is, each row of the matrix is the destination X axis (then Y, then Z) in the source coordinate system.

So if we want to know which way "right" is in eye space (but we want our numbers in model-view space) we just take the top row of the 3x3 upper-left part of the model-view matrix.

Where Is My Camera Location?

Sadly you can't get the camera location in model-view space out of the model-view matrix. Our previous trick of reverse-transforming a vector or plane fails because the origin is a point - it needs to be "forward" transformed, which from eye space to model view space means having a real inverted model-view matrix. (Once you have that, the right-most column is the origin.)

The problem is that the origin, as embedded in the model-view matrix (in the right-most column) is the origin after rotations. This is generally not what we want.

(I suppose that, theoretically, we could invert the 3x3 upper left of the model view matrix, then apply this to the right-most column to find our origin, and I suppose this would be faster than calculating a full inverse matrix. I haven't tried this though - in X-Plane we simply invert the model view matrix as needed.)

OpenGL Matrix Tricks: Transforms

One of the cool things about OpenGL is that, after doing a ton of advanced math to work out your matrices, usually the end results boil down to an astoundingly small amount of C++.

Transforming Vectors and Normals

A vector can be defined via a point whose distance from the origin is zero. Really we need 3 coordinates. If we have a fourth coordinate, what do we store there?

My short answer is: why do you have a fourth coordinate? Don't waste space, most GPUs are faster when operating on less coordinates in shaders as well as bus bandwidth. But if you had to pick something, zero is probably a good choice, as we'll see below.

Now you may have read that you can't just transform your vectors the way you transform your points. The diagrams here explain why.

I have to point out that to a math professor, that "stretched" vector is exactly the expected result from applying a non-uniform scaling matrix to a vector.

The true problem is that we want the normal vector to stay normal - in other words, we really want to transform the plane that the normal vector is normal to, and then recover the normal vector. This is pretty different from actually transforming the vector itself, but you gotta know what you want.

See below for plane transformations, but plane transformations are expensive, because they require calculating the inverse of our transform matrix.

If we know that we don't have any scaling on our matrices (uniform scaling would change the magnitude of the vector, which can be undone I suppose) then we can transform the normal vector directly with our transform matrix. The trick is to only use the 3x3 upper-left corner (or simply set the fourth coordinate to zero). This will remove the translation part of our matrix and leave only the rotations. If we transform the vertex, it's meaning relative to the origin would be lost. See here for more details.

Important: you might think that you can transform your vectors by transforming the vector and the origin, and then subtracting. This is a very bad idea! The problem is that if the origin of your coordinate system is not close to zero, you'll lose a lot of precision on your normal vectors by moving away from the origin. I have had this implementation in X-Plane and the loss of precision quickly turns into visible artifacts.

Transforming Planes

A plane is represented by four values (typically ABCD, as in Ax + By + Cz + Dw = 0), and notation-wise, you would think of a plane as a column. (Since a point is a row, we are saying that point dot plane = 0.) ABC is the normal vector to the plane, and D is a scalar that defines which of the infinite number of parallel planes we have.

To transform a plane, you need to transform it by the transpose of the inverse of our matrix. See here for a derivation.

It should be noted that when you want to reverse-transform a vector (e.g. go from eye coordinates to world coordinates) this works in our favor.

When transforming a plane backward: tranpose(inverse(inverse(MV)) is just transpose(MV) - in other words, the inverse of our "forward transform" (E.g. the model view matrix) cancels out the inverse needed to transform a plane equation. So we can simply turn our vector into a plane with that vector as its normal, quickly transform it, and then pull out our vector.

More Reading

A good explanation of homogeneous coordinates.

Next time: Camera Tricks

Wednesday, August 26, 2009

Updating Textures On The Fly With Threads

In my previous post I described how to load textures "in the background" using threads. It's a riff on loading GL objects on a thread - in this case, we use an atomic object to swap the ID of a stub resource for the real resource.

What if we want to update a texture while rendering? Ideally we'd like to have the texture updating running 100% asynchronously from the render loop, with no blocking or locks. The short of it is that this is possible by using a second texture (which is swapped in using atomic operations); why you can't just call glTexImage2D from a thread has a more complex answer.

The answer lies in Appendix D of the OpenGL specification, which describes the rules for state update when an object is changed. The basic rules are:
  • You always see state change immediately in your own context.
  • You don't see a change in another context until you bind the object at least once after the state change is known to have completed.
That second point is a really monstrous condition. Here are a few ways this can kill you:
  • The pointer to storage of an object is state. If a command changes that storage (e.g. respecify a texture in another format), the state rules apply!
  • You don't see the state until after you bind, but if you're dealing with a stale pointer, the state may not be useful before you bind. I'm not sure how actual GL implementations manage this - I've seen white flashes for textures on OS X when incorrectly dealing with state propagation.
  • The spec requires completion in the server, e.g. after a "finish" (or a sync object in the new 3.2 spec, but that's another blog post). That's a pretty harsh condition, and I believe that most gl drivers will accept a flush. Newer, more modern drivers may require a real sync and not a flush - glFlush only works because there is serialization in communication to the card.
When you put this all together, it becomes clear that you need to have your rendering thread stop using the object before the async load starts, then restart using it with a rebind after it ends.

That's an ugly enough condition that with X-Plane we simply double-buffer: we allocate a whole new texture object, then use atomic operations to swap it in by ID, then deallocate the old one (on the worker thread). If you think about how texture memory works, there are only two other options:
  • Client code holds off rendering while the async happens (the texture itself could be in an inconsistent state).
  • The driver double-buffers for you, so that the old bind of the old texture isn't invalid. It's unclear to me from the spec whether this is required of the driver and what the cost would be. It strikes me as inefficient at best.
By double-buffering with two texture objects we also get around the problem of having to rebind - since the new texture has a new ID, we have to bind anyway.

Atomic Safety

My previous post suggests using atomic operations to switch texture IDs in and out after you've done a threaded load. Atomic operations have the nice property of not blocking, and they're often very low overhead. But...what makes an atomic operation safe?

Well, it turns out you need to be safe from four things, two in your compiler and two in hardware.

(As a side note, the Apple perf-optimization list is a great resource...I didn't know about sequence points until this post.)

Code Reordering

An optimizing compiler will try to reorder code in ways that it thinks might be faster but won't change the meaning of execution. Since the compiler doesn't know or care what other threads are doing, this could be really bad.

C/C++ have the notion of sequence points - basically the optimizer isn't allowed to move code around a sequence point. There are a few types of sequence points but the most useful one is the function call. Call a function, and you've divided your code in half.

Volatility

In C/C++ volatile memory is memory that the compiler has to write to when you tell it to. Normally the compiler might analyze the side effects of a chunk of code and change exactly how it talks to memory to improve performance. Between sequence points, the compiler can do what it wants as long as the end result is the same.

But when a variable is volatile, the compiler must write to it once each time your code says to. The original classic use would be for I/O registers, where the write operation does something, dn you need to do it exactly once or twice, or however many times the code says.

Generally you'll want the variables you use as atomics to be volatile, so that a lock gets written when you want it to be.

Atomicity

The next thing you need to be sure of is that your atomic operation really happens all at once. How this happens depends on the CPU, but fortunately you don't care - as an applications writer you use an operating system function like InterlockedExchangeAdd or __sync_add_and_fetch. All the major operating systems have these functions.

For example, incrementing a variable would traditionally be three instructions: a load, an add, and a store. This isn't very atomic; something could happen between the load and store. Using some CPU-specific technology, the OS atomic operation guarantees that the operation happens all at once. If you have a system with multiple cores and multiple caches, the atomic operation makes sure that future code isn't fooled by old cached values.

Barriers

The final part of the puzzle are memory barriers. Basically some CPUs have some freedom to reorder the reading and writing to memory. Normally this is done in a way that still produces consistent results. But if you are going to write data, and then write "unlock", you don't want those things to be reversed - writing unlock could allow another thread to look at the data...it has to be there.

A memory barrier is a synchronization point in the stream of reads and writes...basically all the writing on one side of the barrier is done before the reading on another.

Four In One

Fortunately operating systems typically give you all four properties in one place:
  • The atomic operations are functions, so they are sequence points.
  • They take inputs of type volatile T *.
  • They are atomic in implementation.
  • They have a barrier built in (or there is a variant that includes a barrier - use that one).
So are you safe? If you use an atomic op function with a barrier then yes.

Atomics and Threaded OpenGL

My previous post describes how to load a VBO or texture on a thread, then "send it" to the main thread for use. This is almost exactly how X-Plane loads its VBOs on worker threads.

For textures we use a slightly differntn strategy. The problem is that we (theoretically) need our textures immediately - that is, if we hit a part of the scene graph that references an unloaded texture, we still need to draw something.

Rather than have the state setup go into some fallback "untextured" mode, we use a proxy-and-switch scheme.
  1. When we first hit the need for a texture, we create one of our C++ objects that manages the texture. This texture object is inited to refer to a dummy gray texture that we use as our proxy for all unloaded textures.
  2. We queue the texture object to be loaded approximately whenever we get around to it. This might come up soon or it might take a while, depending on how much background work is being done.
  3. When a worker thread finally gets around to loading the texture, it loads the real image into a new texture "name" (GLuint texture ID).
  4. When the load is done and flushed, we do an atomic swap , swapping out the old gray proxy texture and swapping in the new texture.
The advantage of this is that the rendering code can be running at full speed, using this texture object (with its OpenGL texture ID inside it) without any thread safety or checking what-so-ever; it's a solution that has zero cost for the rendering engine.

And since the C++ texture object always has something in it, we can use the same shaders even before we've loaded, which simplifies the casing for shader setup quite a bit.

Creating OpenGL Textures or VBOs On A Second Thread

It's always scary when I Google for a question and find my own blog post in the top few search terms...it makes me think I've programmed my way out into the wilderness. Given how many forum questions involve people trying to figure out how to put OpenGL resource loading in a worker thread (and how many times they are told to just use one thread because it's a PITA) I figured I would blog what I have discovered through painful trial and error.

The previous post discusses setup of "loader threads" - that is, a worker thread with a shared GL context that is meant to be used to load textures and VBOs without interrupting the main thread from doing rendering work. The loader thread has a current GL context but usually no framebuffer, which is fine since we don't really want to draw.

What do we need to do to create a texture or VBO on this worker thread? The steps go something like this:
  1. Issue the GL commands to create the texture or VBO. Typically you'd have someting like glBindTexture, glTexImage2D, glTexParamBlaBlaBla.

    Remember: GL state is separate for each thread - if you have OpenGL utility code that "caches" state in global variables, you'll need to make it thread safe or something. I use one set of utilities on the main thread (with caching) to render, and a separate set on worker threads; a debug-build-only check catches incorrect use of utilities on the wrong thread.

  2. Call glFlush...more details here. But basically if you don't force Open to swallow what it's chewed, your texture-create commands might just be sitting around for a while.

    (Side note: as of August 2009, the bugs you get on Windows from not flushing a VBO built in a worker thread are truly spectacular visually...the crazy runways in the sky and other creepy effects are all due to a missing glFlush on a worker.)


  3. Finally, send a signal to the rendering thread to allow it to use the entity.

I use message queues for step 3 because I love message queues in a way that might not be healthy. To go with the "resource ownership" idea, once your worker has loaded and flushed the texture or VBO, you are "passing ownership" to the renderer via the message queue. The main thread can do something like this:
while(1) {
scene_graph.draw();
obj * new_goo = msg_queue.read(do_not_block);
if(new_goo)
scene_graph.insert(new_goo);
}

The cost to the main thread of this design is about as low as it can get - basically you only pay for bucketing your new geometry.

Monday, August 24, 2009

Putting OSM On A Diet

I've been fighting to cut an entire set of X-Plane scenery off of OSM...the stickler: Boston. Why Boston happened to be the tile that had this problem I don't know, but basically I ran out of memory. The scenery creation process unfortunately isn't very space efficient and at one point it needs two copies of the roads: a "planar map" for area calculations and a separate "network" version for actual export. I just didn't have enough RAM for two road grids, plus other raw data and a 3-d triangle mesh.

Douglas Peuker to the rescue - a 7m error limit on roads cuts data down by 25% in San Diego and 75% in Boston.

Once I have the whole process working I might raise this limit back up again...the main culprit is small sections of road with very high node counts. In a few cases I found 7m spacing along a road! The data is definitely inconsistent.