Algoritmus linky Xiaolin Wus - Xiaolin Wus line algorithm - Wikipedia

Demonstrace algoritmu Xiaolin Wu

Lineární algoritmus Xiaolin Wu je algoritmus pro linku Anti aliasing.

Technika vyhlazování

Algoritmus linky Xiaolin Wu byl představen v článku „Efektivní technika vyhlazování“ ve vydání z července 1991 Počítačová grafika, jakož i v článku "Rychlé vyhlazení obsahu" ve vydání z června 1992 Dr. Dobb's Journal.

Bresenhamův algoritmus kreslí čáry extrémně rychle, ale neprovádí vyhlazování. Kromě toho nemůže zpracovat žádné případy, kdy koncové body řádků neleží přesně na celočíselných bodech mřížky pixelů. Naivní přístup k vyhlazení linky by trval extrémně dlouho. Wuův algoritmus je poměrně rychlý, ale stále pomalejší než Bresenhamův algoritmus. Algoritmus se skládá z kreslení dvojic pixelů obkročujících čáru, každý zbarvený podle své vzdálenosti od čáry. Pixely na koncích řádků jsou zpracovávány samostatně. Řádky kratší než jeden pixel jsou zpracovány jako speciální případ.

Xiaolin Wu v knize představil rozšíření algoritmu pro kreslení kruhů Grafické drahokamy II. Stejně jako algoritmus kreslení čar je náhradou za Bresenhamův algoritmus kreslení čar, je algoritmus kreslení kruhu náhradou za Bresenhamův algoritmus kreslení kruhu.

Algoritmus

funkce spiknutí(X, y, C) je    spiknutí the pixel na (X, y) s jas C (kde 0 ≤ C ≤ 1)// celá část xfunkce ipart(X) je    vrátit se podlaha(X)funkce kolo(X) je    vrátit se ipart(X + 0.5)// zlomková část xfunkce fpart(X) je    vrátit se X - podlaha(X)funkce rfpart(X) je    vrátit se 1 - fpart(X)funkce drawLine(x0,y0,x1,y1) je    booleovský strmý := břišní svaly(y1 - y0) > břišní svaly(x1 - x0)        -li strmý pak        vyměnit(x0, y0)        vyměnit(x1, y1)    konec -li    -li x0 > x1 pak        vyměnit(x0, x1)        vyměnit(y0, y1)    konec -li        dx := x1 - x0    dy := y1 - y0    spád := dy / dx    -li dx == 0.0 pak        spád := 1.0    konec -li    // zpracovat první koncový bod    xend := kolo(x0)    napravit := y0 + spád * (xend - x0)    xgap := rfpart(x0 + 0.5)    xpxl1 := xend // toto bude použito v hlavní smyčce    ypxl1 := ipart(napravit)    -li strmý pak        spiknutí(ypxl1,   xpxl1, rfpart(napravit) * xgap)        spiknutí(ypxl1+1, xpxl1,  fpart(napravit) * xgap)    jiný        spiknutí(xpxl1, ypxl1  , rfpart(napravit) * xgap)        spiknutí(xpxl1, ypxl1+1,  fpart(napravit) * xgap)    konec -li    intery := napravit + spád // první průnik y pro hlavní smyčku        // zpracovat druhý koncový bod    xend := kolo(x1)    napravit := y1 + spád * (xend - x1)    xgap := fpart(x1 + 0.5)    xpxl2 := xend // toto bude použito v hlavní smyčce    ypxl2 := ipart(napravit)    -li strmý pak        spiknutí(ypxl2  , xpxl2, rfpart(napravit) * xgap)        spiknutí(ypxl2+1, xpxl2,  fpart(napravit) * xgap)    jiný        spiknutí(xpxl2, ypxl2,  rfpart(napravit) * xgap)        spiknutí(xpxl2, ypxl2+1, fpart(napravit) * xgap)    konec -li        // hlavní smyčka    -li strmý pak        pro X z xpxl1 + 1 na xpxl2 - 1 dělat           začít                spiknutí(ipart(intery)  , X, rfpart(intery))                spiknutí(ipart(intery)+1, X,  fpart(intery))                intery := intery + spád           konec    jiný        pro X z xpxl1 + 1 na xpxl2 - 1 dělat           začít                spiknutí(X, ipart(intery),  rfpart(intery))                spiknutí(X, ipart(intery)+1, fpart(intery))                intery := intery + spád           konec    konec -likonec funkce

Reference

  • Abrash, Michael (červen 1992). „Rychlé vyhlazování (sloupec)“. Dr. Dobb's Journal. 17 (6): 139(7).
  • Wu, Xiaolin (červenec 1991). „Efektivní technika vyhlazování“. Počítačová grafika (publikace). 25 (4): 143–152. doi:10.1145/127719.122734. ISBN  0-89791-436-8.
  • Wu, Xiaolin (1991). "Rychlá generace vyhlazených kruhů". V James Arvo (ed.). Grafické drahokamy II. San Francisco: Morgan Kaufmann. 446–450. ISBN  0-12-064480-0.

externí odkazy