Reprezentace 3D objektů

Kurz počítačové grafiky

Autor: Jiří Hnídek / jiri.hnidek@tul.cz

Základní dělení

  • Hraniční reprezentace
    • Plošková reprezentace
    • Bodová reprezentace
    • Konstruktivní geometrie těles
  • Objemová reprezentace

Plošková reprezentace

Nejčastější způsob uložení 3D objektů v paměti i na disku. Nezajímá nás vnitřek objektu, ale pouze to, co je na povrchu.

Povrch je složen z:

  • Vertexy (3D souřadnice krajních bodů)
  • Hrany (spojení dvou vertexů)
  • Plošky (spojení alespoň tří vertexů)

Trojúhelník & N-úhelník

Síť n-úhelníků se nakonec v zobrazovacím řetězci vždy převádí na śíť trojúhelníků, protože trojúhelník má několik důležitých vlastností.

  • Všechny jeho body leží v jedné rovině.
  • Trojúhelník je vždy konvexní.
  • Lze jednoduše a jednoznačně spočítat jeho normálový vektor z jeho krajních bodů.
  • Lze jednoduše provádět jeho rasterizaci.

Síť trojúhelníků

Síť trojúhelníků i libovolných n-úhelníků má vždy dvě části:

Geometrická struktura

  • Obsahuje pouze souřadnice vertexů

Topologická struktura

  • Obsahuje informace o tom, jak jsou vertexy pospojovány do hran a plošek.

Optimalizace sítě trojúhelníků

Síť je někdy vhodné převést na pruh trojúhelníků nebo vějíř trojúhelníků

  • Není nutné přenášet takové množství dat na grafický akcelerátor
  • Nutná podpora na grafickém akcelátoru a použitém API (OpenGL, WebGL, atd.)

Manifoldní a non-manifoldní objekty

Manifoldní objekt je tzv. vyrobitelný objekt a jeho topologická struktura musí splňovat následující 3 podmínky:

  1. Každá hrana musí být sdílena pouze dvěma ploškami.
  2. Žádná hrana neprotíná jinou plošku.
  3. Žádný vertex nespojuje dvě části objektu.

Jednoduchá plošková reprezentace těles

  • Předpokladem je uložení objektu, který splňuje alespoň některá kritérie pro manifoldní objekt.
  • Obsahuje informace pouze o poloze vertexů a jejich propojení do plošek.
  • Tato struktura je vhodná pro uložení do souboru, případně paměti.
  • Je hrubě nevhodná pro úpravu geometrické/topologické struktury.

Příklad - Krychlička


				   4+----+7
				   /|   /|
				 5+----+6|
				  | |  | |
				  |0+--|-+3
				  |/   |/
				 1+----+2

Příklad sítě trojúhelníků

Geometrická struktura - vetexy

0.0, 0.0, 0.0 1.0, 0.0, 0.0 1.0, 1.0, 0.0 0.0, 1.0, 0.0 0.0, 0.0, 1.0 1.0, 0.0, 1.0 1.0, 1.0, 1.0 0.0, 1.0, 1.0

Topologická struktura - plošky

0, 3, 2, 1 0, 1, 5, 4 1, 2, 6, 5 2, 3, 7, 6 3, 0, 4, 7 4, 5, 6, 7 4, 5, 9, 8

Normálový vektor

Normálový vektor plošky lze jednoznačně spočítat ze souřadnic krajních vertexů.

Když budeme uvažovat trojúhelník s krajními body: $P_{1} = [x_{1}, y_{1}, z_{1}]$, $P_{2} = [x_{2}, y_{2}, z_{2}]$ a $P_{3} = [x_{3}, y_{3}, z_{3}]$, tak normálový vektor $\vec{n}$ můžeme spočítat pomocí:

$$ \vec{v_{21}} = P_{2} - P_{1}; \quad \vec{v_{32}} = P_{3} - P_{2} \\ \vec{n} = \vec{v_{21}} \vec{v_{32}} $$

Datová struktura okřídlené hrany

  • Datová struktura vhodná pro dynamickou úpravu geometrie a topologie.
  • Lze ji použít pouze pro uložení manifoldních objektů.
  • Obsahuje jednak geometrickou strukturu (vertexy).
  • Většina informací o topologii je uložena na hranách.
    • Dva odkazy na oba vertexy
    • Dva odkazy na sousedící plošky
    • Čtyři odkazy na přilehlé plošky
  • Ploška obsahuje pouze odkaz na jednu ze svých hran.

Příklad okřídlené hrany

$E_{1}$
$V_{1}$$V_{2}$
$F_{1}$$F_{2}$
$E_{3}$$E_{4}$
$E_{2}$$E_{5}$
Okřídlená hrana

Vlastnosti okřídlených hran

  • Lze jednoduše nalézt všechny sousední plošky
  • Lze jednoduše nalézt smyčku hran/plošek
  • Ploška nemusí být konvexní
  • Ploška může obsahovat díry

Datová struktura půlhrany

  • Odstraňuje omezení okřídlených hran na manifoldní objekty.
  • Každá hrana je rozdělena na N "půlhran".

Vlastnosti vertexů, hran, plošek a rohů plošek

V aplikacích běžně potřebujeme ukládat společně s geometrickou a topologickou strukturou další dodatečné informace.

Způsob uložení takových dat se liší v závislosti na využití objektů.

Je možné ukládat další uživatelem definované informace.

Vlastnosti vertexů

  • Váha vertexů (viz. dopředná a inverzní kinematika)
  • Barva vertexů

Vlastnosti hran

  • Ostrost hran
  • UV mapování ("šev")

Vlastnosti plošek

  • Typ stínování
  • Textura
  • Barva

Vlastnosti rohů plošek

  • UV souřadnice
  • Barva

Dělené plošky

  • Algoritmus, který vyhlazuje povrch tělesa s ploškovou reprezentací.
  • Existuje několik dělících schémat (aproximační a interpolační).
  • Nejčastěji se používá dělící schéma: Catmull-Clark
    • Rekurzivní algoritmus
    • Generuje čtvercovou síť.
    • Výsledná ploch má spojitost $C^{2}$

Dělící schéma Catmull-Clark

Výsledná plocha jedné iterace je tvořena ploškovými, hranovými a vrcholovými vertexy.

Ploškový vertex $V_{F_{i}}$ je průměrem všech vertexů tvořící danou plošku $F_{i}$.

Hranový vertex se spočítá podle následujícího vztahu:

$$ V_{E} = \frac{E_{1} + E_{2} + V_{F_{1} + V_{F_{2}}}}{4} $$

Vrcholový vertex se spočítá podle následujícího vztahu:

$$ V_{V} = \frac{1}{N}(\frac{1}{N}\sum_{i=1}^{N}V_{F_{i}} + \frac{1}{N}\sum_{i=1}^{N}V_{E_{i}} + \frac{(N-3)}{N}V) $$

kde $V$ je půvdní vertex

Transformace objektů

Stejně jako v případě 2D transformací i ve 3D se transformace objektů (posun, rotace, atd.) realizují pomocí transformačních matic a homogenních souřadnic:

$$ \begin{align} X' &= \frac{X}{w} \\ Y' &= \frac{Y}{w} \\ Z' &= \frac{Z}{w} \\ \end{align} $$

Transformační matice

Obecná transformační matice pro 3D transformace má následující tvar:

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} m_{1,1} & m_{1,2} & m_{1,3} & m_{1,4} \\ m_{2,1} & m_{2,2} & m_{2,3} & m_{2,4} \\ m_{3,1} & m_{3,2} & m_{3,3} & m_{3,4} \\ m_{4,1} & m_{4,2} & m_{4,3} & m_{4,4} \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Posun

Posun můžeme vyjádřit vektorem posunutí $(dx, dy, dz)$ a maticovým násobením:

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & dx \\ 0 & 1 & 0 & dy \\ 0 & 0 & 1 & dz \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Kontrolní otázka: Je posunutí lineární transformace?

Nikoliv! Poloha není lineární kombinací původních souřadnic. Na posunutí můžeme pohlížet jako na zkosení ve čtyřrozměrném prostoru.

Zvětšení/zmenšení

Zvětšení nebo zmenšení může být ve směru os různé a je vztažené vůči počátku soustavy souřadné:

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} S_{x} & 0 & 0 & 0 \\ 0 & S_{y} & 0 & 0 \\ 0 & 0 & S_{z} & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Kontrolní otázka: Jak by vypadala transformační matice pro zrcadlení vůči rovině XZ?

Odpověď: $S_{x} = 1, S_{y} = -1, S_{z} = 1$

Zkosení

Zkosení ve směru jedné osy. V tomto případě ve směru osy x

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} 1 & s_{x} & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Otočení (kolem osy Z)

Transformační matice pro otočení není tak triviální jako ve 2D. Transformace se opět provádí vůči počátku soustavy souřadné kolem osy, ale je nutné určit kolem jaké osy otočení provádíme.

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} \cos\gamma & -\sin\gamma & 0 & 0 \\ \sin\gamma & \cos\gamma & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Otočení (kolem osy X)

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos\alpha & -\sin\alpha & 0 \\ 0 & \sin\alpha & \cos\alpha & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Otočení (kolem osy Y)

$$ \begin{bmatrix} X' \\ Y' \\ Z' \\ w' \\ \end{bmatrix} = \begin{bmatrix} \cos\beta & 0 & -\sin\beta & 0 \\ 0 & 1 & 0 & 0 \\ \sin\beta & 0 & \cos\beta & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\ w \\ \end{bmatrix} $$

Otočení - pořadí transformací

Je zřejmé, že pro obecné ototčení záleží na tom v jakém pořadí se jednotlivé parciální transformace otočení provádí. Tím se myslí, jestli se nejprve provede otočení vůči ose X, následně otočení vůči ose Y a nakonec vůči ose Z.

Různé aplikace i API mohou mít různé pořadí a konvence.

Z tohoto důvodu je vhodné kromě úhlů otočení $(\alpha, \beta, \gamma)$ uvádět i pořadí jednotlivých otočení, např.: XYZ, ZXY, atd.

Rotace vyjádřené pomocí úhlů a pořadí operací se také špatně skládají a interpolují.

Otočení - Kvaterniony (Quaternions)

Z důvodu z míňěné výše se často používá matematický aparát nazývaný kvaterniony.

Kvaterniony trochu připomínají komplexní čísla

Kvaternion obsahuje hned 3 "imaginární" složky:

$$ q = w + ix + jy + kz $$

kde $w, x, y, z$ jsou reálná čísla a $i, j, k$ jsou kvaternionové jednotky.

Kvaterniony - základní pravidla

Kvaterniony mají definováno několik základních pravidel:

$$ i^{2} = j^{2} = k^{2} = ijk = -1; $$ $$ ij = -ji = k, jk = -kj = i, ki=-ik = j $$

Někdy se kvaterniony vyjadřují pomocí:

$$ q = (s, \vec{v}) $$

,kde $s$ je skalární část a $\vec{v}$ je vektorová část

Sdružený kvaternion

Ke kvaternionu $q = w + ix + jy + kz$ definujeme kvaternion sdružený:

$$ q^{*} = w - ix - jy - kz $$

Velikost kvaternionu spočítáme pomocí:

$$ |q| = \sqrt{w^{2} + x^{2} + y^{2} + z^{2}} $$

Kvaternion, jehož velikost je jedna se nazývá jednotkový kvaternion a platí pro něj:

$$ |q| = 1; \quad q^{*}q = qq^{*} = 1 $$

Rotace vyjádřená kvaterniony

Rotaci o úhel $\alpha$ kolem vektoru $\vec{v} = (v_{x}, v_{y}, v_{z})$ lze vyjádřit pomocí:

$$ q = \cos(\alpha/2) + v_{x}\sin(\alpha/2)i + v_{y}\sin(\alpha/2)j + v_{z}\sin(\alpha/2)k $$

Rotace pomocí kvaternionu

Mějme bod $P = [p_{x}, p_{y}, p_{z}]$, a jeho polohový vektor $\vec{p} = (p_{x}, p_{y}, p_{z})$ můžeme chápat jako kvaternion s nulovou skalární částí. Otočení vektoru $\vec{p}$ kolem vektoru $\vec{v}$ o úhel $\alpha$ můžeme vyjádřit jako:

$$ \vec{p}' = q v q^{*} $$

Další informace o kvaternionech naleznete v monografii Moderní počítačová grafika na str. 549.

Děkuji za pozornost.