It is currently Mon Oct 15, 2018 1:58 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 24 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Fri Dec 29, 2017 6:08 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2757
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)) / 2

So 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.


Top
 Profile  
 
PostPosted: Fri Dec 29, 2017 6:19 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6874
Location: Canada
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.


Top
 Profile  
 
PostPosted: Sat Dec 30, 2017 11:20 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2757
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


Top
 Profile  
 
PostPosted: Sun Jan 07, 2018 10:47 am 
Offline

Joined: Wed Jul 30, 2008 12:03 am
Posts: 34
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.


Top
 Profile  
 
PostPosted: Sun Jan 07, 2018 11:39 pm 
Offline
User avatar

Joined: Mon Feb 07, 2011 12:46 pm
Posts: 1017
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.

_________________
.


Top
 Profile  
 
PostPosted: Mon Jan 08, 2018 7:01 am 
Offline

Joined: Mon May 25, 2009 2:20 pm
Posts: 64
https://pastebin.com/tFdQj6VC

here'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 originally

I 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 :(


Top
 Profile  
 
PostPosted: Mon Jan 08, 2018 3:47 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6874
Location: Canada
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.


Attachments:
minsky_test.zip [546 Bytes]
Downloaded 39 times
Top
 Profile  
 
PostPosted: Mon Jan 08, 2018 7:41 pm 
Offline

Joined: Wed Jul 30, 2008 12:03 am
Posts: 34
rainwarrior wrote:
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.



Some discussion here (HACKMEM in html)


Top
 Profile  
 
PostPosted: Sun Jan 14, 2018 6:18 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2757
Here's a similar question. Has anybody ever did a sine*amplitude thing on an SNES without using the mode 7 registers?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 24 posts ]  Go to page Previous  1, 2

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group