Talk:Xiaolin Wu's line algorithm

Aloof

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. — Preceding unsigned comment added by 80.43.3.162 (talk) 17:09, 2005 July 10 (UTC)

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. — Preceding unsigned comment added by 68.48.5.79 (talk) 05:35, 2005 August 21 (UTC)

This Article needs some Images.

Maybe even readers not able to use a compiler themselves may want to know what it looks like... — Preceding unsigned comment added by 84.170.80.64 (talk) 12:36, 2005 September 2 (UTC)

Typo in code?

   // 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)

— Preceding unsigned comment added by 86.136.74.165 (talk) 19:27, 2005 October 19 (UTC)

The nearly-horizontal case

"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? — Preceding unsigned comment added by 86.197.36.160 (talk) 21:48, 2006 April 7 (UTC)

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

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. — Preceding unsigned comment added by 199.120.31.18 (talk) 13:49, 2006 July 21 (UTC)

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)

I agree with the statement made by User:80.137.89.203, Either ipart(x) is wrong or round(x) is. I corrected ipart(x) to floor it, now round(x) will return the correct answer for round(-5.2). Alternatively round should subtract a half when x is less than 0. I'm not completely sure which of those alternatives was intended. 2001:56A:700F:2500:18FF:17D4:9A71:BA39 (talk) 04:19, 15 June 2017 (UTC)

Diagonals

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

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?

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)

---

Divide-by-zero trap

In the pseudo-code, the special-case to deal with dx == 0.0 is done after the division, which is a bit silly. It should be something like

   gradient := 1.0
   if dx != 0.0 then
       gradient := dy / dx
   end if

ChrisDennis (talk) 17:03, 29 December 2021 (UTC)

---

And what about intensity?

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

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. — Preceding unsigned comment added by Amir6723 (talk • contribs) 10:53, 2012 August 4 (UTC)

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

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)

This tweet and this tweet agree with this criticism, saying: "Xiaolin Wu’s algorithm code on Wikipedia is wrong (operates on floats, not ints; doesn’t mirror) and it’s been copied everywhere." and "Look at https://www.codeproject.com/Articles/13360/Antialiasing-Wu-Algorithm#dwuln … for the real algorithm. Ignore Rosetta Code and GitHub repos. They copied from Wikipedia." -David Baron (talk) 23:46, 29 December 2016 (UTC)

Someone needs to remove that code from the page. That code is not only "not the right one", is actually broken and currently being used everywhere. - Fernando Serboncini (talk) 01:29, 12 March 2017

The above is true, but the codeproject algorithm is also incomplete: It starts with integer endpoints, while wu should also work on floating point endpoints — Preceding unsigned comment added by 83.134.230.197 (talk) 10:44, 25 March 2017 (UTC)

"Bresenham's algorithm draws lines extremely quickly, but it does not perform anti-aliasing"

Zingl came up with a version of Bresenham's that does anti-aliasing. Namely it converts the x-error and y-error into an xy-error and then uses the single error value then uses that value to determine the amount of antialiasing required. The statement in the article isn't strictly true, but it's kind of an obscure set of algorithms that'll do the aa-bresenham stuff. http://members.chello.at/easyfilter/bresenham.html

void plotLineAA(int x0, int y0, int x1, int y1)
{             /* draw a black (0) anti-aliased line on white (255) background */
   int sx = x0 < x1 ? 1 : -1, sy = y0 < y1 ? 1 : -1, x2;
   long dx = abs(x1-x0), dy = abs(y1-y0), err = dx*dx+dy*dy;
   long e2 = err == 0 ? 1 : 0xffff7fl/sqrt(err);     /* multiplication factor */

   dx *= e2; dy *= e2; err = dx-dy;                       /* error value e_xy */
   for ( ; ; ){                                                 /* pixel loop */
      setPixelAA(x0,y0,abs(err-dx+dy)>>16);
      e2 = err; x2 = x0;
      if (2*e2 >= -dx) {                                            /* x step */
         if (x0 == x1) break;
         if (e2+dy < 0xff0000l) setPixelAA(x0,y0+sy,(e2+dy)>>16);
         err -= dy; x0 += sx;
      }
      if (2*e2 <= dy) {                                             /* y step */
         if (y0 == y1) break;
         if (dx-e2 < 0xff0000l) setPixelAA(x2+sx,y0,(dx-e2)>>16);
         err += dx; y0 += sy;
    }
}

Tat (talk) 00:11, 16 September 2019 (UTC)

On this, ″...naive antialiasing would take a long time..." Would it? What is the naive algorithm?

— Preceding unsigned comment added by 76.204.59.233 (talk) 14:50, 2020 September 22 (UTC)

Problems

• It should discuss the colour space to be used. I've noticed that software using the wrong colour space draw angled lines a bit fatter for example.
• I think the algorithm as presented will not work correctly in places where the line is near the centre of a pixel, because then three pixels need to be plotted and this algorithm always plots only two. A common case where the error is very visible is that of a line angled at exactly 45°. — Preceding unsigned comment added by 77.61.180.106 (talk) 20:17, 16 March 2022 (UTC)