První série třicátého třetího ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Dostává se k vám první číslo hlavní kategorie 33. ročníku KSP.

Letos se můžete těšit v každé z pěti sérií hlavní kategorie na: 4 normální úlohy, z toho alespoň jedna praktická opendatová. Také na grafický seriál a kuchařky na nějaké zajímavé informatické témata, hodící se k úlohám dané série. Občas se nám také objeví bonusová X-ková úloha, za kterou lze získat X-kové body.

Oproti loňskému ročníku se do výsledkové listiny započítávají všechny úlohy a body se již nepřepočítávají podle počtu vyřešených sérií.

Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.

Odměny & na Matfyz bez přijímaček

Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň 50 % bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, pokud chcete prominutí využít letos, musíte to stihnout do konce čtvrté série, pátá už bude moc pozdě. Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, placku a možná i další překvapení.

Zadání úloh

Letos nebudou mít úlohy žádný velký spojující příběh, na který jste mohli být zvyklí z minulých let. Namísto toho budou mít jednotlivé úlohy své vlastní malé příběhy. Snad se vám budou líbit :)

Praktická opendata úloha33-1-1 Prosperující provincie (10 bodů)

Kevin si z dlouhé chvíle listuje historickou knihou. Vypozoroval, že existovaly říše, které ovládaly provincie. Kontrola provincíí se měnila historickými událostmi.

Historické události lze rozdělit do čtyř typů:

Je zaručeno, že každá provincie zanikne (ať už katastrofou, nebo zničením říše) a každá říše se buď stane součástí jiné říše, nebo bude v průběhu dějin zničena.

V provincii je možné civilizovaně žít od jejího osídlení do jejího zničení. Kevina by zajímalo, v jaké provincii se dalo civilizovaně žít co možná nejdéle (kdyby náhodou objevil stroj času a chtěl se někam přestěhovat).

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku vstupu bude počet říší R, počet provincií P a počet událostí N, říše i provincie indexujeme od jedničky. Na dalších N řádcích následují popisy událostí. Na každém řádku s událostí je nejprve rok (celé kladné číslo) a jednopísmenná zkratka typu události. V závislosti na typu události pak mohou následovat další elementy:

Události nejsou žádným specifickým způsobem seřazeny. V jeden rok může nastat nejvýše jedna událost.

Formát výstupu: Výstupem je číslo provincie, v niž se dá nejdéle civilizovaně žít, a délka tohoto období v letech. Pokud má úloha více správných odpovědí, stačí vypsat libovolnou z nich.

Ukázkový vstup: 
2 3 6
4 K 1
2 O 2 1
5 P 2 1
3 O 3 2
6 Z 2
1 O 1 1
Ukázkový výstup: 
2 4

Jednoduchá úlohaSlibujeme, že v prvních několika vstupech nebudou žádné katastrofy.

Řešení

Teoretická úloha33-1-2 Kuchyňská prkénka (11 bodů)

Kevinův strýček truhlář vyrábějící kuchyňská prkénka se jednou rozhodl, že aby ušetřil, tak si koupí jedno dlouhé prkno o délce N centimetrů. To pak chtěl rozřezat na malá prkénka délky D centimetrů, která pak prodává po K korunách.

Koupené velké prkno ovšem obsahuje vady. Vady se sice dají opravit (například zbrousit, zalepit suky a podobně), ovšem opravy nejsou zdarma. Pro každý centimetr proto truhlář určil cenu, za kterou ho lze opravit. Ovšem neví si rady s tím, které části opravit a jak pak velké prkno nařezat na jednotlivá prkénka. Žádá vás tedy o pomoc, jak to udělat, aby měl nejvyšší výdělek.

Na vstupu dostanete N – délku celého prkna, D – délku požadovaných prkének a K – počet peněz, co si vydělá za jedno prkénko. Pak dostanete N přirozených čísel vyjadřujících, za jakou cenu je možné opravit jednotlivé centimetry z prkna (v případě, že je daná část v pořádku, tak je to nula). Prkno je možné řezat pouze v celočíselných vzdálenostech.

Vašim úkolem je vymyslet algoritmus, který pro daný vstup odpoví, jakou největší částku si může truhlář vydělat (prkno má již koupené, to nepočítejte).

Ukázkový vstup: 
4 2 5
10 1 2 3
Ukázkový výstup: 
2

V tomto případě z prkna vyrobíme jen jedno prkénko délky dva uprostřed (na místech s cenou opravy 1 a 2).

Ukázkový vstup: 
7 1 7
1 6 8 2 3 7 1
Ukázkový výstup: 
22

Tady vyrobíme prkénko délky jedna z každé pozice, kde jde cena za opravu nižší, než 7.

Řešení

Praktická opendata úloha33-1-3 Laser v bludišti (12 bodů)

Ve výzkumném centru LIGO, kde se pomocí laserů měří gravitační vlny, bylo zemětřesení. Všechna zrcadla na odrážení laseru se náhodně pootáčela. Zrcadla jsou ale velmi těžká a křehká, takže je jejich otáčení velmi energeticky náročné. Protože rozpočet na výzkum je omezený granty, vědci musí zjistit jak za co nejméně energie pootáčet zrcadla, aby se laserový paprsek poodrážel ze zdroje do cíle.

Na vědeckém pracovišti se mohou nacházet následující čtyři druhy předmětů:

Číslo na políčku se zrcadlem určuje jeho orientaci. 0 je orientace zrcadlovou plochou nahoru. Pokud číslo o jedna zvětšíme, zrcadlo se otočí o 45 stupňů podle hodinových ručiček. Zrcadlo odráží paprsky pouze z jedné strany, ta druhá je pohlcuje. Otočení zrcadla o libovolný násobek 45 stupňů stojí jednu jednotku energie. Platí, že úhel dopadu se rovná úhlu odrazu. Pokud je plocha zrcadla rovnoběžná s laserem, paprsek zrcadlo mine a políčkem projde jako by to byl vzduch.

Laser ze zdroje vychází vždy směrem nahoru. Skrz zdroj ale laser neprosvítí a zastaví se stejně jako o zeď. Je jedno, ze které strany přijde laser do cíle.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku vstupu je počet objektů N a rozměry vědecké laboratoře R a S. Na každém z následujících N řádcích je popsán jeden objekt. Nejprve je znak #, Z, C nebo číslo 0 až 7 popisující typ objektu, následují jeho souřadnice X a Y. Osa X směřuje vpravo a Y nahoru. Platí, že 0 ≤ X < R a 0 ≤ Y < S.

Dále platí, že na každém políčku je nejvýše jeden objekt a na nepopsaných souřadnicích je vzduch, který laser nijak neovlivňuje.

Formát výstupu: Jako výstup vypište, kolik energie řešení stálo a seznam pozic zrcadel, přes které laser prochází (v pořadí od zdroje do cíle).

Ukázkový vstup: 
20 10 5
4 0 2
Z 1 0
2 1 3
6 1 4
# 3 0
# 3 1
# 3 2
# 3 3
7 4 1
5 4 2
0 4 4
1 6 0
1 6 2
3 6 3
# 8 2
# 8 3
# 8 4
6 9 0
C 9 3
# 9 4
Ukázkový výstup: 
5
1 3
1 4
4 4
4 2
6 2
6 0
9 0

Znázornění:

.6..0...##
.2.#..3.#C
4..#5.1.#.
...#7.....
.Z.#..1..6

Řešení

Teoretická úloha33-1-4 Sbírání bonbónů (12 bodů)

Právě stojíme na grafu v jednom z vrcholů. Graf je stromem. Tedy každou dvojici vrcholů spojuje právě jedna posloupnost hran, kde se žádné hrany neopakují. Graf tedy obsahuje N vrcholů a N-1 hran.

V některých vrcholech jsou umístěné bonbóny. Rádi bychom jich nasbírali alespoň K a vrátili se do stejného vrcholu, odkud jsme vyrazili. Bonbónů zvládneme unést libovolné množství a jejich nošení nás nijak neomezuje. Nechceme dělat zbytečně práci navíc. Počet prošlých hran tedy musí být nejmenší možný.

Vaším úkolem je vymyslet a popsat algoritmus, který dostane na vstupu číslo K, strom popsaný seznamem hran mezi vrcholy (s určeným startovním vrcholem) a informaci, ve kterých vrcholech jsou bonbóny. Na výstupu by měl vydat plán vaší cesty po stromě tak, abyste vyrazili ze startovního vrcholu, prošli co možná nejméně hran, skončili opět ve startovním vrcholu a zároveň cestou posbírali alespoň K bonbónů.

Řešení

Bonusová úloha33-1-X1 Krycí jména (10 bodů)

Toto je bonusová úloha pro zkušenější řešitele, těžší než ostatní úlohy v této sérii. Nezískáte za ni klasické body, nýbrž dobrý pocit, že jste zdolali něco výjimečného. Kromě toho za správné řešení dostanete speciální odměnu a body se vám započítají do samostatných výsledků KSP-X.

Signor Segreto pracuje pro tajnou službu. Přesněji řečeno je jejím tajemníkem. Každý den se na jeho stole sejdou nejrůznější hlášení od tajných agentů v terénu. Ta je potřeba analyzovat, což obnáší zejména zjistit, které hlášení poslal který agent.

To není jen tak: Nejen že agenti vystupují pod krycími jmény, ale navíc se pod hlášení podepisují zkratkami. A nebohý signor Segreto musí pracně zjišťovat, že pod podpisem „A. Šaf.“ se skrývá agentka Andulka Šafářová, toho času maskovaná jako husopaska.

Vymyslete algoritmus, který bude zkratky luštit. Při spuštění nejprve načte seznam krycích jmen, což jsou dvojice křestního jména s příjmením (dvojice jsou navzájem různé, ale jak křestní jména, tak příjmení se mohou opakovat). Poté bude dostávat dotazy tvořené zkratkou jména a zkratkou příjmení. Na každý dotaz najde krycí jméno, jehož křestní jméno i příjmení začíná zadanými zkratkami. Pokud zkratce žádné jméno nevyhovuje, nebo jich naopak vyhovuje více, vypíše chybovou hlášku.

Uvažujme například následující seznam agentů:

Andulka Šafářová
Antonín Šuplíček
Ali Baba
Pěnkavka Šafářová
Popelka Pohádková
Ukázkový vstup: 
A. B.
Al. Bab.
An. Š.
An. Šu.
P. B.
P. Š.
Ukázkový výstup: 
Ali Baba
Ali Baba
--nejednoznačné--
Antonín Šuplíček
--neexistuje--
Pěnkavka Šafářová

Poznámka: Očekáváme řešení, které bude na dotazy odpovídat s lepší než lineární časovou složitostí vzhledem k velikosti seznamu jmen.

Řešení

Seriálová úloha33-1-S Z hlubin fraktálů (15 bodů)

Letošním ročníkem vás bude provázet seriál. V každé sérii se objeví jeden díl, který bude obsahovat nějaké povídání a navíc úkoly. Za úkoly budete moci získávat body podobně jako za klasické úlohy série. Abyste se mohli zapojit i během ročníku, seriál bude možné odevzdávat i po termínu za snížený počet bodů. Vzorové řešení seriálu proto před koncem celého ročníku KSP uvidí jen ti, kdo už seriál odevzdali.

Pojďme si hrát s barvami, náhodnými vzory, paprsky světla a podivnými objekty z hlubin matematiky! Tématem letošního seriálu je počítačová grafika a generování obrazu pomocí shaderů. Cílem je nejen přiblížit vám základní principy vykreslování, ale především vám ukázat, že i z pár řádků kódu můžou vypadnout velmi zajímavé obrázky či animace a že experimentovat s nimi je velká zábava.

Programování nemusí být jen užitečné, může být i hezké.

Co bude potřeba

Ze znalostí se vám bude hodit nějaká základoškolská geometrie, konkrétně Pythagorova věta a trigonometrie. Budeme často používat vektory, tedy pokud jste se s nimi ve škole ještě nesetkali, přečtěte si náš krátký úvod do vektorů.

Co se hardwaru týče, potřebujete GPU (a ovladač k němu) podporující WebGL, psát shadery budeme totiž v prohlížeči. Z hlediska výkonu není třeba nic speciálního, seriál je navržen tak, aby šel bez problémů a i s rezervou napsat na Intel HD 630.

Shadery a GPU

Vrhneme se do toho rovnou po hlavě! Shadery jsou krátké prográmky, které umí běžet na GPU (Graphics processing unit). GPU je kus hardwaru uzpůsobený pro akceleraci všemožné grafické práce. Umí například číst z paměti trojúhelníky reprezentované jako trojice souřadnic v prostoru a převádět je na „hotové“ pixely na obrazovce. Některé části tohoto procesu jsou programovatelné právě pomocí shaderů. Shaderů je mnoho druhů, nás ovšem budou zajímat pouze pixel shadery, též známé jako fragment shadery.

Pixel shadery se provádí na samém konci procesu vykreslování, kdy už víme, které pixely nějaký trojúhelník pokrývá, ale nevíme, jaká bude jejich finální barva – a právě tu spočítá pixel shader. Náš pixel shader se bude spouštět jednou pro každý pixel výsledného obrazu a jeho vstupem budou pouze souřadnice tohoto pixelu.

GPU jsou stroje masivně paralelní. Herní grafické karty mívají tisíce „jader“ (mají blíže k SIMD instrukcím na procesoru než k pravým nezávislým jádrům) a pokud takovou máte, je zcela možné, že se váš shader bude provádět třeba v desetitisíci či více instancích naráz. My si s tímto paralelismem nemusíme dělat těžkou hlavu. Shadery se vždy píší z pohledu jediného vlákna a výpočty různých pixelů se navzájem nemohou nijak ovlivnit (existují vyjímky, my se s nimi ale nesetkáme). Konečný výsledek bude shodný s tím, jako by náš kód běžel ve for smyčce pro každý pixel zvlášť.

Shadertoy

Vše budeme dělat v Shadertoy, což je webová aplikace, která umožňuje psát pixel shadery a snadno vidět jejich výstup.

Všimněte si trojúhelníkového tlačítka v levém dolním rohu editoru, které shader zkompiluje a začne s ním vykreslovat okno v levé části obrazovky. Pokud máte pomalý stroj nebo náročný shader a seká se vám obraz či prohlížeč, můžete překreslování pozastavit tlačítkem "pause" v dolní části okna s obrazem.

V pravém dolním rohu editoru najdete tlačítko s otazníkem, které zobrazí stručnou nápovědu včetně seznamu zabudovaných funkcí a vstupů.

GLSL

Shadery budeme psát v jazyce GLSL (OpenGL Shading Language), který se dá považovat za zjednodušené a velmi osekané C, takže pokud znáte jiné céčkovské jazyky jako C++, C# nebo Javu, tak v něm budete jako doma. Pokud znáte jen Python, tak se také rychle chytnete, jen nezapoměňte psát za každým řádkem středník ;-)

Rozebereme si jeden jednoduchý shader pro Shadertoy. Je to mírně upravený výchozí shader:

vec3 swapRedBlue(vec3 color)
{
    return color.bgr;
}

void mainImage(out vec4 fragColor, in vec2 fragCoord)
{
    // Normalizované souřadnice pixelu (v rozsahu 0..1)
    vec2 uv = fragCoord / iResolution.xy;

    // Barva pixelu měnící se v čase
    vec3 col = 0.5 + 0.5 * cos(iTime + uv.xyx + vec3(0, 2, 4));

    col = swapRedBlue(col);

    // Výstup na obrazovku
    fragColor = vec4(col, 1.0);
}

Otevřete si Shadertoy a copypastněte do něj tento kód, abyste si se shaderem mohli rovnou hrát. Nezapomeňte jej zkompilovat tlačítkem v levém dolním rohu editoru. Výsledek bude tentokrát téměř totožný s výchozím shaderem v Shadertoy:

Komentáře v kódu začínají dvěma lomítky. Každý řádek, na kterém je nějaký příkaz, je ukončen středníkem.

Tento shader obsahuje dvě funkce: swapRedBlue a mainImage. Tělo funkce je blok kódu. Blok kódu bývá obalen složenými závorkami. Před názvem funkce je napsán její návratový typ.

vec3 swapRedBlue(vec3 color)
{
    // ...
}

void mainImage(out vec4 fragColor, in vec2 fragCoord)
{
    // ...
}

Hlavní funkce mainImage nevrací nic, což je značeno klíčovým slovem void, ale může zapisovat do výstupního parametru fragColor, kde je uložena barva (RGBA), která se zobrazí na obrazovku. Dále má jeden vstupní parametr fragCoord, což jsou souřadnice středu aktuálního pixelu (v pixelech, tedy tato hodnota je pro levý dolní pixel rovna (0.5, 0.5), pro pixel vpravo od něj (1.5, 0.5) atd.). Každý parametr funkce má též před názvem napsaný svůj typ. Klíčové slovo in (před parametrem fragColor) je nepovinné, parametr bez něj je automaticky vstupní.

Funkce swapRedBlue, která prohodí červený a modrý kanál v nějaké barvě, vrací vec3 a má jediný vstupní parametr color, též typu vec3.

Datové typy v GLSL, které budeme používat, jsou tyto:

Inty a intové vektory se používají málokdy, budeme pracovat především s floaty a jejich vektory. Existují i boolové vektory (např. bvec2).

Co ten shader dělá?

void mainImage(out vec4 fragColor, in vec2 fragCoord)
{
    // Normalizované souřadnice pixelu (v rozsahu 0..1)
    vec2 uv = fragCoord / iResolution.xy;

    // Barva pixelu měnící se v čase
    vec3 col = cos(iTime + uv.xyx + vec3(0, 2, 4));
    col = 0.5 + 0.5 * col;

    col = swapRedBlue(col);

    // Výstup na obrazovku
    fragColor = vec4(col, 1.0);
}

Hlavní funkce nejprve deklaruje proměnnou uv, do které hned přiřadí souřadnice pixelu v obrázku, převedené do rozsahu 0 až 1. Hodnota (0, 0) je levý dolní roh obrazu, (1, 0) pravý dolní, (0.5, 0.5) je uprostřed a tak dále. Všimněte si, že je zde počátek souřadnic mírně neintuitivně vlevo dole, na rozdíl od běžných grafických programů.

Hodnotu uv získá tak, že souřadnice v pixelech vydělí celkovou velikostí obrazu, který je uložená v zabudovaném vstupu iResolution. Zabudovaných vstupů je v Shadertoy více, jejich seznam je v nápovědě (otazník v pravém dolním rohu editoru).

Když provádíme nějakou z operací plus, mínus, krát, děleno na dvou vektorech, tak se tato operace provede zvlášť na jednotlivých složkách vektoru. Například vec2(2, 3) / vec2(4, 5) nám dá hodnotu vec2(0.5, 0.6). Nepleťte si násobení dvou vektorů po složkách se skalárním a vektorovým součinem, pro ty jsou v GLSL speciální funkce dot a cross. Aritmetické operace musíme vždy provádět na dvou stejně velkých vektorech nebo na vektoru a skaláru, jak uvidíme později.

Další řádek deklaruje proměnnou col a do ní spočítá nějakou zajímavou barvu. Barva je v shaderech tradičně trojice desetinných čísel v rozsahu 0 až 1, které kódují barvu v systému RGB (red, green, blue). Tímto systémem se barvy popisují jako součet (aditivní míchání) různých jasů tří základních barev (červená, zelená, modrá). Například modrá je (0.0, 0.0, 1.0), oranžová je (1.0, 0.5, 0.0). Fungování tohoto barevného systému se nejlépe popíše obrázkem:

Additivní RGB barvy

Barevný přechod

vec3 col = cos(iTime + uv.xyx + vec3(0, 2, 4));

Co dělá výraz cos(iTime + uv.xyx + vec3(0, 2, 4))?

Asi poznáte, že se v tomto řádku počítá nějaký kosinus. Ale z čeho? Nejdřív se vezme iTime, k tomu přičteme uv.xyx a k tomu vec3(0, 2, 4).

iTime je další zabudovaná hodnota, ve které je ve floatu uložen čas od spuštění stránky v sekundách. Hodí se pro animování různých věcí.

Poslední výraz, vec3(0, 2, 4), vyrobí nový trojrozměrný vektor, kde první hodnota bude 0, druhá 2 a třetí 4. Vektor lze vyrobit například i zápisem vec3(1.0), což vytvoří 3D vektor, jehož všechny složky jsou jedničky, nebo zápisem vec4(col, 1.0) (viz poslední řádek hlavní funkce), který vytvoří 4D vektor, jehož první tři složky se překopírují z 3D vektoru col a poslední složka bude mít hodnotu jedna.

Prostřední výraz, uv.xyx, je zajímavější, protože vytváří vec3 z proměnné uv, která je ale pouze vec2. U vektorů můžeme přistupovat k jednotlivým složkám pomocí tečky a písmenka složky, které chceme. Máme-li někde vec4 v, tak v.x je první složka, v.y druhá, v.z třetí a v.w čtvrtá.

Též můžeme pro přístup k jednotlivým komponentám místo písmen xyzw použít písmena rgba, jako je tomu ve funkci swapRedBlue. Výraz color.bgr je tedy ekvivalentní výrazu color.zyx. Je vhodné tak učinit, pokud je ve vektoru uložená barva. Dále lze k jednotlivým složkám přistupovat také jako k prvkům pole, například v[0] je první složkou vektoru v.

Můžeme přistupovat i k více složkám naráz, viz první řádek funkce, kde je iResolution.xy, čímž získáme vec2 z prvních dvou složek iResolution (jejíž typ je vec3). Nic nám nebrání v tomto zápisu změnit pořadí složek nebo některou použít vícekrát.

Tedy uv.xyx je totéž jako zápis vec3(uv.x, uv.y, uv.x).

Nyní víme, že v kosinu sčítáme iTime, což je float, s uv.xyx, co je vec3. Toto není chyba, přestože sčítáme float s trojrozměrným vektorem, protože speciálně aritmetické operace na vektoru a skaláru (jedinému číslu) provádět lze, operace se provede na složkách vektoru zvlášť.

Z toho vyplývá, že iTime + uv.xyx je ekvivalentní zápisu vec3(iTime + uv.x, iTime + uv.y, iTime + uv.x).

Též cos se provede zvlášť na každé složce vektoru, to samé platí i pro podobné funkce, například absolutní hodnotu abs.

Přechody mezi rozsahy

col = 0.5 + 0.5 * col;

Nyní je v proměnné col výsledek kosinu, tedy hodnoty v rozsahu -1 až 1. Nicméně zobrazitelné barvy jsou jen v rozsahu 0 až 1, tedy pokud bychom výsledek kosinu zobrazovali napřímo, přijdeme o onu zápornou půlku rozsahu, která se zobrazí stejně jako hodnota 0.

Proto na tomto řádku přesuneme col z rozsahu -1…1 do rozsahu 0…1.

Prvním problémem je, že pokud si tyto rozsahy představíme na číselné ose, -1…1 má „šířku“ 2, ale 0…1 má šířku jen 1. Proto col vynásobíme jednou polovinou, čímž tuto hodnotu převedeme do rozsahu -0.5…0.5, který už má správnou šířku. Nyní nám stačí tento rozsah posunout o 0.5 „doprava“, což uděláme přičtením 0.5.

Tento převod mezi rozsahy je v shaderech dost častý a stojí za to si ho pamatovat. Opačný přechod, tedy z rozsahu 0…1 do -1…1, se provede následovně:

value = value * 2.0 - 1.0;

Vraťme se k barevnému přechodu. Shader tedy nejprve spočítá kosiny z tří různých hodnot, kde každá je součtem nějaké souřadnice na obrazovce uv.xyx, času od počátku iTime a konstanty vec3(0, 2, 4), a výsledek namapuje do 0…1. Protože se argument kosinu mění se souřadnicemi pixelu, dostáváme v obrazu barevný přechod z jedné strany na druhou, a protože se mění také v čase, tak se daný přechod postupně posunuje. A protože je každý ze tří argumentů v kosinu posunutý o konstantu (0, 2 nebo 4), získáváme zajímavé barvy.

Schválně zkuste, co se stane bez tohoto posunu! Proč se ve výsledné animaci střídá zelená, černá, bílá a fialová?

Též můžete zkusit vynásobit proměnnou uv něčím velkým, třeba 10.0, ještě před řádkem s kosinem. Tím se obraz „odzoomuje“ a budou vidět kosinové vlny jednotlivých barev.

Ještě se vraťme k funkcím. Možná jste zvyklí hojně využívat rekurzi, ale vězte, že GPU žádný zásobník nemají, tudíž je rekurze v GLSL zakázána. Jinak jsou funkce naprosto v pořádku.

Na posledním řádku hlavní funkce zapíšeme spočítanou barvu do fragColor, což je vec4, protože výsledkem shaderu je barva ve formátu RGBA, tedy i s alfa kanálem (průhledností). Hodnota alfa kanálu v Shadertoy nemá na nic vliv, je ovšem doporučené nechávat ji nastavenou na 1.

Shrnutí shaderu

Tím jsme prošli celý ukázkový shader. Shrňme si to nejdůležitější, co jsme se naučili:

Dejte také pozor na to, že když napíšete nějaké celé číslo, například 4, tak se automaticky považuje za int a překladač si pak občas stěžuje na to, že má nesprávný typ v nějaké funkci. Float z něj uděláte prostě tak, že za něj připíšete desetinnou tečku a nulu: 4.0.

Případně, pokud potřebujete převést intovou proměnnou na float, dělá se to výrazem float(value). Převod floatu na int se dělá obdobně.

A co když něco nefunguje jak má? Shadertoy neumožňuje debugování, ale lze si poradit i bez něj. Nic vám nebrání si nějakou zajímavou proměnnou vizualizovat pomocí trošky kódu! Zkuste přidat na konec hlavní funkce předchozího shaderu tento řádek: fragColor = vec4(uv, 0.0, 1.0);.

Tím přepíšete hodnotu ve fragColor na něco, co má v prvních dvou složkách (červená a zelená) hodnotu z uv, ve třetí nulu a čtvrté jedničku. To nám krásně vizualizuje právě souřadnice na obrazovce (a opět si všimněte, že (0, 0), tedy černá, je vlevo dole a ne vlevo nahoře).

Mandelbrotova množina

Jedna z nejzajímavějších a zároveň poměrně snadných věcí, které můžeme nakreslit pomocí shaderu, je Mandelbrotova množina (též známá jako Mandelbrotův fraktál).

Budeme používat komplexní čísla. Pokud jste se s nimi ještě nesetkali, podívejte se do encyklopedie o vektorech. Pro naše účely je komplexní číslo dvojrozměrný vektor se speciální operací násobení.

Mějme nějaké komplexní číslo c. Definujeme pro něj následující funkci:

fc (z) = z2 + c.

Mandelbrotova množina je množina takových c, pro které je posloupnost fc(0), fc(fc(0)), fc(fc(fc(0))), … omezená, tedy každý její prvek je v absolutní hodnotě menší než nějaké pevné číslo m. V opačném případě by se čísla v posloupnosti v absolutní hodnotě stále více rostla. Za m lze položit číslo 2, protože lze dokázat, že jakmile je nějaký člen posloupnosti v absolutní hodnotě větší než 2, tak tato posloupnost nebude omezená.

V množině jsou tedy ty body komplexní roviny, kde výše popsaná posloupnost nevystřelí do vysokých hodnot. Jaký budou tyto body tvořit tvar? Pojďme si to vizualizovat. Jistě tušíte, že uvidíme něco zajímavého.

Plochu obrázku namapujeme na komplexní rovinu prostě tak, že x-ovou souřadnici prohlásíme za reálnou část a y-ovou za imaginární. A jak v GLSL reprezentovat komplexní čísla? Bude nám stačit obyčejný vec2. Sčítání a odčítání pak funguje jak má (tedy po složkách, pro reálnou a imaginární část zvlášť), jen pro násobení dvou komplexních čísel si potřebujeme napsat vlastní funkci (viz funkce complexMultiply níže).

Samozřejmě nemůžeme reálně zkontrolovat celou posloupnost, zda nepřekročí hodnotu 2, ale vystačíme si s tím, že zkontrolujeme prvních 100 prvků ve smyčce for.

Množinu vizualizujeme tak, že pokud v ní pixel je (či spíše komplexní číslo, na které jsme jej namapovali), tak jej vybarvíme bíle, pokud v ní není, tak černě. Výsledný kód vypadá takto:

vec2 complexMultiply(vec2 a, vec2 b)
{
    return vec2(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

bool mandelbrot(vec2 z, vec2 c)
{
    const int iterations = 100;

    for (int i = 0; i < iterations; i++)
    {
        z = complexMultiply(z, z) + c;
        if (length(z) > 2.0)
            return false;
    }

    return true;
}

vec2 mapToComplex(vec2 uv)
{
    vec2 complex = uv * 2.0;
    return complex;
}

void mainImage(out vec4 fragColor, in vec2 fragCoord)
{
    vec2 uv = fragCoord/iResolution.xy;

    uv = uv * 2.0 - 1.0; // Převedeme uv do rozsahu -1..1

    // "Natáhneme" X tak, aby byl zachován poměr stran
    uv.x *= iResolution.x / iResolution.y;

    // Nyní je tedy čtverec v souřadnicích i čtvercem na monitoru

    vec2 complex = mapToComplex(uv);

    vec3 col = vec3(0.0);

    if (mandelbrot(vec2(0.0), complex))
        col = vec3(1.0);

    fragColor = vec4(col, 1.0);
}
Mandelbrotův fraktál

Všimněte si, že ve funkci mainImage nějak upravujeme hodnotu uv. Samotný první řádek, který jsme používali už dříve, totiž do uv uloží souřadnice pixelu v rozsahu od 0 do 1, a to tak, že například nula v x-ové souřadnici znamená levý okraj obrázku a 1 pravý, v y-ové je 0 dolní okraj a 1 horní.

Nicméně zobrazovací plocha je pro vás velmi pravděpodobně obdélníková, takže čtverec v těchto souřadnicích by se na monitoru jevil jako obdélník (o stejném poměru stran jako zobrazovací plocha či monitor).

Toto opravují dva následující řádky. První převede souřadnice do rozsahu -1 až 1. V tomto rozsahu totiž bude platit, že střed obrazu má souřadnice (0, 0), což je velmi užitečná vlastnost.

Druhý přeškáluje x-ovou souřadnici tak, aby byl zachován poměr stran. Nyní -1 či 1 v x-ové ose už nebude odpovídat okrajům zobrazovací plochy, ale pravděpodobně bodům někde těsně před ním (pokud je zobrazovací plocha širší než je vysoká). Díky tomu, že je střed obrazu na (0, 0), s ním škálování nijak nepohnulo a stále se „díváme“ na stejné místo.

Dále si všimněte funkce mapToComplex. Souřadnice pixelu nejsou na komplexní číslo převedené přímo, ale jsou změněné tak, aby obraz pokrýval rozsah přibližně -2…2 a -2i…2i v komplexní rovině. Reálná (x-ová) část bude ve skutečnosti z předchozích operací přeškálována tak, aby byl zachován poměr stran. Bez vynásobení dvěmi v mapToComplex bychom viděli jen rozsah přibližně -1…1 a -1i…i.

Také ve funkci mandelbrot je použita zabudovaná funkce length, která vrátí velikost (délku) vektoru, což odpovídá absolutní hodnotě komplexního čísla.

Též jsme zde použili for a if, které fungují stejně jako v každém jiném céčkovském jazyku.

Nicméně binární černobílý fraktál je docela nuda. Proto funkci fraktálu upravíme tak, aby místo boolu vracela číslo od nuly do jedné. Toto číslo bude nula, pokud c patří do množiny, jinak bude rovno počtu iterací, než prvek posloupnosti překročil absolutní hodnotu vyděleném celkovým počtem iterací.

float mandelbrot(vec2 z, vec2 c)
{
    const int iterations = 100;

    for (int i = 0; i < iterations; i++)
    {
        z = complexMultiply(z, z) + c;
        if (length(z) > 2.0)
            return float(i) / float(iterations);
    }

    return 0.0;
}

A v hlavní funkci barvu získáme následovně: vec3 col = vec3(mandelbrot(vec2(0.0), complex));

Všimněte si, že ve smyčce jsme i a iterations před dělením převedli na floaty. Jinak by se provedlo celočíselné dělení.

Zkuste si upravený shader spustit. To už je zajímavější, že? Nyní už jsme téměř připravení na nějaké zajímavé úkoly.

Co odevzdávat?

Vždy odevzdávejte zdrojový kód vašich shaderů zabalený v zipku. Sice v tomto díle stačí modifikovat na každý úkol jen několik málo řádků kódu, přesto prosíme odevzdávejte celý shader, který je po překopírování do Shadertoy spustitelný.

Pokud váš shader dělá něco složitějšího, přidejte prosíme ke kódu i slovní komentář.

Pokud naprogramujete například zoom i barevný přechod dohromady v jednom shaderu, můžete jej odevzdat jako jeden soubor. Nemusí platit, že jeden shader je jeden úkol. Pokud tak učiníte, pojmenujte výsledný soubor tak, aby bylo jasné, že se jedná o řešení více úkolů naráz.

Nebudeme hodnotit estetičnost řešení (ale za hezké výsledky budeme rádi :-) ), ale funkčnost a zda dělá to, co podle zadání dělat má.

Pokud byste se na něčem zasekli nebo řešili na první pohled nesmyslný bug, neváhejte se nám ozvat. Rádi pomůžeme :-) V shaderech a grafice se občas vyskytují obskurní nástrahy a je lepší nám napsat než si pár dní trhat vlasy. S radostí vám poradíme na mailové adrese zdrojaky@ksp.mff.cuni.cz.

Úkol 1 [3b]

Pojďme si hrát s funkcí mapToComplex. Co se stane, když hodnotu proměnné complex před vrácení něčím vynásobíte, třeba hodnotou 2.0 nebo 0.5? A co se stane, když k ní něco přičtete? A co když uděláme obojí naráz? Jak se výsledek liší, když nejdřív násobíte a pak přičítáte, a když to uděláme obráceně?

Naprogramujte animovaný zoom na bod v komplexní rovině -0.745428 - 0.113009i. Tento bod by měl být celou dobu uprostřed obrazu, měnit se bude pouze úroveň přiblížení. Inspirujte se některým z předchozích shaderů, který využíval vestavěnou hodnotu iTime či nějakou její funkci.

Fraktál zazoomovaný na tento bod by měl vypadat nějak takto:

Zazoomovaný Mandelbrot

Můžete si vybrat i jiný zajímavý bod. Buď zkuste najít vlastní nebo si vyberte jeden z tohoto seznamu. Pokud vám tento bod přijde při velkém přiblížení nudný, zkuste zvýšit konstantu iterations na něco vyššího, třeba 256.

Pokud při velkém přiblížení vidíte obdélníkové artefakty, tak jste právě narazili na hranici přesnosti 32 bitových floatů. A pokud zvýšíte počet iterací na 2000 a dostatečně zazoomujete, uvidíte další Mandelbrot :-)

Úkol 2 [5b]

Použijte hodnotu z funkce fraktálu k tomu, abyste vnějšek fraktálu nějak zajímavě obarvili. Místo plynulého přechodu mezi černou a bílou udělejte nějaký zajímavý netriviální barevný přechod. Můžete se inspirovat barevným přechodem z výchozího shaderu. Zároveň ale nechte vnitřek množiny černý!

Můžete použít animaci či zazoomování z minulého úkolu, aby byly vidět detaily fraktálu.

Zde se vám mohou hodit nějaké další zabudované funkce.

První je funkce clamp(x, a, b), která hodnotu x „uzavře“ do rozsahu mezi a a b, pokud v něm už neleží. Všechny parametry musí být stejného typu. Pro vektory zpracovává každou složku zvlášť. Je ekvivalentní zápisu min(max(x, a), b).

Druhou je funkce mix(x, y, a), která vrací přechod mezi hodnotami x a y na základě parametru a. x a y mohou být floaty či vektory (ale vždy musí mít stejný typ).

Funkce se chová tak, že pokud je a nula, tak vrací x, pokud je jedna, tak y, pokud je a 0.5, tak vrací hodnotu na půli cesty mezi x a y a tak dále. Je ekvivalentní zápisu x * (1 - a) + y * a. I když hodnota a nemusí být v rozsahu 0…1, většinou chceme, aby tam byla, a právě k tomu se nám hodí clamp.

Pro zajímavé přechody můžete použít třeba i funkce sin a cos nebo funkci pow(a, b), která vrací mocninu ab. Též mohou být zajímavé jiné barevné soustavy, například HSV (hue, saturation, value), tedy (odstín, sytost, světlost). Kód pro převod z HSV do RGB můžete použít cizí.

Obarvený mandelbrotův fraktál

Úkol 3 [2b]

Změňte funkci mapToComplex (ať už původní, nebo vaši vlastní z úkolu 1) tak, aby se obraz zrcadlil podle svislé čáry procházející jeho středem.

Je dobré si uvědomit, že barva každého pixelu opravdu závisí jen na jeho souřadnicích uv. Zrcadlení tedy lze dosáhnout tak, že je vhodně zmanipulujeme…

Výsledek by měl vypadat nějak takto:

Zrcadlený mandelbrotův fraktál

Úkol 4 [1b]

Připomeňme si funkci, ze které fraktál vzniká:

fc (z) = z2 + c.

Používáme zde druhou mocninu. Co kdybychom zkusili použít třetí nebo ještě vyšší? Zkuste to!

Implementujte Mandelbrotův fraktál používající nějakou vyšší celočíselnou komplexní mocninu, třeba z3. Není třeba, aby byla implementace obecná, stačí, když bude natvrdo zadrátovaná na konkrétní mocninu.

Fraktál také vypadá zajímavě s neceločíselnými mocninami, implementace je ovšem hodně složitá. Pro fc (z) = z5.5 + c vypadá takto:

Mandelbrotův fraktál s 5.5 mocninou

Úkol 5 [4b]

Vraťme se k definici Mandelbrotovy množiny. Počáteční hodnotu jsme zvolili pevně na 0 + 0i a parametr c jsme namapovali na plochu obrazu. Co když to uděláme obráceně, tedy parametr c určíme pevně a na počáteční z namapujeme obraz? Zkuste to! Výsledku se říká Juliova množina. Za c zkuste dosadit různé hodnoty. Zajímavé je třeba 0 + 0.7i.

Také ve výsledku animujte parametr c podle času, třeba ho můžete nechat kroužit po jednotkové kružnici. Použijte barevný gradient z předchozích úkolů. Odevzdejte zdrojový kód shaderu s touto animací.

Juliův fraktál

Kam dál?

Pokud vás shadery nadchly a chcete si s nimi hrát nezávisle na seriálu, mohl by vás zajímat The Book of Shaders. Je to velmi hezky zpracovaná webová učebnice shaderů, ve které najdete také různé šumové funkce, vzory a co se s nimi dá všechno dělat. Tento seriál je jí inspirovaný a je na ní částečně založený. Vězte, že tam najdete spoilery na příští díl, který se bude věnovat šumovým funkcím :-)

Kuba Pelc

Řešení