úterý 10. října 2017

Rasterizace čtyřstěnu (tetrahedronu)

Autor: Vojtěch Molek

Mějme čtyřstěn zadaný čtyřmi vrcholy $P_0, P_1, P_2, P_3$ a šesti hranami. Konkrétní čtyřstěn, který použijeme pro demonstraci, je na následujícím obrázku:



Pozn.: Souřadnice na obrázku neodpovídají skutečným souřadnicím v programu Blender, jenž byl využit pro vytvoření ukázky. Souřadnice byly přeškálovány (vynásobeny konstantou) pro zvětšení při rasterizaci ve studentských frameworcích.

V prvním kroku vytvoříme strukturu pro uložení vrcholů. Formálně se jedná o dvou rozměrnou matici:
\[
verticies = \begin{bmatrix}
44 & 474 & 0 \\
380 & 216 & 140 \\
12 & 134 & 176 \\
90 & 466 & 444 \\
\end{bmatrix}
\]
kde řádky jsou jednotlivé vrcholy čtyřstěnu a sloupce jsou souřadnice $x, y, z$ jednotlivých vrcholů. Tuto matici převedeme do zdrojového kódu v jazyce Java jako dvourozměrné pole celočíselného datového typu. První dimenze pole bude obsahovat body (tj. řádky matice) a druhá dimenze souřadnice daných bodů (tj. sloupce matice):
int [][] vertices = {{44, 474, 0}, {380,216, 140}, {12, 134, 176}, {90, 466, 444}};
Dále definujme matici, která bude obsahovat informaci o hranách čtyřstěnu (byť jsou všechny vrcholy spojené hranou se všemi ostatními vrcholy). Matice bude ve sloupcích obsahovat všechny hrany (tedy 6 sloupců) a řádky indexy počátečních a koncových vrcholů hran (tedy 2 řádky). Indexy vrcholů musí korespondovat s vrcholy v poli/matici vertices! Matice bude vypadat následovně:
\[
verticies = \begin{bmatrix}
0 & 1 & 2 & 3 & 3 & 3 \\
1 & 2 & 0 & 0 & 1 & 2 \\
\end{bmatrix}
\]
Po zapsání matice ve zdrojovém kódu, dostáváme opět dvourozměrné pole:
int [][] edges = {{0, 1}, {1, 2}, {2, 0}, {3, 0}, {3, 1}, {3, 2}};
Pro samotnou rasterizaci použijeme pouze $x, y$ souřadnice vrcholů, tzn. pouze první a druhý sloupec verticies. Budeme tedy iterovat skrze všechny hrany a ty následně rasterizovat pomocí algoritmu pro rasterizaci úsečky:
int p1, p2; // proměnné pro vrcholy hran, pro přehlednost
        for(int i=0; <edges.length; i++){
            p1 = edges[i][0]; // počáteční vrchol hrany
            p2 = edges[i][1]; // koncový vrchol hrany
            graphic.DDA(vertices[p1][0], //souřadnice x počátečního vrchol hrany
                        vertices[p1][1], //souřadnice y počátečního vrchol hrany
                        vertices[p2][0], //souřadnice x koncového vrchol hrany
                        vertices[p2][1]), //souřadnice y koncového vrchol hrany
                        G_Color.G_cBlack); //barva pro rasterizaci čtyřstěnu
        }
Po spuštění toho kódu, dostaneme následující výstup:


Nyní můžeme ověřit, že náš výstup koresponduje s výstupem Blenderu. Jediný rozdíl nastává v měříku a přehození os (nezapomeňte, že Java ma počátek souřadnic v levém horním rohu). Náš výstup by měl korespondovat s okny Blenderu, které jsou označeny osami y (zelená osa) a x (červená osa). Po otočení a zmenšení dostáváme následující porovnání:


Vidíme, že jsou čtyřstěny (téměř) stejné. K drobné chybě došlo kvůli přeškálování souřadnic (zaokrouhlovací chyba).