Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!gem.mps.ohio-state.edu!apple!voder!pyramid!versatc.VERSATEC.COM!ritter
From: ritter@versatc.VERSATEC.COM (Jack Ritter)
Newsgroups: comp.graphics
Subject: Re: 3-D Rotation Algorithm
Summary: Accurate rotation with integer arith.
Message-ID: <19634@versatc.VERSATEC.COM>
Date: 11 Oct 89 21:12:59 GMT
References: <6734@hubcap.clemson.edu>
Organization: Versatec, Santa Clara, Ca. 95051
Lines: 57

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
> 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).
> 
If you want to rotate pts by a variety of angles,
then you can Table-It-To-Death:

	Do calculations in FIRST quadrant. Pick a gradation
	of thetas, let's say 90 (eg, can rotate any # of degrees).

	Then you generate (at COMPILE time) a table of
	16 bit integer values, of the form: sin*SCALE.
	 For 16 bit values, SCALE should be 16384 (2**14).

	 table[i] would be set to: sin(i*RADFAC) * 16384
			for (i=0; i<90; i++).

		(RADFAC converts from degrees to radians).
	table[90] must be 16384. This means table[] has 91 entries.

	 To rotate (x,y) by th degrees, compute the 4 values
	x*cos, y*cos, x*sin, y*sin by this technique:

	coord*sin(th) = coord*table[th] >> 14
		  &
	coord*cos(th) = coord*table[90-th] >> 14

Then do the adds/subs. The "table[th]*coord"
should be an INTEGER multiply, creating a 32 bit
number, which will be shifted back down to 16 bits by the >>.
(On an 8 bit machine, use 2**7).
This transformation uses NO floating pt arith.

This is for angles of 0-90 degrees. The other 3 quadrants
can be calculated with the same table[] by using reflection
and/or transposition (which are well known).

If you sucessively accumulate theta, you need to WRAP AROUND
from 360 degrees -> 0. If you use 128 gradations instead
of 90, wrap-around is very simple: 
			new_theta &= 511. 
	This works for + OR - delta_thetas.
----------------------------------------------
-- 
	      ->  B O Y C O T T    E X X O N    <-
   Jack Ritter, S/W Eng. Versatec, 2710 Walsh Av, Santa Clara, CA 95051
   Mail Stop 1-7.  (408)982-4332, or (408)988-2800 X 5743
   UUCP:  {ames,apple,sun,pyramid}!versatc!ritter