Digital Differential Analyzer with Wu's Algorithm in OpenGL

Question

I'm trying to make an algorithm which draws lines, using the DDA (Digital Differential Analyzer), that also use the Wu's algorithm as anti-aliasing.

The problem is that the output doesn't look quite good. In particular:

• the color that i choose, it changes (i know why but i want to know if it has to be like this)
• the color of the pixel more bright is to bright

How can i choose the color that i want for the line? Considering that it's affected by the algorithm ?

Here's the code:

void dda(int x0, int y0, int x1, int y1, int z, float red, float green, float blue) {
    float dy = y1-y0;
    float dx = x1-x0;
    float m = dy/dx;

    if (m<=1) {
        int x;
        float y;
        y = y0;
        for (x=x0; x<x1; x++) {
            pixel(x, round(y), z, frame, rfpart(red), rfpart(green), rfpart(blue));
            pixel(x, round(y)+1, z, frame, fpart(red), fpart(green), fpart(blue));
            y = y+m;
        }
    }
}

int round(float d) {
  return floor(d + 0.5);
}

float fpart(float x) {
    if (x < 0)
        return 1 - (x - floor(x));
    return x - floor(x);
}

float rfpart(float x) {
    return 1 - fpart(x);
}

Answer 1

1. your code works only for first octant

   so I hope you are testing only there

2. you have forgot to mix the background color and line color

   so add transparency or read the background pixel directly and mix colors on your own. The a,a0 coefficients would be the alpha for transparency color mixing. In that case you should not change the r,g,b values but the alpha only instead. Also if you know the background color you could ignore the reading of pixels but the result will be of a bit while crossing something already rendered.

I change your code to be compatible with mine coding in C++:

void DDA_line_antialiasing(int x0,int y0,int x1,int y1,int col) // DDA antialiasing
    {
    int   x,y,dx,dy,kx,ky,f,df;
    DWORD a,a0;
    union
        {
        DWORD dd;
        BYTE db[4];
        } c,c0;
    dx=x1-x0; kx=0; if (dx>0) kx=+1; else if (dx<0) { kx=-1; dx=-dx; }
    dy=y1-y0; ky=0; if (dy>0) ky=+1; else if (dy<0) { ky=-1; dy=-dy; }
    if (dx+dy==0)
        {
        pnt(x0,y0,col);
        pnt(x1,y1,col);
        return;
        }
    if (dx>=dy)
     for (df=(dy<<8)/dx,x=x0,y=y0,f=0;;f+=df,x+=kx)
        {
        // fixed point y step
        if (f>=256) { f-=256; y+=ky; }
        // line color + background color mixing
        c.dd=col; c0.dd=pnt(x,y); a=256-f; a0=f;
        c.db[0]=DWORD(((DWORD(c.db[0])*a)+(DWORD(c0.db[0])*a0))>>8);
        c.db[1]=DWORD(((DWORD(c.db[1])*a)+(DWORD(c0.db[1])*a0))>>8);
        c.db[2]=DWORD(((DWORD(c.db[2])*a)+(DWORD(c0.db[2])*a0))>>8);
        pnt(x,y   ,c.dd);
        // line color + background color mixing
        c.dd=col; c0.dd=pnt(x,y+ky); a=f; a0=256-f;
        c.db[0]=DWORD(((DWORD(c.db[0])*a)+(DWORD(c0.db[0])*a0))>>8);
        c.db[1]=DWORD(((DWORD(c.db[1])*a)+(DWORD(c0.db[1])*a0))>>8);
        c.db[2]=DWORD(((DWORD(c.db[2])*a)+(DWORD(c0.db[2])*a0))>>8);
        pnt(x,y+ky,c.dd);
        if (x==x1) break;
        }
    else
     for (df=(dx<<8)/dy,x=x0,y=y0,f=0;;f+=df,y+=ky)
        {
        // fixed point x step
        if (f>=256) { f-=256; x+=kx; }
        // line color + background color mixing
        c.dd=col; c0.dd=pnt(x,y); a=256-f; a0=f;
        c.db[0]=DWORD(((DWORD(c.db[0])*a)+(DWORD(c0.db[0])*a0))>>8);
        c.db[1]=DWORD(((DWORD(c.db[1])*a)+(DWORD(c0.db[1])*a0))>>8);
        c.db[2]=DWORD(((DWORD(c.db[2])*a)+(DWORD(c0.db[2])*a0))>>8);
        pnt(x,y   ,c.dd);
        // line color + background color mixing
        c.dd=col; c0.dd=pnt(x+kx,y); a=f; a0=256-f;
        c.db[0]=DWORD(((DWORD(c.db[0])*a)+(DWORD(c0.db[0])*a0))>>8);
        c.db[1]=DWORD(((DWORD(c.db[1])*a)+(DWORD(c0.db[1])*a0))>>8);
        c.db[2]=DWORD(((DWORD(c.db[2])*a)+(DWORD(c0.db[2])*a0))>>8);
        pnt(x+kx,y,c.dd);
        if (y==y1) break;
        }
    }

changed to fixed point (8-bit fractional part) f,df
changed the round to floor (my pixels are already shifted by half)
added color mixing with background color
pnt(x,y,col); draws a pixel x,y with color col
col=pnt(x,y); reads the pixel from screen/image into col
col is 32 bit color (0x00RRGGBB) that union is there just for easy r,g,b access

Answer 2

Here is a complete source which seems to work for me, with the VCL (Embarcadero). I put the modifications below to fix a problem on long lines which made position errors on x1,y1 drawing (pb discovered by comparing with a standard Bresenham line, MoveTo() and LineTo):

• Change the variables type from 'int' to 'float',
• Casting 'dy' value to int, in the loops.

Some Lambdas where also added, and C++ types for 32 and 8 bit are used. Tests of speed have not been done (double is sometimes faster than float).

The speed is ok for me, as I work in a bitmap buffer; this needs to be done, because drawing directly on a component is too slow, as opposed to memory drawing (pC below is a pointer to a bitmap canvas). Then, all the bitmap is transfered in the paintbox. Thanks to the contributors, @giogix and @Spektre.

void aaLine(int x0, int y0, int x1, int y1, int col)
{
    auto pnt = [&](int x, int y, uint32_t c){
        pC->Pixels[x][y] = static_cast<TColor>(c);
    };//-----------------------------

    auto pix_color = [&](uint32_t x, uint32_t y){
        return pC->Pixels[x][y];
    };//-----------------------------

    float   x, y, dx, dy, kx, ky, f, df;//Changed 'int' into 'float' to avoid error on x1,y1 drawing
    uint32_t a,a0;
    union {
        uint32_t dd;
        BYTE db[4];
       } c,c0;

    auto mix_colors = [&](){
        c.db[0]= uint32_t(( uint32_t(c.db[0])*a + uint32_t(c0.db[0])*a0)>>8);
        c.db[1]= uint32_t(( uint32_t(c.db[1])*a + uint32_t(c0.db[1])*a0)>>8);
        c.db[2]= uint32_t(( uint32_t(c.db[2])*a + uint32_t(c0.db[2])*a0)>>8);
    };

    dx=x1-x0; kx=0; if (dx>0) kx=+1; else if (dx<0) { kx=-1; dx=-dx; }
    dy=y1-y0; ky=0; if (dy>0) ky=+1; else if (dy<0) { ky=-1; dy=-dy; }

    if (dx+dy==0) {
        pnt(x0,y0,col);
        pnt(x1,y1,col);
        return;
    }
    if (dx>=dy)
     for (df=(int(dy)<<8)/dx, x=x0, y=y0, f=0;  ; f+=df, x+=kx) //Put int(dy)
     {
        // fixed point y step
        if (f>=256) { f-=256; y+=ky; }
        // line color + background color mixing
        c.dd=col; c0.dd=pix_color(x,y); a=256-f; a0=f;
        mix_colors();
        pnt(x,y   ,c.dd);
        // line color + background color mixing
        c.dd=col; c0.dd=pix_color(x,y+ky); a=f; a0=256-f;
        mix_colors();
        pnt(x,y+ky,c.dd);
        if (x==x1) break;
     }
    else
     for (df=(int(dx)<<8)/dy, x=x0, y=y0, f=0;  ; f+=df, y+=ky) //Put int(dx)
     {
        // fixed point x step
        if (f>=256) { f-=256; x+=kx; }
        // line color + background color mixing
        c.dd=col; c0.dd=pix_color(x,y); a=256-f; a0=f;
        mix_colors();
        pnt(x,y   ,c.dd);
        // line color + background color mixing
        c.dd=col; c0.dd=pix_color(x+kx,y); a=f; a0=256-f;
        mix_colors();
        pnt(x+kx,y,c.dd);
        if (y==y1) break;
     }
}