peterl@ibmpcug.co.uk (Peter Leaback) (01/03/90)
[this message has been re-posted because it did not reach some sites] At the moment,I define my rotations as a 3x3 matrix containing 16 bit fixed point numbers from 1 to -1. The problem I face is that after a few thousand rotations,the errors that occur in combining rotations has malformed the matrix. In fact, the matrix then becomes a scaling matrix and reduces the size of the rotated object. What I require is some method of keeping the errors from amplifying. I have been told there are methods of reconstructing rotation matrices. But I have also been told that reconstructing a rotation matrix is costly in processor time,so microcomputer flight simulators that use this method can only afford to reconstruct the rotation matrix every 500 or 1000 rotations. This method is undesirable because at the point where reconstruction of the matrix occurs, the object visibly jolts back into shape. What I would prefer (and some flight simulators use) is a method that after every rotation the matrix is nudged back into shape. I did think of using a method where the rotation is defined as x,y,z degrees from the axes. This would mean that any errors that occur would only affect the angles through which to rotate and NOT malform into any other geometrical transformation. The problem with this data structure is that combining two rotations defined as x,y,z degrees is very costly on processor power and requires 2 divisions. *ANY* comments on how to solve my problem would be greatly appreciated. Regards,Pete Leaback. -- Automatic Disclaimer: The views expressed above are those of the author alone and may not represent the views of the IBM PC User Group.
MA.JOE@forsythe.stanford.edu (Joe Bayus) (01/04/90)
REGARDING: peterl@ibmpcug.co.uk (Peter Leaback)
Errors in rotations
Peter, here are some comments, from an admitted novice in the field:
1. Might try displaying at less resolution - then 500/1000
reconstruct might not be visible, as errors are below level of
resolution. (might be possible to increase size of matrix
cells from 16-bit to 24 ????).
2. Might try calculating rate of distortion & when it becomes visible
(via tracing and sampling) (e.g., every n rotations). Then, re-
construct every n-1 rotations ( this is really a variation of 1.,
above).
3. Might also take distortion into account, designing reduced-
perspective (object farther away) occurrences to coincide with
object movements, and reconstructing when jumps might be credible
("hyperspace" leaps, for example). This might be cute, but
doesn't really solve your problem, does it?
4. Might try maintaining a "read-only" copy of the matrix, to which
cumulative rotation calculations are applied to produce the
displayed image (as an oversimplified example, 5 object rotations
are done currently as follows:
Mat 1 -> rotation1 -> Mat 2 -> display
Mat 2 -> rotation2 -> Mat 3 -> display
Mat 3 -> rotation3 -> Mat 4 -> display
Mat 4 -> rotation4 -> Mat 5 -> display
Mat 5 -> rotation5 -> Mat 6 -> display
Instead, you might try something like:
"read-only" Mat -> rot1 -> display Mat -> display
"read-only" Mat -> rot1 + rot2 -> display Mat -> display
etc.,
Probably you would then have to "refresh" the read-only Mat to be
equal to the display Mat every so often, so that the number of
"rotN + rot(N+1)" items can be "started over", to prevent
"animation slow-down" . This should reduce the distortion errors
to accumulate only at the "refresh" rate. You'd have to play with
this, I think, to tune for optimum speed vs image-integrity.
If the rotation formulae are functional (e.g., logarithmic,
hyperbolic, parabolic, etc.), you may not have to actually add
"rotN" items, instead pulling them iteratively from a function
table - you MIGHT(?) be able to do this anyway, if you know all
the moves that will be made (good luck for a billion-move game!!)
and you have LOTS of memory to play with and a good algorithm for
placing entries in the table.
Hope this is useful...these are novitiate comments by all accounts !!wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) (01/04/90)
In article <1990Jan2.163405.24094@ibmpcug.co.uk> peterl@ibmpcug.co.uk (Peter Leaback) writes: > >At the moment,I define my rotations as a 3x3 matrix containing 16 bit >fixed point numbers from 1 to -1. The problem I face is that after a few >thousand rotations,the errors that occur in combining rotations has >malformed the matrix. In fact, the matrix then becomes a scaling matrix >and reduces the size of the rotated object. One of the graphics texts (either F&vD or N&S) mentions in 2D perturbing the matrix so that its determinant is exactly 1 before applying it. At this point it's not exactly a rotation matrix but apparently that's less important than a non one det, since that is a scaling. My idea would be to have a sequence of rotation matrices for bigger and bigger angles, that is a matrix for t, 5t, 9t, etc. Then after compounding the t matrix 4 times, apply the 5t matrix to the original data, then apply the t matrix to that result several times, etc. This shouldn't be too expensive and if done right, there would be no visible jumps. Another method would be to rotate in a different coordinate system, such as one with the axis of rotation the Z axis. Here the errors would accumulate more slowly. After compounding the rotations transform to the desired coordinate system. This means you would apply two matrices for each rotation. -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180
brian@hpfcdj.HP.COM (Brian Rauchfuss) (01/04/90)
One method which would eliminate scaling would be to use quaternions.
Quaternions are a compact form of representing rotations, and they combine
easily and faster than matrixes. They *only* represent rotations, so any math
errors after a few thousand rotations would not create any weird scaling
problems. You would combine the rotation quaternion with the viewing matrix
before drawing.
"Quaternion Calculus as a Basic Tool in Computer Graphics", Daniel Pletinckx
The Visual Computer 5:2-13, (1989)
"Animating Rotation with Quaternion Curves", Ken Shoemake
ACM 0-89791-166-0/85/007/0245
----------------------------------------------------------------------
Brian Smokefoot "... never knowing I could shape my life
brian@hpfcbdr.HP.COM like the artist paints his dreams
on a canvas." - Minor Detailoj@apollo.HP.COM (Ellis Oliver Jones) (01/05/90)
In article <1990Jan2.163405.24094@ibmpcug.co.uk> peterl@ibmpcug.co.uk (Peter Leaback) writes: >...I define my rotations as a 3x3 matrix containing 16 bit >fixed point numbers from 1 to -1. ... after a few >thousand rotations,the errors that occur in combining rotations has >malformed the matrix.... I faced this problem some years ago on an E&S Picture System II. I used a compromise solution (hack) as follows. (1) The rotation matrix was kept separate, and was not composed with translation or perspective matrices. (2) A good rotation matrix (as opposed to a malformed one) is unitary. This means that its determinant is one, obviously, but it also means that each of the rows taken by itself is a unit vector. Ditto for the columns. (3) Every nth rotation cycle (1<n<20, empirically determined), perform a normalization step. Adjust the rotation matrix such that each of the rows or columns, considered separately, are unit vectors. This works well if you alternate between rows and columns in successive normalization steps. If you just normalize columns (or just rows) the rotation will deteriorate into a skew. In practice the alternation prevents this deterioration. (4) The implementation of the normalization step was carefully coded, using integer multiplies and a decent integer Newton-Raphson-method square root. See earlier postings in this newsgroup for some ideas. /Ollie Jones (speaking for myself, not necessarily for HP Apollo, nor for UCSF's computer graphics lab, where I worked when I did this).
robert@victoria.esd.sgi.com (Robert Skinner) (01/06/90)
In article <47d784ba.20b6d@apollo.HP.COM>, oj@apollo.HP.COM (Ellis Oliver Jones) writes: > I faced this problem some years ago on an E&S Picture System II. > I used a compromise solution (hack) as follows. > (1) The rotation matrix was kept separate, and was not composed > with translation or perspective matrices. > (2) A good rotation matrix (as opposed to a malformed one) is > unitary. This means that its determinant is one, obviously, > but it also means that each of the rows taken by itself > is a unit vector. Ditto for the columns. > (3) Every nth rotation cycle (1<n<20, empirically determined), > perform a normalization step. Adjust the rotation matrix > such that each of the rows or columns, considered separately, > are unit vectors. This works well if you alternate > between rows and columns in successive normalization > steps. If you just normalize columns (or just rows) > the rotation will deteriorate into a skew. In practice > the alternation prevents this deterioration. > (4) The implementation of the normalization step was > carefully coded, using integer multiplies and > a decent integer Newton-Raphson-method square root. > See earlier postings in this newsgroup for some ideas. > > /Ollie Jones (speaking for myself, not necessarily for HP Apollo, nor for UCSF's > computer graphics lab, where I worked when I did this). Ollie is correct on (1), (2), and (4), but step (3) depends on luck for the corrections applied to rows to correctly cancel out the corrections applied to columns. Remember that rotation matrices are not only unitary, but are also orthogonal -- which means that each row (column) vector is orthogonal to all other row (column) vectors. You can use this fact to get a correct rotation matrix without switching between rows and columns. Here's how: starting with the first row vector (which I will call X, because this is what a unit vector on the X axis gets transformed into), normalize it to obtain X'. Then obtain the correct Z direction by finding the cross product of X' and Y and normalizing: Z' = norm( X' x Y ) Now you can find the correct Y by using the cross product again: Y' = Z' x X' (no need to normalize, because X' and Z' are unit length and orthogonal). The matrix is now a real rotation matrix, unitary and orthonormal. You still need a fast square-root for the normalization. Of course, this sort of assumes that X is correct each time. You could start with Y or Z other times, but my guess is that you probably won't notice any difference in sticking with X first, because the matrix is now correct. Robert Skinner robert@sgi.com
peterl@ibmpcug.co.uk (Peter Leaback) (01/06/90)
[this message has been resent because of CONTUNUEING problems at my end] Many thanks to everyone who has replied by mail and here. I think the most promising method i will follow up is a mixture of Quaternions and normal rotations. If i define my rotations as a Qaternion this poses another problem for me, that of movement.I would need to extract something approaching a direction vector from the Quaternion. This was simple with a rotation matrix because i would just pick up the Z vector of the matrix and multiply this with the speed to get the velocity. The Z vector of the matrix can be found from a Quaternion but this requires 6 multiplications which invalidates the speed advantage of Quaternions. Would it be possible to use the vector part of the Quaterion as the direction vector of the object ? Peter Leaback. -- Automatic Disclaimer: The views expressed above are those of the author alone and may not represent the views of the IBM PC User Group.