Bilinear interpolation is a process that enhances textures that would
normally be larger on-screen than in texture memory, i.e. a single
texel is used for more than one screen pixel. Regular texture mapping
would appear to be 'blocky' in this case. Bilinear interpolation
reduces the blockyness by interpolating between texels.
To be more precise: The texel coordinates are internally kept at a
certain precision (usually using 8:8 fixed point). During texel
fetching, usually only the integer part is used to index the texels.
With bilinear interpolation, 4 texels are fetched, and the fractional
part of the texel coordinate is used to calculate a weight factor
for each of these four pixels, so that the final color of the pixel
on screen is a mix of the four fetched pixels.
This process enhances enlarged texture maps, but also rotated
texture maps, because for these textures effectively the pixels on
screen are anti-aliased.
Obviously, this process requires substantial calculations per pixel.
First, four weight factors must be determined. These are:
1. Uf * Vf
2. (1 - Uf) * Vf
3. (1 - Uf) * (1 - Vf)
4. Uf * (1 - Vf)
where Uf and Vf are fractional parts of the texel coordinates (U,V).
Then the 4 texels must be fetched and multiplied by these factors.
Finally, the four weighted colors must be added and drawn on the
To speed up this process, I decided to use the four most significant
bits of my U/V coordinates. So, Uf and Vf together fill 8 bits.
For each of these 256 combinates I then precalculate a weight factor.
This weightfactor is multiplied by 16 and stored as a byte.
So, the 'multiply table' (called multab in the sources) contains
To make the multiply of the weightfactor and the color fast, I
decided to use palletized textures. Each texture can have up to
256 distinct colors, wich is usually enough. Note that EACH
texture can have it's own palette, so the display will certainly
not look as monochrome as Quake. Besides, these are only
source colors, shading and transparency can increase the actual
number of different colors used to draw a texture.
The 256 colors are stored in a table in the texture class. Each
color is represented by it's 5/6/5 or 5/5/5 value. Besides this
original value there are 15 scaled versions of the color (one for
each possible weightfactor).
So, to retrieve a color and multiply it by the correct weight-
factor, I can now simply look up the right color in the palette
table. The palette table is by the way 256*16*2 bytes, that's
8Kb for each texture.
Because I retrieve scaled versions of each colors, two things
should draw your attention:
1. The four scaled colors can be added, and will never exceed
the maximum R/G/B values, even when all four fetched texels
where completely white.
2. Four scaled versions of the same color will result in a
potentially lower quality mix, because we loose some
accuracy here and there.
The final pixel can now be drawn to the screen without further