Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!diamond!ihaka
From: ihaka@diamond.tmc.edu (Ross Ihaka)
Newsgroups: comp.graphics
Subject: Re: 3-D Rotation Algorithm
Keywords: fixed-point log-base-2
Message-ID: <15026@bloom-beacon.MIT.EDU>
Date: 11 Oct 89 13:31:56 GMT
References: <6734@hubcap.clemson.edu>
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: ihaka@dolphin.mit.edu (Ross Ihaka)
Organization: MIT Statistics Center
Lines: 45

In article <6734@hubcap.clemson.edu> bo@hubcap.clemson.edu (Bo Slaughter) writes:
|
|
|I have written a program in Turbo Pascal to take a simple line drawing
|and rotate in any of the 3 demensions. The "drawing" consists of a
|series of lines with X,Y,Z coordinates, which my program then can rotate
|using the simple formula (and variations thereof):
|
|  X'=X*cos(THETA)-Y*sin(THETA)
|  Y'=X*sin(THETA)+Y*cos(THETA) 
|
|My problem is that this is extremely slow for any medium sized drawing
|(32 points took over a second).  Does anyone know of, or have, an
|algorithm that could do the same calculations, without all the mucking
|about with slow foating point calculations (No, I don't have a math
|coprocessor).
|

Here is a trick you can use to get fast rotations when the angle is small.
It uses integers to represent floats in [0,1], you can scale the problem
this way easily.

Approximation for sin(theta) and cos(theta)

	sin(theta) ~ theta
	cos(theta) ~ 1 - theta^2 / 2

The rotation is then given by

	x' = x * (1-theta^2/2) - y * theta
	y' = x * theta + y * (1 - theta^2 /2 )

The trick is to choose theta to be a (negative) power of 2.  Then
you can do the multiplications by shifting.  [In C code]

	l2theta = ...	/* some small integer (eg 5) */
	sgn = ...	/* 1 or -1 */
	other = 1+2*l2theta;
	...
	xnew = x - (x>>other) - sgn * (y>>l2theta);
	ynew = sgn * (x>>l2theta) + y - (y>>other);

You can do rotation through larger angles as a product of these small
rotations and maybe doing the obvious for things like pi/4 etc.
	Ross Ihaka