[A83] Re: Faster Multiplication
[Prev][Next][Index][Thread]
[A83] Re: Faster Multiplication
This is true. I forgot O(n^3) is only for square matrices, which isn't the
case here, where there's a 1x3 matrix/vector and a 3x3 matrix. The formulas
given aren't less than accurate -- but they will degrade the points because
of rounding errors. The same problem doesn't exactly happen if you rotate
another way -- in this case the rounding errors will show up in the angles
instead, which isn't nearly as detrimental to the look of the game. The
matrix method should be faster, which it is slightly (multiplications are
traded for additions), since all the matrices have been premultiplied into a
single one.
My point generally speaking was that projecting a point is not the main cost
of 3D graphics. Even with the 98 tstate multiplication routine, rotating
each point will probably require ~2000 tstates, and in most realistic games
(where there are objects besides the central one), each point will most
likely be rotated twice. Thus the cost of the rotation is reasonably larger
than the cost of projecting the point. Notably, however, the greatest cost
involves in actually drawing the graphics to the screen. A 3D program that
simply displayed the points as dots rather than connected or filled would
run rather quickly.
-----Original Message-----
From: assembly-83-bounce@lists.ticalc.org
[mailto:assembly-83-bounce@lists.ticalc.org]On Behalf Of Patrick
Davidson
Sent: Thursday, May 31, 2001 5:08 PM
To: assembly-83@lists.ticalc.org
Subject: [A83] Re: Faster Multiplication
The O(n^3) may appear frightening, but consider what n refers to. In the
context of matrix multiplication, this would be the size of the matrix.
However, if the rotation matrix is always 3x3 (or always 4x4) then this is
a constant, so I might as well say that each rotation required O(1)
multiplications which doesn't seem nearly as bad.
I also don't see why you consider the formulas given as being less
accurate, since each step is actually mathematically equivalent to
multiplying by the rotation matrix for that axis. Then again, since you
are referring to degeneration "after a while" I might guess you were
talking about what would happen if the results of doing the rotation where
written over the original coordinates, but then again, the same problem
could happen if you rotated another way.
The thing that really seems strange to me, however, is why you would need
to use matrix multiplication in any case. Even though the rotation matrix
is a matrix, points are usually vectors, so multiplying a point by your
rotation matrix would not be the multiplication of two matrices, but
instead of a matrix and a vector, requiring n^2 multiplications which is
in O(n^2) in the dimension of the matrix and vector (of course, you could
consider a vector to be an n by 1 matrix, but that doesn't change the
running time).
For these reasons, it actually seems that rotating a point using a
rotation matrix should take only 9 multiplications (which incidentally
would be better than the other method posted if using 3 axes, since it
would take 12 in this case).
References: