Add draw arc procedure.

[olikraus]

Discussed in #1740

^{Originally posted by AndreZinoviev December 30, 2021}
Hi.
Happy New Year, everyone!!!
Is it possible to draw an arc of any size? How can I do that?
If there is no such function, is it possible to integrate such a function into your library?
I guess it should be like this:
void U8G2::drawArc(u8g2_uint_t x0, u8g2_uint_t y0, u8g2_uint_t rad, u8g2_uint_t line width, u8g2_uint_t starting angle, u8g2_uint_t end angle)

[olikraus]

@motla :

Hello!

I had the same feature request, so implemented the Andres circle algorithm, which I adapted to include arc features.

This algorithm is quite effective, as it sets each pixel only once, and can run with no floating points and no trigonometric function (in this case an approximation for the number of pixels drawn has to be made, so the arc edge can be noisy on large arc widths/radius: it can be annoying for some use cases, but if you make an animated spinner it is ok...)

I made a JavaScript version so you can test it and see for yourself here: https://motla.github.io/arc-algorithm/

C implementation for u8g2

It is just a proposal.

u8g2_arc.h

#ifndef U8G2_ARC_H
#define U8G2_ARC_H

#include "u8g2.h"

typedef float (*u8g2_atan2f_t)(float, float);

void u8g2_DrawArc(u8g2_t *u8g2, u8g2_uint_t x0, u8g2_uint_t y0, u8g2_uint_t rad_in, u8g2_uint_t rad_out, u8g2_uint_t angle_start, u8g2_uint_t angle_end, u8g2_atan2f_t atan2f_func);

#endif // U8G2_ARC_H

u8g2_arc.c

#include "u8g2_arc.h"

static const float M_PI_2 = 1.57079632679489661923;
static const float M_PI_4 = 0.78539816339744830962;

static void u8g2_draw_arc(u8g2_t *u8g2, u8g2_uint_t x0, u8g2_uint_t y0, u8g2_uint_t rad_in, u8g2_uint_t rad_out, u8g2_uint_t angle_start, u8g2_uint_t angle_end, u8g2_atan2f_t atan2f_func)
{
  // Declare variables
  u8g2_long_t x, y, d, r, as, ae, cnt, num_pts;

  // Manage angle inputs
  if(angle_start == angle_end) return;
  uint8_t inverted = (angle_start > angle_end);
  as = inverted ? angle_end : angle_start;
  ae = inverted ? angle_start : angle_end;

  // Trace each arc radius with the Andres circle algorithm
  for(r = rad_in; r <= rad_out; r++)
  {
    x = 0;
    y = r;
    d = r - 1;
    cnt = -1;
    num_pts = atan2f_func ? 100 : (r * 8 / 10); // if no atan2f() function is provided, we make a low cost approximation of the number of pixels drawn for a 1/8th circle of radius r
    
    // Process each pixel of a 1/8th circle of radius r
    while (y >= x)
    {
      // If atan2f() function is provided, get the percentage of 1/8th circle drawn, otherwise count the drawn pixels
      cnt = atan2f_func ? ((M_PI_2 - atan2f_func(y, x)) * 100 / M_PI_4) : (cnt + 1);

      // Fill the pixels of the 8 sections of the circle, but only on the arc defined by the angles (start and end)
      if((cnt > num_pts * as / 45 && cnt <= num_pts * ae / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 + y, y0 - x);
      if((cnt > num_pts * (90 - ae) / 45 && cnt <= num_pts * (90 - as) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 + x, y0 - y);
      if((cnt > num_pts * (as - 90) / 45 && cnt <= num_pts * (ae - 90) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 - x, y0 - y);
      if((cnt > num_pts * (180 - ae) / 45 && cnt <= num_pts * (180 - as) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 - y, y0 - x);
      if((cnt > num_pts * (as - 180) / 45 && cnt <= num_pts * (ae - 180) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 - y, y0 + x);
      if((cnt > num_pts * (270 - ae) / 45 && cnt <= num_pts * (270 - as) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 - x, y0 + y);
      if((cnt > num_pts * (as - 270) / 45 && cnt <= num_pts * (ae - 270) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 + x, y0 + y);
      if((cnt > num_pts * (360 - ae) / 45 && cnt <= num_pts * (360 - as) / 45) ^ inverted) u8g2_DrawPixel(u8g2, x0 + y, y0 + x);

      // Run Andres circle algorithm to get to the next pixel
      if (d >= 2 * x)
      {
        d = d - 2 * x - 1;
        x = x + 1;
      } else if (d < 2 * (r - y))
      {
        d = d + 2 * y - 1;
        y = y - 1;
      } else
      {
        d = d + 2 * (y - x - 1);
        y = y - 1;
        x = x + 1;
      }
    }
  }
}

void u8g2_DrawArc(u8g2_t *u8g2, u8g2_uint_t x0, u8g2_uint_t y0, u8g2_uint_t rad_in, u8g2_uint_t rad_out, u8g2_uint_t angle_start, u8g2_uint_t angle_end, u8g2_atan2f_t atan2f_func)
{
  /* check for bounding box */
#ifdef U8G2_WITH_INTERSECTION
  {
    if ( u8g2_IsIntersection(u8g2, x0-rad_out, y0-rad_out, x0+rad_out+1, y0+rad_out+1) == 0 ) 
      return;
  }
#endif /* U8G2_WITH_INTERSECTION */
  
  
  /* draw arc */
  u8g2_draw_arc(u8g2, x0, y0, rad_in, rad_out, angle_start, angle_end, atan2f_func);
}

Usage

Angles are between 0 and 360 degree.

Fast approximation mode

#include "u8g2.h"
#include "u8g2_arc.h"

u8g2_DrawArc(&u8g2, 30, 30, 12, 16, 0, 300, NULL);

Precision mode

#include <math.h>
#include "u8g2.h"
#include "u8g2_arc.h"

u8g2_DrawArc(&u8g2, 30, 30, 12, 16, 0, 300, atan2f);

If you have a DSP, you can provide its atan2f() function instead. You can also provide lookup-table implementations.

[motla]

@olikraus cool! happy to contribute to a library that I used for a decade now... thank you and don't hesitate if you have questions about the implementation

[olikraus]

With u8g2 i wanted to avoid float, because it might require a lot of extra code space, which is not available for very small uC.
I did some tests with the float less version:

But indeed it looks a little bit odd.
I also think we should do some speed improvements.
Instead of using 0..359 we could use 0..255 which might allow shift operation instead of multiplication.

My test code is currently here: https://github.com/olikraus/u8g2/blob/master/sys/sdl/draw_arc/main.c

[olikraus]

I also wonder, what the 100 means in

num_pts = atan2f_func ? 100 : (r * 8 / 10);

[olikraus]

One more problem is: Although the atan2 function can be provided, the float calculation is still part of the code, which causes Arduino to include all the float math procedures.

Ideally a pure integer version would be preferred.

[motla]

But indeed it looks a little bit odd.

I think the only way to improve it is to run the circle algorithm twice (only for 1/8th a circle), one time just to get the pixel count for radius r (which I now approximate with a linear function), another time for the drawing. I'm not sure it will be perfect but it should be a lot less expensive than using floats and atan2f anyway. I will make a version. Can you test the performance with your SDL setup?

Instead of using 0..359 we could use 0..255 which might allow shift operation instead of multiplication.

Yes good idea. We will have less granularity on angles, but for small displays I guess it's ok.
However the code uses negative numbers in angle comparisons so it would have to be casted to int16_t...
I adapted the code for 0..255 angles:

// Fill the pixels of the 8 sections of the circle, but only on the arc defined by the angles (start and end)
if((cnt > num_pts * as / 32 && cnt <= num_pts * ae / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 + y, y0 - x);
if((cnt > num_pts * (64 - ae) / 32 && cnt <= num_pts * (64 - as) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 + x, y0 - y);
if((cnt > num_pts * (as - 64) / 32 && cnt <= num_pts * (ae - 64) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 - x, y0 - y);
if((cnt > num_pts * (128 - ae) / 32 && cnt <= num_pts * (128 - as) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 - y, y0 - x);
if((cnt > num_pts * (as - 128) / 32 && cnt <= num_pts * (ae - 128) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 - y, y0 + x);
if((cnt > num_pts * (192 - ae) / 32 && cnt <= num_pts * (192 - as) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 - x, y0 + y);
if((cnt > num_pts * (as - 192) / 32 && cnt <= num_pts * (ae - 192) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 + x, y0 + y);
if((cnt > num_pts * (256 - ae) / 32 && cnt <= num_pts * (256 - as) / 32) ^ inverted) u8g2_DrawPixel(u8g2, x0 + y, y0 + x);

I also wonder, what the 100 means in

num_pts = atan2f_func ? 100 : (r * 8 / 10);

It is just a random value for comparaison in the case you use atan2f. I have set 100 to have a percentage of angle, that helped me for debug. It can be anything as long as you put the same number in the formula for cnt two lines below.

Ideally a pure integer version would be preferred.

Yes I agree, I will test the solution mentioned above.

[olikraus]

I found an algorithm here: https://dl.acm.org/doi/pdf/10.1145/245.246 appendix A which fully avoids any kind of float math, but procedure arguments are little bit different.

I am not sure how to continue from here. In order to fit into Arduino Uno, the algorithm should not use float at all. I can add the integer version of the above code, but the errors are very visible.

I also wonder, whether we should remove the radius range and instead draw the arc only for one radius. The users could simply do their own loop of a radius range.

[motla]

I found an algorithm here: https://dl.acm.org/doi/pdf/10.1145/245.246 appendix A

Nice paper, I have to check it.

I chose Andres algorithm because if you increment the radius, it doesn't let holes between traces unlike traditional Bresenham algorithms.

Andres	Bresenham

I also wonder, whether we should remove the radius range and instead draw the arc only for one radius. The users could simply do their own loop of a radius range.

Ok I agree, it will work the same. We just have to remove the for loop. Also we could share the same code with the u8g2_DrawCircle function.

Regarding the idea to run the algorithm twice to avoid floats, the render is slightly better but there is still noise, because the number of drawn pixels by the algorithm is not exactly proportional to the angle.

Demo here: https://motla.github.io/arc-algorithm/better_approx_version

Will have to check your paper then.

[olikraus]

Can you test the performance with your SDL setup?

Not really, the SDL version just runs on an intel based Ubuntu laptop.

I chose Andres algorithm because if you increment the radius, it doesn't let holes between traces unlike traditional Bresenham algorithms.

this makes sense...

Will have to check your paper then.

It has a complete different approach regarding the arc specification. Not so sure whether this makes sense.
Your code is actually very clever.

[motla]

It has a complete different approach regarding the arc specification. Not so sure whether this makes sense.

@olikraus I checked your paper, it is really great but indeed for the arc algorithm we have to provide two points with (x,y) coordinates for the start and the end of the arc, which is unpractical for the user.

On another hand, I found a formula which approximates arctan very well:

double fast_atan(double x) {
  return M_PI_4*x - x*(fabs(x) - 1)*(0.2447 + 0.0663*fabs(x));
}

Now it runs on floats but a very interesting lead I'd like to fiddle with is to adapt this function with normalized integers, for example let's say instead of running between 0.0 and 1.0 making it run between 0 and 4095 and to use it internally to process cnt.

I have to finish urgent ongoing projects but I hope I can take a look at it soon, probably a month from now I will have more time to work on it.

[motla]

Hi @olikraus,

I'm finally back and finished the version with fast arctan formula using no floating points, which works really good. No more glitchy edges.

This line:

ratio = (M_PI_2 - atan2f(y, x)) * 32 / M_PI_4; // [0..32]

can been replaced by these two lines:

ratio = x * 255 / y; // x/y [0..255]
ratio = ratio * (770195 - (ratio - 255) * (ratio + 941)) / 6137491; // arctan(x/y) [0..32]

The only thing is that we must use at least uint32_t for ratio, and I don't know how to manage this with the library types naming.

I removed the arc width (the user has to make a for loop for every radius). Also the start and end angles [0..255].

I made a pull request so you can test it (I played around a bit to make an animated spinner with SDL).

Alternatively I also updated the online JavaScript version: https://motla.github.io/arc-algorithm/

[olikraus]

very nice... ok, i read the PR first. let me link both together.

[olikraus]

very cool

arguments:
rad = radius in pixel
start = start angle, mapped from 0..359 to 0..255
end = end angle, mapped from 0..359 to 0..255

[olikraus]

some documentation required in the wiki

[motla]

thanks! 😉 with github I can't do pull requests on the wiki, but it should be straightforward. just tell me if you want me to do something in particular or if you miss information 👍

[olikraus]

ah, no, that was just a reminder for myself. I will do the wiki updates.

[nordblick2]

Moin!
I am a bit confused and need some help for using drawArc implementation (version 2.35.15).

I would like to use drawArc for a compass element, in detail for drawing an arc as a direction marker (small line in the area of current wind direction). In that case start and end could be > 255 . But that's not possible with an u8-type for start and end angle! Current signature of draw method is all void drawArc(u8g2_uint_t x0, u8g2_uint_t y0, u8g2_uint_t rad, uint8_t start, uint8_t end); Is uint8_t a bug maybe?

Example code of my project:

uint16_t wd = 300; // winddirection in degree 
drawArc(40, 40, 15, wd-10, wd+10); // draw an marker at the current direction (+/- 10 degree)

Any hints are welcome 🙃

Olli

[motla]

@nordblick2 Thanks for your interest! Indeed we made this implementation to optimize for 8bit calculus, it's not a bug. Angles are thus 0-255 and not in degrees. If the first angle is superior to the second, it will draw backwards. You can try values quickly with this tool: https://motla.github.io/arc-algorithm/

[olikraus]

Thanks everyone for the contribution here.
PR is included and I added a documentation also: https://github.com/olikraus/u8g2/wiki/u8g2reference#drawarc
Hope my english isn't that bad... docu fixes are always welcome.