How did the Rush 3D engine in Crazy Taxi: Catch a Ride work?

Question

In an interview with the developers of the Crazy Taxi game for the GBA, they mention that they were able to achieve 3D graphics with a pure-software 3D rendering engine that they called Rush:

It is a full 3D poly engine – so it is ideal for most types of game. This engine allows us to develop games in 3D on the handheld, providing a much closer gameplay and visual experience for the player to those found on the next-gen consoles and PC. It includes an open plan environment meshing system which allows use of huge landscapes (such as the cities in Crazy Taxi), only limited by cartridge size. Also – as it is a software renderer we are not restricted to the GBA’s sprite limitations – so we can have more sprites on-screen, including very large sprites.

This engine allowed for impressive graphics on a rather limited system without hardware 3D:

(video)

How did it achieve such high quality graphics on a GBA system? From what I know, many objects are just sprites of objects from different view angles (such as the cars and the green arrow), and the audio quality is arguably not much better than that of Pole Position. It also understandably had a very poor framerate that would sometimes get as low as 8 or so fps, at least judging from memory. But even all of these tradeoffs do not seem sufficient, at least intuitively, to provide the graphics it has.

How did the Rush 3D engine work, and how did it achieve such impressive graphics?

Answer 1

I don't have knowledge of the Rush 3D engine itself, but I used to work for a company that made software graphics engines, so I can speak in general terms about how they're likely to work.

The GBA has a low screen resolution (240x160) and a reasonably powerful CPU (16.8 MHz ARM7 core). This is easily sufficient to run a Doom-style game engine with no further explanation required; Doom itself originally ran on x86 CPUs with higher clock speeds but much lower efficiency, and in a resolution of 320x200 which has substantially more pixels to produce.

Rush 3D, however, describes itself as a fully polygonal engine, more similar to Quake than Doom. A quick look at the provided screenshot suggests single, nearest-neighbour textures (probably without perspective correction) or Gouraud shading are the options available, and that the vertex/polygon count of each object is very low (which is fine for such a small screen). It is not immediately clear whether a Z-buffer is employed (which saves CPU but uses more RAM), or whether objects are simply rendered from furthest to nearest (slower but smaller). These limitations are typical of early software 3D rendering.

The usual process starts by filling the screen with the background, in this case a distant landscape and sky which is scrollable. Then the vertex coordinates of each object are transformed from object space to world space by a vector-matrix multiplication, and from there to screen coordinates with a second vector-matrix multiplication and a per-vertex perspective division. This yields a list of triangles defined by their corners' X and Y coordinates on the screen, depth into the screen, plus S and T coordinates into any texture they might have. Untextured triangles perform a lighting calculation instead of determining S-T coordinates.

Then rasterisation begins, converting those triangles into pixels. Each triangle covers many pixels on average, so this part is the most carefully optimised. Bresenham's algorithm (or something similar) gives the triangle edge coordinates along each scanline (pixel row). Textured triangles determine the S and T coordinates for the left end of each scanline by interpolation, then calculate a step by which S and T should be incremented for every pixel along the scanline.

It is then a simple matter to perform a texture lookup, or take the interpolated lit colour in Gouraud shading, and transfer that colour to the screen. Untextured triangles perform similar interpolation steps to convert the lit vertex colours to individual pixels. If a depth buffer is used, it is tested (using an interpolated depth) before the texture fetch and updated if the test passes.

Finally, HUD UI elements are drawn on top using normal 2D rendering techniques, which are much more efficient than converting them into 3D primitives and rasterising those.