nesdev.comhttp://forums.nesdev.com/ How to describe a circle trajectory on nes?http://forums.nesdev.com/viewtopic.php?f=2&t=16867 Page 2 of 2

 Author: psycopathicteen [ Fri Dec 29, 2017 6:08 pm ] Post subject: Re: How to describe a circle trajectory on nes? I was responding to your above post.Quote:Yes, it's due to the family of identities that relate multiplication to sum and difference, e.g.:cos(a) * cos(b) = (cos(a+b) + cos(a-b)) / 2So if you have a cosine/sine table, you can get the multiplied result with a few sums, a few lookups, and a shift. Each step loses some precision, yes. I've half-written an NES demo experimenting with this concept but I haven't gotten around to finishing it yet.1024 angle steps gives you no gaps in amplitude for 8-bit values.

 Author: rainwarrior [ Fri Dec 29, 2017 6:19 pm ] Post subject: Re: How to describe a circle trajectory on nes? psycopathicteen wrote:1024 angle steps gives you no gaps in amplitude for 8-bit values.Oh, well the precision of your angle is one thing, and the precision of the sine/cosine result is another, and both of them have a bearing on how precise things are. Being able to represent every integer output value is not sufficient to make it completely precise (to that output grandularity). So, 1024 steps is more accurate than 256, but there's lots of precision lost from the 8-bit output quantization too, so you'd also get improvements from making the output wider too. There's not really a clear break point to me for precision, it's a big pile of tradeoffs.MartsINY wrote:In real life, I would simply use sinus for the first unknown, then pythagore for the second one.From the way you described this, might be worth pointing out that cos(x) = sin(x+90°) so if you have sine you have cosine available as well. If it's a table lookup, one table does both.

 Author: psycopathicteen [ Sat Dec 30, 2017 11:20 pm ] Post subject: Re: How to describe a circle trajectory on nes? This has some nice multiplication algorithms. It uses some self modifying code, so you might want to change abs,x to (dp),y for it to run on the NES.http://codebase64.org/doku.php?id=base: ... iplication

 Author: bogax [ Sun Jan 07, 2018 10:47 am ] Post subject: Re: How to describe a circle trajectory on nes? Here's code (6502.org) for a simple parabolic approximation of a sine wave.If you run two instances 90 degrees apart that will give you something like a circle.Of course, it's incremental not random access.There's an example here (AtariAge) in Batari Basic.

 Author: zzo38 [ Sun Jan 07, 2018 11:39 pm ] Post subject: Re: How to describe a circle trajectory on nes? One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:Code:for(;;) {  y-=epsilon*x;  x+=epsilon*y;  plot(x,y);}The value epsilon is less than one. If it is 1/256 then you do not need to implement multiplication/division; you can just use the carrying (you do not even need bit shifting). Note that these coordinates are signed numbers, which complicates the implementation a bit.

 Author: kuja killer [ Mon Jan 08, 2018 7:01 am ] Post subject: Re: How to describe a circle trajectory on nes? https://pastebin.com/tFdQj6VChere's a really interesting file from Puresabe, ..from rockman 4 minus infinity, which i've been able to implement into my game.I only had to change the raw hex numbers on a couple of the JSR's, and stuff, to match the megaman 3 versions, and then it worked like a charm.This is the un-edited rockman 4 minus infinity file i gotten from him originallyI do not really understand how this works, but it can do circles very "butter smooth" though ..oh yea, it uses the MMC5's multiply registers 5205/5206 though. (not shown here)comments are in japanese though..sorry

Author:  rainwarrior [ Mon Jan 08, 2018 3:47 pm ]
Post subject:  Re: How to describe a circle trajectory on nes?

zzo38 wrote:
One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:
Code:
for(;;) {
y-=epsilon*x;
x+=epsilon*y;
plot(x,y);
}

The value epsilon is less than one. If it is 1/256 then you do not need to implement multiplication/division; you can just use the carrying (you do not even need bit shifting). Note that these coordinates are signed numbers, which complicates the implementation a bit.

This is very interesting!

It seems that as epsilon gets larger, it becomes more elliptical, diagonally oblong. As epsilon gets smaller it becomes more circular.

At first glance it seems similar to just rotating a 2D point, which is one of the "normal" ways to produce a circle:
Code:
ox = x;
oy = y;
a = cos(angle); // constant
b = sin(angle); // constant
x = a * ox - b * oy;
y = b * ox + a * oy;

But in your Minsky example only has one multiply, not two, and the way the Y update feeds back into the X update instead of using a temporary value makes the actual result kinda complicated to analyze. I feel like each iteration does like half of an approximation of the rotation somehow?

The speed of the rotation is dependent on epsilon, so probably you're limited to power-of-2-ish factors for epsilon unless you want a full generic multiply, but it does appear to be quite stable (I was testing it with 8.8 fixed point) and easy to control the radius because it stays on the circle you start X/Y on!

I wrote a simple processing sketch to test it, attached below. Click the mouse to pick a starting point for X/Y, and press A/Z to adjust epsilon.