Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 3 - Mandelbrotova množina

V minulé lekci, Plechovka aneb Flood fill či seed seed, jsme si ukázali algoritmus Flood fill, který určuje a mění oblast spojenou s daným uzlem ve vícerozměrném poli s některým shodným.

Na Mandelbrotovu množinu narazil Benoid Mandelbrot v 70. letech minulého století, při zkoumání Juliových množin. Pokoušel se sestavit jakýsi jejich katalog. Ale rozhodně nebyl jejím objevitelem. Ve stejné době (kousek před Mandelbrotem) byl na matematické konveci představen článek od Brookse a Matelskiho, který také obsahoval obrázky Mandelbrotovy množiny. Mandelbrot ji však důkladně popsal a prvenství připadlo jemu. Někteří z vás možná zaslechli zprávy o starodávné rytině přisuzované starodávnému umělci Udo von Aachenovi, která údajně obsahovala Mandelbrotovu množinu, schovanou v obrazu. Ty ale bohužel musím zklamat - jedná se samozřejmě o hoax :)

Ale teď k tomu, co to Mandelbrotova množina vlastně je. Je to fraktál ležící v komplexní rovině a to v rozmezí [-2;-2] do [2;2] (hranatými závorkami značím komplexní číslo). Je to zřejmě nejznamější fraktál vůbec. Je vyjádřena vzorcem Z = Z2 + C, kde Z a C jsou komplexní čísla. C je konstantní a je pozicí bodu, pro který koeficient Z počítáme. Z je na začátku [0;0]. Z budeme počítat iteračně, to znamená, že budeme výpočet Z = Z2 + C provádět tak dlouho, dokud nám nedojde námi stanovený počet pokusů (například 20) nebo se splní podmínka, že zkoušený bod neleží v množině. Tato podmínka zní: |Z| > 2 (absolutní hodnota Z je větší než 2). Pokud nám dojdou pokusy a podmínka se nesplnila, vybarvíme bod černě (bod do množiny patří). Pokud dojde k tomu, že |Z| > 2, bod obarvíme. Pro začátek ho můžeme obarvit třeba bíle. Pokud by jsme chtěli hezčí obrázek, můžeme bod vybarvit například modře a odstín určit podle toho, kolik pokusů bylo potřeba k tomu, aby jsme zjistili, že v množině neleží. Této variace jsem využil já. Potom tu je ještě řada palet (vzorců), pro ještě zajímavější obarvení.

Postup při vykreslení

Vzorec Z = Z2 + C musíme aplikovat na všechny body v množině. Ta je v rozsahu X od -2 do 2 a Y také od -2 do 2. Budeme tedy potřebovat 2 do sebe vnořené cykly a 2 celočíselné proměnné X a Y, ktere nám tyto body "projedou" (dle velikosti výřezu, např 0..799 a 0..599).

Určíme si nějaký počet pokusů (iterací) na vyzkoušení, jestli právě testovaný bod do množiny patří nebo nikoli. Vytvoříme tedy proměnnou nebo konstantu maxiter, které přiřadíme 20. Dále nějaké počítadlo pokusů, které si nazveme iter. K samotnému testu bodu budeme potřebovat komplexní číslo Z, které před každým pokusem vynulujeme, komplex. číslo C (reálná a imaginární část budou proměnné X a Y, protože C je pozice bodu v množině) a dále absolutní hodnotu Z a Z2.

Absolutní hodnota komplexního čísla Absolutní hodnotu komplexního čísla spočítáme použitím Pythagorovy věty, protože absolutní hodnota je vzdálenost čísla od nuly.
Čili :

Z ^2 = Z.r2 + Z.i2
Z = odmocnina(Z.r2 + Z.i2)

S vypočítáním druhé mocniny Z je to malinko složitější. Z2 můžeme vyjádřit jako součin Z * Z, čili součin dvou komplexních čísel, pro který platí obecný vzorec :

(A + Bi) * (C + Di)
AC + BCi + ADi + BDi2             (i2 = -1)
Re = AC - BD       (reálná část násobku)
Im = BCi + ADi       (imaginární část násobku)

V našem případě jsou hodnoty:
A = Z.r
B = Z.i
C = Z.r
D = Z.i

A po dosazení:
Re = Z.r2 - Z.i2
Im = Z.i * Z.r + Z.i * Z.r = 2 * Z.i * Z.r

Takže cykly X a Y projedeme všechny body množiny. Pro každý bod vynulujeme číslo Z, do C dosadíme [X;Y] a počítadlo iterací také vynulujeme. Spočítáme si Z2 (viz výše) a do Z dosadíme [Z2 + C]. Spočítáme si absolutní hodnotu Z a pokud je větší než 2, skončíme a bod obarvíme příslušnou barvou. Pokud ne, zvýšíme iter o jedna a jedeme znovu. Pokud vyplýtváme všechny pokusy a podmínka se stále nesplní, obarvíme bod černě.

Výsledek se základním obarvením vypadá asi takto:

mandelbrotova množina - Grafické algoritmy

Zdrojový kód a ukázkový program

Můžete se podívat na ukázkový program Mandelbroth včetně zdrojového kódu

V další lekci, Optimalizace vykreslování ve 2D hrách, si ukážeme optimalizaci vykreslování ve 2D hrách aneb návod jak zvýšit FPS a výkon.


 

Předchozí článek
Plechovka aneb Flood fill či seed seed
Všechny články v sekci
Grafické algoritmy
Přeskočit článek
(nedoporučujeme)
Optimalizace vykreslování ve 2D hrách
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
10 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity