Task

Implement the   Xiaolin Wu's line algorithm   described in Wikipedia.



This algorithm draws anti-aliased lines.



Related task

   See   Bresenham's line algorithm   for aliased lines.


bresline = false   // space toggles, for comparison
 
rB = 255 : gB = 255 : bB = 224
rL = 0 : gL = 0 : bL = 255
 
sub round(x)
    return int(x + .5)
end sub
 
sub plot(x, y, c, steep)
//  plot the pixel at (x, y) with brightness c (where 0 <= c <= 1)
 
    local t, C
 
    if steep then t = x : x = y : y = t end if
    C = 1 - c
    color rL * c + rB * C, gL * c + gB * C, bL * c + bB * C
 
    dot x, y
end sub
 
sub plot2(x, y, f, xgap, steep)
    plot(x, y, (1 - f) * xgap, steep)
    plot(x, y + 1, f * xgap, steep)
end sub
 
sub draw_line(x0, y0, x1, y1)
    local steep, t, dx, dy, gradient, xend, yend, xgap, xpxl1, ypxl1, xpxl2, ypxl2, intery
 
    if bresline then
        line x0, y0, x1, y1
        return
    end if
    steep = abs(y1 - y0) > abs(x1 - x0)
    if steep then
        t = x0 : x0 = y0 : y0 = t
        t = x1 : x1 = y1 : y1 = t 
    end if
    if x0 > x1 then
        t = x0 : x0 = x1 : x1 = t
        t = y0 : y0 = y1 : y1 = t
    end if
 
    dx = x1 - x0
    dy = y1 - y0
    if dx = 0 then
        gradient = 1
    else
        gradient = dy / dx
    end if
 
    // handle first endpoint
    xend = round(x0)
    yend = y0 + gradient * (xend - x0)
    xgap = 1 - frac(x0 + 0.5)
    xpxl1 = xend // this will be used in the main loop
    ypxl1 = int(yend)
    plot2(xpxl1, ypxl1, frac(yend), xgap, steep)
    intery = yend + gradient // first y-intersection for the main loop
 
    // handle second endpoint
    xend = round(x1)
    yend = y1 + gradient * (xend - x1)
    xgap = frac(x1 + 0.5)
    xpxl2 = xend // this will be used in the main loop
    ypxl2 = int(yend)
    plot2(xpxl2, ypxl2, frac(yend), xgap, steep)
 
    // main loop
    for x = xpxl1 + 1 to xpxl2 - 1
        plot2(x, int(intery), frac(intery), 1, steep)
        intery = intery + gradient
    next x
end sub
 
w = 640 : h = 480
open window w, h
 
color 0, 0, 255
 
draw_line(0, 0, 200, 200)
draw_line(w, 0, 200, 200)
draw_line(0, h, 200, 200)
draw_line(w, h, 200, 200)