Understanding Half Texels

August 27, 2012 General News 0 Comments

Last night I was revisiting terrain generation on the GPU. I ran into the same problem that always crops up when you try to generate heightmaps on the GPU: slight misalignments that cause cracks between neighboring terrain patches. The root cause of this is texture coordinates, but it's easy to overlook the problem, especially since it is well-known that chunked terrain WILL have cracks between neighboring chunks of different LOD levels. However, the cracks caused by LOD differences should only exist at every other vertex (i.e., every other vertex should line up perfectly). But if you don't take special care when thinking about texture coordinates, you won't have any vertices lining up perfectly between neighboring chunks. Skirts will pretty much fix the problem, especially at high resolutions, but it's still discomforting to know that your implementation is fundamentally wrong.

Here's what you're probably doing: float height = H(tex.x + offsetX, tex.y + offsetY, ...), where tex is the texture coordinates, and offsetX and offsetY are uniforms passed in to the shader that indicate the location of the chunk relative to the world. In a perfect world, where texture coordinates range between 0 and 1, this would work, because the border of one chunk, H(1 + 0, ...), for example, would exactly line up with the border of the neighboring chunk, H(0 + 1, ...). So when you see cracks in the terrain, you must immediately begin to suspect that the texture coordinates are doing something strange. And indeed, they are.

Try this: make a pixel shader that outputs the texture coordinates to a floating point texture. Then read it back and examine the results. They may surprise you (they surprised me): the texture coordinates do NOT range from 0 to 1. On the contrary, they range between [1/(2w), 1 - 1/(2w)] in u and [1/(2h), 1 - 1/(2h)] in v, where w and h are the width and height of the texture in pixels, respectively. Wait, what??? Yes. Believe it or not, this makes sense. Texels are addressed by their CENTER, so 0 is actually the upper-left corner of the upper-left texel. To get to the center of the first texel, you must add a half-texel offset in both dimensions, which is 1/(2w) in u and 1/(2h) in v. The same reasoning applies to all other texels. So why is the shader lying to you? Well, if the shader had handed you coordinates that actually ranged from 0 to 1 and you tried to do a texture lookup, then you would be accessing, for example, the texel at (0, 0), which would invoke filtering - probably not what you wanted. This is a big problem in DirectX, where the driver does NOT automatically offset the texture coordinates for you, so it's really easy to end up invoking a bilinear filter on your whole texture if you aren't specifically aware of this subtlety. Luckily, GL is nice enough to anticipate this problem and solve it for us. But it has the nasty side-effect of getting in the way when we try to do things like this where we want [0, 1].

Ok, hopefully I've made a convincing case that texture coordinates don't range from 0 to 1 in your fullscreen fragment shader, and that there's actually a good reason for that. Once we understand the issue, the solution is really simple. We want to map the range [1/(2x), 1 - 1/(2x)] to [0, 1]. Luckily, it doesn't take a lot of heavy math to realize that we can easily achieve this with the formula u' = b * (u + a), where a = -1/(2x) and b = x / (x - 1). Intuitively, this means we first subtract a half-texel, which gives us the range [0, 1 - 1/x], then we scale by x / (x - 1) to bring that second component back to 1: (1 - 1/x) * x / (x - 1) = (x - 1) / (x - 1) = 1. And that solves it!

And now, the obligatory pretty picture of the day! I found this system today and really loved the background and the asteroid arrangement.

Finally, here's a great resource on the half texel issue, and it includes some nice images: http://drilian.com/2008/11/25/understanding-half-pixel-and-half-texel-offsets/.