Rasterizace objetů #2: Bresenhamův algoritmus

Rasteriace je proces, při kterém převádíme základní grafické objekty do systému posloupnosti obrazových bodů. Toto je důležité při práci s různými výstupními zařízeními, které nejsou schopny zobrazit přesně daný objekt, ale při svém zobrazení používají rastr.

V minulém článku jsme si řekli o DDA algoritmu, v tomto, druhém pokračování, se podíváme na Bressahamův algoritmus pro generování úsečky.

Breansshamův algoritmus funguje na principu hledání nejbližších bodů, které leží k úsečce. Mějme bod, jehož souřadnice jsou Xi a Yi. Bod representuje počáteční bod úsečky, kterou se snažíme vykreslit.

Víme že úsečka pokračuje doprava směrem nahoru, takže je jasné, že souřadnice X _i+1 bude o hodnotu 1 větší, ale souřadnici Y _i+1 neznáme. V podstatě máme dvě možnosti, který ze dvou bodů zvolit. Můžeme volit bod, který je shodný s bodem Yi, nebo můžeme volit bod Y _{i + 1} :

[X
i+1
, Y
i
] nebo [X
i+1
, Y
i+1
]

Jak je vidět na obrázku, bod, který leží blíže úsečky můžeme určit pomocí hodnot d1 a d2:

Δd = d
1
 – d
2

Pokud d < 0: hodnota následujícího pixelu je Y _i
Pokud d > 0: hodnota následujícího pixelu je Y _i+1

m =   ΔY/ ΔX
b = ((X2*Y1) – (X1*Y2))/(X2-X1)
d
1
 = m (x
i + 1
) + b - yi
d
2
 = y
i + 1
 - m (x
i + 1
) - b

Iteračním způsobem můžeme počítat hodnoty další souřadnice:

k =   Δx/ Δ y
e1 = 2  Δy -  Δx

Pro ei+1 platí:

e
i
 > 0 : e
i+1
 = e
i
 + 2 Δy - 2 Δx
ei 
<= 0: ei + 1 = ei + 2 Δy

Zdrojový kód v jazyce java může vypadat například takto:

public static void line(int x1,int y1,int x2, int y2 ) {
    int w = x2 - x1;
    int h = y2 - y1;
    int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0 ;
    if (w
<0)
        dx1 = -1;
    else if (w>0)
        dx1 = 1;
    if (h
<0)
        dy1 = -1;
    else if (h>0)
        dy1 = 1;
    if (w
<0)
        dx2 = -1 ;
    else if (w>0)
        dx2 = 1 ;
    int longest = Math.abs(w);
    int shortest = Math.abs(h);
    int numerator = longest >> 1;
    for (int i=0;i
<=longest;i++){
        System.out.println(x1 + " " + y1);
        numerator += shortest;
        if (!(numerator > longest)) {
            numerator -= longest;
            x1 += dx1;
            y1 += dy1;
        } else {
            x1 += dx2;
            y1 += dy2;
        }
    }
}

Závěrem:

Oproti DDA algoritmu nabízí Bresenhamův algoritmus velké zrychlení, co do počítání souřadnic pro výpis hodnot.

Velkou výhodou, kterou nám Breasshamův algoritmus umožňuje, je snadný převod do celočíselné aritmetiky, který velmi zjednodušuje výpočty.