| dbo:abstract
|
- 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 (de)
- El algoritmo de Xiaolin Wu es una mejora del algoritmo de Bresenham que permite dibujar rectas en dispositivos de gráficos rasterizados reduciendo el aliasing. El algoritmo se basa en dibujar parejas de pixeles a lo largo del trazado de la recta con diferentes intensidades en función de la cercanía a la recta real.
* Datos: Q2835867 (es)
- L'algorithme de tracé de segment de Xiaolin Wu est un algorithme permettant de tracer des courbes non-crénelées qui a été présenté dans l'article An Efficient Antialiasing Technique de juillet 1991 issue de Computer Graphics ainsi que dans l'article Fast Antialiasing de juillet 1992 issue du journal du docteur Dobb. L'algorithme de Bresenham trace des lignes extrêmement rapidement, mais n'est pas conçu pour l'anticrénelage. En plus de cela, il ne gère pas le cas où les points de bout de ligne ne sont pas situés exactement sur la grille de pixel. L'approche naïve pour dessiner des lignes sans crénelage prend énormément de temps, mais l'algorithme de Wu est assez rapide (tout en restant plus lent que l'algorithme de Bresenham). La base de l'algorithme est de dessiner des paires de pixels chevauchant la ligne, colorée selon leur proximité. Les pixels de bout de ligne sont traités séparément. Une extension de l'algorithme pour les cercles a été présentée par Wu dans Graphics Gems II. Tout comme l'algorithme de tracé de segment de Wu est un remplaçant de l'algorithme de tracé de segment de Bresenham, celui de tracé de cercle de Wu est un remplaçant de l'algorithme de tracé de cercle de Bresenham. (fr)
- Xiaolin Wu's line algorithm is an algorithm for line antialiasing. (en)
- 吴小林算法是一种绘制抗锯齿直线的算法，因为其较高的执行效率被发表在1991年7月的《 Computer Graphics》和1992年6月的《Dr. Dobb's Journal》上。 布雷森漢姆直線演算法绘制直线非常快，但它不支持抗锯齿。此外，它不能处理线段端点的坐标不是整数的情况。一个不成熟的反锯齿画线方法需要非常长的时间，但吴的算法是相当快的（虽然它仍然较布雷森汉姆直线算法慢）。该算法的基本思想是画两个像素点在岔在直线两边，并按照直线相近的颜色着色，而线段末端的像素点另外处理。如果线段宽度小于一像素，将会被作为特殊情况考虑。 吴小林的《Graphics Gems II》一书描述了一个绘制圆的算法，作为布雷森汉姆圆绘制算法的替代品。 function plot(x, y, c) is plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)// integer part of xfunction ipart(x) is return floor(x)function round(x) is return ipart(x + 0.5)// fractional part of xfunction fpart(x) is 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 if dx == 0.0 then gradient := 1.0 end if // handle first endpoint xend := round(x0) yend := y0 + gradient * (xend - x0) xgap := rfpart(x0 + 0.5) xpxl1 := xend // this will be used in the main loop 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 // first y-intersection for the main loop // handle second endpoint xend := round(x1) yend := y1 + gradient * (xend - x1) xgap := fpart(x1 + 0.5) xpxl2 := xend //this will be used in the main loop 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 // main loop if steep then for x from xpxl1 + 1 to xpxl2 - 1 do begin plot(ipart(intery) , x, rfpart(intery)) plot(ipart(intery)+1, x, fpart(intery)) intery := intery + gradient end else for x from xpxl1 + 1 to xpxl2 - 1 do begin plot(x, ipart(intery), rfpart(intery)) plot(x, ipart(intery)+1, fpart(intery)) intery := intery + gradient end end ifend function 注意：如果在程序开始abs(dx) < abs(dy)为 true，那么所有的绘图应该做X和Y逆转。 (zh)
- Алгоритм Ву — это алгоритм разложения отрезка в растр со сглаживанием. Был предложен У Сяолинем (Xiaolin Wu, отсюда устоявшееся в русском языке название алгоритма) в статье, опубликованной журналом в июле 1991 года. Алгоритм сочетает высококачественное устранение ступенчатости и скорость, близкую к скорости алгоритма Брезенхема без сглаживания. (ru)
- Алгоритм Ву — алгоритм для малювання ліній зі згладжуванням, був представлений в статті Ефективна техніка згладжування у липневому випуску видання Computer Graphics, а також в статті Швидке згладжування в червні 1992 в випуску Dr. Dobb's Journal. Алгоритм Брезенхейма малює відрізок дуже швидко, але він не виконує згладжування. В додаток, він не може обробити ситуацію коли кінцеві точки мають не цілочисельні координати. Наївна спроба малювання зі згладжуванням вимагає багато часу, в той час як алгоритм Ву дуже швидкий (хоча й повільніший за алгоритм Брезенхейма). (uk)
|
