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 = Z² + 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 = Z² + 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 = Z² + 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 Z².

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 :

S vypočítáním druhé mocniny Z je to malinko složitější. Z² 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 + BDi²             (i² = -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.r² - Z.i²
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 Z² (viz výše) a do Z dosadíme [Z² + 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:

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.