Multipart MIME and Apple Mail

I finally figured out why attachments from our bug report script don't have icons in Apple mail: Apple mail requires multipart/mixed as the MIME type, while Thunderbird will accept multipart/related.

Apple mail also cares about Content-disposition; it will show an icon for "attachment"-style disposition, even for text files, but it will show the text (with no markings showing it is an attachment) for "inline" style. Thunderbird shows the full text, with horizontal rules, no matter what.

How To Change Your UV Map on the Fly

I've been playing with "stupid UV map tricks" lately - the basic idea is to (in the fragment shader) change the texture coordinates before fetch. For example, given a texture divided into equally useful grid squares, we can on a per-grid square basis change which square we're in, to make the texture repetition less obvious. Why do this?

• You can make your textures look less repetitive without making meshes more complex.
• Since the effect is in-shader, it can be turned off on lower end machines - scalability!

But there's this one bit of fine print, and it escaped me for about four months: if you want to "swizzle" the UV map in a discontinuous way (e.g. using "fract", "mod", etc.) you need to use the explicit gradient texture fetch functions! If you don't, you get artifacts at the discontinuities.

Huh?!?!

In order to understand why this is necessary, you first have to understand how the hardware selects a mipmap level, and to understand that you have to understand how OpenGL generates derivatives.

First the derivatives. Most of the video cards I know about generate derivatives of a shader variable by "cross-differencing" - that is, a 2x2 block of pixels is run using the same shader, and when the shader hardware gets to the derivative (dFdx, and dYdx) it simply subtracts the interim values from the four pixels to find how much they "change" in the box. In other words, the derivative function in GLSL works by discreet per-pixel sampling.

(BTW this is why when you screw up code that needs to treat derivatives carefully, often you'll get 2x2 pixel artifacts.)

These derivatives allow the graphics card to select a LOD. At the sight of a texture fetch, the card can do a derivative operation on the input texture coordinates and see how fast they change per pixel. The faster they change, the lower the effective texture res and the lower LOD mip-map we need. That is how the card "knows" to use the lower mip-maps even when you use expressions for your texture coordinates - the derivative is taken on the entire expression.

But...what happens when you have a discontinuity in your UV map? Take a simple case like "fract". If you "fract" a wrapping texture, you will quite possibly see an artifact at the edges. This is because, right at the edge, the rate of change of the UV map is much higher than before, as it "jumps" from one edge of the texture to the other. High rate of change = low LOD - the graphics card goes and selects the lowest level LOD it has!

(If you don't know what's in your lowest mip, you might not know where the color was coming from.)

The solution is here: texture2DGradARB. This function lets you separately specify the texture coordinates and the derivatives. Here's a simple example. Imagine you have this:

vec2 uv_swizzled = fract(uv);
vec4 rgba = texture2D(my_tex, uv_swizzled);

That example will create a few pixels of low-mipmap texture at the discontinuity (where the texture goes from 1 back to 0). To use texture2DGradARB, you do this:

vec2 uv_swizzled = fract(uv);
vec4 rgba = texture2DGradARB(my_tex,uv_swizzled,dFdx(uv),dFdy(uv));

By using the original (continuous) texture coordinates for the derivative, but the modified ones for the fetch, you can have discontinuous fetches with no LOD artifacts.

NVidia and ATI cards don't respond the same way to discontinuous coordinates, but both will produce artifacts, and both are right to do so.

One last note. From the shader texture LOD extension:

   Mipmap texture fetches and anisotropic texture fetches
  require an implicit derivatives to calculate rho, lambda
  and/or the line of anisotropy.  These implicit derivatives
  will be undefined for texture fetches occuring inside
  non-uniform control flow or for vertex shader texture
  fetches, resulting in undefined texels.

I can tell you from experience that a number of my artifacts have come from conditional code flow. I believe that by non-uniform control flow they mean the case where the shader branches are not all taken the same way for a 2x2 block, but I am not sure.

Running Out of Derivative Res

In a previous post I went over the math behind generating the coordinate system for normal mapping in a pixel shader, which allows you to use tangent space bump mapping without encoding coordinate axes on your vertex mesh. (In X-Plane we do this so that we can allow authors to add bump maps to "unmodified" meshes.)

One of the problems with writing shaders is that it can be write-once, debug everywhere. As it turns out, this technique has a problem that I can repro on a GF8800 but not HD4870. On the 8800, I run out of precision in my derivative (dFdx and dFdy) functions.

In the scene in question, the UV map is generated in the vertex shader via projection off the world-space input vertices and the input mesh is big - 300 x 300 km in fact. (It is of course the base terrain.)

This means that the UV coordinates are pretty big too, particularly for highly scaled up textures. And that means that the effective resolution limit of the texture coordinates may be larger than one pixel.

When this happens, the result is a derivative that will be inconsistent across pixels, and the basis for the bump map will be corrupted on a per-pixel level.

Work-arounds? I can think of two:

1. Modify the texture coordinate generation system to produce higher precision UV maps.
2. Modify the shader to generate basis vectors from the projection parameters (rather than by "sampling" via the UV map) in the texture coordinate generation case.
   

glXGetProcAddressARB Syntax

I was slightly astounded to read that glxGetProcAddressARB is declared like this:

void (*glXGetProcAddressARB(const GLubyte *procName))();

Wha? Well, fortunately when you read the spec you'll note that they're just being clever...that's very strange C for

typedef void (*GLfunction)();
extern GLfunction glXGetProcAddressARB(const GLubyte *procName);

In other words, unlike all other operating systems, which define the returned type of a proc query as a void *, GLX typedefs it as a pointer to a function taking no arguments and returning nothing.

Why this is useful is beyond me, but if you are like us and call one of wgl, AGL, or GLX, you may have to cast the return of glXGetProcAddressARB to (void *) to make it play nice with the other operating systems.

How To Scroll the OpenGL World

So...despite my best efforts to post ridiculous and stupid ideas to this blog, there appear to still be people reading and commenting on it. Chris and I don't really understand this at all, but what the heck: this post is aimed at soliciting feedback. I'm wondering if I've missed a very basic case in a very basic problem.

The problem is the scrolling world. If you have a 3-d "world" in your game implemented in OpenGL, you're up against the limited (32-bit at best) coordinate precision of the GL. As your user migrates around the world and gets farther away from the origin, you start to lose bits of precision. At some point, you have to reset the coordinate system.

I see three fundamental ways to address this problem:

1. Stop the world and transform it. This is what X-Plane does now, and it's not very good. We bring multi-core processing into play, but what we're really bottlenecked by is the PCIe bus - many our meshes are on the GPU, and have to come back to the CPU for transformation.

   (Transform feedback? A cool idea, but in my experience GL implementations often respond quite badly to having to "page out" meshes that are modified on card.)

2. Double-buffer. Make a second copy of the world and transform it, then swap. This lets us change coordinate systems quickly (just the time of a swap) but requires enough RAM to have two copies of every scene-graph mesh in memory at the same time. We rejected this approach because we often don't have that kind of memory around.

3. Use local coordinate systems and transform to them. Under this approach, each small piece of the world is in its own local coordinate system, and only the relationship between these "local" coordinate systems and "the" global coordinate system is changed.

This third approach strikes me as the most promising one, but it also strikes me as difficult from a mesh-cracking standpoint. I don't see any way to guarantee that two triangles emitted under different matrix transforms will have the same final device coordinates, and if they don't, there can be mesh artifacts.

So that's my question: is there a way to connect two meshes under different coordinate transforms without cracking? Is there a limited set of matrix transforms that will, either in theory or practice produce acceptable results? Do game engines just hack around this by using clever authoring (e.g. overlap the tiles slightly and cheat on the Z buffer)?

The STL Is Not An Abstraction

I came to a realization the other day, having been burned by the STL for approximately the 100,000th time. Okay here goes that quotable crap again:

The STL is not an abstraction; it is a shortcut.

In computer programming, an abstraction is something that hides the details. Abstractions let us get stuff done, and most of the time they leak. Is the STL the leakiest abstraction in the universe?

No. It's not an abstraction at all. Abstractions hide implementation from you - the STL simply provides implementation.

An indication that the STL is an abstraction would be that you could change the implementation of an STL algorithm or container and not notice. Does the STL meet that criteria? I don't think so, at least not in any sane way.

With the STL, you need to know all of the fine print for any algorithm or class you do. Picking the type means picking an algorithm or data structure for its strengths and weaknesses. For example, if you pick vector, you are picking the following:

• A simple, compact representation.
• Blazingly fast random access iteration.
• The copy constructor of your data is going to be called a gajillion times.
• Mutating the size of the vector is going to hose outstanding iterators.
• Non-far-end insertion and deletion cost a fortune.

That's how vectors roll. A container abstraction might hide these things; picking vector prescribes what will happen, pretty exactly.

And that's okay; typing vector is still faster and less error prone than typing int * and remembering not to screw up the dynamic memory allocation. But let's recognize what the STL is: a way to make certain known containers and algorithms much faster to put into your code - not a way to write code without knowing what your algorithms and containers do!

Moore's Law and Openness

If you look back at Windows and how the west was won, you'll see a story of network effects and compatibility: an unbroken chain of being able to run old apps unmodified from DOS to Windows, and an architecture (x86) that we're still stuck with today. If there are two lessons to take away, it might be:

• Software takes forever to die - it's really hard to throw it out and start over again.
• Network effects are very strong - once all the apps are on Windows, everyone wants to run Windows. Once everyone runs Windows, we want to write apps for Windows.

I realize that this blog article might look really, really stupid in a year or two (and in that case, all hail Google, our new overlords). But...the strong networking effects in the embedded games space all point towards the iphone. App developers know that if you want to be on one platform to make money, you have to look at the iphone first, even if you hate Objective C. And if you want to run apps, the iPhone is in its own category. (Just spend a car ride with an iPhone owner and you'll see..."Look, you can flick a ball of paper". I can't knock it - it's a fun app!)

What's weird here is that the iPhone is pretty much invented out of whole cloth. It doesn't run software from any other platform, it builds its UI off of Objective C and Cocoa (which, to the non-Kool-Aid drinking half of the Apple third party development community looks like a new way to force us to use what we've been ignoring for years) and Apple has had the device locked up from day 1. This couldn't be more different than how Windows gained domination. So how did we get here?

Clearly having a beautiful device way before everyone else makes a huge difference. But I want to focus on another idea: is it possible that technology "productivity dividends" have fundamentally changed the calculus of building a new platform?

Development of applications for the original Macintosh was, by modern standards, brutal. You had 128K for the OS and your app, and it was a tight squeeze. Every line of code was performance critical and size critical. Those first GUI-based apps were written by some seriously brilliant programmers who had to sweat bullets.

Fortunately for us working programmers, computers are now much much faster and bigger. Instead of writing apps that are millions of times faster (which no one would care about - at some point, the window appeared to open instantly and any speed improvement is moot) we write at a higher level of abstraction, which means we write apps more quickly. To draw a supply and demand analogy, apps for the iphone (or any computer now) are less expensive in man hours because we have better tools that trade hardware horsepower for ease of development.

So that might partly explain why Apple now has 140,000 apps or so on their phone. It's not that hard to write them. But what about this business where Apple hand-picks apps and rejects the ones they don't like? My first reaction as an iPhone app developer was "hrm....it sure looks like a real computer, but man is it locked down." It certainly wasn't what I was used to.

The iPhone is surprising device to develop for, because as an app developer, you aren't given the tools to hose the machine. As a Windows developer you might be grumpy that, after decades, Microsoft has finally said that you can't dump files randomly in the system folder without user permission, but the iPhone takes things more seriously. It's somebody's phone, damnit, and your app isn't getting outside of its sandbox, let alone into the OS.

I see the fact that the iPhone has successfully developed a third party market despite being locked down as an indication that user demands may be changing. In the old world, where apps were rare and expensive to write, what we wanted was: more software. Perhaps in the new world, where writing apps isn't so hard, what users want is an experience that focuses on quality rather than quantity of apps.

(Or to put it another way: if you would agree to audit every single piece of software that a user might put on their Windows computer and guarantee that none of it was going to wreck that computer, you'd have a service you could sell. The iPhone comes with that out of the box.)

Of course, I could be missing the point entirely; the iPhone cuts distributors out of the loop, with sales going only to store and studio - perhaps that's enough to launch 140,000 apps.