6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) (11/22/90)
Ok. ok ok ok ok. .. Have you seen these hacker demos where the balls or whatever follow sinusoidal paths around the screen? And where there are HUNDREDS of balls all going very smoothly through what appear to be complex hypo-cycloids and such? My question is how these paths are computed. The number of objects and their speed incidates that they aren't being done by floating-point techniques, and i'm pretty sure the numbers are not pre-calculated, so it seems that smooth curves like the sin and cos can be done using integer (native MC68000) arithmatic. Is this so? Does anybody out there know what these algorythms are? Am i posting in the wrong area? And why hasn't my mouse come home? For the answers to these questions and more, please write me so i may learn. -- 6600mage@ucsbuxa.ucsb.edu ## These are ## Secrets of ################################### Melodious Monk
mclaren (Gavin McLaren) (11/22/90)
In article <7336@hub.ucsb.edu> 6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) writes: > .. Have you seen these hacker demos where >the balls or whatever follow sinusoidal paths around >the screen? And where there are HUNDREDS of balls >all going very smoothly through what appear to be >complex hypo-cycloids and such? >My question is how these paths are computed. The >number of objects and their speed incidates that >they aren't being done by floating-point techniques, >and i'm pretty sure the numbers are not >pre-calculated, so it seems that smooth curves like >the sin and cos can be done using integer (native >MC68000) arithmatic. Well, I can't speak for the second example, with hypo-cycloid path, but the standard balls demos don't have to involve trig functions at all. These demos start with a ball(s) at the bottom of the screen. Then, the position relative to the screen bottom is calculated using the formula y = (ay * t * t)/2 + vy * t + ystart t is the iteration number, which increases at a specified interval. ay is initial acceleration vy is initial velocity. ystart is the initial position Now acceleration is a constant, as is the initial position. These demos provide the illusion of random motion by resetting the equation (t = 0) and giving a random upward velocity when the position == ystart (or is below ystart) There is also horizontal morement, usually calculated as x = (ax * t * t) / 2 + vx * t + xstart ax is usually zero, since gravity does not intuitively operate sideways. judicious selection of the constants can even obviate the need to convert the results back into screen coordinates. IE. make ystart the bottom of the screen, positive acceleration, negative initial velocity. Of cource, enhancements allow balls to either bounce off of the sides of the screen, or wrap around. Some algorithms convert the equations into incremental additions, which has to keep track of current position and velocity and incrementally change both every iteration. This saves multiplications and operates faster (but there are more errors in cumulative roundoff). Now the bad news is that I don't know for sure. The two equations could be rewritten for polar coordinates, and thus use sines and cosines, but I'm not sure this would be a good use of anyone's time. :) --Gavin McLaren ...!uunet!van-bc!mdivax1!mclaren
hebrais@olivier.IRO.UMontreal.CA (Philippe Hebrais) (11/23/90)
In article <7336@hub.ucsb.edu> 6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) writes: > .. Have you seen these hacker demos where >the balls or whatever follow sinusoidal paths around >the screen? And where there are HUNDREDS of balls >all going very smoothly through what appear to be >complex hypo-cycloids and such? >My question is how these paths are computed. The >number of objects and their speed incidates that >they aren't being done by floating-point techniques, >and i'm pretty sure the numbers are not >pre-calculated, so it seems that smooth curves like >the sin and cos can be done using integer (native >MC68000) arithmatic. Hmmm, seems to me you could just evaluate the Taylor series for sine and cos in fixed point arithmetic. And also wouldn'it be faster to compute the pair (sine, cosine) than to compute sine and then cosine. sin(x) = 1 - (x^2)/2! + (x^4)/4! - (x^6)/6! + ...+ (-1)^k*(x^(2k))/(2k)! cos(x) = x - (x^3)/3! + (x^5)/5! - (x^7)/7! + ...+ (-1)^k*(x^(2k+1))/(2k+1)! Also, don't forget that all the balls follow the same trajectory so you need only worry with the "lead" ball. (off course, "x^n" means "x" to the power of "n" and "5!" is "1*2*3*4*5", that is "n!" is "n factorial") -- Philippe Hebrais hebrais@IRO.UMontreal.CA phil@MirkWood.CAM.ORG FREE CANADA uunet!philmtl!iros1!phaze!mirkwood!phil TRADE MULRONEY Voice: 514-731-9146
paasivir@tukki.jyu.fi (Risto Paasivirta) (11/23/90)
> >and i'm pretty sure the numbers are not > >pre-calculated, so it seems that smooth curves like > >the sin and cos can be done using integer (native > >MC68000) arithmatic. > >Hmmm, seems to me you could just evaluate the Taylor series >for sine and cos in fixed point arithmetic... Just create table of sine values. Table of 1024 values is a plenty for 16-bit maths. Keep things simple, if you want to keep things fast... paasivir@jyu.fi -- Bus error (core dumped)
gilmore@macc.wisc.edu (11/23/90)
In article <HEBRAIS.90Nov23024202@olivier.IRO.UMontreal.CA>, hebrais@olivier.IRO.UMontreal.CA (Philippe Hebrais) writes... > In article <7336@hub.ucsb.edu> 6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) writes: > >My question is how these paths are computed. The > >number of objects and their speed incidates that > >they aren't being done by floating-point techniques, > >and i'm pretty sure the numbers are not > >pre-calculated, so it seems that smooth curves like > >the sin and cos can be done using integer (native > >MC68000) arithmatic. If you use pre-calculated values for sine and cosine, it doesn't take up much space, and speeds things up considerably. As well, if the number of possible positions is 200, it only takes 200 * 2 (x and y) * 2 (bytes per word) 800 bytes, which isn't all that much, and speeds up even more. I know guys who never use the sin and cos, they just use a .1 degree table for the functions, as even in floating-point, the size of the table is dwarfed by the extra junk that X adds on....
jcs@crash.cts.com (John Schultz) (11/24/90)
In <HEBRAIS.90Nov23024202@olivier.IRO.UMontreal.CA> hebrais@olivier.IRO.UMontreal.CA (Philippe Hebrais) writes: > In article <7336@hub.ucsb.edu> 6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) writes: [stuff deleted about real-time sin's and cos's, motion paths] >Hmmm, seems to me you could just evaluate the Taylor series >for sine and cos in fixed point arithmetic. And also wouldn'it be >faster to compute the pair (sine, cosine) than to compute sine and >then cosine. >sin(x) = 1 - (x^2)/2! + (x^4)/4! - (x^6)/6! + ...+ (-1)^k*(x^(2k))/(2k)! >cos(x) = x - (x^3)/3! + (x^5)/5! - (x^7)/7! + ...+ (-1)^k*(x^(2k+1))/(2k+1)! >Also, don't forget that all the balls follow the same trajectory so you need >only worry with the "lead" ball. >(off course, "x^n" means "x" to the power of "n" and "5!" is "1*2*3*4*5", >that is "n!" is "n factorial") Hey, mon, ya don't need tah do thot! Precompute sin and cos in a table for 2pi (360 deg, one rev, etc). The index increment depends on how many pseudodegrees you have in your numbering system. If you want to save space at the expense of a little time, you only need to compute one quadrant, and can get the other three with symmetry. Further, you don't need to even compute the whole quadrant- intermediate values can be interpolated. This technique is known as "look-up and interpolate" and is described in the book "Microcomputers, Displays, Graphics, and Animation" by Bruce Artwick. The motion paths of those objects could easily by tabled. All values would not be stored, just deltas (doesn't take much space). John
jap@convex.cl.msu.edu (Joe Porkka) (11/24/90)
hebrais@olivier.IRO.UMontreal.CA (Philippe Hebrais) writes: > In article <7336@hub.ucsb.edu> 6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) writes: > > .. Have you seen these hacker demos where > >the balls or whatever follow sinusoidal paths around > >the screen? And where there are HUNDREDS of balls > >all going very smoothly through what appear to be > >complex hypo-cycloids and such? > >My question is how these paths are computed. The > >number of objects and their speed incidates that > >they aren't being done by floating-point techniques, > >and i'm pretty sure the numbers are not > >pre-calculated, so it seems that smooth curves like > >the sin and cos can be done using integer (native > >MC68000) arithmatic. I wrote aturtle graphics hack in assembly language once - it used SIN and COS for dealing with angles. How? Lookup tables and 16bit fixed point math. (32bit math with the faction point in the middle.) The lookup tables dont need to be big. I needed one decimal point of precision (i.e. ###.#) and worked with degrees (though you could do it with radians). So, 0.0 - 359.9 sounds like about 3600 32bit constants times two for each SIN and COS - right? Nope - I think I only used one 1800 32bit entry table and used that fact that SIN and COS look a lot alike, and things like sinx = -sin(360-x)
static@phoenix.pub.uu.oz.au (geoff c wing) (11/26/90)
In <7336@hub.ucsb.edu> 6600mage@ucsbuxa.ucsb.edu (Orion Wilson the Passable) writes: > .. Have you seen these hacker demos where >the balls or whatever follow sinusoidal paths around >the screen? And where there are HUNDREDS of balls ^^^^^^^^^^ It depends on the size of the "balls", and how many planes. Most I've seen is 240 or so, 16*11(?)*2bp "balls". >all going very smoothly through what appear to be >complex hypo-cycloids and such? >My question is how these paths are computed. The >number of objects and their speed incidates that >they aren't being done by floating-point techniques, Don't do it with FFP. It takes way too long. Since you have to recalculate every frame and redraw(use the blitter), you can only calculate about 30 points. >and i'm pretty sure the numbers are not >pre-calculated, so it seems that smooth curves like >the sin and cos can be done using integer (native >MC68000) arithmatic. > > Is this so? Does anybody out there know what >these algorythms are? Am i posting in the wrong >area? And why hasn't my mouse come home? > For the answers to these questions and more, > please write me so i may learn. Do you want to start up a new newsgroup - "amiga.teachme68k" ? Here's some code for a 3d rotation. The blitter line drawing routine can be found on pages 163-165 of Abacus' "Amiga System Programmer's Guide" or you could easily find someone to tell you. I've used the code below for a filled vector graphic demo(still not yet released though). I can't find many other ways to optimize the code(with respect to speed,not size). I assume you know about swapping which planes are being displayed(eg.work on one, display other). Don't use rubbish like the Taylor series to work out angles. People who recommend it have been studying Mathematics too long and obviously don't code much. You don't need to change the base positions. Just use pointers to places within the sine table. Well, actually, this is untrue for some routines, and some other nice effects(of course), like merging from one shape to another. You'll need to do a bit more work to get the nice hyperboloid effects, but we wouldn't want you to get there too easily. Put some effort it. Anyway here's some text I wrote a while back: ANGLETABLE: 360 Sine words stored multiplied by 32767. All cosine angles are sin(angle+90degrees). One pair for each angle stored here. eg. 0.8386 is [(8386*32767)/10000] = 27478 ($6b56) -0.4324 is [(-4324*32767)/10000] = -14168 ($c8a8) They are thus used : (see rotation example at end) A0: pointer to angle table D1: offset of angle move.w number,d0 muls (a0,d1.w),d0 lsr.l #8,d0 lsr.l #7,d0 bclr #16,d0 ; often unnecessary D0: now contains integer position Storage: blk.w 360,0 Angles : 91 words (for sine angles 0-90 degrees). All other angles in the angletable can be made from these, so leave block storage at end. ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** dc.l $0000023b,$047706b2,$08ed0b27,$0d610f99 ; 0 - 7 dc.l $11d01405,$1639186c,$1a9c1cca,$1ef72120 ; 8 - 15 dc.l $2347256c,$278d29ab,$2bc62dde,$2ff23203 ; 16 - 23 dc.l $340f3617,$381c3a1b,$3c173e0d,$3fff41ec ; 24 - 31 dc.l $43d345b6,$4793496a,$4b3b4d07,$4ecd508c ; 32 - 39 dc.l $524653f9,$55a5574b,$58e95a81,$5c125d9c ; 40 - 47 dc.l $5f1e6099,$620c6378,$64dc6638,$678d68d9 ; 48 - 55 dc.l $6a1d6b58,$6c8b6db6,$6ed96ff2,$7103720b ; 56 - 63 dc.l $730a7400,$74ee75d2,$76ad777e,$78467905 ; 64 - 71 dc.l $79bb7a67,$7b097ba2,$7c317cb7,$7d327da4 ; 72 - 79 dc.l $7e0d7e6b,$7ec07f0a,$7f4b7f82,$7faf7fd2 ; 80 - 87 dc.l $7feb7ffa,$7fff0000 ; 88 - 90 ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** THREE DIMENSIONAL ROTATION -------------------------- (x,y,z) must be rotated with matrices (in any order) : |cos -sin 0||x| |cos 0 -sin||x| |1 0 0 ||x| |sin cos 0||y| | 0 1 0 ||y| |0 cos -sin||y| | 0 0 1||z| |sin 0 cos||z| |0 sin cos||z| however this can be done with the standard rotation matrix A : A =|cos -sin| A|x| A|x| A|y| NB. Make sure the correct |sin cos| |y| |z| |z| angle is used each time. ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** A0: pointer to angle table A1: x position A2: y position A3: z position D0-D2/D4-D7: work ROTATION: -getangle(d6,d7) ; D6: sine offset about Z axis move.w a1,d4 ; D7: cosine offset about Z axis move.w a2,d5 bsr.S MATRIX move.w d0,a1 move.w d1,a2 -getangle(d6,d7) ; D6: sine offset about Y axis move.w a1,d4 ; D7: cosine offset about Y axis move.w a3,d5 bsr.S MATRIX move.w d0,a1 move.w d1,a3 -getangle(d6,d7) ; D6: sine offset about X axis move.w a2,d4 ; D7: cosine offset about X axis move.w a3,d5 bsr.S MATRIX move.w d0,a2 move.w d0,a3 ...... ...... rts MATRIX: move.w d4,d0 muls (a0,d7.w),d0 lsr.l #8,d0 add.l #64,d0 (round off properly-remove if unnecessary) lsr.l #7,d0 move.w d5,d1 muls (a0,d6.w),d1 lsr.l #8,d1 add.l #64,d1 (round off properly-remove if unnecessary) lsr.l #7,d1 sub.w d1,d0 move.w d4,d1 muls (a0,d6.w),d1 lsr.l #8,d1 add.l #64,d1 (round off properly-remove if unnecessary) lsr.l #7,d1 move.w d5,d2 muls (a0,d7.w),d2 lsr.l #8,d2 add.l #64,d2 (round off properly-remove if unnecessary) lsr.l #7,d2 add.w d2,d1 rts ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** -- +---------------------------------+ _ _ _ _ __ | Geoff //| /\ |\/| | / _ /\ | static@phoenix.pub.uu.oz.au \X/ | //\\ | | _|_ \__| //\\ +---------------------------------+
wuethri@ifi.unizh.ch (11/29/90)
In article <1990Nov23.175553.15606@msuinfo.cl.msu.edu> jap@convex.cl.msu.edu (Joe Porkka) writes: >hebrais@olivier.IRO.UMontreal.CA (Philippe Hebrais) writes: > >So, 0.0 - 359.9 sounds like about 3600 32bit constants >times two for each SIN and COS - right? Nope - I think >I only used one 1800 32bit entry table and used that >fact that SIN and COS look a lot alike, and things >like sinx = -sin(360-x) Not to forget that the symmetries are many more, in fact you need to store only sine values from 0 to 90 degrees (1/4 of the sinus periodic range, which is from 0 t0 360), as sin(x)=-sin(360-x), and sin(90-x)=sin(90+x) and sin(270-x)=sin(270+x). Greetings Charles -- Charles Wuethrich, Dept. of Computer Science | wuethri@ifi.unizh.ch Univ. of Zurich, 8057 Zurich-Irchel, Switzerland | k114910@czhrzu1a.bitnet