Texture mapping paints a picture onto a polygon. Instead of filling a triangle with one colour, or a smooth blend between its corners, the renderer looks up the colour of every pixel it draws in a small image, the texture. A brick wall becomes one polygon and one picture of bricks, not a lattice of tiny ones. In the early 1990s it was what separated the new 3D games from the old: Edge’s caption for Ridge Racer in April 1994 asked readers to “remember the blocky pit crew in Virtua Racing? Texture-mapping makes all the difference.”
The hard part is not the picture but the arithmetic. Working out the right point in the texture for each pixel needs a division, and in 1993 a division per pixel was more than most processors could afford. How each machine dodged that division explains why Doom’s walls look solid, why Quake’s look solid too, and why the PlayStation’s textures swim when the camera moves.
Fast facts
- What it does: each corner of a polygon is given a position in a texture; each pixel’s colour is read from the matching point in between.
- Affine mapping: step evenly across the texture as you step across the screen. Cheap, and correct only where depth does not change.
- Perspective-correct mapping: step evenly through u/z, v/z and 1/z instead, and divide. Correct everywhere, at the cost of a division.
- On the PC: Ultima Underworld and Wolfenstein 3-D (1992), Doom (1993), Quake (1996).
- In the arcade: Namco’s Ridge Racer (1993) and Sega’s Model 2 (1994).
- PlayStation: affine only, “for reasons of cost”, in Sony’s words.
- Nintendo 64: perspective correction, filtering and mip-mapping in the graphics hardware.
How it works
Give each corner of a triangle a pair of texture coordinates, usually called u and v. As the renderer fills the triangle line by line, it needs u and v for every pixel.
The obvious method is to interpolate them in a straight line across the screen: work out how much u and v change per pixel, and add that on each time. This is affine texture mapping. It costs, as André LaMothe’s Black Art of 3D Game Programming put it in 1995, “a couple of additions per pixel and quite a few multiplications per polygon”. It is exactly right for a polygon facing the viewer square on. It is wrong for one seen at an angle, because perspective squeezes the far end of the surface into fewer pixels than the near end. Equal steps on the screen are not equal steps across the wall, so an affine mapper puts too much texture at the near end and too little at the far end. Straight lines in the texture bend, and because the error depends on where the polygon’s corners are, the bend shifts as the view moves.
The correct method rests on a property of the projection: u and v do not change in a straight line across the screen, but u/z, v/z and 1/z do, where z is the depth. A perspective-correct mapper interpolates those three values evenly and divides at each pixel to get u and v back. The additions are as cheap as before; the division is the cost.
LaMothe’s book shows how much that cost mattered. Its own texture mapper ignores depth altogether: “the perspective foreshortening that it adds isn’t worth the trouble when we’re trying to learn”. The same assumption, he noted, had been made for years in smooth shading, where “the interpolation was carried out without considering the depth of the triangles”.
Avoiding the division
Doom: lines of constant depth
LaMothe called the texture mapping in Doom and Dark Forces “special cases” that could “be done relatively easily in real-time”, unlike a game such as Descent that let “the viewpoint rotate in all axes”. The special case is depth. In Doom the player can never look up or down, walls are always vertical, and floors and ceilings are always flat. Every vertical column of a wall is therefore at a single distance from the viewer, and so is every horizontal row of floor.
The source code, which id Software released in 1997, shows the renderer taking advantage of both. For a wall, r_segs.c works out each column’s position in the texture and its scale once, and the column is then drawn with a constant step down the screen, which is exactly right because depth does not change along it. For a floor, R_MapPlane in r_plane.c takes one distance for each row of the screen and steps evenly across it. The renderer still does one division per column or per row, but never one per pixel, and the result is perspective-correct. It also explains Doom’s limits, set out in the BSP trees entry: no sloping floors and no tilted walls, because those would break the constant depth.
Quake: correct every few pixels
Quake let the player look in every direction, so its surfaces could lie at any angle. Its software renderer draws them in horizontal spans and does the perspective division only every few pixels, stepping evenly in between. In the released source, the C version, D_DrawSpans8, interpolates s/z, t/z and 1/z across the span and divides every 8 pixels. The hand-written x86 assembly that the game normally used is described in its own header as span-drawing code “with 16-pixel subdivision”. The error over 16 pixels is too small to see, and the division happens a sixteenth as often.
Small polygons
The cheapest defence was to keep polygons small. Affine error grows with the change in depth across a polygon, so a surface cut into many small pieces bends far less than one large one. Sony recommended this approach for its own console, as the next section shows.
The PlayStation’s warping textures
The PlayStation brought Ridge Racer home and made textured polygons ordinary on consoles, but its graphics chip mapped textures affinely. Sony said so in Edge in August 1995, answering an anonymous letter about the machine. Allan Murphy of Sony’s European developer support wrote that “the PlayStation does not include perspective correction in its hardware as standard for reasons of cost”. He did not deny the effect. “If very large polygons are drawn with certain types of texture map design, it is possible to see effects that are described as ‘texture map distortion’. By carefully considering the design of 3D meshes and application of textures this effect can be eliminated.”
Developers were less sure. Edge’s February 1996 feature on Tenka, a first-person game from Sony Interactive Entertainment (formerly Psygnosis), explained that “texture warping is caused by the GPU interpolating texture coordinates linearly, without perspective correction”, and reported that its designer, Paul Hilton, did not expect it to end “without severely limiting the graphical-environment”. The magazine added “the PlayStation’s habit of smearing larger polygons when they reach the edges of the screen”, which “seems to be something that cannot be avoided.”
Edge itself had already taken a view in October 1995, answering a reader: “Given that the PlayStation is a fraction of the cost of a high-end Pentium PC and yet is considerably more powerful, its lack of perspective correction is a small and excusable omission.” By then reviewers treated the effect as a known quantity. Alien Trilogy’s engine, in April 1996, “very rarely surrenders to PlayStation’s habit of warping textures when it fancies.”
The Nintendo 64: correction and mip-mapping in hardware
The Nintendo 64’s drawing chip did the division itself. Nintendo’s programming manual lists among the values it interpolates across a triangle “s/w, t/w, 1/w, lod for texture index, perspective correction, and mipmapping”, the same quantities as the method above, with w standing for depth. Correction could be switched off. It “is typically enabled for 3D geometry and disabled for 2D sprites”, and some of Nintendo’s faster microcode versions dropped it: “The features not supported by gspTurbo3D are: Clipping, lighting, perspective-corrected textures, and matrix stack operations.”
The same hardware tackled the opposite problem: a texture seen from far away, where many texture pixels fall into each screen pixel and the image shimmers. N64 Magazine explained the remedy in October 1997. The console “allows designers to store a number of different versions of each texture, and it decides for itself which version to be used based on the distance from the camera or the angle of view. The designers at DMA working on Silicon Valley, for instance, use a set of six versions of each texture at definitions of 32x32 pixels, 16X16, 8x8… and so on to 1x1.” These smaller copies are called mip-maps. The magazine was careful not to oversell them: “people have been doing all that in PC games for ages. What’s wonderful is that the N64 can handle all that for itself — it’s built into the hardware.”
How it reached games
Texture mapping was established in computer animation before games could afford it. ACE listed it in January 1988 among the techniques used to build animation on expensive graphics workstations, and by December 1988 it was a feature of Forms in Flight 2, a 3D rendering package for the Amiga that the magazine thought “seems to hold the crown as the most advanced graphics package for a home computer”. Rendering a frame in such a package took far longer than a game could spend.
Games brought it into real time from the early 1990s. Computer Gaming World’s report from the summer Consumer Electronics Show in September 1991 described Chris Roberts’s Strike Commander as using “graphics techniques of texture mapping, shading and use of disguised polygons”, with requirements that were “steep (one really needs 2 MB of RAM and a fast 386 to get the most out of the game)”. The magazine’s September 1992 review placed Wolfenstein 3-D “much like Origin’s Ultima Underworld … in a free-scrolling, texture mapped environment. Though less detailed than Underworld, the scrolling action is much faster.” By February 1994 it could look back on an arms race: “Successive releases like Strike Commander and Aces Over Europe have expanded the detail on the texture maps that cover the blocky polygon shapes and, once again, the technological ante has been upped. Now, gamers need 486s”.
The March 1994 issue reviewed Doom, whose “detailed textures of the walls, ceilings, and floors, the superb shading effects, and the fluid animation provide the most believable environment”, and whose maker had achieved “a huge technical improvement over id’s earlier titles”. The same issue’s report from the winter show summed up the year: “Want to talk about texture-mapping? It’s here in a lot of places.”
In the arcade
Edge used the technique to separate Namco’s Ridge Racer from Sega’s Virtua Racing in April 1994: “While Virtua Racing oozes class and, of course, has those incredible camera angles, the sheer quality of Ridge Racer’s texture-mapped images has the contest sewn up: 400 million floating-point operations per second, if anyone is interested in the maths involved, and enough polygons generated at 60fps to give a Silicon Graphics rep a heart attack.” Sega’s reply was the Model 2 board, whose texture-mapping chips came from a defence-simulation group that had passed from General Electric to Martin Marietta. In 1995 the merged Lockheed Martin offered the same technology for PCs as Real3D, with a specification that listed “True-perspective corrected texture” and up to 192 mip-mapped textures of 128×128 pixels.
The cost, and the cards that paid it
On the PC the work fell on the main processor. PC Zone in May 1996 called texture mapping “one of the biggest killers of frame rates. The effort needed to wrap those pretty bitmaps round polygons can cause serious strain to even the fastest CPU”, and observed that flight simulators such as US Navy Fighters and Apache Longbow “really benefit from leaving textures out”. The same issue carried a graphics-card advertisement promising “Precision, non-warping texture mapping.”
Perspective correction became a selling point for the first PC 3D accelerators. PC Gamer’s list of PowerVR’s features in March 1996 included “Perspective-correct textures do not bend or warp”. Edge’s round-up of accelerators in June 1996 marked Yamaha’s earlier chip down for “no perspective-correct textures” and noted that Rendition’s Vérité “offers perspective-correct texturing, bilinear filtering, z-buffering, alpha effects”, with id already calling it “the premier platform for Quake”.
Sources
- André LaMothe, Black Art of 3D Game Programming (Waite Group Press, 1995), chapter 12, pp. 762-763: the cost of texture mapping, the special cases of Doom and Dark Forces against Descent, and interpolation without depth.
- id Software, Doom source code, released 23 December 1997,
linuxdoom-1.10/r_segs.candr_plane.c(GPL-2.0; web, secondary): one texture column and scale per wall column, one distance per floor row. https://github.com/id-Software/DOOM - id Software, Quake source code, released 21 December 1999,
WinQuake/d_scan.candd_draw16.s(GPL-2.0; web, secondary): s/z, t/z and 1/z interpolated along a span, divided every 8 pixels in C and every 16 in the x86 assembly. https://github.com/id-Software/Quake - Nintendo, Nintendo Ultra 64 Programming Manual (NU6-06-0030-001G, 21 October 1996): the RDP’s interpolated values, perspective correction for 3D geometry, and the microcode versions that leave it out.
- ACE issue 4, January 1988: computer animation on workstations. ACE issue 15, December 1988: Forms in Flight 2.
- Computer Gaming World issue 86, September 1991 (Summer CES report, Strike Commander); issue 98, September 1992 (Wolfenstein 3-D review); issue 115, February 1994 (flight-simulator graphics); issue 116, March 1994 (Doom review and winter CES report).
- Edge issue 2, November 1993 (Ridge Racer); issue 7, April 1994 (Ridge Racer against Virtua Racing); issue 22, July 1995 (Real3D and Model 2); issue 23, August 1995 (Allan Murphy’s letter for SCEE Developer Support); issue 25, October 1995 (reply to a reader); issue 29, February 1996 (Tenka); issue 31, April 1996 (Alien Trilogy review); issue 33, June 1996 (PC accelerators).
- N64 Magazine issue 7, October 1997: graphics feature, mip-mapping.
- PC Zone issue 38, May 1996: texture mapping and frame rates; graphics-card advertisement.
- PC Gamer (UK) issue 28, March 1996: PowerVR feature list.