From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: rec.games.design
Subject: Re: 3d-graphics problem
Date: 9 Oct 92 14:16:42 GMT
Organization: Department of Computer Science, U of Copenhagen

boender@dutiws.tudelft.nl (Hildo Biersma) writes:

>Hi all,
>A friend of mine is writing a 3d-game. (Elite-ish, I guess).
>In this game, the orientation of objects is kept in a 9*9 matrix. This
>matrix is in 4+12 bit fixed point representation. Now, this matrix is altered
>whenever the object rotates. And, because the matrix is in fixed-point, it
>suffers from a loss in precision. He tried to fix this by getting the 
>determinant of the matrix. Whenever it gets too large or too small, he divides
>all elements of the matrix by the determinant. However, this doesn't work:
>the elements of the matrix get out of proportion, resulting in a distorted view
>and (eventually) in a crash.
>Now, how is this to be solved? He could keep the three angles of the object,
>calculate the matrix from that, and change the angles whenever the object is
>rotated. This makes it hard to rotate the object about any axis other than
>x, y, z. Also, it is slow. So, are there any ways to repair the matrix quickly
>and efficiently?

>Hope you can solve this one...
>Bye, Hildo Biersma


I can't see why a 9x9 matrix is needed to hold the orientation. A
single 3 vector should suffice. If this is normalized and the 3x3
matrix you multiply it with to change the orientation has determinant
1, then the result should be normalized as well. You can compensate
for some of the worst effects of rounding errors by normalizing the
vector if its length is not close to 1. This will of course not
correct the error, but the result will always be a consistent
orientation vector. True normalization is expensive (as it requires a
square root), but if you just want to keep the length within, say 1%
of 1, you can multiply the length by 1.01 if it is below 0.99 and by
.99 if it is above 1.01.

16 bit fixed point numbers are rather small if you use them for
position in a 3D space game, but I guess they are sufficient (or even
overkill) for orientation. Of course, if you have a 16x16 -> 32 bit
multiply in hardware, that is a good reason to use 16 bit numbers ;-).

Here is an idea that can speed up your fixed point computations if you
use a relatively small number of bits, and have access to reasonable
amounts of RAM. You construct tables of log and exp for your numbers.
When you want to multiply, you take the log of both numbers, add these
and take the exp of the result. This takes 3 memory references and an
addition (plus some extra overhead if the numbers are signed).
Division is handles similarly, with subtraction instead of addition.
Square root is really good: two memory references and a single shift.

This method may be marginal for signed multiplication, but wins for
division and square root (unless you have these in hardware). The
tables are each 16 bit -> 16 bit, so use a total of 256K. This may be
much on some computers, but if you have around 1MB it should be
possible to fit this in. The precision is worse than doing the muls
and divs directly, but if speed is the important factor it may be an
advantage.

Also, you get log and exp for free (though you may have no need of
those).

	Torben Mogensen (torbenm@diku.dk)