# 4. 3D modelování a datové struktury (90%)
###### tags: `grafika`, `PA010`

:::warning

* Mnohoúhelníkové a trojúhelníkové sítě:
* datové struktury
* modelování
* filtrování
* změna struktury sítě
* Implicitní reprezentace a modelování

:::

## Mnohoúhelníkové a trojúhelníkové sítě
:::success
**Geometrie**
* Ovlivněné deformacemi
* pozice a tvar vrcholů, hran, stěn
:::

:::success
**Topologie**
* Neovlivněné deformacenmi
* konektivita/sousednost mezi různými vrcholy, hranami, stěnami
* Topologicky **identické** sítě
* Topologicky **odlišné** sítě
:::

:::success
**Manifold**
* N-manifold: pro každý bod existuje okolí, které je topologicky ekvivalentní (homeomorfní) otevřené podmnožině n-rozměrného euklidovského prostoru
* Plochy jsou 2-Manifold
* Pro každý povrchový bod existuje okolí, které je topologicky ekvivalentní s rovinou
* 
:::

:::success
**Oritentace**
* Orientovatelné povrchy umožňují konzistentní definici orientace ve směru a proti směru hodinových ručiček
* Můžeme definovat přední/zadní nebo vnitřní/vnější stranu
* U neorientovatelných povrchů se může orientace změnit po průchodu smyčkou povrchu
* 
:::

:::success
**Elementy topologie**
* Základní topologické prvky hraničních reprezentací/sítí:
* **Vrcholy** $(V)$, **hrany** $(E)$, **plochy** $(F)$
* Kromě toho musíme sledovat:
* Genus $(G)$
* Okrajové smyčky hran $(R)$
* Shells $(S)$
:::

:::success
**Genus**
* $1/2$ Maximálního počtu uzavřených cest které nerozpojí objekt
* Informačně - počet rukojetí, dír v donutu
:::

:::success
**Okrajové smyčky hran**
* Označováno jako prstence - Rings $R$
* Okrajové smyčky uvnitř ploch nespojené s vnějšími hranicemi ploch
* "Díry" v plochách
* $𝑅 = 𝐿 − 𝐹$
* $𝐿$ – all edge loops, $𝐹$ – faces
* 
:::

:::success
**Shells**
* Povrchově spojené komponenty
* 
:::

:::success
**Eulerova charakteristika**
* Eulerova charakteristika $X(M)$
* Popisuje topologii tvaru $M$
* Topologický invariant – nemění se s deformací $M$
* $X(M) = 2$ pro libovolný konvexní mnohostěn
* Euler-Poincaré formula
* $X(𝑀) = 𝑉 − 𝐸 + 𝐹$
* $𝑉$ – vertices, $𝐸$ – edges, $𝐹$ – faces
* Zobecněnější verze pro tvary s otvory
* $X(𝑀) = 𝑉 − 𝐸 + 𝐹 − 𝑅 = 2 (𝑆 − 𝐺)$
* $𝑅$ – hraniční okrajové smyčky (rings), $𝐺$ – genus, $𝑆$ – shells
* 
:::

:::success
**Implikace polygonální sítě**
* Pro uzavřené 2-manifold trojúhelníkové sítě
* Každý trojúhelník má přesně 3 hrany
* Každý hrana náleží dvěma trojúhelníkům
* $E = 3/2 F$
* Z Euler-Poincarého vzorce $V = 2 + E – F$
* Tedy $V = 2+ 3/2F – F = 2 + 1/2 F$
* $V \doteq 1/2 F$
* Poměr $E:F:V \doteq 3:2:1$
* V důsledku toho je průměrný vrcholový stupeň $2E/V = 6$
:::

:::success
**Eulerovy operátory**
* Operátory topologie zachovávající Euler-Poincarého formuli
* Kompletní sada operátorů pro konstrukci topologicky korektní reprezentace
* Mezivýsledky nemusí být platnými reprezentacemi tělesa
* > 
> MSFV make shell, face, vertex
> MEV make edge, vertex
> MFE make face, edge
> MSH make shell, hole
> MEKL make edge, kill loop
> KEV kill edge, vertex
> KFE kill face, edge
> KSFV kill shell, face, vertex
> KSH kill shell, hole
> KEML kill edge, make loop
:::

:::success
**Regularizované booleovské operátory**
* Reprezentace těles lze také upravit pomocí booleovských operací
* Booleovská operace s platnými tělesy může vytvořit neplatná tělesa
* 
* Regularizované booleovské operátory eliminují „visící“ struktury nižší dimenze, které mohou být vytvářeny booleovskými operacemi
* AND = Průnik
* OR = Spojení
* SUB = Rozdíl
* Vnitřní body (Fialová) – všechny body $p$ z $A ∩ B$ takové, že otevřená koule o poloměru se středem v $p$ sestává pouze z bodů $A ∩ B$ pro dostatečně malý poloměr.
* Hranice (Zelená) – bod $q$, který je hraničním bodem $A ∩ B$ sousedí s vnitřkem, pokud mezi $q$ a dalším bodem $r$ z $A ∩ B$ najdeme úsek křivky $(q; r)$ dostatečně malé délky, takový, že všechny body tohoto segmentu jsou vnitřními body $A ∩ B$, kromě $q$.
* Množina $A ∩ B$ je otevřená, obsahuje-li pouze vnitřní body, a uzavřená, obsahuje-li i její hranici
* Regulační kroky:
1. Vypočítejte obvyklou booleovskou operaci.
2. Vypočítejte vnitřek výsledku.
* Tento krok odstraní všechny komponenty nižší dimenze.
* Výsledkem je těleso bez hranic
3. Vypočítejte uzavření získaného interiéru sečtením všech hraničních bodů sousedících s nějakým vnitřním okolím.
:::

:::success
Validita hraniční reprezentace
* Topologická validita
* Orientovatelnost – sousední plochy musí mít správnou orientaci
* Eulerovy operátory zachovávají Euler-Poincarého vzorec
* Regularizované booleovské operátory zajišťují fyzicky platná tělesa (ale ne nutně manifold)
* Geometrická platnost
* Numerické chyby v geometrii (např. pozice vrcholů) mohou vést ke konfliktům mezi topologickými a geometrickými informacemi.
* Například rovnice roviny říkají, že hrana leží uvnitř tělesa, ale topologie říká, že leží mimo
:::

### Datové struktury

:::success
**Seznam trojůhelníků**
* Jednoduchý
* Obsahuje redundantní informace o vrcholu
* 
:::

:::success
**Seznam bodů / indexované trojúhelníky**
* Sdílení vrcholů snižuje využití paměti
* Zajistí integritu sítě
* Pohyb vrcholu způsobí, že se tento vrchol ve všech polygonech posune
* 
:::

:::success
**Matice sousednosti**
* Pokud je mezi $v_i$ a $v_j$ hrana, pak $A_{ij} = 1$
* Symetrická pro neorientované jednoduché grafy
* Může představovat nemanifoldní sítě
* Žádné spojení mezi vrcholem a jeho sousedními plochami
* 
:::

:::success
**Matice rohů**
* Matice všech rohů
* Seznam sousedních rohů pro každý vrchol
* Dobré pro dotazy na sousedství
* Určitá redundance dat, pouze pro trojúhelníkovou síť
* 

:::

:::success
**Half Edge**
* Datová struktura s manifold topologií
* Rychlé vyhledávání sousedství
* Umožňuje snadnou implementaci úprav sítě
* Každá položka neboli half-edge $e$ se skládá z:
* Počáteční bod $A$
* Koncový bod $B$ (nepovinný)
* Sousední (Twin) half-edge $twin(e)$
* Plocha $face(e)$
* Náledník $next(e)$
* Předchůdce $prev(e)$ (nepovinný)
* 

:::

### Modifikace sítě

:::success
**Lokální**
* **Překlápění hrany**
* Nahraďí hranu (b,c) hranou (a,d), trojúhelníky (a,b,c), (b,d,c) se stanou (a,d,c), (a,b,d)
* 
* Výsledné úpravy sítě:
* Změňí se přiřazení ukazatelů pro úpravu vrcholů hran, vrcholů ploch a informací o sousedství
* Nebyly přidány ani odstraněny žádné prvky
* **Rozdělění hrany**
* Vložte střední bod $m$ hrany (b,c), připojte jej k vrcholům $a$ a $d$
* 
* Výsledné úpravy sítě:
* Přidány nové prvky: vrchol, hrany, plochy
* Změněny/přiřazeny ukazatele podle nových prvků
* změneny vrcholy hran a ploch, ukazatele z hran na sousední plochy atd.
* **Zhroucení hrany**
* Nahraďte hranu $(a,c)$ jedním vrcholem $m$
* 
* Výsledné úpravy sítě:
* Odstraňeny prvky: hrana, plochy
* Změna přiřazení ukazatelů k úpravě vrcholů hran a ploch
:::

:::success
**Globální**
* **Upsampling**, např. podle dělení, používá rozdělení hran
* **Downsampling** pro zjednodušení nebo kompresi, využívá zhroucení hran
* **Regularizace** pomocí překlápění hran
* **Remeshing**, např. z trojúhelníkové sítě na čtyřúhelníkovou
:::

#### **Mesh upsampling (Subdivision)** - Zvýšení počtu vzorků sítě
:::success
* Vyhlazuje síť opakovaným dělením každého prvku na menší kousky
* 
* Nahraďí pozice vrcholů váženým průměrem sousedů
* Užitečné při modelování a animaci
* Hrubá „kontrolní klec“ pro místní úpravy
* Globální dělení pro konečný povrch
* Hlavní úvahy:
* Interpolace vs. aproximace
* Limitní spojitost povrchu (C1, C2, ...)
* Chování v nepravidelných vrcholech
* Několik různých přístupů
* Aproximace (např. Catmull-Clark, Loop subdivision)
* Interpolace (např. Butterfly)
:::

:::info
**Polygonální sítě**
* Výhoda - jednoduchá reprezentace 3D modelů
* Problém - velký počet polygonů pro hladké povrchy

**B-spline plochy**
* Hladce spojené polynomiální oblasti aproximující vrcholy řídicí sítě
* Síť kontrolních bodů musí být pravidelná
* Nemůže popsat povrchy s libovolnou topologií
* 

**Rekurzivní dělení**
* Rekurzivní zjemnění polygonální (kontrolní) sítě přidáním nových vrcholů, hran a ploch (rozdělení původní sítě)
* Vytvoření hladkého (mezního) povrchu
* 
:::

:::success
**Bézierovo dělení**
:::

:::success
**Pravidelné B-spline dělení**
* Kvadratický B-Spline (Chaikin)
* Liché koeficienty $(1/4, 3/4)$
* Sudé koeficienty $(3/4, 1/4)$
* Kubický B-Spline (Catmull-Clark)
* Liché koeficienty $(4/8, 4/8)$
* Sudé koeficienty $(1/8, 6/8, 1/8)$

:::

:::success
**Nepravidelné B-spline dělení**
* Catmull-Clark
* Generaluje Pravidelné B-Spline dělení
* 
* 

:::

#### **Mesh downsampling** - Simplifikace
:::success
* Snížení počtu síťových prvků při snaze zachovat celkový tvar
* Úroveň detailů (LOD)
* Některé objekty (např. vzdálené) nepotřebují vysokou LOD
* Menší LOD zlepšuje výkon, paměťové úložiště
* Několik různých přístupů:
* Variační tvarová aproximace
* Iterativní decimace (odstranění vrcholu nebo zhroucení okraje)
:::

:::success
**Variační aproximace tvarů**
* Shluk povrchových prvků (např. trojúhelníků) do $k$ oblastí
* Začneme s náhodnými seedy ($k$ trojúhelníků)
* Aplikuje se růst oblastí na základě podobnosti se seedy (blízkost, normální orientace, ...)
* Upraví se seedy (naleznou se nejlepší zástupci každé oblasti)
* proces se opakuje, dokud se oblasti nestabilizují
* Proložte každou oblast rovinou, která minimalizuje chyby z oblasti
* Např. vážený průměr normál trojúhelníku
* 
:::

:::success
**Simplifikace hroucením hran**
* Hladový přístup:
* Přiřaďí se cena každé hraně
* Zhroutí se okraj s nejnižší cenou
* Opakuje se, dokud není dosažen cílový počet prvků
* Vyžaduje cenovou funkci, např. **metriku kvadrické chyby**:
* Kvadrická chyba = součet vzdáleností mezi bodem a rovinou
* Pro každou hranu najděte vrchol, který minimalizuje kvadrickou chybu, pak se zhorutí hrana s minimální chybou
* 
* 
:::

#### **Mesh resampling** - Regularizace
:::success
* Upravení distribuci vzorků pro zlepšení kvality
* Co je „dobrá“ trojúhelníková síť?
* Tvar trojúhelníku
* 
* Stupěň vrcholu
* Trojúhelníkové sítě: ideální je každý vrchol se stupněm 6:
* Sudivision
* 
* Delaunay triangulace
* Maximalizuje minimální úhel všech úhlů trojúhelníků
* Ze všech vrcholových triangulací má nejmenší součet délek všech svých hran
* Vyhýbá se dlouhým a tenkým trojúhelníkům
* Kružnice/koule opsané trojúhelníky neobsahují žádné další vrcholy
* 
* Vylepšení tvaru
* Překlápění hran
* Pokud $α+β > π$, překlopit
* V praxi jednoduchý a účinný způsob, jak zlepšit kvalitu sítě
* Může změnit původní geometrii
* Třeba zvážit úhel originálních trojúhelníků
* 
* Vylepšení stupně
* Překlápění hran
* Pokud se celková odchylka od stupně 6 zmenší, převrátit
* Iterativní překlápění hran funguje jako „diskrétní difúze“ stupně
* Žádné (známé) záruky
* Funguje dobře v praxi
* Vylepšení tvaru
* Vystředíme body
* Izotropní remeshing
* Opakuj čtyři kroky:
* Rozděl hrany delší než 4/3 průměrné délky hrany
* Kolapsuj hrany menší než 4/5 průměrné délky hrany
* Překlop hrany pro zlepšení stupně vrcholu
* Vystřeď body tangenciálně
* 
* Klady a zápory Regularizace
* Klady
* Zlepšuje výkon některých algoritmů
* Vyhýbá se dlouhým tenkým trojúhelníkům – žádné problémy s vykreslováním
* Žádný vysoký stupeň – žádné subdivision problémy
* Zápory:
* Ne vždy je to možné nebo vhodné
* Může vést ke ztrátě úrovně detailů
* 
* Adaptivní remeshing k vyřešení tohoto problému
* Adaptivní Remeshing
* Regulace sítě s důrazem na LOD
* Na základě různých kritérií
* Lokální zakřivení (vysoké = vyšší detaily)
* Cena/chyba modifikace
* Potřebná LOD (např. vzdálenost od kamery)
* 
* 
:::

### Modelování

:::success
**A.Barr - Globální deformace**
* Zavedena hierarchická transformace ploch
* Lokální/tangentní transformační matice (Jakobiány)
* Lokálně specifikovaná deformace
* Prolínání základních deformací (kroucení, ohýbání, zužování)
* Dnes běžné

:::

:::success
**Free-form deformace (FFD)**
> [color=#666666] Příklad:
> 1. Vytvoří se nástroj FFD (mřížka/mřížka pro Bezierův objem)>
> 2. Objekt je umístěn do prostoru FFD (světové souřadnice jsou převedeny na lokální)
> 3. Upraví se nástroj FFD (přesunou se body mřížky)
> 4. Transformuje se vložený objekt podle změn v prostoru FFD (lokální na světové)

* Lze použít pro část modelu
* Část modelu je uzavřena v deformační mřížce (objem FFD)
* Deformace mřížky mění obsah
* 

:::

:::success
**Extended Free Form Deformations (EFFD)** Sabine Coquillart (INRIA)
* Rozšíření techniky FFD
* Libovolně tvarované deformace použitím nerovnoběžných mřížek
* Stejné principy jako pro deformaci
* Klíčovou roli hraje definice mřížky a výpočet lokálních souřadnic $[s, t, u]$
* Mřížka je konstruována z rovnoběžnostěnových a válcových mřížek
* Dělení vytváří prvky – „Chunks“
* Chunk je řízen kontrolními body
* Topologie musí být zachována
* Lokální souřadnicový systém
* Chunk definuje svůj vlastní lokální souřadnicový systém
* Místní souřadnice nelze vypočítat přímo kvůli obecnému tvaru chunku
* Souřadnice mohou být aproximovány
* převod na jiný souřadnicový systém
* rekurzivní dělení chunků
* numerická interace
* Iterace Newtonovou metodou s počátečním bodem $X_0 (s,t,u) = (0.5, 0.5, 0.5)$
* Vede k velmi dobré konvergenci (2-3 iterační kroky)
* Lze vylepšit pomocí dělení po částech
* S degenerovanými kusy nemusí být inverze matice požadovaná Newtonem možná,
* Používá se metoda pseudoinverzní matice
:::

:::success
**Animované FFD**
* Dvě varianty
* Nástroj pohybující se kolem objektu – lokální deformace
* Pohyb objektu uvnitř mřížky – globální deformace
:::

:::success
**Axiální deformace**
* Fáze 1:
1. Definujeme původní křivku (osu) a parametry definující rozsah vlivu.
2. Připojíme všechny vrcholy objektu k ose, tj. najdeme nejbližší body $S(t_i)$ na křivce.
3. V každém bodě osy definujeme lokální souřadnicový rám
* Rotace minimalizující ortogonální rám (např. Frenet frame)
* Fáze 2:
1. Deformujeme křivku a aplikujeme změny na ovlivněné vrcholy pomocí lokálních rámových transformací.
:::

:::success
FFD s **Catmull-Clark objemy (CCV)**
* mřížka: vrchol, hrana, plocha, buňka

Příklad:
* Sestrojíme mřížku obsahující původní povrch.
* Pomocí n-kroků dělením CC zpřesníme mřížku na menší buňky.
* Pro všechny definující body původního povrchu:
1. Najdeme buňku rafinované mřížky obsahující tento bod, $P(x,y,z)$ a označíme jej indexem buňky.
2. Vypočítáme trilineární parametrizaci u,v,w bodu $P(x,y,z)$ uvnitř buňky, např. numerickou iterací počínaje (0,5, 0,5, 0,5).
3. Deformujeme původní mřížku
4. Upřesníme ji v n-krokovém dělení, abychom získali nové pozice buněk.
5. Pomocí indexu najdeme odpovídající buňku a pomocí $(u,v,w)$ spočítáme novou polohu deformovaného bodu $P_{cjd}(u,v,w)$.
* 
:::

:::success
**De Casteljau** FFD
:::

:::success
**Dráty** (Wires) – deformace na povrchu
* Drát je definován jako n-tice $(W,R,s,r,f)$
* $W$ – parametrická křivka volného tvaru (drátová křivka)
* $R$ – parametrická křivka volného tvaru (referenční křivka)
* $s$ – skalární, které řídí radiální škálování kolem křivky
* $r$ – skalární definující poloměr vlivu
* $f$ – funkce skalární hustoty,
* alespoň $C^1$
* monotónně klesající
* $f(0)=1$, $f(x)=0$ pro $x \geq 1$
* $f '(0)=0$, $f '(1)=0$
:::

:::success
**Sweep-based** FFD
* vyberou se části, které se mají deformovat
* Vytvoří se klíčové průřezy rovinami vybrané části polygonálního modelu
* 
* Vyberou se průřez na potaženém povrchu
* Aplikují se afinní transformaci na průřez
* 
:::

### Rekonstrukce
:::success
* Rekonstrukce 3D modelu z mračen bodů
* Potřebuje se vypořádat s mnoha problémy
* Nerovnoměrné vzorkování
* Chybějící data
* Šum a odlehlé hodnoty
* Zdrojová data mohou obsahovat další informace
* Normály
* Barva
* Tvarová omezení (CAD, architektura)
* 
* Různé přístupy založené na dostupných datech a cílech
* Interpolace (založená na Delaunay)
* Aproximace (implicitní funkce, CSG, rozdělení prostoru...)
* 
:::

### Filtrování
:::success
* Odstranění šumu, zdůraznění důležitých vlastností
* Podobné jako filtrování obrázků (PB130, PV131)
* Gaussův filtr
* Vážený průměr vrcholů
* Vyhlazuje také hrany
* Bilaterální filtr
* Zachovává hrany
* Spektrální filtrování
* Založeno na eigen-decomposition
* Atd.
* 
:::

## Implicitní reprezentace a modelování
:::info
* Definované reálnou funkcí
* Klasifikuje body v prostoru
* Implicitní povrchy vs. polygony
* Hladší
* Kompaktní reprezentace, méně primitiv
* Obtížnější zobrazení v reálném čase
* Implicitní povrchy vs. parametrické pláty
* Snazší spojování
* Bez topologických problémů
* Nižší stupeň
* Obtížnější parametrizace
* Snadnější sledování paprsku
:::

:::success
**Rovina jako implicitní povrch**
* Rovina ohraničuje poloprostor
* Určena bodem $p$ a normálou $N$
* $f(x) = (x-p)\cdot N$ je vzdálenost bodu od roviny, pokud $||N||$ = 1$
:::

:::success
**Kvadriky**
* Elipsoid (koule)
* Válec
* Hyperboloid (Kužel)
* Paraboloid
* Torus
:::

:::success
**Distanční povrchy**
* Koule: $d(x,$ bod$) – r$
* Cylindr: $d(x,$ přímka$) – r$
* Sfylindr: $d(x,$ úsečka$) – r$
* Torus: $d(x,$ kružnice$) – r$
* Obecný cylindr: $d(x,$ křivka$) – r$
* Ofsetový povrch: $d(x,$ povrch$) – r$
:::

:::success
**CSG s implicitními objekty**
* Předpoklad: $f < 0$ = uvnitř objektu
* CSG operace pomocí min/max operací
* Sjednocení: $min(f,g)$
* Průnik: $max(f,g)$
* Doplněk: $-f$
* Rozdíl: $max(f,-g)$
* C1 nespojitost
:::

:::success
**Bloby (kapky)**
* Součet Gaussových křivek
* $B_i$ – „kapkovitost“ (pozitivní)
* $R_i$ – poloměr kapky v klidu
* $r_i$ – funkce poloměru
\begin{align*}
r_i^2 (x,y,z) &= (x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2 \\
f(x,y,z) &= -1 + \sum_i exp(-B_i) \frac{r_i^2 (x,y,z)}{R_i^2} + B_i) \\
f(x,y,z) &= -1 + \sum_i D(r_i)
\end{align*}
* 
* 
:::

:::success
**Metaballs**
* Omezení potenciálové funkce, nahrazení exponenciály
* $\alpha$ - měřítko
\begin{align*}
D(r_i)= \begin{cases}
\alpha(1 - \frac{3r_i^2}{R_i^2}) \quad \quad & 0 \leq r_i \leq R_i/3 \\
\frac{3\alpha}{2} (1 - \frac{r_i}{R_i})^2 & R_i/3 \leq r_i \leq R_i \\
0 & R_i \leq r_i
\end{cases}
\end{align*}
* 
:::