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 Computer Graphics 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 Graphics Gems II vorgestellt. Genau wie sein Linien-Algorithmus ist er ein Ersatz eines bereits existierenden Algorithmus von Bresenham.

functionplot(x,y,c)is
plotthepixelat(x,y)withbrightnessc(where0≤c≤1)
// Ganzzahliger Teil von x
functionipart(x)is
returnint(x)
functionround(x)is
returnipart(x+0.5)
// Bruchteil von x
functionfpart(x)is
ifx<0
return1-(x-floor(x))
// else:
returnx-floor(x)
functionrfpart(x)is
return1-fpart(x)
functiondrawLine(x0,y0,x1,y1)is
booleansteep:=abs(y1-y0)>abs(x1-x0)
ifsteepthen
swap(x0,y0)
swap(x1,y1)
endif
ifx0>x1then
swap(x0,x1)
swap(y0,y1)
endif
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)
ifsteepthen
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)
endif
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)
ifsteepthen
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)
endif
// Hauptschleife
forxfromxpxl1+1toxpxl2-1do
begin
ifsteepthen
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))
endif
intery:=intery+gradient
end
endfunction

• Rasterung von Linien

• Abrash, Michael: Fast Antialiasing (Column). In: Dr. Dobb’s Journal . Band 17, Nr. 6, Juni 1992, S. 139(7) (gamedev.net). 
• Xiaolin Wu: An Efficient Antialiasing Technique. In: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques (= SIGGRAPH '91). ACM, New York, NY, USA 1991, ISBN 0-89791-436-8, S. 143–152, doi:10.1145/122718.122734 (acm.org [abgerufen am 3. August 2016]). 
• Wu, Xiaolin: Graphics Gems II. Hrsg.: James Arvo. Morgan Kaufmann, San Francisco 1991, ISBN 0-12-064480-0, Fast Anti-Aliased Circle Generation, S. 446–450. 

• Xiaolin Wu’s Website
• Matlab-Algorithmus

• Algorithmus (Computergrafik)

• Wikipedia:Qualitätssicherung Informatik