Bresenhamův algoritmus je způsob kreslení čar do rastru tak, aby se vytvořil co nejlepší dojem úsečky mezi dvěma body. Běžně se používá ke kreslení čárových primitiv v bitmapovém obrazu (např. na obrazovce počítače), protože používá pouze celočíselné sčítání, odčítání a posun bitů, což jsou v běžných počítačových architekturách velmi rychlé operace. Jedná se o algoritmus pro inkrementální chyby a jeden z prvních algoritmů vyvinutých v oblasti počítačové grafiky. Na kreslení kružnic, elips a Beziérových křivek se používají algoritmy Aloise Zingla, pohrát si s nimi můžete zde.
Metoda
Budou použity následující konvence:
-
Počátek souřadnicového systému (bod [0,0]) je vlevo nahoře.
-
Souřadnice x se zvyšuje doprava a souřadnice y se zvyšuje dolů.
-
Středy pixelů mají celočíselné souřadnice.
Koncové body čáry jsou pixely \((x_0,y_0)\) a \((x_1,y_1)\). První souřadnice dvojice x je sloupec a druhá souřadnice y je řádek.
Algoritmus bude zpočátku ukázán pouze v oblasti, kde úsečka jde dolů a doprava \(x_0 \le x1\) a \(y_0 \le y_1\) a její vodorovná projekce je delší než její svislá projekce \(x_1-x_0 > y_1-y_0\). To znamená, že směrnice přímky (sklon) je menší než 1.
| Je to trochu jinak, než se učíme v matematice. Tam kladná osa y jde nahoru. Ale zvyknete si. |
V této oblasti existuje pro každý sloupec \(x\) mezi \(x_0\) a \(x_1\) přesně jeden řádek \(y\) (vypočítaný algoritmem) obsahující pixel dané čáry, zatímco každý řádek mezi \(y_0\) a \(y_1\) může obsahovat více rastrových pixelů.
Bresenhamův algoritmus vybírá celé číslo y odpovídající středu pixelu, který je nejblíže ideálnímu (zlomkovému) y pro stejné x; v po sobě jdoucích sloupcích může y zůstat stejné nebo se zvýšit o 1. Obecná rovnice přímky procházející koncovými body je dána vztahem:
Protože známe soupec x, řádek y pixelu je dán zaokrouhlením této hodnoty na nejbližší celé číslo:
Sklon \(\frac{y_1-y_0}{x_1-x_0}\) závisí pouze na souřadnicích koncových bodů a lze jej předem vypočítat. Ideální y pro po sobě jdoucí celočíselné hodnoty x lze vypočítat od \(y_0\) opakovaným přidáváním sklonu.
V praxi algoritmus nesleduje souřadnici y, která se zvětšuje o \(m = \frac{\Delta y}{\Delta x}\) pokaždé, když se x zvětší o jedna, ale v každé fázi udržuje hranici chyby err, která představuje zápornou hodnotu vzdálenosti od (a) bodu, kde čára opouští pixel, do (b) horního okraje pixelu.
Tato hodnota je nejprve nastavena na \(y_0 - 0.5\) (kvůli použití středových souřadnic pixelu) a pokaždé, když se souřadnice x zvýší o jedna, se zvýší o m. Pokud je chyba větší než 0.5, víme, že se čára posunula o jeden pixel nahoru a že musíme zvýšit naši souřadnici y a chybu znovu upravit tak, aby reprezentovala vzdálenost od vrcholu nového pixelu –- což se provede odečtením jedničky od chyby.
Odvození alogoritmu
Pro odvození Bresenhamova algoritmu je třeba provést dva kroky. Prvním je transformace rovnice přímky z typického tvaru \(y=k\cdot x + t\) do obecného tvaru \(A\cdot x + B\cdot y + C = 0\) a poté tuto rovnici použít k nakreslení přímky na základě myšlenky akumulace chyby.
Rovnice přímky
Rovnice přímky ve směrnicovém tvaru se zapisuje jako:
kde m je sklon a b je průsečík s osou y. Protože je to funkce jedné proměnné x, nemůže pomocí ní popsat svislou čáru. Je proto užitečné zapsat tuto rovnici jako funkci dvou proměnných \(f(x,y)\), kdy můžeme kreslit čáry pod libovolným úhlem k ose x. Sklon, či směrnici m lze vyjádřit jako \(\frac{\Delta y}{\Delta x}\). Potom pomocí algebraických operací dostaneme:
Tato poslední rovnice je funkcí x a y a můžeme ji zapsat jako
kde jsou konstanty
-
\(A = \Delta y = y_1 - y_0\)
-
\(B = -\Delta x = -(x_1-x_0)\)
-
\(C = (\Delta x)b = ( x_1 - x_0)b\)
Přímka je definována pro některé konstanty \(A,B,C\) kdekoli je \(f(x,y) = 0\). To znamená, že pro jakékoliv x a y mimo přímku je \(f(x,y) \ne 0\) Jestliže konstanty \(A,B,C\) jsou celá čísla, potom i y a x budou celá čísla.
Například přímku definovanou rovnicí \(y = \frac{1}{2}x+1\) můžeme zapsat v obecném tvaru:
Bod [2,2] leží na této přímce.
Zatímco bod [2,3] na teto přímce neleží.
Stejně tak bod [2,1] také neleží na přímce.
Všimněte si, že body [2,1] a [2,3] jsou na opačných stranách přímky a hodnota funkce stem[f(x,y)] je kladná nebo záporná. Přímka rozděluje celou rovniu na dvě části. Polorovnina kde \(f(x,y) < 0\) se nazývá záporná polorovina a polorovina kde \(f(x,y) > 0\) se nazývá kladná polorovina.
Tento poznatek je velmi důležitý při zbytku odvození algoritmu.
Algoritmus
Počáteční bod úsečky budiž:
protože úsečka musí být definována tak, aby začínala a končila na celočíselných souřadnicích.
Víme, že sklon musí být menší než 1, takže další bod by měl být buď \((x_0+1,y_0)\) nebo \((x_0+1,y_0+1)\). Intuitivně, další bod bychom měli zvolit ten, který je blíže přímce v bodě \((x_0+1)\). Je-li blíž první, zvolíme jej, jinak bereme druhý. Zjistíme to tak, že spočítáme hodnotu funkce v prostředním bodě mezi těmito dvěma body:
Pokud je hodnota funkce kladná, pak je ideální přímka pod středem a blíže požadovaného bodu \((x_0+1,y_0+1)\) a souřadnice y by se měla zvětšit. Jinak ideální přímka prochází středem nebo nad ním a souřadnice y by měla zůstat stejná. V tomto případě vybíráme bod \((x_0+1,y_0)\). Čili hodnota funkce ve středním bodě určuje, který kandidátský bod se vybere.
Obrázek ukazuje modrý bod (2,2) na přímce a za ním dva zelené kandidátské body (3,2) a (3,3). Černý bod (3, 2.5) je středem mezi těmito dvěma kandidátskými body.
Algoritmus pro celočíselnou aritmetiku
Alternativně lze namísto vyhodnocování funkce \(f(x,y)\) ve středových bodech použít rozdíl mezi body. Tato alternativní metoda umožňuje pouze celočíselnou aritmetiku, která je obecně rychlejší než použití aritmetiky s plovoucí desetinnou čárkou. Pro odvození druhé metody definujeme rozdíl takto:
Pro první rozhodnutí je tato formulace ekvivalentní metodě středního bodu, protože v počátečním bodě \(f(x_0,y_0) = 0\). Zjednodušením tohoto výrazu získáme:
Stejně jako v metodě střeního bodu, pokud \(D_0 \gt 0\), pak se vybere bod \((x_0+1, y_0+1)\), jinak se zvolí bod \((x_0+1,y_0)\).
Pokud je zvolen bod \((x_0+1,y_0)\), pak změna v \(D_i\) bude:
Pokud je zvolen bod \((x_0+1,y_0+1)\), pak změna v \(D_i\) bude:
Je-li rozdíl kladný, potom další bod bude \((x_0+2,y_0+1\), jinak \(x_0+2,y_0\). Tento postup lze zobecnit akumulací chyby v každém následujícím bod;.
Odvození algoritmu je nyní hotové. Jeden drobný problém máme v tom, že na počátku máme ve výpočtu \(D = ...\) zlomek \(\frac{1}{2}\). Protože se to však týká znaménka akumulovaného rozdílu, můžeme vše vynásobit 2 bez jakýchkoliv následků.
Výsledkem je algoritmus, který používá pouze celočíselnou aritmetiku,
plotLine( x0, y0, x1, y1)
dx = x1 - x0
dy = y1 - y0
D = 2*dy - dy
y = y0
for x from x0 to x1
plot(x,y)
if( D > 0 )
y = y + 1
D = D - 2xdx
endif
D = D + 2*dySpustíme tento algoritmus pro \(f(x,y) = x - 2y + 2\) z bodu (0,1) do bodu (6,4) a dostaneme rozdíly dx=6 a dy=3:
D=2*3-6=0
Loop from 0 to 6
* x=0: plot(0, 1), D≤0: D=0+6=6
* x=1: plot(1, 1), D>0: D=6-12=-6, y=1+1=2, D=-6+6=0
* x=2: plot(2, 2), D≤0: D=0+6=6
* x=3: plot(3, 2), D>0: D=6-12=-6, y=2+1=3, D=-6+6=0
* x=4: plot(4, 3), D≤0: D=0+6=6
* x=5: plot(5, 3), D>0: D=6-12=-6, y=3+1=4, D=-6+6=0
* x=6: plot(6, 4), D≤0: D=0+6=6a výsledek je vidět na obrázku. Modré vypočtené body jsou totéž co na obrazovce žluté čtverečky.
Všechny případy
Jak je však uvedeno výše, toto funguje pouze pro oktant nula, tj. pro čáry začínající v počátku souřadné soustavy se sklonem mezi 0 a 1, kde x se zvyšuje přesně o 1 na iteraci a y se zvyšuje o 0 nebo 1.
Algoritmus lze rozšířit tak, aby pokrýval sklony mezi 0 a -1, a to kontrolou, zda je třeba y zvýšit nebo snížit (tj. dy < 0).
plotLine(x0, y0, x1, y1)
dx = abs(x1 - x0)
sx = x0 < x1 ? 1 : -1
dy = -abs(y1 - y0)
sy = y0 < y1 ? 1 : -1
error = dx + dy
while true
plot(x0, y0)
e2 = 2 * error
if e2 >= dy
if x0 == x1 break
error = error + dy
x0 = x0 + sx
end if
if e2 <= dx
if y0 == y1 break
error = error + dx
y0 = y0 + sy
end if
end whilePřepnutím os x a y lze implementaci pro kladné nebo záporné strmé sklony zapsat jako:
plotLineHigh(x0, y0, x1, y1)
dx = x1 - x0
dy = y1 - y0
xi = 1
if dx < 0
xi = -1
dx = -dx
end if
D = (2 * dx) - dy
x = x0
for y from y0 to y1
plot(x, y)
if D > 0
x = x + xi
D = D + (2 * (dx - dy))
else
D = D + 2*dx
end ifKompletní řešení by muselo zjistit, zda x1 > x0 nebo y1 > y0, a před vykreslením obrátit vstupní souřadnice, tedy:
plotLine(x0, y0, x1, y1)
if abs(y1 - y0) < abs(x1 - x0)
if x0 > x1
plotLineLow(x1, y1, x0, y0)
else
plotLineLow(x0, y0, x1, y1)
end if
else
if y0 > y1
plotLineHigh(x1, y1, x0, y0)
else
plotLineHigh(x0, y0, x1, y1)
end if
end ifV nízkoúrovňových implementacích, které přistupují k videopaměti přímo, by bylo typické, že se speciální případy svislých a vodorovných čar řeší odděleně, protože je lze vysoce optimalizovat.
Některé verze používají Bresenhamovy principy celočíselné inkrementální chyby k provádění všech kreslení oktantových čar, přičemž vyvažují kladnou a zápornou chybu mezi souřadnicemi x a y. Viz Alois Zingl: Rasterizační alogoritmus pro kreslení křivek.
plotLine(x0, y0, x1, y1)
dx = abs(x1 - x0)
sx = x0 < x1 ? 1 : -1
dy = -abs(y1 - y0)
sy = y0 < y1 ? 1 : -1
error = dx + dy
while true
plot(x0, y0)
e2 = 2 * error
if e2 >= dy
if x0 == x1 break
error = error + dy
x0 = x0 + sx
end if
if e2 <= dx
if y0 == y1 break
error = error + dx
y0 = y0 + sy
end if
end whileKonkrétní implementace
void drawLine(int x0, int y0, int x1, int y1, unsigned int color)
{
int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
int dy = -abs(y1-y0), sy = y0<y1 ? 1 : -1;
int err = dx+dy, e2; /* error value e_xy */
for(;;){ /* loop */
drawPixel(x0, y0, color);
if (x0==x1 && y0==y1) break;
e2 = 2*err;
if (e2 >= dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */
if (e2 <= dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */
}
}function bline(x0, y0, x1, y1) {
var dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
var dy = Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
var err = (dx>dy ? dx : -dy)/2;
while (true) {
setPixel(x0,y0);
if (x0 === x1 && y0 === y1) break;
var e2 = err;
if (e2 > -dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
}
}#define swap(a, b) { short t = a; a = b; b = t; }
void drawLine(short x0, short y0, short x1, short y1, char color) {
/* Draw a straight line from (x0,y0) to (x1,y1) with given color
* Parameters:
* x0: x-coordinate of starting point of line. The x-coordinate of
* the top-left of the screen is 0. It increases to the right.
* y0: y-coordinate of starting point of line. The y-coordinate of
* the top-left of the screen is 0. It increases to the bottom.
* x1: x-coordinate of ending point of line. The x-coordinate of
* the top-left of the screen is 0. It increases to the right.
* y1: y-coordinate of ending point of line. The y-coordinate of
* the top-left of the screen is 0. It increases to the bottom.
* color: 3-bit color value for line
*/
short steep = abs(y1 - y0) > abs(x1 - x0);
if (steep) {
swap(x0, y0);
swap(x1, y1);
}
if (x0 > x1) {
swap(x0, x1);
swap(y0, y1);
}
short dx, dy;
dx = x1 - x0;
dy = abs(y1 - y0);
short err = dx / 2;
short ystep;
if (y0 < y1) {
ystep = 1;
} else {
ystep = -1;
}
for (; x0<=x1; x0++) {
if (steep) {
drawPixel(y0, x0, color);
} else {
drawPixel(x0, y0, color);
}
err -= dy;
if (err < 0) {
y0 += ystep;
err += dx;
}
}
}