CODEWITHSUNDEEP
c++cgraphics
Tom Brinkman
Tom Brinkman

Reputation: 65

Line Drawing Algorithm

I wrote a line drawing algorithm using the wu technique. It works but has issues. See below.

What I'm wondering is if anyone has tackled the problem of drawing anti-aliased lines? Suprisingly, a google search results in no satisfactory algorithms. Lots of discusions, but not a single complete, robust algorithm, independent of any dependencies on a graphics library.

If anyone wants sample code for the following function let me know. I'm hoping to replace this with a more robust function, but I have not found one yet. I'm sure that my algorithm can be improved, but it works.

struct xya
{
    int x;
    int y; 
    uint8_t a;
    xya(int x=0, int y=0, uint8_t a=0) : x(x), y(y), a(a) {}
};

inline void wuline(xya*& out, int x0, int y0, int x1, int y1)
{
    short DeltaX, DeltaY, XDir;
    static const int intensity = 8;

    if (y0 > y1)
    {
        short Temp = y0; 
        y0 = y1; 
        y1 = Temp;
        Temp = x0; 
        x0 = x1; 
        x1 = Temp;
    }

    *out++ = xya(x0,y0,255);

    if ((DeltaX = x1 - x0) >= 0)
    {
        XDir = 1;
    } 
    else 
    {
        XDir = -1;
        DeltaX = -DeltaX; 
    }

    if ((DeltaY = y1 - y0) == 0)
    {
        while (DeltaX-- != 0) 
        {
            x0 += XDir;
            *out++ = xya(x0,y0,255);            
        }

        return;
    }

    if (DeltaX == 0) 
    {
        do 
        {
            y0++;
            *out++ = xya(x0,y0,255);            
        } 
        while (--DeltaY != 0);

        return;
    }

    if (DeltaX == DeltaY) 
    {
        do 
        {
            x0 += XDir;
            y0++;
            *out++ = xya(x0,y0,255);            
        } 
        while (--DeltaY != 0);

        return;
    }

    if (DeltaY > DeltaX) 
    {
        unsigned short ErrorAcc = 0;  
        unsigned short ErrorAdj = ((unsigned long) DeltaX > intensity;
            *out++ = xya(x0,y0,Weighting ^ 255);
            *out++ = xya(x0+XDir,y0,Weighting);
        }

        *out++ = xya(x1,y1,255);            
    }
    else
    {
        unsigned short ErrorAcc = 0;  
        unsigned short ErrorAdj = ((unsigned long) DeltaY > intensity;
            *out++ = xya(x0,y0,Weighting ^ 255);            
            *out++ = xya(x0,y0+1,Weighting);
        }

        *out++ = xya(x1,y1,255);
    }
}

Upvotes: 3

Views: 3975

Answers (3)

Mick
Mick

Reputation: 7937

I was once given the task of drawing all sorts of complex and overlapping shapes that needed anti-aliasing. My solution was to draw everything to memory at a higher resolution (2x? 3x?) than the image that needed to be displayed. Then as a last step convert the high res image to low res by averaging the R,G and B separately for each of the multiple pixels in the high res version that would be reduced to a single pixel in the display image.

It may not be the most efficient way of doing things, but its dead easy to code and the visual effect was excellent.

Upvotes: 0

Zac
Zac

Reputation: 3285

Just curious why aren't you using a library to do this for you? For example on windows GDI+ supports antialiasing, and I'm sure that there is probably an implementation for QT & WX. Aside from those options, OpenGL would do the trick too.

GDI+ docs on anti-aliasing http://msdn.microsoft.com/en-us/library/ms535723%28VS.85%29.aspx

If you are doing it for the heck of it or academic, then just ignore me..

Upvotes: 1

John Feminella
John Feminella

Reputation: 311516

The canonical example for drawing antialiased lines quickly and efficiently is Xiaolin Wu's algorithm. You may want to look at that for a solid approach. Here's some sample code, too. The result of applying Wu's algorithm is on the right:

alt text http://www.suchit-tiwari.org/writings/antialias/antialias.png

Upvotes: 3

Related Questions