Používá floaty, což je pomalé. Princip stejný jako ECDDA, akorát nevyužívá error, ale zaokrouhluje y na nejbližší celé číslo.
Algoritmus funguje pro jeden směr „rychlejší“, než druhý – vzdálenost bodů na jedné ose je větší nebo stejná než na druhé. Řekněme, že úsečka vede převážně zleva doprava a pomalu stoupá. Pak je rychlejší směr po ose X. To znamená, že v každém kroku algoritmu se posuneme vždy o 1 pixel doprava a zbývá akorát zjistit, jestli se zároveň budeme posouvat i po ose Y.
Vypočítáme si poměr délky úsečky v pomalém směru oproti rychlému (y2−y1)/(x2−x1) a označíme ho delta
. Ta vyjadřuje, o kolik se v každém kroku posune skutečná úsečka po pomalejší ose. Protože máme však k dispozici pixely o určite velikosti, musíme počkat, až se úsečka posune o dostatečný kus po rychlejší ose, než se můžeme po pomalejší posunout. Zavedeme si proměnnou error
a nastavíme ji na 0. Poté v každém kroku zvyšujeme error
o delta
. Pokud nastane error
> 0.5, odečteme od error
jedničku a posuneme se o pixel na ose Y.
The Bresenham Line-Drawing Algorithm, by Colin Flanagan
Jde o výkonný algoritmus, který nepoužívá floating-point aritmetiku. Toho je docíleno, že obě strany nerovnice porovnávající error a 0,5 vynásobíme výrazem 2Δx. Následně převedeme vše na jednu stranu, výsledek označíme jako prediktor a porovnáváme jej s 0. Pokud je prediktor menší než 0, navýšíme ho o 2Δy. Pokud je větší nebo roven 0, zvýšíme y o 1 (posuneme se o pixel) a přičteme k prediktoru 2Δy − 2Δx.
LineBres(int x1, int y1, int x2, int y2) { int dx = x2 - x1, dy = y2 - y1; int P = 2 * dy - dx; int P1 = 2 * dy, P2 = P1 - 2 * dx; int y = y1; for (int x = x1; x <= x2; x++) { draw_pixel(x, y); if (P >= 0) { P += P2; y++; } else { P += P1; } } }
Vychází se z rovnice pro kružnici: x² + y² = r². Každý bod kružnice by se dal počítat klasicky přes dosazaní jedné souřadnice a počítání druhé, jenže tam by se musela počítat odmocnina, což je výpočetně celkem náročné. Proto vznikla iterativní metoda midpoint, která nemusí počítat odmocninu.
Podobně jako u Bresenhama je potřeba definovat „rychlejší“ směr. Taková část kružnice se nachází například v 1. kvadrantu do úhlu 45°. Kružnici proto kreslíme pro tento úsek – zbytek kružnice je získány zrdcadlením tohoto úseku. Začneme v bodě [0, r]. Určíme tedy jako rychlejší osu X, protože kružnice v tomto úseku jde rychleji doprava, než se pohybuje dolů. V každém kroku se tedy posouváme o 1 pixel doprava, o posunu po ose Y rozhoduje prediktor. Končíme, pokud X = Y.
Tohle je trochu zábavnější než úsečka. Vpodstatě vezmeme aktuální X a Y a počítáme pro X+1 a Y−½ hodnotu r². Pokoušímě se tímto posunout se po ose Y o polovinu pixelu (správným směrem). Výsledek je umocněný poloměr kružnice, která tímto bodem prochází. Odečteme r² naší vykreslované kružnice. Pokud byla vypočítaná kružnice větší nebo stejná jako vykreslovaná, vyjde číslo nižší než 0. Znamená to, že naše kružnice je už pro toto X níž nebo stejně vysoko jako půlka pixelu, takže se posuneme o pixel dolů. V opačném případě zůstáváme.
Odvození vzorce pro prediktor je: dosadíme do rovnice kružnice Xi+1 a Yi−½ a převedeme r² na levou stranu.
Tady to však nekončí - chceme, abychom nemuseli pokaždé prediktor počítat a zároveň nechceme pracovat s floating-point aritmetikou. Proto odvodíme rekurentní prediktor, který tomu bude vyhovovat. Rekurentní prediktor = získání příštího prediktoru z aktuální hodnoty.
Pokud prediktor v kroku i spočítáme jako <m>({x_i + 1})^2 + ({y_i - 1/2})^2 - R^2</m>, jeho další krok je spočítaný úplně stejně, jen s jinými indexy u x a y. Stačí nám tedy najít rozdíl. Pokud je prediktor v aktuálním kroku menší než 0, posouváme se pouze po ose X a další prediktor se tedy mění pouze v části <m>({x_i + 1})^2</m> a to konkrétně o <m>+ 2x_i + 3</m>. Pokud je prediktor větší než 0, mění se i v části s y a to konkrétně o <m>+ 2x_i - 2y_i + 5</m>. Zkuste si to dosadit a uvidíte…
No a protože je počáteční hodnota prediktoru 1-R (dosazením bodu [0, R] do rovnice prediktoru) a rozdíly v prediktoru jsou celočíselné, nemusíme pracovat s floating-point aritmetikou.
Požadované vlastnosti křivek:
Křivky se dají rozdělit na:
Je určena dvěma koncovými body a dvěma tečnými vektory. Pokud na sebe chceme tyto segmenty navazovat, musí mít společné koncové body a tečné vektory (samozřejmě ale v opačném směru).
Interpolační spline křivka. Pro interpolaci využívá Fergusonových kubik. Určeno množinou N interpolovaných bodů Pi a odpovídajícími koeficienty ai, bi a ci.
Význam koeficientů:
Interpolační spline, často v praxi používaný. Nesplňuje ale požadavky na konvexní obálku a interpolaci krajních bodů (takže musíme přidat bod před začátek a konec). Tečný vektor řídícího bodu je rovnoběžný s průsečíkem dvou okolních bodů. Je to vlastně Kochanek–Bartels s nulovými koeficienty.
Aproximační křivka. Používá Bernsteinovy polynomy, křivku stupně n určuje n + 1 bodů.
Prvním krokem je postupné spojení kontrolních bodů (první s druhým, druhý se třetím, …). Každou úsečku pomyslně rozdělíme na tolik kroků, kolik bodů má mít výsledná křivka. Podle délky kroku bude výsledná křivka plynulá nebo hranatá. Potom postupně v každém kroku vezmeme další z těchto kroků na každé úsečce a vybrané body spojíme opět popořadě novými úsečkou. Tím nám vznikne polygon, který má o jeden kontrolní bod méně, než původní řídící polygon. Na tomto novém polygonu celý proces opakujeme. Postupujeme rekurzivně tak dlouho, dokud nezbyde jen jeden bod, který vykreslíme. Algoritmus se provádí nad celou křivkou, takže nesplňuje lokalitu změn.
Aproximační polynomiální křivka, která prochází koncovými body. Křivka stupně n je určena n + 1 body. Je definována Bernsteinovými polynomy, které se dají definovat i rekurentně, čehož se využívá pro algoritmus de Casteljau. Bernsteinovy polynomy mají vždy nezápornou hodnotu, mají jednotkový součet – křivka leží v konvexní obálce.
Používají racionální polynomy R. Tyto polynomy jsou váženým průměrem Bernsteinových polynomů. Pro jejich vykreslení nelze použít algoritmus de Casteljau (nejsou rekurentně zapsané). Křivka leží v konvexní obálce.
Beziérova kubika je tvořená 4 řídícími body, která vychází z teorie Beziérových křivek. Pro spojování Beziérových kubik je třeba si pamatovat pravidlo, že koncový bod prvního úseku musí být středem úsečky mezi předposledním bodem prvního úseku a druhým bodem druhého úseku. Laicky řečeno – každý oblouk je tvořen čtyřmi body, pokud navazují oblouky za sebou, tak mají vždy 1 bod společný. Pro stejnou křivku jako reprezentuje druhý animovaný obrázek (2 oblouky) je proto třeba 7 řídicích bodů (1 je společný pro obě křivky – je to vlastně inflexní bod).
Aproximační křivka, která neprocházi koncovými řídícími body. Křivka stupně n je určena n + 1 řídícími body. S křivkou pracujeme po segmentech, nelze přidat jeden bod, jen celý segment. Segment je kubika, takže má 4 body.
Zobecnění Coonsových křivek. Křivka je určena n + 1 body a má spojitost k + 1, kde k je stupeň křivky. Její polynomy mají nezápornou hodnotu a jednotkový součet – křivka leží v konvexní obálce. Při dělení 0 je výsledek 0. Vykreslování probíhá algoritmem de Boor, což je obdoba de Casteljau. Uzlový vektor představuje hodnoty parametru t v uzlech, čímž umožňuje lokální změnu tvaru křivky.
V praxi se používá, asi by bylo dobrý o něm něco víc napsat. (pořád je to docela málo)
Zobecnění B-spline. Je racionální, takže uzly mají váhy. Je invariantní vůči lineárním transformacím.