Datové struktury

Než se pustíme do vlastní analýzy algoritmu, ukážeme si datové struktury, které program využívá. Souřadnice vrcholů krychle jsou uloženy v matici points:

    var points = Matrix.create([
       [-1,-1,-1],[1,-1,-1],[1,1,-1],[-1,1,-1],
       [-1,-1, 1],[1,-1, 1],[1,1, 1],[-1,1, 1]
    ]);

Matice points se sestává z osmi řádků obsahující souřadnice jednotlivých vrcholů, tj. je to následující matice:

$$\left(\begin{array}{rrr} -1&-1&-1\\ 1&-1&-1\\ 1&1&-1\\ -1&... ... -1&-1& 1\\ 1&-1& 1\\ 1&1& 1\\ -1&1& 1 \end{array}\right) .$$

Krychle má tedy stranu velikosti $2$ se středem v bodě $(0,0,0)$.

K tomu abychom mohli zobrazit jednotlivé stěny krychle, musíme vědět, z kterých bodů se skládají. K tomu slouží dvourozměrné pole faces:

    var faces = [
       [1,2,3,4],[1,2,6,5],[2,3,7,6],[3,4,8,7],[4,1,5,8],[5,6,7,8]
    ];

Například položka [1,2,3,4] říká, že nultá stěna se skládá z prvních čtyř řádků matice points. Zde pozor aby nedošlo ke zmatení. Řádky matice points jsou číslovány od jedničky, kdežto položky v poli faces od nuly.

Když se díváme na neprůhlednou krychli v prostoru, nevidíme samozřejmě všechny stěny. K tomu abychom mohli zjistit, které stěny vidět jsou, budeme potřebovat normálové (tj. kolmé) vektory k jednotlivým stěnám. Navíc musí všechny tyto vektory směřovat buď ven z krychle nebo dovnitř, abychom rozpoznali vnější stranu stěny od vnitřní. V našem případě jsem zvolil normálové vektory směřující ven z krychle. K určení takových normálových vektorů slouží pole normals:

    var normals = [
       [1,5],[1,4],[2,1],[4,1],[1,2],[5,1]
    ];

Položka [1,5] říká, že normálový vektor k nulté stěně získáme odečtením pátého bodu od prvního. Např. pro počáteční nastavení matice points najdeme normálový vektor k nulté stěně takto $(-1,-1,-1)-(-1,-1,1)=(0,0,-2)$.

Jednotlivé stěny jsou vyplněny barvami, které jsou uloženy v poli colors:

    var colors = [[200,50,0],[50,200,50],[50,50,200],[50,200,50],[50,50,200],[200,50,0]];

Barvy jsou uloženy v RGB formátu. Pokud tyto hodnoty změníte, bude krychle jinak barevná.

Každá stěna se sestává ze čtyř bodů. Pokud chceme tuto stěnu vykreslit na obrazovku, musíme tyto čtyři body nějak promítnout do 2D prostoru, protože obrazovka je placatá. To jak to uděláme vysvětlíme později. Souřadnice těchto čtyř bodů po promítnutí, budeme ukládat do pole vert:

    var vert = [[0,0],[0,0],[0,0],[0,0]];

Dále následují konstanty udávající střed našeho kreslícího prostoru daného <canvas> tagem a měřítko v jakém se krychle vykreslí (ačkoli máme krychli o straně $2$, budeme chtít, aby na obrazovce byla větší než dva pixely).

    var x_center = 75, y_center = 75;
    var scale = 300;

Musíme také určit polohu pozorovatele od středu krychle. Ta je daná pomocí vektoru shift:

    var shift = Vector.create([0,0,10]);

Na konci definic proměnných máme vektor r určující směr osy rotace, konstantu angle udávající o kolik se otočí krychle v jednom kroku animace v radiánech a matici rot typu $(3,3)$, která bude obsahovat matici rotace podle osy dané vektorem r o úhle angle vzhledem ke standardním bázím.

    var r = Vector.create([1,1,1]);
    var angle = 0.1;
    var rot = Matrix.create([
       [0,0,0],[0,0,0],[0,0,0]
    ]);