Daggerfall Mod:UV texture coordinates

Problem Statement

Daggerfall treats texture UV coordinates slightly differently than most 3D programs. If we consider a sequence of 3D Object Record's PlanePoint structures the solution presents itself.

Daggerfall UV Coordinate Interpretation by PlanePoint Ordinal

Ordinal	Interpretation
0	Actual Daggerfall UV Coordinate
1	Delta from UV[ 0 ]
2	Delta from UV[ 1 ]
3	Actual Daggerfall UV Coordinate
4 or more	zero-filled and unused

Experiments show the Daggerfall rendering engine only uses the UV coordinates for the first three PlanePoint records. Altering or changing UV[ 3 ] or UV[ 4 ] has no effect. This means we must find a relationship between a PlanePoint's Point and a PlanePoint's UV. Since all Plane values are associated with at least three PlanePoint values then we have enough information to attempt a solution. Furthermore, since some records do contain a fourth PlanePoint, we also have at our disposal a verification mechanism.

Integer Representation

While the UV coordinates are stored in 16 bit values, only the lower 12 bits appear to be directly meaningful. It is possible that some additional information is stored in the high order 4 bits, but it is unclear what that information would be. Properly considering only the lower 12 bits as a signed 12 bit integer, however, does correct some problematic polygons. While there are probably more efficient ways to handle it, something like the following should be done with the 16 bit integers that are read from the file before attempting to use them as mathematical values.

short fromFile = readCoordFromFile();
short valActual = fromFile & 0x0FFF;
if (valActual & 0x0800) {
    // sign extend so that 16 bit signed int has same value as 12 bit signed int
    valActual |= 0xF000;
}

As a historical point of interest, after valActual is divided by the subpixel factor of 16 (see "UV Scaling" below), this leaves a signed byte with an effective pixel addressing range of -128 to 127. This 8 bit value probably helped the efficiency of the software rasterizer considerably, as opcodes for working on 16 bit values are the slowest integer operations available on 32 bit x86 architectures. 16 bit opcodes require an additional prefix bit that adds a step to the decoding stage. Using a short int as a loop index in a tight loop can have a significant impact on running speed. On modern machines, you can speed up such a loop with either an 8 bit or a 32 bit index, but on the 486s and Pentiums in use when DF was released, 8 bit was still faster than 32 bit for certain operations.

Conversion

The first thing to bear in mind, is that if the plane is defined by 2 or more points, we must convert the second's UV coordinate from a differential to a Daggerfall absolute value.

U[ 1 ] += U[ 0 ]
V[ 1 ] += V[ 0 ]

If the Plane is defined by 3 or more points, we must then convert the third.

U[ 2 ] += U[ 1 ]
V[ 2 ] += V[ 1 ]

If the plane is defined by 4 or fewer points, our work is done. Of the 10,251 records within the file, 5,253 are successfully processed with no more work.

If the plane is defined by 5 or more points, then we have our work cut out for us. Points 0-3 are now in Daggerfall absolute UV, but the remainder must be translated.

If we assume the relationship between the point's ( X, Y, Z ) value and the ( U, V ) value is a linear equation, then we can attempt a solution with matrixes. The first thing we must do is add a new coordinate component to each point. We will call this component "W", and each point will have a value of 1.

        { X[0], Y[0], Z[0], W[0] }
Let P = { X[1], Y[1], Z[1], W[1] }
        { X[2], Y[2], Z[2], W[2] }
        { X[3], Y[3], Z[3], W[3] }

         { U[0], V[0] }
Let UV = { U[1], V[1] }
         { U[2], V[2] }
         { U[3], V[3] }

        { a, e }
Let C = { b, f }
        { c, g }
        { d, h }

If UV is defined as P * C, then we can solve for the unknown matrix C iif P is unimodular. Let Pi be the inverse matrix of P.

Let C = Pi * UV

Now for points 5+ defining the plane, we simply multiply by the coefficient matrix to solve for the point's UV value.

Let Pn = { X[n], Y[n], Z[n], W[n] }
Let { U[n], V[n] } = Pn * C

This much to date successfully converts 8,789 records within the file. The remaining records require a bit more work.

Things Going Wrong

If the above matrix P is not unimodular, we must determine which minor matrix of P is unimodular, then remove the corresponding row from UV, and then solve for C. The following pseudocode demonstrates the idea:

int index = -1;
for ( i = 0..(P.Height) ) { 
    Let probe = P.GetMinorAt( i, i )
    if ( probe.IsUnimodular ) { 
      index = i;
      break;
    } else { 
      probe = nil;
    }
}
if ( ( -1 == index ) or ( nil == probew ) ) { 
  // report failure
}

UV = UV.RemoveRow( index );

At this point we may solve for C:

Let Pi = P.Inverse
Let C = Pi * UV

Finally we may iterate through the 5+ points defining the plane, multiplying by C as we did above, except we must compute using a minor matrix of Pn:

Let Pn = { X[n], Y[n], Z[n], W[n] }
Pn.RemoveColumnAt( index )
Let { U[n], V[n] } = Pn * C

Of the 10,251 records contained within the file, 9,894 records are successfully translated via this method of using minor matrixes. There do remain 357 records which require considerably more complex coding because there is no single minor matrix which is unimodular. This means we will need to successively solve for minor matrixes.

Things Still Going Wrong

The remaining 357 records cannot be solved via a single minor matrix, and instead we must solve using the minor matrix of a minor matrix. In essence, for each minor matrix Pp of P, for each minor matrix Pq of Pp, if Pq is unimodular then we can solve for this plane's coefficient matrix C. We must remember to remove row p from the UV matrix, and then row q from the UV matrix, and then multiply by Pq.Inverse to UV for the value of matrix C.

UV Scaling

Normal UV coordinates are based on a value of 1.0 equaling the texture width or height as are usually used in 3D modeling programs, or 3D environments such as DirectX or OpenGL.

The units of Daggerfall UV texture coordinates are absolute, in subpixel resolution. Every 16 units of UV represents 1 pixel of texture width/height. Thus, the first step before converting Daggerfall UV coordinates into "normal" UV is to divide by 16. The next step is to divide by the texture's width or height as appropriate. So, if we had a texture of ( 64, 64 ) and Daggerfall UV values of ( 1024, 768 ), we would convert to "normal" UV as ( 1.0, 0.75 ).