Texture Coordinates and Valid Ranges

When writing a software rasterizer for textured geometry you might have come across the following conversion from UV coordinates to texture coordinates:

int texX = int(u * (width – 1));

int texY = int(v * (height – 1));

It is simple, it never results in access violations for valid ranges of UV coordinates, and it is relatively fast. However, this conversion is actually wrong, but you might never have noticed it. In fact, the problem really only gets noticeable given low resolution textures.

First of all, let us take a look at the valid range of UV coordinate components and texture coordinate components. UV coordinates are real numbers that range [0.0, 1.0] while texture coordinates, which are laid out in memory in discrete steps of 1 have a valid discrete range of [0, N-1], where N is the dimension of the texture. However, since UV coordinates are floating point values multiplied by a texture dimension minus one and then converted to an integer the valid range for floating point texture coordinates, rather than discrete texture coordinates, becomes [0.0, N).

Let us try to map a quad with the entirety of this 2x2 texture

 

using the UV coordinates and conversion technique specified above. We will then get the following result:

 
 

We want to map the entire texture across the quad, yet we only get the lower left texel of the texture, with a sliver of the top left texel at the topmost scanline of the quad. This is clearly wrong. But what exactly is wrong? Well, there are actually two connected issues in our UV to texture coordinate conversion.

The first issue that I will bring up is the fact that our conversion function will only display a texture coordinate component N-1 when a UV coordinate component is exactly 1.0, the very end of the valid range for UV coordinates. For UV coordinate components of anything below 1.0 the texture coordinate rendered will not be N-1. This means that the texel N-1 will only be rendered at the edges of our quad where the UV coordinate components are exactly 1.0, or maybe not at all depending on the orientation of our quad and the subpixel accuracy scheme used for rasterization. We partially solve the problem by using the full width and height of the texture as multipliers to the UV coordinates when converting to texture coordinates. However, we must be weary of not reading outside of the allocated memory for the given texture, so we need to wrap those values to the valid range of the texture. The conversion function is therefore updated to look like the following:

int texX = int(u * width) % (width – 1);

int texY = int(v * height) % (height – 1);

Using the modulo operator we make sure to wrap the texture around should the resulting texture coordinate lie outside the discrete range [0, N-1]. For power-of-two textures we can use the AND operator instead of the more expensive modulo operator. By making these changes we get the following result:

 

This looks much better, but there is still a problem where the UV coordinate components are exactly 1.0, see the top scanline of the quad where the texture has been wrapped around to sample from the bottom of the texture. This is actually a correctly rendered quad, but it is not the way we want it to look. Inspecting the ranges of UV that correspond to a unique texture coordinate we will find that the texturing process is performing exactly as it should, but that we as programmers expect it to do something illogical.

What our algorithm does is that for each UV coordinate range of [1.0/N * i, 1.0/N * (i+1)), where i is a discrete number, we get a unique texture coordinate for every unique i, or so we might expect. However, both i = N and i = 0 result in the texture coordinate 0, which is something we do not always want.

You might be tempted to say that rounding is the solution, but the problem does not exactly stem from rounding per se. It is rather caused by a discrepancy in the valid ranges of UV coordinates as opposed to the valid ranged of texture coordinates. Notice the difference in range notation between the two coordinate systems. UV coordinates are valid for the real value 1.0, but texture coordinates are not valid for the real value N, but are valid for all real values below N since built-in floating to fixed point conversion in C and C++ simply disregard decimals.

So how can we actually solve the problem? The answer is UV hinting (I made up that term). UV hinting is a simple process in which the rasterizer simply takes the relevant adds or subtracts a fraction of the relevant UV interpolation deltas from the UV coordinates used for interpolation. This makes sure that UV coordinates are interpolated within the range (a, b) rather than [a, b] and, ultimately, avoids the edge cases where 1.0 is converted to N.

The result speaks for itself:

So, then the question becomes what fraction should be added or subtracted? Well, the answer is fairly simple. Instead of sampling texture coordinates at the edges of the screen pixels, you instead sample from the center of the pixels, thereby shifting the UV coordinates that are sampled. This means that when interpolating a scanline with the end-point U coordinates [1.0, 0.0] (which means that interpolation starts from 1.0 and decrements until 0.0 is reached) between the screen pixels 0 and 100 you will start sampling from the U coordinate 1.0 - 1.0 / (100 - 0) * 0.5 = 1.0 - 0.005 = 0.995. Then this starting point is interpolated for every pixel in the screen x-axis using the delta (0.0 - 1.0) / (100 - 0) = -0.01.

The end point is also shifted in the same direction as the starting point. However, since we (should) be stopping one pixel short of hitting the end-point [for (int x = x1; x < x2; ++x)] we will not overshoot, or even hit, the end-point of the valid UV range. Generalized, the entire interpolation for UV coordinates inside the scanline function should look like the following:

u = u1 - 1.0 / (x2 - x1) * 0.5 + (u2 - u1) / (x2 - x1) * x

v = v1 - 1.0 / (x2 - x1) * 0.5 + (v2 - v1) / (x2 - x1) * x

Remember that this correction will also have to be done for the y-axis on the screen (this will most likely occur inside the triangle edge interpolation stage rather than the scanline interpolation stage).