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.
function plot(x, y, c) is
plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)
// Ganzzahliger Teil von x
function ipart(x) is
return int(x)
function round(x) is
return ipart(x + 0.5)
// Bruchteil von x
function 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
end
end function
Siehe auch[Bearbeiten | Quelltext bearbeiten]
Literatur[Bearbeiten | Quelltext bearbeiten]
- 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.