Rasterizace úsečky pomocí Bresenhamova algoritmu – applet

Při rasterizaci rozhodujeme, který pixel nejblíže ležící teoretické úsečce vybereme, abychom dostali co možná nejlepší vizuální výsledek. Protože nejmenším bodem v bitmapové počítačové grafice na daném zobrazovacím zařízení je pixel, výstupem z algoritmu by měly být celočíselné souřadnice vybraných pixelů. Jednoduchý algoritmus kreslící body nejbližší úsečce se nazývá DDA. J. E. Bresenham vyvinul algoritmus, který dává shodný výsledek, ale narozdíl od DDA používá celočíselné aritmetiky, čímž dosahuje vyšší efektivity. Rychlost vykreslení úsečky je přitom klíčová, protože v praxi nahrazujeme složitější útvary sérií mnoha úseček.

Reset - +

Teorie k rasterizaci úsečky

Vyjdeme z obecné rovnice přímky

rovnice 1

kde m je směrnice a b posun na ose y. Jinak psáno

rovnice 2

kde [x1, y1] a [x2, y2] jsou koncové body úsečky (předpokládáme je celočíselné).
Předpokládejme, že je již nakreslen bod o souřadnicích [xi, yi]. Dále uvažujme, že tzv. řídicí osa je x, tedy úsečka má směrnici odpovídající úhlu 0 až 45 stupňů. V dalším kroku n + 1 máme na výběr ze dvou souřadnic, a to [xi + 1, yi] nebo [xi + 1, yi + 1]. Definujeme si dvě proměnné d1 a d2, což jsou vertikální vzdálenosti teoretického bodu na přímce od celočíselných souřadnic.

rovnice 3

Rozdílem vzdáleností d1 a d2 získáme rozhodovací prvek algoritmu:

rovnice 4

Nyní jsme schopni rozhodnout, který z možných pixelů leží blíže y-ové souřadnici skutečného bodu. Nezáleží nám přitom na velikosti delta d, ale pouze na jejím znaménku. Je-li hodnota delta d záporná, leží blíž pixel se souřadnicí yi, kladná hodnota značí, že blíž leží pixel o souřadnici yi + 1. Tento postup je výhodný pro převod výpočtu do celočíslené aritmetiky.

Ovládání appletu

Tlačítky plus a minus můžeme měnit velikost pixelu, a to je možné jak před, tak i po zadání řídicích bodů. Pokud jsme již zadali body a rozhodneme se měřítko změnit, automaticky se úsečka zobrazí v novém měřítku. Zbývá tlačítko reset, které nám umožní zvolit dva nové koncové body pro vykreslení jiné úsečky v základní velikosti pixelu. Nemusíme však body vždy znovu a znovu zadávat, můžeme editovat jejich polohu kliknutím na daný bod a tažením myši. Při puštění levého tlačítka myši bod umístíme. Rasterizace probíhá průběžně při každé změně bodů.

Modrá čára, zobrazuje teoretickou úsečku, která začíná a končí na celočíselných souřadnicích. Červená čára propoje body, které jsme zadali myší. Applet tedy zároveň ukazuje chybu, která nastává díky zaokrouhlení koncových bodů.


(c) 2019 Matúš Lipa, Pavel Rajmic, Ústav telekomunikací, FEKT, VUT v Brně