Hi
I just started coding on my good ol' friend, c64 again.
I'm trying to code a simple 2d routine using precalulated sin and cos tables. Since multiplication routines are far to slow for my taste, I've used an old method that was common back in the days, but unfortunately lacked accuracy.

the standard formula for rotating a 2d (x,y) co-ordinate around an origin by a certain angle goes something like..

x = oldx * cos(angle) - oldy * sin(angle)
y = oldx * sin(angle) + oldy * cos(angle)

..as most of us know by now ;)

the old routine i mentioned converted all multiplications to divisions.

sin(45) = 0,7
1 / 0,7 = 1,4 ; since we're going to use div instead of multi.

now.. we had to convert it so it could easily be divided by a single LSR
1,4 would turn in to 1.. so.. (55 would turn into 64 and so on)

x = oldx / 1 - oldy / 1
y = oldx / 1 + oldy / 1

we're still cursed dealing with signed numbers but hey, div by LSR is far less speed consuming than any multiplication routines. :) but as I mentioned before we're bound to falter into the problem of accuracy. so I'm wondering if you guys got any better ideas? I remember that someone once talked about a routine that only used additions and subtractions together with tables, but since I'm no math pro I can't figure it out :P any help would be appreciated.


Cheers
Undo

_________________
I need to find
Something to blame for a long lost time

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

thanks for the insight. :)

Well since speed is a priority over accuracy, I won't be using floating point routines at all. If I convert all floating points in the tables to integers using the following method I get a little loss in accuracy but not really that much.

ex.
0,52 * 64 = 33,28 (33 when we round off)

..64 is dividable easily using LSR 6 times and leaves pretty good accuracy. so just divide the final result of the eq with 64 et voila :) no nasty floating points. Since It's graphics I'm dealing with, to many 16bit variables would take far to much cycles away from me if I want a reasonably high framerate. So I'll be using 8bit as much as possible.

Oh.. I found a very interesting link..
http://www.catalase.com/optrot3d.htm

It's a fast 3d transform method for the 68000.. the last example on the page is one using only add and sub. I have to admit, I'm no math professor and I haven't even studied trig in school. (We simply didn't have that here in Sweden were I went :P) I've learned pretty much everything on my own. So I'm a little bit confused about the whole idea he's introducing. so once again any help would be appreciated :P

Cheers
Undo

_________________
I need to find
Something to blame for a long lost time

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

True it will be a low resolution but since the graphic "screen" I'll be using is only 31*31 vpixels ('vpixel = 4*4 real pixels) 8 bits should be enough.

I got around 11592cycles left per frame to do calculations and other stuff for the rotation and there's around 961 pixels to calculate, that would allow around 603cycles per individual pixel/frame. Though we have to keep in mind that those 603 cycles includes converting, calculating and moving the pixels to the right location in a non-linear array. A framerate of 3-5fps would be nice.

In any way I would need to do atleast 4 (possibly even 5) signed multiplications per pixel, and that would take far to much time :/ If I'd narrow it down to 4 divisions and 1 possible multiplication then I'm left with the great loss of accuracy. Surely there's got be another way using a tad more memory and make the whole process move faster.

_________________
I need to find
Something to blame for a long lost time

Hi Garth,

> As far as using only addition and subtraction, there is a way to get a
> square root this way, but it's extreeeeeemely slow

Without using tables it's the fastest method I know of calculating roots.
See....

http://www.6502.org/source/integers/root.htm

... for an integer 6502 coded example.

A very similar routine is used in EhBASIC to calculate the 24 bit floating
point root and is better than eight times faster than the standard Microsoft 6502 BASIC root routine.

Lee.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Hi Garth,

> Don't blink or you'll miss it. This one handles inputs from 1 to
> $8002. Put the input in a 2-byte variable INPUT, and the output
> comes out as a single byte in ROOT.

Not quite, it's only faster for values up to 7.5 bits and that can be
done much quicker with a lookup table. For the high limit of your
routine it's over 15 times slower.

> When I clicked "Preview", all the spaces added for readability
> disappeared. Someone please tell me what I need to do to get
> monospacing for pieces of code like this!

I tried inserting [TAB] characters but that doesn't work either.

Lee.

Everyone,


Here's how you can format your text. Type it in as you want it to be displayed. When done, Select all of the text by holding down your mouse button while dragging over the text. Now click the "CODE" button above.

Here's an example of Garth's code:




As far as the math goes, I've done some 2D and 3D conversions...I'll try to dig some of the code up and see if it would help.

Daryl

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Thanks for the advice Daryl on how to get the intentional spaces in code to stay. I edited my post above. The forum software still wouldn't do exactly what I wanted, but hopefully some more experimentation will do the trick.

Garth

Undo,

Can you elaborate more on what you will be doing? Will your rotations always be around the center of your 31x31 display? Will there be a fixed shape in it ( or maybe just a few)? What will be the minimum/maximum angle of rotation per display update?

I have done some 2D & 3D coding in the past and found tables of data to be the best way as far as speed goes, depending upon the data being processed.

If you are rotating around the center point of your display, then there are several short-cuts available in using pre-calculated lookup tables.

I'd be glad to help if you can help to describe the application!

Daryl

:)



Yeah, the rotation will always be around the center of the 31x31 "screen". The whole 31x31 (961 pixels) image shall be rotated, I guess you could call it some sort of "bitmap rotation". The angle? around 10 deg. (10, 20, 30 and so on ;)

I agree that tables are by far the fastest way to do rotations in a case like this, the problem is finding a nifty method avoiding cycle-eaters like multiplication routines and such. any ideas?

thanks
Undo

_________________
I need to find
Something to blame for a long lost time

I think I can give you a method using look-up tables and no multiplication/division if you can afford about 6k for the tables & code.

The basic idea is pre-calculate the new x,y position from the old one for each pixel. Since you are rotating about the center, you only have to calculate one quarter of the screen. The other three will be the same offsets, they'll just have different signs. Since you will be limiting the angles to 10,20,30, ect, only 8 tables would be needed. Each table will hold 2 bytes for each of the 256 pixels in the first quadrant (the new x and new y). This method will also eliminate the need to check to see if a pixel was rotated "off the screen".

Let me know if this method sounds practical.

Daryl

Thanks Daryl.
I'm not quite sure how much memory I'll be able to spare but 6kb is quite a nice price to pay for such great speed.

I'll try to fiddle some with the idea later tonight..

_________________
I need to find
Something to blame for a long lost time