Minsky Circle Algorithm. Generate sin and cos fast with only add, sub and shift.

2»

Comments

  • Heater.Heater. Posts: 21,213
    edited 2015-08-30 - 02:33:56
    More nerding out with numbers:

    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:
    0/0   1/0   2/0   3/0 
    0/1   1/1   2/1   3/1 
    0/2   1/2   2/2   3/2 
    0/3   1/3   2/3   3/3
    
    Which is:
    NaN   ∞     ∞     ∞
    0     1     2     3
    0     0.5   1     1.5
    0     0.33  0.66  1
    
    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.
  • Mark_T,
    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.
  • BeanBean Posts: 8,042
    edited 2016-01-03 - 04:08:56
    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.

    Bean
  • automaton3dautomaton3d Posts: 1
    edited 2019-09-04 - 22:39:17
    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?
Sign In or Register to comment.