bo@hubcap.clemson.edu (Bo Slaughter) (10/11/89)
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). Thanks, Bo Slaughter
ihaka@diamond.tmc.edu (Ross Ihaka) (10/11/89)
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
ritter@versatc.VERSATEC.COM (Jack Ritter) (10/12/89)
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
miller@cam.nist.gov (Bruce Miller) (10/12/89)
In article <15026@bloom-beacon.MIT.EDU>, ihaka@diamond.tmc.edu (Ross Ihaka) writes: > 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. ... > |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 > > Here is a trick you can use to get fast rotations when the angle is small. > Approximation for sin(theta) and cos(theta) > sin(theta) ~ theta > cos(theta) ~ 1 - theta^2 / 2 > ... > xnew = x - (x>>other) - sgn * (y>>l2theta); > ynew = sgn * (x>>l2theta) + y - (y>>other); > Ross Ihaka Forgive me if I'm on the wrong track; no insult intended. If you are calling sine & cosine for *each* point you transform, that is where your problem is. The rotation angles, and hence the sines & cosines of them, are the same for all the points you want to transform, so you should just compute them once and use them many times. On the other hand, if you *have* saved the trig values then your only savings by using the suggested algorithm is that you halve the number of multiplications. But repeating the process for non-infinitesimal angles is likely to eat into the savings, [never mind the fact that repeated applications is actually a spiral and not a rotation... well formally, anyway :)] So, i dont think you gain much for this application, for others definitely. Why dont you go a step further and look up homogeneous transformations in most graphics texts; they are a bit tedious to construct initially, but you can combine all the rotations, translations & scale into one. Bruce
brown@ncratl.Atlanta.NCR.COM (Kyle Brown) (10/12/89)
Another trick that you may try (I've done this myself often for animation) is to pre-calculate the values of sine and consine for some set of thetas and do a table lookup when you do your rotation. This may or may not work, depending on what you're doing. While I have everyone's attention - Does anyone have C code or an algorithm to generate a fractal image called a Koch snowflake? I've been trying to hack one out myself but my geometry is not up to it. ------------------------------------------------------------------- "Earth - Mostly Harmless." The Hitchikers Guide to the Galaxy brown@ncratl.atlanta.ncr.com
brian@hpfcdj.HP.COM (Brian Rauchfuss) (10/12/89)
What you can do is come up with a table of sines and cosines (remembering that sin(x)=cos(x+90), so only one table is required) and then use linear interpolation between table entries to get exact values. This eliminates the slow sin and cos functions, but still uses some floating point. Brian Rauchfuss
Kenneth.Maier@p3.f11.n369.z1.FIDONET.ORG (Kenneth Maier) (10/14/89)
In an article of <12 Oct 89 12:46:25 GMT>, brown@ncratl.Atlanta.NCR.COM (Kyle Brown) writes: > >While I have everyone's attention - Does anyone have C code or an >algorithm to generate a fractal image called a Koch snowflake? I've >been trying to hack one out myself but my geometry is not up to it. Kyle, I would recommend _The_Science_of_Fractal_Images_ or another book called _FRACTAL_Programming_in_C_ -- both of these tell you how to do what you want. The first book provides general algorithms for fractal related topics including the Koch snowflake. The second book actually contains source that can run on PC's for most of the stuff mentioned in The Science of Fractal Images. Here is a little more info on the above books: The Science of Fractal Images, by Heinz-Otto Peitgen and Dietmar Saupe ISBN 0-387-96608-0 ISBN 3-540-96608-0 FRACTAL Programming in C, by Roger T. Stevens ISBN 1-55851-037-0 Hope this helps! -Kenneth -- Kenneth Maier via FidoNet node 1:369/11 UUCP: {attctc,<internet>!mthvax}!ankh,novavax!branch!11.3!Kenneth.Maier
mark.williston@canremote.uucp (MARK WILLISTON) (10/16/89)
Bo: I do not program in pascal at all, sorry, but I have dabbled a bit in 3d with Turbo C. It should be easy to transform what I have done into pascal. This idea was inspired after reading the book: Microcomputer Displays, Graphics & Animation by Bruce A. Artwick ISBN 0-13-580226-1 01 Very well writen, having many ideas in the graphics area. What I have done with this tidbit of code is rotate objects in 3-D with out using any floating points at all. building the shiftwise table uses floats but this matrix can be hardwired into the program. Code will follow in next message. Let me know how you make out! Mark Williston --- * QDeLuxe 1.10 #3694 <\/>ark </\>illiston - Author of 2-Bit Poker [EGA]
mark.williston@canremote.uucp (MARK WILLISTON) (10/16/89)
int x, y, z, xa, ya, za, angle;
double d, r, convert=3.141593/180;
int Sin[360], Cos[360];
void rot(void)
{
int t;
t = ((Cos[xa]*x)>>8)-((Sin[xa]*z)>>8); /* Rotate around the X Axis */
z = ((Sin[xa]*x)>>8)+((Cos[xa]*z)>>8);
x = t;
t = ((Cos[ya]*y)>>8)+((Sin[ya]*z)>>8); /* Rotate around the Y Axis */
z =-((Sin[ya]*y)>>8)+((Cos[ya]*z)>>8);
y = t;
t = ((Cos[za]*x)>>8)+((Sin[za]*y)>>8); /* Rotate around the Z Axis */
y =-((Sin[za]*x)>>8)+((Cos[za]*y)>>8);
x = t;
}
void main(void)
{
Call_Set_Vid_Mode( Your_Mode );
for(angle=0; angle<360; angle++) /* table of shiftwise degs */
{
r=(double)angle*convert;
Cos[angle]=(int)(cos(r)*256);
Sin[angle]=(int)(sin(r)*256);
}
while(you_want_to_rotate_points)
{
x=xval; /* fill x from somewhere! */
y=yval; /* fill y from somewhere! */
z=zval; /* fill z from somewhere! */
/*
With this pseudodegree method, x, y and z
must not overflow the integer. This works
well with small numbers. Using long ints
would give a larger capacity.
*/
rot(); /* rotate them */
x+=screen_centre; /* bring the point into view */
y+=screen_centre; /* bring the point into view */
CallYourPlot(x,y,color);
}
Mark Williston
---
* QDeLuxe 1.10 #3694 <\/>ark </\>illiston - Author of 2-Bit Poker [EGA]