27

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?

  • 2
    The Apollo Guidance Computers did such transformations (e.g. REFSMMAT), and they were far less powerful than a 6502. – DrSheldon Jan 29 at 18:56
  • 1
    Elite also ran on Z80 computers (also 8-bit) such as the Amstrad CPC. – CJ Dennis Jan 30 at 4:07
  • 1
    Please define "true 3D". – Mast Jan 30 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 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 at 9:01
39

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.

  • 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). – Wheelmagister Jan 29 at 12:33
  • 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 at 8:30
  • +1 for "cheating and tables". Some of the ingenious techniques still baffle me. – chrylis -on strike- Jan 30 at 11:17
  • 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 at 18:34
  • @Tommy heh you're right didnt think about to convert camera into object local space ... – Spektre Jan 31 at 8:56
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
  • 7
    "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 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 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 at 15:20
  • 4
    @Spektre There is already a C recreation of Elite that was written byte by byte from the original disassembly called The New Kind. It is pretty hard to track down the source these days, Mr Braben was very pro-active in keeping it from the internet. As far as I have been able to ascertain, it appears to be 100% accurate in the recreation of the maths used. There is a 'feature' in the original that causes you to move backwards when simultaneously climbing and rolling whilst moving at full speed that is present in The New Kind. – Mick Waites Jan 31 at 7:59
  • 2
    This seems to be the proper source, although it's extremely unreadable: github.com/kieranhj/elite-beebasm – pjc50 Jan 31 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.