Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-winken!lll-lcc!pyramid!leadsv!kallaus
From: kallaus@leadsv.UUCP (Jerry Kallaus)
Newsgroups: comp.graphics
Subject: Re: 3D Rotations/Instancing
Message-ID: <5941@leadsv.UUCP>
Date: 1 Feb 89 03:21:42 GMT
References: <65@sdcc10.ucsd.EDU> <5909@leadsv.UUCP> <25598@sgi.SGI.COM>
Distribution: usa
Organization: LMSC-LEADS, Sunnyvale, Ca.
Lines: 59

> In article <5909@leadsv.UUCP>, kallaus@leadsv.UUCP (Jerry Kallaus) writes:
    (Jerry demonstrates an incredible lack of math talent.)
> In article <25598@sgi.SGI.COM>, andru@rhialto.SGI.COM (Andrew Myers) writes:
    (Andrew notices this.)

Thanks to Andrew Myers for pointing out errors in my previous posting in
this thread.  They really were gross.  I abandoned that approach, and offer
the following obsersvation.

A well known iterative method for improving the estimate of the inverse
of a matrix is as follows (the n and n+1 refer to the iteration step).
If the matrix Bn is an estimate of the inverse of the matrix A,
then   A Bn - I = E ,  and if the norm of E < 1 , the following:

    Bn+1 = Bn ( 2I - A Bn )         ( 1 )
converges quadratically as per
    A Bn+1 = I - E**2
to the correct inverse.

The original problem was the orthonormalization of a rigid body rotation
matrix which contained errors due to frequent updating.
If the matrix A is a rigid body rotational transformation matrix, then
    A* A = I   and   A A* = I     ( where * denotes transpose ).
In other words, the transpose of A is the inverse of A.  If we have such
a matrix, only contaminated with errors, we could consider using
equation (1) to find the inverse of the contaminated matrix, using the
transpose of the contaminated matrix as the intial estimate for Bn.
However, this would only give us the inverse of the contaminated matrix,
and if this result were iterated through equation (1) again, we would
simply bounce back to the original A* (approximately).  Presumably, after
a single iteration of (1) the differences in the elements of
A and A-* (A inverse transpose) are small enough to make some linearity
assumptions.  The following is an intuitive supposition (and possibly
quite wrong); a math derivation evades me.

It seems to me that the approximation to the desired
(nearest to A in some sense) orthonormal matrix is half way between A and A-*.
If so, then the two could be averaged, or from (1):

       Bn+1 = Bn  + Bn - Bn A Bn
showing the step update delta as    Bn - Bn A Bn .
Using half of this step size and replacing Bn with  An*  provides

       An+1*  = (1/2) An* ( 3I - A An* )         ( 2 )

Showing that there are basically two matrix multiplies involved.
Depending on the accuracy with which rotational matrices
are being updated, only one iteration of (2) would probably be
needed per 10 to 1000 rotation updates.

Once again, the above is only an intuitive derivation, and sometimes
my intuition takes a hike.  Unfortunately, I don't have time to
try it.
-- Jerry
-- 
Jerry Kallaus         {pyramid.arpa,ucbvax!sun!suncal}leadsv!kallaus
(408)742-4569
     "Funny, how just when you think life can't possibly get
      any worse, it suddenly does." - Douglas Adams