© 2013 All rights reserved.
3

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.


breasshem alg.

Víme že úsečka pokračuje doprava směrem nahoru, takže je jasné, že souřadnice Xi+1 bude o hodnotu 1 větší, ale souřadnici Yi+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 Yi + 1:

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

Pokud d < 0: hodnota následujícího pixelu je Yi

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

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

Pro ei+1 platí:

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


Zdrojový kód převzat: http://tech-algorithm.com/index.php?post=30

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.

Comments (3)

A co výběr řídící osy?

Hello there! Quick question that’s totally off topic. Do you know how to make your site mobile friendly? My site looks weird when viewing from my iphone 4. I’m trying to find a theme or plugin that might be able to resolve this problem. If you have any suggestions, please share. Many thanks!|

Oh my goodness! Amazing article dude! Thank you so much, However I am going through issues with your RSS. I don know the reason why I can’t subscribe to it. Is there anyone else getting the same RSS problems? Anyone who knows the solution will you kindly respond? Thanks!!

Add comment

About
Hi, i am programmer from the Czech Republic. I love web development (Ruby, Ruby on Rails, PHP, Nette) and iOS development (Objective-C, Cocoa).
To cooperate, here is my phone:
+420 608 836