Anti-aliasing Bresenham's line not working as expected

Question

I'm trying to implement bresenham's line drawing with anti-aliasing using this article: http://members.chello.at/~easyfilter/bresenham.html

And here's the function:

void ColoringScene::drawLineAA(int x0, int y0, int x1, int y1, int r, int g, int b, int a)
{
    float dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
    float dy = abs(y1-y0), sy = y0<y1 ? 1 : -1;
    float err = dx-dy, e2, x2;                       /* error value e_xy */
    float ed = dx+dy == 0 ? 1 : sqrt((float)dx*dx+(float)dy*dy);

    for (;;){                                         /* pixel loop */
        setPixel(x0, y0, r, g, b, a*abs(err-dx+dy)/ed);
        e2 = err; x2 = x0;
        if (2*e2 >= -dx) {                                    /* x step */
            if (x0 == x1) break;
            if (e2+dy < ed) setPixel(x0, y0 + sy, r, g, b, a*(e2+dy)/ed);
            err -= dy; x0 += sx;
        }
        if (2*e2 <= dy) {                                     /* y step */
            if (y0 == y1) break;
            if (dx-e2 < ed) setPixel(x2 + sx, y0, r, g, b, a*(dx-e2)/ed);
            err += dx; y0 += sy;
        }
    }
}

Don't know if it changes anything, but I changed all int's to float's. Just to make sure if dividing is working on floats. Anyway on integers result is the same.

Now, example call:

drawLineAA(10, 10, 50, 400, 255, 0, 0, 255);
drawLineAA(100, 10, 500, 40, 255, 0, 0, 255);

Results in this:

If I change y0 + sy to y0 - sy like this:

if (e2+dy < ed) setPixel(x0, y0 - sy, r, g, b, a*(e2+dy)/ed);

Output becomes this:

If I change x2 + sx to x2 - sx like this:

if (dx-e2 < ed) setPixel(x2 - sx, y0, r, g, b, a*(dx-e2)/ed);

Output now is:

So the last configuration is both negatives, which gives:

Almost good, but some holes appear. So it's still wrong. I cannot figure it out, why it's not drawing properly. When I tried ordinary bresenham's without anti-aliasing and it works without any problem.

Also important note, in my case I use cocos2d-x texture, so y is flipped. That's why I have this method:

void ColoringScene::setPixel(int x, int y, int r, int g, int b, int a){
    if(x < 0 || x >= img->getWidth() || y < 0 || y >= img->getHeight()) return;
    int index = (x + (img->getHeight() - y - 1) * img->getWidth()) * 4;
    data[index] = r;
    data[index + 1] = g;
    data[index + 2] = b;
    data[index + 3] = a;
}

Maybe the issue is, because of this. How can I fix this?
Regards

Answer 1

This algorithm seems just incorrect.

• x0==x1 or y0==y1 is a fatal error.
• dx==dy is a fatal error.
• Setting ed=1 when dx+dy=0 is completely arbitrary.
• 2*e2==dy and 2*e2==-dx results in drawing three pixels per step.

Recommendations: treat dx=dy, dx=-dy, dx=0, dy=0 as special cases, make separate cases for each octant, don't use floats if you don't need them.