31

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?

6
  • 2
    The Apollo Guidance Computers did such transformations (e.g. REFSMMAT), and they were far less powerful than a 6502.
    – DrSheldon
    Jan 29, 2020 at 18:56
  • 1
    Elite also ran on Z80 computers (also 8-bit) such as the Amstrad CPC.
    – CJ Dennis
    Jan 30, 2020 at 4:07
  • 1
    Please define "true 3D".
    – Mast
    Jan 30, 2020 at 20:35
  • 1
    As to algorithms, not implementation, check out Elite: The New Kind, which took the original 6502 sources and transcribed them into C. Not line for line, and adopting floats and built-in operators for arithmetic, but in no way altered so as fundamentally to change the algorithms. It was pulled from the internet for predictable copyright infringement reasons way back when but the Version 1.0 sources are available on GitHub for browsing nevertheless: github.com/fesh0r/newkind
    – Tommy
    Jan 30, 2020 at 21:31
  • 1
    @Tommy I updated my answer with info from disecting of the Elite TNK (I found the repo on my own as I did not see your comment until now :) )
    – Spektre
    Jan 31, 2020 at 9:01

3 Answers 3

9

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.

45

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.

5
  • 1
    It would be, by the way, very interesting to read a comparison (by the limitations of the generated images, for example) of the techniques used in the Elite and Atari Battlezone (and other games that used Math Box). Jan 29, 2020 at 12:33
  • 1
    hidden line removal will still need to process all the vertexes they just do not render the edge but transformations must be applied
    – Spektre
    Jan 30, 2020 at 8:30
  • 1
    @Spektre a convex object would always lead to a BSP tree with no geometry changes, so you could transform the player into object space, do log(n)*(3 multiplies + 4 adds) to bucket the player into a convex leaf and then consult a pre-generated PVS. If it actually did tend to throw away roughly half the geometry then it'd be a net win, I think. And I will bet anyone that this is not what Elite does, due to the increased memory footprint per object, even assuming the authors considered the same solution.
    – Tommy
    Jan 30, 2020 at 18:34
  • @Tommy heh you're right didnt think about to convert camera into object local space ...
    – Spektre
    Jan 31, 2020 at 8:56
  • 2
    @Tommy There are three tables: vertices, edges, faces. The face table holds surface normals. The dot product of the surface normal and a vector from the camera to the surface is used to determine visibility of each face. Each vertex has 1-4 associated faces; if none of the faces are visible, the vertex is hidden. Each edge has two vertices and 1-2 associated faces. If none of the faces are visible, or one of the vertices is hidden, the edge is hidden. This allows the code to avoid transforming vertices that aren't visible.
    – fadden
    Mar 6, 2020 at 21:10
6

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

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:

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
9
  • 9
    "However at the time of Elite was common to use quaternions.... So Elite most likely used those"* That seems very unlikely, at least in graphics. AFAICS Elite only came out in 1984. My copy of "Fundamentals of Interactive Computer Graphics" AKA Foley and Van Dam, published in 1982 (reprinted in 84) does not have quaternions listed in the index. We certainly were not taught it in Computer Graphics of that era. The later "Comp. Grap. Principles and Practice" 1990, however does and cites Ken Shoemake 1985 dl.acm.org/doi/10.1145/325334.325242
    – Simon F
    Jan 30, 2020 at 9:12
  • 3
    Follow up: Just reading through Shoemake's 1985 paper and it seems likely he did introduce quaternions to CG. It's slightly tongue-in-cheek ;-) "What is the best representation for general rotations, and how does one in-between them? Surprisingly little has been published on these topics, and the answers are not trivial. This paper suggests that the common solution, using three Euler's angles interpolated independently, is not ideal. The more recent (1843) notation of quaternions is proposed instead..."
    – Simon F
    Jan 30, 2020 at 9:31
  • 1
    @SimonF according to wiki there where quite a few publications up to 1940 so the knowledge was already there... so its possible they where lectured on some schools at that time (I first heard about them on Cybernetics lectures few decades ago...) but as I stated with "most likely" its just a guess and to be sure we would need to contact the authors or dissect the assembly ...
    – Spektre
    Jan 30, 2020 at 15:20
  • 2
    This seems to be the proper source, although it's extremely unreadable: github.com/kieranhj/elite-beebasm
    – pjc50
    Jan 31, 2020 at 10:46
  • 1
    In github.com/fesh0r/newkind/blob/… is the projection into screenspace handled: a 8-bitshift (for multiplying with the hardcoded eyepoint) and a single division per x and y coordinate Jan 31, 2020 at 11:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .