Talk:Xiaolin Wu's line algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer graphics  
WikiProject icon This article is within the scope of WikiProject Computer graphics, a collaborative effort to improve the coverage of computer graphics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Aloof[edit]

The extension to cover nearly-vertical lines is trivial, and left as an exercise for the reader.

Doesn't get any more aloof than that, gentlemen.

Indeed it doesn't, and could frustrate someone coming to Wikipedia for algorithm help (I know I have). If they haven't studied Bresenham's algorithm the way to fix it may not be so obvious. I'll edit the article.

This Article needs some Images.[edit]

Maybe even readers not able to use a compiler themselves may want to know what it looks like...

Typo in code?[edit]

   // check that x1 < x2
   if x2 < x1
       swap x1, x2

Surely just swapping x1 and x2 creates a mirror-image of the line? Shouldn't y1 and y2 also be swapped?

This is what is done in Bresenham's_line_algorithm:

    if x0 > x1 then
        swap(x0, x1)
        swap(y0, y1)

The nearly-horizontal case[edit]

"the nearly-horizontal case (Δx > Δy)"

makes more sense (to me) if it would read

"the nearly-horizontal case (Δx ≫ Δy)"

Am I missing something obvious here?

- Yes, the word "nearly" is a bit misleading. Δx > Δy is just the more-horizontal-than-not case, in which one can iterate over x to draw all the points. 80.137.89.203 17:07, 1 August 2006 (UTC)

Posted Pseudo-Code Works[edit]

FYI, I used the pseudo-code posted on the wiki page as the basis for my own Wu line generator in C++ combined with SDL (Simple DirectMedia Layer). It works very well, is very fast, and can be easily generalized to other octants in the plane. Thanks a ton to the original poster.

- I just implemented this in python and IMHO "ipart(x) == integer part of x" should be clarified to really mean floor(x), that is for negative numbers (like -2.5) it should still round down (to -3.0) instead of to the integer part (-2.0). Also i used "1.0-(intery-floor(intery))" to calculate the alpha (also because of negative numbers) 80.137.89.203 17:18, 1 August 2006 (UTC)

Diagonals[edit]

This algorithm doesn't antialias diagonal lines (+45°, -45°, +135°, -135°) nor lines close to these angles aren't antialiased very visibly. Maybe this should be mentioned? 82.229.207.75 09:07, 15 December 2006 (UTC)

-

It should probably be noted - it was in the paper and by any authoritative coverage of the algorithm. Horizontal, vertical, and diagonal lines are special case scenarios that simply shouldn't be handled by the Wu algorithm as it can be done much faster using special code; the pixel weightings are constant, after all. 83.84.34.115 00:07, 14 March 2007 (UTC)

Author[edit]

Does the article link to the correct Xiaolin Wu? His website has no mention of anti-aliasing algorithm. --24.13.179.215 04:21, 24 June 2007 (UTC)

Code error?[edit]

Shouldn't be this code inside the distinction between horizontal-ish and vertical-ish lines? The way it is implemented now can have the result that after swapping x and y, x2 is again smaller than x1.

   if x2 < x1
       swap x1, x2
       swap y1, y2
   end if

194.78.35.195 (talk) 15:29, 19 February 2008 (UTC)

---

And what about intensity?[edit]

This code does not seem to handle pixel intensity very well (if at all). It seems a very cheap substitution for real antialiasing line drawing algorithms. /Nurse Dragonbreath —Preceding unsigned comment added by 85.19.218.76 (talk) 08:11, 6 September 2008 (UTC)

-

The intensities produced by the algorithm are just that, intensities. To convert them to RGB values you have to do gamma correction. —Preceding unsigned comment added by 109.108.24.166 (talk) 19:27, 30 October 2010 (UTC)

Using Wu's line algorithm in SDL[edit]

Amir6723 (talk) 10:53, 4 August 2012 (UTC)Amir6723

this function Draws Wu's line algorithm based lines, in SDL:


void WULinesAlpha(double x1,double y1,double x2,double y2,Uint32 color,SDL_Surface* screen)
{   bool vertical=false;
   Uint8 r,g,b;
   //temporary Surface with alpha support.
   SDL_Surface* alpha = SDL_CreateRGBSurface(SDL_ALPHA_OPAQUE,WIDTH,HEIGHT,32, 0x000000FF, 0x0000FF00, 0x00FF0000, 0xFF000000);
   SDL_GetRGB(color,screen->format,&r,&g,&b);
   //new color but with alpha value.
   Uint32 colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255);
   //checking if this is a vertical or horizental line type.
   if(abs(y2-y1)>abs(x2-x1))
   {
       vertical=true;
   }
   //make vertical lines horizental.
   if (vertical)
   {
       swap (&x1, &y1);
       swap (&x2, &y2);
   }
   //if x is decreasing swap x1 and x2;
   if (x2 < x1)
   {
       swap (&x1, &x2);
       swap (&y1, &y2);
   }
   //line WIDTH and HEIGHT!!!
   int dx = (x2 - x1);
   int dy = (y2 - y1);
   //this is for calculating y from x ;)
   double gradient = ((double)dy) / ((double)dx);
   // handle first endpoint. endpoints will be handle seperately. cuz they are thricky.
   // wu's line algorithm can draw lines with non integer start and end. so we need to
   //have an integer to start with.
   int xend = round(x1);
   //some good y for end point this is also an int.
   double yend = y1 + gradient * (xend - x1);
   //xgap is simply pixel around integer
   double xgap = rfpart(x1 + 0.5);
   int xpxl1 = xend;  // this will be used in the main loop
   //in original algorithm, ypxl1 was integer part of yend!!!
   int ypxl1 = floor(yend);
   colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(rfpart(yend) * xgap));
   if(vertical)
   {
       putPixel(ypxl1,xpxl1,colorAlpha,alpha);
       colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(fpart(yend) * xgap));
       putPixel(ypxl1 + 1, xpxl1, colorAlpha,alpha);
   }
   else
   {
       putPixel(xpxl1, ypxl1,colorAlpha,alpha);
       colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(fpart(yend) * xgap));
       putPixel(xpxl1, ypxl1 + 1, colorAlpha,alpha);
   }
   //putPixel(xpxl1, ypxl1,colorAlpha,alpha);
   double intery = yend + gradient; // first y-intersection for the main loop
   // handle second endpoint
   xend = round(x2);
   yend = y2 + gradient * (xend - x2);
   xgap = fpart(x2 + 0.5);
   int xpxl2 = xend;  // this will be used in the main loop
   int ypxl2 = floor(yend);
   //calculate color of pixel based in its distant from logical line.
   colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(rfpart (yend) * xgap));
   //following if, elses are for handling vertical and horizental lines:
   if(vertical)
   {
       //first pixel
       putPixel(ypxl2, xpxl2, colorAlpha,alpha);
       //calculate color of pixel based in its distant from logical line.
       colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(fpart (yend) * xgap));
       //second pixel
       putPixel(ypxl2 + 1,xpxl2, colorAlpha,alpha);
   }
   else//same as if.
   {
       putPixel(xpxl2, ypxl2, colorAlpha,alpha);
       colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(fpart (yend) * xgap));
       putPixel(xpxl2, ypxl2 + 1, colorAlpha,alpha);
   }
   // main loop. this is where we draw the rest of the line. like end points
   //we need to draw 2 pixel. and their alpha is calculaed from their distance
   //from logical line.
   for (int i=xpxl1+1;i<=xpxl2-1;i++)
       {
           colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*(rfpart (intery)));
           if(vertical)
           {
               putPixel(floor(intery),i, colorAlpha,alpha);
               colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*( fpart (intery)));
               putPixel(floor(intery) + 1,i,  colorAlpha,alpha);
           }
           else
           {
               putPixel(i,floor(intery), colorAlpha,alpha);
               colorAlpha=SDL_MapRGBA(alpha->format,r,g,b,255*( fpart (intery)));
               putPixel(i, floor(intery) + 1, colorAlpha,alpha);
           }
           intery = intery + gradient;
       }//end for now we need to blit alpha surface to original one
SDL_BlitSurface(alpha,0,screen,0);
SDL_FreeSurface(alpha);
}


and for swap,fpart and rfpart functions:

Numbered list item
template <class T>
void swap (T *x,T *y)
{
    T temp;
    temp=*x;
    *x=*y;
    *y=temp;
}

//returns fractional part of any number.
double fpart(double x)
{
    return (x-floor(x));
}
double rfpart(double x)
{
    return (1-fpart(x));
}

oh you will need putPixel function:

bool putPixel(Uint16 x,Uint16 y,Uint32 color1,SDL_Surface* screen)
{
   //pData is an array that points to pixels locations
   char* pData=(char*)screen->pixels;
   //lock the surface if needed;
   if(SDL_MUSTLOCK(screen))
   {
       SDL_LockSurface(screen);
   }
   //cecking for location of pixel. we dont want to go ot of screen size.
   if(x<0||x>=WIDTH||y>=HEIGHT||y<0)
    {
     return false;
    }
    else
   {
       //next two lines are for setting location of pixel.
       pData+=x*screen->format->BytesPerPixel;
       pData+=y*screen->pitch;
       //copy the color to pixel
       memcpy(pData,&color1,screen->format->BytesPerPixel);
   }
   //unlock the surface if needed;
   if(SDL_MUSTLOCK(screen))
   {
       SDL_UnlockSurface(screen);
   }
   return true;
}


this function is written by Amir6723. you will need cmath header included. you don't need to turn on alpha support in you display surface. colors should be made using SDL_MapRGB() (not SDL_MapRGBA()) and then be passed to function. this function is complete but if anyone can improve this and also keep it simple feel free to change it.

Pseudo-code does not match Wu's Fast Antialiased Line Generator[edit]

While presented pseudo-code does the antialiasing part, it misses two features of original algorithm. First is utilising symmetry and drawing line from both ends to the middle thus doing only one calculation of intensity per two pixels advancement on x axis. Second is that it should actually be purely integer algorithm outside of initialization. Hence the claim in original paper that this algorithm is actually faster than Bresenham's. It says nothing about performance of either algorithm on today's hardware, but for history that's how it was: Wu's algorithm does half as much of additions, sign tests and comparisons as Bresenham's and about twice as much buffer writes. Loiten (talk) 08:09, 10 February 2014 (UTC)