Subject: SUMMARY - roto-matrix -

From: <[email-masked]>
Date: Thu, 24 Oct 1996 10:17:44 GMT

Dear Netters,

	Here is the summary and the original message concerning
roto translations.
An easy solution to the problem is to use/look the quaternion-fit program
as suggested by David Heisterberg, while for theory I found all the other
contributions very interesting.

	Thank you very much for your help

-Alfonso

###############
Initial Posting
###############

Dear Netters,

	I would like to ask for an expertise about linear transformations
performed via rotational matrixes.

	Given the 3D coordinates of three points P1(xyz) P2(xyz) and P3(xyz)
in their initial (T0) and final (T1) position. Which is the best way
for calculating the rotational matrix and translation capable of such
transformation ? (distances between the three points are constants so we
can consider it "rigid" between each others)

	Any help and or information is very welcome and I will summarize
your contributions.

	Yours sincerely

	-Alfonso Pozzan

#############
   ANSWERS
#############

#####################
From:     Jan Reimers
#####################

Without the translation its a simple 3x3 system of equations.  Let p1, p2,p3
be the original 3 coordinate vectors and p1', p2' p3' be the transformed
vectors.  Then

[p1x' p2x' p3x']      [r11 r12 r13][p1x p2x p3x]
[p1y' p2y' p3y']   =  [r21 r22 r23][p1y p2y p3y]
[p1z' p2z' p3z']      [r31 r32 r33][p1z p2z p3z]

Or in matrix notation

p' = Rp

and so R = p' * inverse(p)

Note that R must be unitary if it is a rotation matrix.  In general R can
contain dialations as well, this is determined completely by your p and p'
vectors.

Now to add the translation you will need 1 more vector, and expand
to the problem to a 4x4 system

[p1x' . . p4x']     [      Tx] [p1x . . p4x]
[ .   . .  .  ]  =  [  R   Ty] [ .  . .  . ]
[ .   . .  .  ]     [      Tz] [ .  . .  . ]
[ 1   1 1  1  ]     [0 0 0 1 ] [ 1  1 1  1 ]

Now solve the 4x4 system to get R and T.

Hope this helps

+--------------------------------------+-------------------------------------+
| Jan N. Reimers,  Research Scientist  | Sorry, Don't have time to write the |
| Moli Energy (1990) Ltd. B.C. Canada  | usual clever stuff in this spot.    |
| [email-masked]                |                                     |
+--------------------------------------+-------------------------------------+

#########################
From:     Dr Mark J Biggs
#########################

Hi Alfonso,
	for transformation matricies around axes or a vector, you
can refer to most "robotics" texts, also texts for "computer graphics".

A good book is "Mathematical Elements for Computer Graphics" by Rogers
and Adams (McGraw Hill, 1976) but most have this sort of thing in. A'
another book is Introduction to computing with geometry by Bowyer and
Woodwark (Information Geometers, 1993).

Hope this helps

Mark

#############################
From:     Dr Malcolm E Parker
#############################

Hi
   If T0 and T1 are the original and final 3*3 co-ordinate matrices and R is
your transformation (in this case rotation) matrix then it is the following
least squares calculation is required:-

   if T0 * R = T1

 then      R = (T0t * T0)**-1 * T0t * T1

 where T0t is the transpose of T0. The inverse of the covariance matrix can be
calculated via NAG routine or probably numerical recipes. Good luck.

--

Dr Malcolm Parker               | email: [email-masked]
Department of Chemistry,        | www:   http://www.chem.surrey.ac.uk/~chs1mp
University of Surrey,           |
Guildford, Surrey. GU2 5XH. UK. | Tel: (01483) 300800x2580  Fax: (01483) 259514
                                |(International calls replace 01483 by +44 1483)

#######################
From:     Konrad Hinsen
#######################

First of all, there is no unique answer. There are infinitely many
combinations of rotation and translation that will do the job. The
rotations differ in the point around which you rotate, but not in
axis and amount.

A convenient choice is to define the translation by the difference
between the centers of mass (if you have no masses, take the centre of
volume). Then the rotation will be around an axis passing through this
centre of mass. All three displacement vectors must be perpendicular
to this axis, and that is sufficient information to find its direction
(Take the cross product of two non-equal displacement vectors. If all
three are equal, then your three points are on a line which is
parallel to the axis). After that, finding the angle of rotation
is a simple trigonometric problem, which however I will not attempt
to solve this late in the day...
--
-------------------------------------------------------------------------------
Konrad Hinsen                          | E-Mail: [email-masked]
Laboratoire de Dynamique Moleculaire   | Tel.: +33-76.88.99.28
Institut de Biologie Structurale       | Fax:  +33-76.88.54.94
41, av. des Martyrs                    | Deutsch/Esperanto/English/
38027 Grenoble Cedex 1, France         | Nederlands/Francais
-------------------------------------------------------------------------------
##########################
From:    David Heisterberg
##########################

Look on the ccl archives for fitest (Fortran) or quaternion-fit (C).
Of course for three points this method probably isn't optimal, but
it's very robust and will give you essentially the exact rotation
matrix.  If you do want the best way, that's pretty easy.  Just
translate T1 so that the centroid is the same as for T0, rotate
T1 so that the P1s are coincident, then rotate about P1 to match
up P2 and P3.  For the initial rotation to match P1, find the
cross product of P1 in the initial and final configuration and
use that as the axis of rotation.

Dave Heisterberg

>>>>>>>>>>>>Alfonso Pozzan Ph.D, GlaxoWellcome
e-mail: [email-masked], fax: +39-45-9218196
via Fleming 2, 37100 Verona ITALY <<<<<<<<<<<<