Translate
EnglishFrenchGermanItalianPortugueseRussianSpanish

The XL Engine is and will remain free, donations are purely optional but greatly appreciated.

It has been a long time since my last update but my life has been undergoing a series of changes – for the better – that have occupied my time. I have started to settle in and have resumed working on the DaggerXL Beta. In this post I will talk a little about the Daggerfall Renderer, starting with some simple basics.

Below is the Object structure – the structure itself (i.e. size of variables and such) is fully known though a few members still do not have appropriate names yet, u1, u2, u3. As you can see the world space position is stored in (xPosition, yPosition, zPosition) in inches and  the rotation angles are stored in angles[3]. Positions are stored in absolute world space – this position is not relative but the actual position on the world map. The angles range from 0 – 2047 – which maps to 360 degrees. In other words 512 = 90 degrees, 2048 = 360 degrees.

struct Object
{
   //0x00
   byte type;
   //0x01
   word angles[3];
   //0x07
   int xPosition;
   //0x0B
   int yPosition;
   //0x0F
   int zPosition;
   //0x13
   word index2;
   //0x15
   word flags;
   //0x17
   word dataSize;
   //0x19
   word index;
   //0x1B
   word arrayIndex;
   //0x1D
   word model;
   //0x1F
   int ID;
   //0x23
   byte u1;
   word u2;
   byte u3;
   //0x27
   int curLocID;
   //0x2B
   dword time;
   //0x2F
   Object *target2;
   //0x33
   Object *target;
   //0x37
   Object *siblingNext;
   //0x3B
   Object *siblingPrev;
   //0x3F
   Object *child;
   //0x43
   Object *parent;
};

To generate a rotation transform for an object or for the camera Daggerfall uses the following matrix:

Given angles: x=xAngle, y=yAngle, z=zAngle – the Daggerfall rotation matrix =

[ cos(z)*cos(y) + sin(x)*sin(z)*sin(y)  -sin(z)*cos(x)     sin(z)*sin(x)*cos(y) ]
[-sin(x)*sin(y)*cos(z) + sin(z)*cos(y)   cos(x)*cos(z)    -cos(z)*sin(x)*cos(y) ]
[ sin(y)*cos(x)                          sin(x)            cos(x)*cos(y)	]

The 3×3 rotation matrix is stored in 1.3.28 fixed point.

Here is the function used to generate the 3×3 rotation matrix from the angles:

void Build3x3Matrix(int xAngle, int yAngle, int zAngle, int *matrix)
{
    int x = xAngle&0x07ff;
    int y = yAngle&0x07ff;
    int z = zAngle&0x07ff;

    const int64 half = 134217728LL;
    int64 c = (int64)sinTable[z] * (int64)sinTable[y] + half;
    camAngle0 = (int)( c >> 28LL );

    c = (int64)sinTable[y] * (int64)sinTable[512+z] + half;
    camAngle1 = (int)( c >> 28LL );

    c = (int64)sinTable[x] * (int64)sinTable[512+y] + half;
    camAngle2 = (int)( c >> 28LL );

    c = (int64)sinTable[512+z] * (int64)sinTable[512+y] + 
        (int64)sinTable[x] * (int64)camAngle0 + half;
    matrix[0] = (int)( c >> 28LL );

    c = -(int64)sinTable[z] * (int64)sinTable[x+512] + half;
    matrix[1] = (int)( c >> 28LL );

    c = (int64)sinTable[z] * (int64)camAngle2 + half;
    matrix[2] = (int)( c >> 28LL ) - camAngle1;

    c = -(int64)sinTable[x] * (int64)camAngle1 + 
         (int64)sinTable[z] * (int64)sinTable[y+512] + half;
    matrix[3] = (int)( c >> 28LL );

    c = (int64)sinTable[x+512] * (int64)sinTable[z+512] + half;
    matrix[4] = (int)( c >> 28LL );

    c = -(int64)sinTable[z+512] * camAngle2;
    matrix[5] = (int)( c >> 28LL ) - camAngle0;

    c = (int64)sinTable[y] * (int64)sinTable[x+512] + half;
    matrix[6] = (int)( c >> 28LL );

    matrix[7] = sinTable[x];

    c = (int64)sinTable[x+512] * (int64)sinTable[y+512] + half;
    matrix[8] = (int)( c >> 28LL );
}

A few things to note – the fixed point format is 1.3.28 so 64 bit math is required to avoid overflows, fortunately x86 assembly makes this fairly easy to do quickly. Also note that Daggerfall has a sine table that stores the sin values for all angles ranging from 0 to 2047 (remember that this maps to 0 to 360 degrees). As you can see the cosine values are computed as sinTable[angle+512] – since sine and cosine are out of phase by 90 degrees, we can compute cosine as cos(angle) = sin(angle+90degrees) which Daggerfall does to limit the size of the table.

The camera uses the same position and angles to generate the view and projection matrices. However the way positions are transformed into screenspace are a little different from most modern engines. The projection matrix is build directly from the view matrix by scaling by the x relative and y relative screen aspect ratios, built as follows:

void BuildAspectScaledMatrix(int *rotMatrix, int *outScaledMatrix)
{
    int64 c = (int64)rotMatrix[0] * (int64)screenAspectX;
    outScaledMatrix[0] = (int)( c >> 14LL );

    c = (int64)rotMatrix[1] * (int64)screenAspectX;
    outScaledMatrix[1] = (int)( c >> 14LL );

    c = (int64)rotMatrix[2] * (int64)screenAspectX;
    outScaledMatrix[2] = (int)( c >> 14LL );

    c = (int64)rotMatrix[3] * (int64)screenAspectY;
    outScaledMatrix[3] = (int)( c >> 14LL );

    c = (int64)rotMatrix[4] * (int64)screenAspectY;
    outScaledMatrix[4] = (int)( c >> 14LL );

    c = (int64)rotMatrix[5] * (int64)screenAspectY;
    outScaledMatrix[5] = (int)( c >> 14LL );

    outScaledMatrix[6] = rotMatrix[6];
    outScaledMatrix[7] = rotMatrix[7];
    outScaledMatrix[8] = rotMatrix[8];
}

Note that the screenAspectX and screenAspectY are stored in 1.17.14 fixed point but the resulting projection matrix is still stored in 1.3.28 fixed point.

Positions in view space are stored as 1.23.8 fixed point so a position can be transformed as follows:
Given (x,y,z) in absolute world space:
(Note s_xPosition, s_yPosition and s_zPosition are the camera positions extracted from the camera objects and used by the renderer).

//Convert to camera relative coordinates, stored in 1.23.8 fixed point), still in inches.
int viewX = (x - s_xPosition)*256;
int viewY = (y - s_yPosition)*256;
int viewZ = (z - s_zPosition)*256;
TransformPoint(&viewX, &viewY, &viewZ, projMatrix);

void TransformPoint(int *x, int *y, int *z, int *matrix)
{
    int64 xp = (int64)(*x)*16LL;
    int64 yp = (int64)(*y)*16LL;
    int64 zp = (int64)(*z)*16LL;

    *x = (int)( ( xp*(int64)matrix[0] + yp*(int64)matrix[1] + zp*(int64)matrix[2] ) >> 32LL );
    *y = (int)( ( xp*(int64)matrix[3] + yp*(int64)matrix[4] + zp*(int64)matrix[5] ) >> 32LL );
    *z = (int)( ( xp*(int64)matrix[6] + yp*(int64)matrix[7] + zp*(int64)matrix[8] ) >> 32LL );
}

Finally the following functions are used to cull the bounds, stored as spheres – center in relative camera coordinates and radius in inches.

enum ClipPlanes_e
{
    PLANE_NEGX =  1,
    PLANE_POSX =  2,
    PLANE_POSY =  4,
    PLANE_NEGY =  8,
    PLANE_NEAR = 16,
    PLANE_FAR  = 32,
    PLANES_ALL = PLANE_NEGX | PLANE_POSX | PLANE_POSY | PLANE_NEGY | PLANE_NEAR | PLANE_FAR
};
static int nearPlane=2560;	//[1E9CC0] :the near plane is 10 inches.
static int farPlane =393216;	//[1E9CC4] :the far plane is 128 feet 
                                //(at normal maximum settings).

int CullPlaneDistX(int xScaled, int yScaled, int radius)
{
    int r = (zRadius*xScaled)>>16 + (xRadius*yScaled)>>16;
    if ( r < 0 ) 
    { 
        r = -r; 
    }
    return r+radius;
}

int CullPlaneDistY(int xScaled, int yScaled, int radius)
{
    int r = (zRadius*xScaled)>>16 + (yRadius*yScaled)>>16;
    if ( r < 0 ) 
    { 
        r = -r; 
    }
    return r+radius;
}
//Is the sphere: center = (x,y,z), radius = r at least partially visible?
//Returns 0 if visible else 1.
//Note that the sphere position must be relative to the camera and be in 1.23.8 fixed point format.
int IsSphereVisible(int x, int y, int z, int r)
{
    //transform into projection space.
    TransformPoint(&x, &y, &z, projMatrix);

    //figure out which planes the sphere needs to be tested against.
    int clipFlags = PLANES_ALL;	//6 planes = 111111 binary = 63
    if ( z >= nearPlane )
    {
        clipFlags ^= PLANE_NEAR;
    }
    if ( z <= farPlane ) 	
    { 
        clipFlags ^= PLANE_FAR; 	
    } 	
    if ( x >= -z )
    {
        clipFlags ^= PLANE_NEGX;
    }
    if ( x <= z )
    {
        clipFlags ^= PLANE_POSX;
    }

    if ( y <= z ) 	
    { 
        clipFlags ^= PLANE_POSY; 	
    } 	
    if ( y >= -z )
    {
        clipFlags ^= PLANE_NEGY;
    }

    //compute plane data.
    xRadius = (int)( ((int64)x*(int64)x*(int64)ScreenAspectA   )>>32LL );
    yRadius = (int)( ((int64)y*(int64)y*(int64)ScreenAspectA_SC)>>32LL );
    zRadius = z;

    //test against each plane based on the clipflags set (see above).
    if ( clipFlags ) 
    {
        if ( s_clipFlags&PLANE_NEAR ) 
        {
            if ( z+r <= nearPlane ) 				
                return 1; 		
        } 		
        if ( s_clipFlags&PLANE_FAR ) 		
        { 			
            if ( z-r >= farPlane )
                return 1;
        }

        if ( s_clipFlags&PLANE_NEGX )
        {
            if ( CullPlaneDistX(ScreenX_Scaled, ScreenH_Scaled, r) <= 0 )
                return 1;
        }

        if ( s_clipFlags&PLANE_POSX )
        {
            if ( CullPlaneDistX(ScreenX_Scaled, -ScreenH_Scaled, r) <= 0 )
                return 1;
        }

        if ( s_clipFlags&PLANE_POSY )
        {
            if ( CullPlaneDistY(varD34, -varD30, r) <= 0 )
                return 1;
        }

        if ( s_clipFlags&PLANE_NEGY )
        {
            if ( CullPlaneDistY(varD34, varD30, r) <= 0 )
                return 1;
        }
    }

    return 0;
}

Anyway that is enough about the renderer for this post but I will talk about the lighting system, more about culling objects and other topics in future blog posts. If you want to see the original assembly for these functions, visit the Renderer Part I – Original Functions in Assembly page. As you will see I have rearranged the code a little to make some things more clear.

17 Responses to “Daggerfall Rendering, Part I”

  • Nick:

    I know jack shit about coding, but I am glad to see this post.

    Keep up the good work, man.

  • Bob:

    Nice, but since you settled in does that mean you’ll be posting more often?

  • Simon Buchan:

    Hey you’re not dead! Glad to hear it’s not for bad reasons, seems to be pretty rare for the people I’m following.

    I would describe the angles as a 0.16 fixed point unit angle – even before you mentioned fixed point further down ;). I’ve not seen the ’1.’ prefix for sign before – I’ve always seen it assumed in the integral size and explicitly ‘unsigned fixed point’ if it’s not present (though ’0.x’ makes that pretty obvious).

    I’ve noticed that you stick to C (ish?) in your decompilations: I can see the appeal of not getting distance between it and the assembly you’re comparing it to, but I can’t help but cringe seeing all those >> 17 and * 256′s where a quick template <int MantissaBits, typename BaseInteger=int> struct fixed_point would make it all pretty :).

    I’m at an annoying point with matrices where I know enough to try to use them, but not enough to be efficient at using them – I can never keep straight which side of the multiplication is “first”, and as soon as there is a projection matrix involved my head explodes. Almost certainly just because I’ve not had enough practice using them, and the mathematical matrices being layed out differently (often with different axes!) probably doesn’t help.

    • luciusDXL:

      The code is intentionally in C in order to try and replicate the original structure and keep things simple. The game code will probably remain in C, even though the XL Engine itself is in C++.

  • Great, good news!!! Hope this year will see a Daggerfall Beta!!! :)

    • ebbpp:

      I lost hope for such things long ago, but still hope that the rebuild will be good enough to come back to Daggerfall.

  • Bobsled7:

    Always exciting to see an update on DaggerXL!

  • Mike:

    I think my brain exploded. :(

  • Damanslaya:

    (First seconds in.) Okay!
    (Thirty seconds in.) Mmmmmmm…
    (5 minutes in.) Uhhhhhhh…
    (After Reading it all) Holy #%&$ what a post!

    I must say, this is truly an art form of its own and you are like the Star Wars Rock Band picture, just completely awesome with reverse-engineering and coding. :O

  • nullzero:

    Welcome back! :)

  • Andy B:

    Glad to see you’re back, and great blog post!

    It’s pretty weird that they mapped angles from 0-2048 to 0-360, and even weirder that they used fixed point representation — were either of those practices at all “standard” when Daggerfall was made back in the 90s? Or are they just weird, Daggerfall-specific quirks?

    • luciusDXL:

      In those days floating point co-processors could not be relied to be in the system and operating with pure integers, using fixed point, was standard – especially in the core engine code. To store angles as integers, obviously 360 discreet angles are far too few for smooth rotation and mouse control. With 2048 discreet levels then a 320×200 view gives approximately 1 angular unit percision per pixel, allowing for smooth mouse control of the camera. At higher resolutions the angular precision would need to be increased to continue feeling smooth – 640×400/640×480 will probably still feel good, as evidenced by SkyNet – but the feeling would quickly degrade as the resolution increased beyond that point.

      • Dag:

        Floating point arithmetic is a historical curiosity. No, floats still are noticeably slower & obviously dirtier, sloppier than a pure integer, combinatorics approach (the mere float/int conversion is already unbearable). Yes, there are empires built on the inefficiency of floating point arithmetic e.g., NVIDIA & such. You don’t need floats, / or * in a 3-D renderer. You don’t even need the weaklings’ parallelism. There are existence proofs.

  • Dan:

    I’m very glad you understand this so well. Even with 3D experience most of those details are unfamiliar to me. Keep up the good work!

  • Claus:

    Glad to see you’re not dead!

  • Klasodeth:

    This post is a test.

Leave a Reply

The XL Engine is and will remain free, donations are purely optional but greatly appreciated.