SOLVED! Need another set of eyes: Polygon draw algorithm

(mods please don’t move this to “displays” since it IS a programming problem…)

Hi all,

I’m trying to incorporate a polygon drawing function into my VFD graphic display driver.

It works, but it’s not perfect. The problem is that some X,Y coordinates for a vertex are off by one, so that sometimes what SHOULD be a straight vertical or horizontal line has a slight “jink” to it. (see attached snapshot).

I’m sure it’s some kind of a rounding problem, but I’ll be darned if I can find it.

One thing I do (you’ll see in the attached code below) is to take the desired rotation angle of the polygon and subtract 90.0 degrees from it in order to make 0 degrees “straight up” (i.e. the 12:00 o’clock position). Larger rotation angles rotate the polygon CLOCKWISE.

OK, so here’s the code:

// draw a polygon of any number of sides, rotated by any "angle"
// note angle "0" degrees is straight up (i.e. a triangle is
// drawn like this:    /\
//                    /__\
// and the angle goes clockwise so that an angle of 90 degrees
// points the apex to the 3:00 o'clock position.
void Noritake_GUU100::drawPolygon (uint8_t x, uint8_t y, uint8_t radius, uint8_t sides, double angle, uint8_t on)
{
    uint8_t x1, y1, x2, y2;
    double th, inc;

    if (sides < 3) { // polygon must be at least 3 sides!
        return;
    }

    if (sides > 31) { // too many sides is slow and just makes a circle anyway...
        drawCircle (x, y, radius, on);
    }

    // we work in radians here
    th = rad (angle - 90.0); // make 0 degrees straight up
    inc = (2.0 * M_PI / sides); // radians to next vertex

    x2 = round (cos (th) * radius + x); // get first vertex
    y2 = round (sin (th) * radius + y);

    while (sides--) {

        x1 = x2; // old vertex is...
        y1 = y2; // ...the new startpoint

        th += inc; // angle of next vertex in radians

        x2 = round (cos (th) * radius + x); // get next vertex
        y2 = round (sin (th) * radius + y);

        drawLine (x1, y1, x2, y2, on); // draw side
    }
}

(click pic for higher res)
vfd.jpg

Any ideas will be greatly appreciated.

The problem is in

th += inc;

robtillaart: The problem is in

th += inc;

Could you elaborate?

Note that what I'm trying to do is set "th" to the rotation angle specified which becomes the first vertex.

Then I copy it to X1,X2, increment the angle (in radians) to the next vertex, then simply draw a line from X1, Y1 to X2, Y2 until all sides are done.

What is the mistake in [b]"th += inc"[/b]?

robtillaart: The problem is in

th += inc;

Let me add that at some angles, I do not have the problem. For example, specifying "0" degrees makes the second side (the bottom of the triangle) straight, but then 360 degrees (which is the same as 0) makes it jagged.

Or, if I rotate the triangle 90 degrees so that the flat "bottom" points to the left, then other angles (like +90 or -270) make a jagged edge.

I can't pin it down to problem "only with negative angles" or "only with positive angles".

When I additionally print the X1, Y1, X2, Y2 values at run time for each side, I'll see something like this:

[b]X1:  88, Y1:   0, X2: 115, Y2:  47 
X1: 115, [color=red]Y1:  47[/color], X2:  61, [color=red]Y2:  46[/color] 
X1:  61, Y1:  46, X2:  88, Y2:   0 

[/b]

Notice that for the second side (the bottom of the triangle) Y1 and Y2 differ by 1 (causing the jagged line). Notice also that for the second line, X2, Y2 is copied into X1, Y1, defining the start of the second side.

The first side is defined outside the loop (the very first X2= and Y2= lines).

I'm sure it's a rounding problem of some sort, but I've been beating my head against the wall for 3 days now and aspirin no longer helps.......

try this variation

void Noritake_GUU100::drawPolygon (uint8_t x, uint8_t y, uint8_t radius, uint8_t sides, double angle, uint8_t on)
{
  uint8_t x1, y1, x2, y2;
  double th, startAngle;

  if (sides < 3) { // polygon must be at least 3 sides!
    return;
  }

  if (sides > 31) { // too many sides is slow and just makes a circle anyway...
    drawCircle (x, y, radius, on);
  }

  // we work in radians here
  startAngle = PI / 180 * (angle - 90.0); // make 0 degrees straight up
  th = startAngle;
  x2 = x + round (cos (th) * radius); // get first vertex
  y2 = y + round (sin (th) * radius);

  for (uint8_t i = 1; i <= sides; i++)
  {
    // Serial.print(x2);
    // Serial.print("\t");
    // Serial.print(y2);
    // Serial.print("\t");
    // Serial.println(th, 7);

    x1 = x2; // old vertex is...
    y1 = y2; // ...the new startpoint
    th = startAngle + (i * TWO_PI) / sides ; // angle of next vertex in radians
    x2 = x + round (cos(th) * radius); // get next vertex
    y2 = y + round (sin(th) * radius);

    drawLine (x1, y1, x2, y2, on); // draw side
  }
  // Serial.print(x2);
  // Serial.print("\t");
  // Serial.print(y2);
  // Serial.print("\t");
  // Serial.println(th, 7);
}

th += inc;

adds up the errors (sides times)

th = startAngle + (i * TWO_PI) / sides;

does not add up errors


y2 = round (sin(th) * radius + y);
has 6 floating point operations

  • sin()
  • and 2 times the implicit uint8_t → float
  • round

y2 = y + round (sin(th) * radius);
has 4 floating point operations

  • sin()
  • and 1x implicit uint8_t → float
  • round

and floating point operations should be minimized.

check also - https://www.mathsisfun.com/geometry/regular-polygons.html

slightly faster version

void Noritake_GUU100::drawPolygon (uint8_t x, uint8_t y, uint8_t radius, uint8_t sides, double angle, uint8_t on)
{
  uint8_t x1, y1, x2, y2;
  double th, delta, startAngle;

  if (sides < 3) { // polygon must be at least 3 sides!
    return;
  }

  if (sides > 31) { // too many sides is slow and just makes a circle anyway...
    drawCircle (x, y, radius, on);
  }

  // we work in radians here
  startAngle = PI / 180 * (angle - 90.0); // make 0 degrees straight up
  delta = TWO_PI / sides;
  th = startAngle;
  x2 = x + round (cos (th) * radius); // get first vertex
  y2 = y + round (sin (th) * radius);

  for (uint8_t i = 1; i <= sides; i++)
  {
    // Serial.print(x2);
    // Serial.print("\t");
    // Serial.print(y2);
    // Serial.print("\t");
    // Serial.println(th, 7);

    x1 = x2; // old vertex is...
    y1 = y2; // ...the new startpoint
    th = startAngle + i * delta;
    x2 = x + round (cos(th) * radius);
    y2 = y + round (sin(th) * radius);

    drawLine (x1, y1, x2, y2, on); // draw side
  }
  // Serial.print(x2);
  // Serial.print("\t");
  // Serial.print(y2);
  // Serial.print("\t");
  // Serial.println(th, 7);
}

for faster sin() and cos() you could interpolate lookup tables
see - http://forum.arduino.cc/index.php?topic=69723.0 -

robtillaart: check also - https://www.mathsisfun.com/geometry/regular-polygons.html

OK, I see what you did there. When I defined "inc(rement)", it wasn't exact, and by simply adding it over and over again, the errors added up.

Re-calculating it each time around (along with REMOVING the round () statements) made it work perfectly.

Now, any angle and any radius draws a perfect polygon. I can tell it's right because a polygon with a large number of sides (like 16) draws almost a circle, but with a few artifacts. At 0 degrees, the artifacts are symmetrical left and right (where before they were not).

You solved it for me... the problem is so obvious and the solution so simple I can't believe I didn't see it before.

By the way, you mentioned fast sin and cos using lookup tables. I actually tried that... I made a table of 90 signed ints (16 bit signed) ranging from +32767 to -32768.

Only 90 are needed because a sine curve is mirror image from 0 to 89, 90 to 179 degrees, and again mirror image (but inverted) for 180 to 269 and 270 to 359, and cosine is simply sin (angle + 90) (degrees), so 90 entries define it all.

Unfortunately, 90 ints take up 180 bytes of PROGMEM (which really is no problem), but I found that the speed gain, although "good", is not "amazing" and to me not worth the extra storage and code. Probably because I need to scale the +/- 32K number to -1 to +1 (that probably consumes the time).

Anyway, THANK YOU for your input. You solved my problem!

(and Karma++ for you as well!)

Thanks once again! -- Roger

robtillaart:
check also - Regular Polygons - Properties

Interesting thing… a long time ago I found that the “while (x–)” loop is faster than the “for x=1; x<zzz; x++” loop, so I wanted to use that so I re-did your code to use “while (sides–)”. It works, and to see how it draws I put a _delay_ms (100) into the “setdot” part of “drawline”.

When using a for loop, it draws clockwise. For example, a triangle at 0 degrees (apex up) draws like this:

[b]    A
[tt]     /\
   /  \
C /____\

B
[/b][/tt]

[b]A-->B, B-->C, C-->A
[/b]

But with a while loop, it draws like this!

[b]A-->C, C-->B, B-->A
[/b]

…and it’s a bit faster (about 6500 microseconds for a 3 sided triangle, 31 pixel radius using for/x++ and about 4900 microseconds for a while (x–) loop).

Regardless, the whole thing is quite a bit faster with the way you re-arranged the code to minimize floating point calculations.

Thanks again!

This is an issue with the fact the sin(30) is exactly 0.5. With an even radius value there wouldn't be an issue, with a pentagon there wouldn't be an issue - only things with 30 degrees cropping up and odd integral radii will trip over this little gotcha:

the 30 degree (or 150 degree) angles cause sin to return 0.5 (plus or minus floating point errors). Thus it might be 0.499997 or 0.5000004 or suchlike. Thus rounding these values is sensitive to the rounding errors in the implementation of sine.

Try printing 31 * sin (30*PI/180)

the while(x--) loop does compare with zero which is automatically done when a register is loaded.

for (x++) needs to compare with the endvalue, which is in fact a subtraction followed by a compare with zero.

That's why the while(x--) is faster.

You can see that if you rewrite the for loop to

for (int i=sides; i> 0; i--);

We can make the polygon a bit faster still. The origin is calculated twice.
reusing the original value (at the price of 2 bytes and some code) results in this.

Can you measure the performance gain? (you need to copy it in your version)

I expect about 250 uSec as it does 1x sin() and 1x cos() less

void Noritake_GUU100::drawPolygon (uint8_t x, uint8_t y, uint8_t radius, uint8_t sides, double angle, uint8_t on)
{
  uint8_t x1, y1, x2, y2, ox, oy;
  double th, delta, startAngle;

  if (sides < 3) 
  { // polygon must be at least 3 sides!
    return;
  }

  if (sides > 31) { // too many sides is slow and just makes a circle anyway...
    drawCircle (x, y, radius, on);
    return;
  }

  // we work in radians here
  startAngle = PI / 180 * (angle - 90.0); // make 0 degrees straight up
  delta = TWO_PI / sides;
  th = startAngle;
  ox = x1 = x + round (cos (th) * radius); // get first vertex
  oy = y1 = y + round (sin (th) * radius);

  for (uint8_t i = 1; i < sides; i++)
  {
    th = startAngle + i * delta;               // change + in - to change CW <-> CCW
    x2 = x + round (cos(th) * radius);
    y2 = y + round (sin(th) * radius);
    drawLine (x1, y1, x2, y2, on);             // draw side

    x1 = x2; // old vertex is...
    y1 = y2; // ...the new startpoint
  }
  drawLine (x1, y1, ox, oy, on);

}

if (sides > 31) needs a return after the drawCircle()
by the way a polygon with 2 sides becomes a line, 1 side would be a dot.

BTW do you use Bresenham for Circle and Line?

robtillaart: We can make the polygon a bit faster still. The origin is calculated twice. reusing the original value (at the price of 2 bytes and some code) results in this.

Can you measure the performance gain? (you need to copy it in your version)

BTW do you use Bresenham for Circle and Line?

I'll compare the current code to your latest iteration and see what happens.

BTW, yes I do use Bresenham's algorithm for lines and circles (rectangles too!) :)

I have pounded my head against a wall for a couple of hours with this routine. It is great at drawing a triangle, which I what I need but it puts the triangle center at the x,y point. I want the apex of the equilateral triangle at the x,y point and the rest of the points lowered the same amount. For some reason these routines always give me almost infinite trouble. Please, someone tell me how to put the apex at the x,y position, not the center of the triangle.

I am using this (slightly modified) routine, from above, just to be clear. My angle is already rotated so the 90º shift is removed. I think the rest is stock.

I tried taking out the “* radius” code on the lines starting with ox and oy and that put the apex at x,y but then the triangle was too short. The opposite sides were too short relative to the hypotenuse.

Thanks for any help on this. I am sure it is dead simple but I just cannot hit on the right change. Mike

/*********************************************************/
void drawPolygon3 (uint8_t x, uint8_t y, uint8_t radius, uint8_t sides, double angle)
/*********************************************************/
{
 uint8_t x1, y1, x2, y2, ox, oy;
 double th, delta, startAngle;
//  if (sides < 3) return;  // Polygon must be at least 3 sides!
//  if (sides > 31) {       // Too many sides is slow and just makes a circle anyway...
//    display.drawCircle (x, y, radius); return;
//  }
//We work in radians here.  None of those easy to use degrees, thank you!  Thank who?!?!?
 startAngle = PI / 180 * angle; // make 0 degrees straight up
 delta = TWO_PI / sides;
 th = startAngle;
 ox = x1 = x + round (cos(startAngle) * radius); // get first vertex
 oy = y1 = y + round (sin(startAngle) * radius);
 for (uint8_t i = 1; i < sides; i++)
 {
   th = startAngle + i * delta;               // Change "+" to "-" to change CW <-> CCW
   x2 = x + round (cos(th) * radius);
   y2 = y + round (sin(th) * radius);
   display.drawLine (x1, y1, x2, y2);         // Draw a side
   x1 = x2; // old vertex is...
   y1 = y2; // ...the new startpoint
 }
 display.drawLine (x1, y1, ox, oy);
}