Xiaolin Wus Linien-Algorithmus

Xiaolin Wus Linien-Algorithmus ist ein Algorithmus für das Darstellen von Linien mit Antialiasing (Kantenglättung), erstmals vorgestellt im Artikel An Efficient Antialiasing Technique in der Ausgabe von im Juli 1991 sowie im Artikel Fast Antialiasing in Dr. Dobb’s Journal vom Juni 1992. Der Bresenham-Algorithmus ist bei der Darstellung von Linien zwar besonders schnell, unterstützt aber nicht die Glättung der Linien. Außerdem können nur Linien dargestellt werden, deren Endpunkt-Koordinaten ganzzahlig sind. Ein naiver Ansatz der Linienglättung wäre extrem langsam. Wus Algorithmus ist vergleichsweise schnell, aber immer noch langsamer als der Bresenham-Algorithmus. Wus Algorithmus zeichnet Pixel immer paarweise auf je einer Seite der Linie und färbt sie nach ihrem Abstand von der Linie. Gesondert behandelt werden die Pixel an den Linienenden sowie Linien mit einer Länge kürzer als ein Pixel. Eine Erweiterung des Algorithmus zum Darstellen von Kreisen wurde von Xiaolin Wu im Buch II vorgestellt. Genau wie sein Linien-Algorithmus ist er ein Ersatz eines bereits existierenden Algorithmus von Bresenham. function plot(x, y, c) is plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)// Ganzzahliger Teil von xfunction ipart(x) is return int(x)function round(x) is return ipart(x + 0.5)// Bruchteil von xfunction fpart(x) is if x < 0 return 1 - (x - floor(x)) // else: return x - floor(x)function rfpart(x) is return 1 - fpart(x)function drawLine(x0,y0,x1,y1) is boolean steep := abs(y1 - y0) > abs(x1 - x0) if steep then swap(x0, y0) swap(x1, y1) end if if x0 > x1 then swap(x0, x1) swap(y0, y1) end if dx := x1 - x0 dy := y1 - y0 gradient := dy / dx // Vorgehen fuer ersten Endpunkt xend := round(x0) yend := y0 + gradient * (xend - x0) xgap := rfpart(x0 + 0.5) xpxl1 := xend // fuer die Hauptschleife ypxl1 := ipart(yend) if steep then plot(ypxl1, xpxl1, rfpart(yend) * xgap) plot(ypxl1+1, xpxl1, fpart(yend) * xgap) else plot(xpxl1, ypxl1 , rfpart(yend) * xgap) plot(xpxl1, ypxl1+1, fpart(yend) * xgap) end if intery := yend + gradient // erste y-Koordinate fuer die Hauptschleife // Vorgehen fuer ersten Endpunkt xend := round(x1) yend := y1 + gradient * (xend - x1) xgap := fpart(x1 + 0.5) xpxl2 := xend // fuer die Hauptschleife ypxl2 := ipart(yend) if steep then plot(ypxl2 , xpxl2, rfpart(yend) * xgap) plot(ypxl2+1, xpxl2, fpart(yend) * xgap) else plot(xpxl2, ypxl2, rfpart(yend) * xgap) plot(xpxl2, ypxl2+1, fpart(yend) * xgap) end if // Hauptschleife for x from xpxl1 + 1 to xpxl2 - 1 do begin if steep then plot(ipart(intery) , x, rfpart(intery)) plot(ipart(intery)+1, x, fpart(intery)) else plot(x, ipart(intery), rfpart(intery)) plot(x, ipart(intery)+1, fpart(intery)) end if intery := intery + gradient endend function