This may be obvious but I had to scratch my head a bit over it. A radius of 4096 and a shift of 10 has to have 20 sides because:
After the shift we only have 2 bits left, so we can only move the current position by 0, 2, or 3 in x or y directions. We will ignore the negative directions.That means the possible gradients of the line segments can only be:
We can remove duplicates and "Not A Number" and we have these possible gradients:
∞
0 1 2 3
0.5 1.5
0.33 0.66
We can remove remove things that are nice multiples if a half: 1/2, 2/2 and 2. Leaving:
∞
0 3
1.5
0.33 0.66
The five different gradients 0, 0.33, 0.66, 1.5 and 3 are enough to get us a quarter of the way around the circle with equal length line segments.
Ergo we have to get a 20 sided polygon.
By a similar argument we see that a radius of 4096 has three bits to make adjustments in direction, 64 possible directions. 14 of them are used to get us around a quadrant for a 56 sided polygon. The sides are not all of equal length in this case.
I think this is now a footnote in the textbooks, Bressenhams (ie DDA) is a more general and flexible approach and doesn't risk accumulating errors.
I just noticed a little detail here. Your statement hints that there is a risk of accumulating errors with the Minsky Circle algorithm. Actually part of it's magic is that it is stable. You can run around that circle forever and it won't accumulate errors.
The Minsky circle algorithm is a modification of cordic.
If you use the temporary variable (which you should NOT do for Minsky) it IS cordic and the radius will grow by COS(step) per step. By not using the temporary variable causes the growth to be signed so over the whole circle it cancels.
The number of steps required for a whole circle is (2*PI)/ATAN(step) (assuming radians).
COS(step) of small steps is much smaller than larger steps. For example COS(step/32)*32 is much smaller than COS(step), smaller steps cause less gain even though there are more steps. This makes larger steps have much more gain which makes them more oblong.
I'm very interested in this wonderful algorithm. There is a case in which Bresenheim's cannot be used directly, while this gem comes in handy: Markovian generation of a circle or a quadrature signal, my research problem.
There are some issues however that I'm trying to understand and possibly fix in order to apply it to my work:
1) The radius is different from the initial cosine value;
2) A formula to calculate the shift amount from a power of two grid index;
3) The number of steps should be exactly twice cos(0);
4) A formula to calculate the eccentricity from the index above.
Could possibly some of these issues be attenuated in the approximation of large numbers?
Hi I came across this discussion while googling minsky circle, some very useful explanations thank you. I see mentioned here a few times about a good explanation of FFT by Heater. I'm searching for that discussion but can't seem to find it, anyone can supply a link to it please? FFT is something I been trying to wrap my brain around for awhile, so any simplified explanations will be extremely helpful
Welcome to the forums! You can type FFT into the search box in the upper right corner to get a few pages of suggestions. I have also attached "Fourier Transform For Dummies"
Wow that was soo crystal clear, I can honestly say I understood everything in that document(s) and now got a (almost complete) grasp on Fourier Transform
Just nitpicking... in the document the 3rd and 4th graphs showing phase of 45 degrees... unless my trigonometry is off but ain't that 90 degrees that is shown?!?
I know maybe this isn't the right thread to be asking these questions,
but since I have your attention here Bean...
Can you point me to an active link to your 'CORDIC for dummies' (which also I'm very interested in) please? Heater has given me link to a discussion of fourier for dummies and the first link is to your CORDIC explanantion which is broken... https://forums.parallax.com/discussion/127306/fourier-for-dummies-under-construction/p1
I'm sure it will be as enlightening as your Fourier expalantion, short sharp and to the point
Comments
This may be obvious but I had to scratch my head a bit over it. A radius of 4096 and a shift of 10 has to have 20 sides because:
After the shift we only have 2 bits left, so we can only move the current position by 0, 2, or 3 in x or y directions. We will ignore the negative directions.That means the possible gradients of the line segments can only be: Which is: We can remove duplicates and "Not A Number" and we have these possible gradients:
∞ 0 1 2 3 0.5 1.5 0.33 0.66We can remove remove things that are nice multiples if a half: 1/2, 2/2 and 2. Leaving:∞ 0 3 1.5 0.33 0.66The five different gradients 0, 0.33, 0.66, 1.5 and 3 are enough to get us a quarter of the way around the circle with equal length line segments.Ergo we have to get a 20 sided polygon.
By a similar argument we see that a radius of 4096 has three bits to make adjustments in direction, 64 possible directions. 14 of them are used to get us around a quadrant for a 56 sided polygon. The sides are not all of equal length in this case.
If you use the temporary variable (which you should NOT do for Minsky) it IS cordic and the radius will grow by COS(step) per step. By not using the temporary variable causes the growth to be signed so over the whole circle it cancels.
The number of steps required for a whole circle is (2*PI)/ATAN(step) (assuming radians).
COS(step) of small steps is much smaller than larger steps. For example COS(step/32)*32 is much smaller than COS(step), smaller steps cause less gain even though there are more steps. This makes larger steps have much more gain which makes them more oblong.
Bean
There are some issues however that I'm trying to understand and possibly fix in order to apply it to my work:
1) The radius is different from the initial cosine value;
2) A formula to calculate the shift amount from a power of two grid index;
3) The number of steps should be exactly twice cos(0);
4) A formula to calculate the eccentricity from the index above.
Could possibly some of these issues be attenuated in the approximation of large numbers?
Bean
Thanks Bean!
Just nitpicking... in the document the 3rd and 4th graphs showing phase of 45 degrees... unless my trigonometry is off but ain't that 90 degrees that is shown?!?
Thanks,
Bean
but since I have your attention here Bean...
Can you point me to an active link to your 'CORDIC for dummies' (which also I'm very interested in) please? Heater has given me link to a discussion of fourier for dummies and the first link is to your CORDIC explanantion which is broken...
https://forums.parallax.com/discussion/127306/fourier-for-dummies-under-construction/p1
I'm sure it will be as enlightening as your Fourier expalantion, short sharp and to the point