c++ Bresenham's line algorithm draw arc and rotate

Question

I'm searching way to make arc with Bresenham's line algorithm. This algoritm draw perfect circle, but what if i need draw arc (from 0 to Pi) and rotate it for 30 degrees (for example)?

void DrawCircle(HDC hdc,int x0, int y0, int radius) 
{
        int x = 0;
        int y = radius;
        int delta = 2 - 2 * radius;
        int error = 0;

        while(y >= 0) {
                //SetPixel(hdc,x0 + x, y0 + y,pencol);
                SetPixel(hdc,x0 + x, y0 - y,pencol);
                //SetPixel(hdc,x0 - x, y0 + y,pencol);
                SetPixel(hdc,x0 - x, y0 - y,pencol);
                error = 2 * (delta + y) - 1;
                if(delta < 0 && error <= 0) {
                        ++x;
                        delta += 2 * x + 1;
                        continue;
                }
                error = 2 * (delta - x) - 1;
                if(delta > 0 && error > 0) {
                        --y;
                        delta += 1 - 2 * y;
                        continue;
                }
                ++x;
                delta += 2 * (x - y);
                --y;
        }
}

Solution 1

To get 1/2 a circle (to pi), only call one of your SetPixel routines. To have your arc rotated 30 degrees requires some trig. You could let the above loop run until your x/y ratio is equal to tan(30 degrees), then start actually drawing until your ratio hits the value at which you want to stop. Not the most efficient way, but it will work. To get it better, you'd need to pre-calculate your starting 4 var values. You could take the values from the above run and plug them in as starting values and that would be very efficient.

Did you get the above algorithm from Michael Abrash's Black Book stuff? If not, I'd google for that as a second point of reference on fast circle/arc drawing.

Well, alas, the ellipses that rip chapter wasn't included in there. Here's something I found on the web that claims to be from Abrash:

/* One of Abrash's ellipse algorithms  */

void draw_ellipse(int x, int y, int a, int b, int color)
{
    int wx, wy;
    int thresh;
    int asq = a * a;
    int bsq = b * b;
    int xa, ya;

    draw_pixel(x, y+b, color);
    draw_pixel(x, y-b, color);

    wx = 0;
    wy = b;
    xa = 0;
    ya = asq * 2 * b;
    thresh = asq / 4 - asq * b;

    for (;;) {
        thresh += xa + bsq;

        if (thresh >= 0) {
            ya -= asq * 2;
            thresh -= ya;
            wy--;
        }

        xa += bsq * 2;
        wx++;

        if (xa >= ya)
          break;


        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }

    draw_pixel(x+a, y, color);
    draw_pixel(x-a, y, color);

    wx = a;
    wy = 0;
    xa = bsq * 2 * a;

    ya = 0;
    thresh = bsq / 4 - bsq * a;

    for (;;) {
        thresh += ya + asq;

        if (thresh >= 0) {
            xa -= bsq * 2;
            thresh = thresh - xa;
            wx--;
        }

        ya += asq * 2;
        wy++;

        if (ya > xa)
          break;

        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }
}

The idea being you draw an 8th of the circle at a time x4 and then flip to get the other 8ths drawn. Still doesn't directly answer your question though. Working on that...

Again, your code above should work, you just need to control the starting and ending conditions carefully. The y >= 0 needs to become whatever the y would be upon finishing your 'arc' length and the starting values need to be calculated to be the start of your arc.

This will not be a straight forward task with things as they are. Might just be easier to use a floating point routine instead. The math is much more straight forward and processors tend to handle them better now than when these integer routines were crafted.

Solution 2

If you don't need for sure Bresenham, there is a fast step method introduced in this SO post, where you can set center point, starting point and arc angle. It doesn't need stopping criterion, because it is already included in algorithm (by arc angle). What makes it fast is the precalculation of tangential and radial movement factors and the actual loop has no trig function calls, only multiply, add and subtract.

AFAIK there is three types of methods:
A) Incremental like Bresenham
B) Subdivide method like this
C) Step (or segment) method

I'll take an slow example of step method (don't use this if speed is important):

// I know the question is tagged c++, but the idea comes clear in javascript
var start_angle = 0.5, end_angle = 1.1, r = 30;
for(var i = start_angle; i < end_angle; i = i + 0.05)
{
  drawpixel(x: 50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (x = 50, y = 100)
}

The slowness comes from cos and sin which are repeated (unnecessarily) in loop. This can be solved by precalculating cos and sin as described in the above mentioned SO post. This means huge speedup (average 12x in top5 javascript engines).

I made a non-full-comparable speedtest of various circle and arc drawing algorithms. The Bresenham is fast, but the starting and stopping criterion logic need to be added, which slows down the algo a little. If you really need Bresenham and arc, I have no ready solution for this and not found such yet. It surely is possible. By the way, the step method using precalculated trigs is not so bad in performance compared to Bresenham (in javascript at least). Please test in c++ and report.

Comments

[PePe]

Thanks, I thought that we should change the equation, but my version did not work. Could you give example please? And it not from Michael Abrash's Black Book.

[Michael Dorgan]

Alas, it was from the graphics programming book in a chapter not included in the black book. I remembered reading and assumed it would be in the compilation version. Digging around on the net for it now...

[PePe]

Thanks, but I preferred to use Bresenham's algorithm.