How did Elite do vertex transformation?

Question

In 3D graphics, vertex transformation is the process of converting x,y,z coordinates in 3D space, to x,y coordinates on the screen. According to https://www.khronos.org/opengl/wiki/Vertex_Transformation it is done by matrix multiplication.

That sounds great on modern hardware, but Elite implemented true 3D on 6502-based machines; wireframe to be sure, but that requires vertex transformation nonetheless. The problem I have with imagining this being done by matrix multiplication is that the 6502 was a CPU on which adding a pair of 16-bit numbers took seven instructions. It seems difficult to imagine it multiplying matrices fast enough to animate three-dimensional objects reasonably smoothly.

Am I underestimating the speed at which matrices were actually multiplied, or did Elite use some faster trick for vertex transformation?

Answer 1

I recently posted a disassembly of the Apple II version, which is substantially similar to the C64 and BBC Micro implementations. One of the things I focused on was the way meshes were stored and rendered.

For each "hull definition" there are three tables:

• Vertices: 9-bit X/Y/Z coordinates, 5-bit level-of-detail value, 1-4 faces
• Edges: two vertex indices, 5-bit level-of-detail value, 1-2 faces
• Faces: 9-bit X/Y/Z surface normal vector, 5-bit visibility cutoff

The key to Elite's rendering is the surface normals. Each face of the object has a vector whose direction is orthogonal to the face, and whose magnitude is proportional to the distance of the face from the center of the object. By transforming this vector, and comparing it to a vector from the eye position (i.e. player), it's possible to determine whether the surface is facing toward or away from the viewer. If it's facing away, everything associated with the face can be ignored.

Each vertex and edge has a few associated faces. If any of the faces are visible, the vertex or edge must be rendered. If not, the vertex calculations can be skipped entirely.

Vertices and faces also have level-of-detail thresholds. Fine details turn distant objects into a smear, especially when drawing lines with exclusive-or, so some vertices and edges can be excluded when objects are far away.

This same mechanism is also what allows the turrets on ships like the Cobra Mk III and Krait -- something that isn't strictly allowed because backface culling on wireframes looks funny unless your shapes are convex. The edges are associated with nearby faces; when those rotate away from the viewer, the turrets aren't drawn. This works well on older low-resolution systems, but you can see things popping out when images are drawn at higher resolution.

This system isn't perfect. For example, parts of missile fins will disappear at certain angles, because edges can only be associated with two faces. There were also some errors in the data as well, ranging from incorrect surface normals to faces with non-coplanar vertices. Some of these problems can be corrected by re-computing the normals.

This is explained in more detail, with pictures and math, on the Classic Elite Hull Meshes page. You can see renderings of all of the hulls, with corrected normals, on this page. At 64x64 it's hard to see the flaws, even on the Krait. (If you download the SourceGen project you can make it full screen and single-step through the angles.)

---

As far as the math goes, you can see Elite's basic multiplication routine here. It uses three 256-byte tables. I didn't dig into the math for this disassembly, but it appears to be based on tables of logarithms (some notes here).

For comparison, Stellar 7 for the Apple II uses tables for trig functions but has massive unrolled multiply/divide functions, e.g. Divide16 and Multiply16_8. Stellar 7 was mathematically much simpler because shapes can only rotate about the Y axis, but computationally more expensive because the concave meshes didn't allow for simple backface culling.

Answer 2

Like all games from that era, cheating and tables.

• Two 256 byte tables and logarithms gave a 10x speed boost on multiply and divide on Commodore 64 at least.
• Matrix operations using addition only for fixed known rotation rates.
• Lazy evaluation.
• Only convex shapes making hidden line removal simpler and hidden line removal meaning only half the vertices needed to be considered.

This is discussed by David Braben himself from about the 24:10 mark in this GDC presentation.

Answer 3

all boils down to (4x4) * (4x1) multiplication where some elements are known so it can be done with 4 * 4D dot products in full but sometimes its enough just 3 * 3D dots and single 3D addition ... For more info see

• Understanding 4x4 homogenous transform matrices.

with fixed point and 4bit digit long multiplication + LUT is the multiplication not that slow ... Anyway asm was pretty fast and capable of doing this easily ... remember there where not many objects in Elite around.

However at the time of Elite was common to use quaternions instead of transform matrices which required much less operations for rotation So Elite most likely used those.

[Edit1]

Thanks to Mick Waites I found this:

• Elite The New Kind

which is reverse engineered BBC Elite source code in C. However from a quick look at the alg_gfx.c its clear it uses different gfx engine at low level as some of the stuff did not exist at the time. Its something between BGI,3Dfx and SW. But it might be just resolution and gfx API handling for different platforms.

in elite.h the player is defined as:

struct player_ship
{
    int max_speed;
    int max_roll;
    int max_climb;
    int max_fuel;
    int altitude;
    int cabtemp;
}; 

extern int flight_speed;
extern int flight_roll;
extern int flight_climb; 

which implies something like Euler Angles (but just 2 instead of 3 probably to avoid gimbal locks).

in vector.h there is:

struct vector { double x; double y; double z; };

typedef struct vector Matrix[3];
typedef struct vector Vector;

void mult_matrix (struct vector *first, struct vector *second);
void mult_vector (struct vector *vec, struct vector *mat);
double vector_dot_product (struct vector *first, struct vector *second);
struct vector unit_vector (struct vector *vec);
void set_init_matrix (struct vector *mat);
void tidy_matrix (struct vector *mat); 

Which implies 3x3 rotational matrix usage (so not uniform 4x4 !!!). It looks like the transformations are done in space.c:

void move_univ_object (struct univ_object *obj)
{
    double x,y,z;
    double k2;
    double alpha;
    double beta;
    int rotx,rotz;
    double speed;

    alpha = flight_roll / 256.0;
    beta = flight_climb / 256.0;

    x = obj->location.x;
    y = obj->location.y;
    z = obj->location.z;

    if (!(obj->flags & FLG_DEAD))
    { 
        if (obj->velocity != 0)
        {
            speed = obj->velocity;
            speed *= 1.5;   
            x += obj->rotmat[2].x * speed; 
            y += obj->rotmat[2].y * speed; 
            z += obj->rotmat[2].z * speed; 
        }

        if (obj->acceleration != 0)
        {
            obj->velocity += obj->acceleration;
            obj->acceleration = 0;
            if (obj->velocity > ship_list[obj->type]->velocity)
                obj->velocity = ship_list[obj->type]->velocity;

            if (obj->velocity <= 0)
                obj->velocity = 1;
        }
    }

    k2 = y - alpha * x;
    z = z + beta * k2;
    y = k2 - z * beta;
    x = x + alpha * y;

    z = z - flight_speed;

    obj->location.x = x;
    obj->location.y = y;
    obj->location.z = z;    

    obj->distance = sqrt (x*x + y*y + z*z);

    if (obj->type == SHIP_PLANET)
        beta = 0.0;

    rotate_vec (&obj->rotmat[2], alpha, beta);
    rotate_vec (&obj->rotmat[1], alpha, beta);
    rotate_vec (&obj->rotmat[0], alpha, beta);

    if (obj->flags & FLG_DEAD)
        return;


    rotx = obj->rotx;
    rotz = obj->rotz;

    /* If necessary rotate the object around the X axis... */

    if (rotx != 0)
    {
        rotate_x_first (&obj->rotmat[2].x, &obj->rotmat[1].x, rotx);
        rotate_x_first (&obj->rotmat[2].y, &obj->rotmat[1].y, rotx);    
        rotate_x_first (&obj->rotmat[2].z, &obj->rotmat[1].z, rotx);

        if ((rotx != 127) && (rotx != -127))
            obj->rotx -= (rotx < 0) ? -1 : 1;
    }   


    /* If necessary rotate the object around the Z axis... */

    if (rotz != 0)
    {   
        rotate_x_first (&obj->rotmat[0].x, &obj->rotmat[1].x, rotz);
        rotate_x_first (&obj->rotmat[0].y, &obj->rotmat[1].y, rotz);    
        rotate_x_first (&obj->rotmat[0].z, &obj->rotmat[1].z, rotz);    

        if ((rotz != 127) && (rotz != -127))
            obj->rotz -= (rotz < 0) ? -1 : 1;
    }


    /* Orthonormalize the rotation matrix... */

    tidy_matrix (obj->rotmat);
}

So if I see it right the rendering uses 3x3 rotation matrix + 3D translation vector (I commonly use that too in the 8bit past) and to compute the translation there is a strange formula:

    k2 = y - alpha * x;
    z = z + beta * k2;
    y = k2 - z * beta;
    x = x + alpha * y;   
    z = z - flight_speed;

That looks something between quaternion, Euler angles and 2D rotation... To sumarize the math is mostly:

• 3x3 rotation transform matrtix
• 3D translation
• 2 Euler angles