4. 3D modelování a datové struktury (90%)

tags: grafika, PA010

• 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ě

Geometrie

• Ovlivněné deformacemi
• pozice a tvar vrcholů, hran, stěn

Topologie

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

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

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

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)$

Genus

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

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

Shells

• Povrchově spojené komponenty

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

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/2F$
• Z Euler-Poincarého vzorce
  $V=2+E–F$
• Tedy
  $V=2+3/2F–F=2+1/2F$
• $V\doteq 1/2F$
• Poměr
  $E:F:V\doteq 3:2:1$
• V důsledku toho je průměrný vrcholový stupeň
  $2E/V=6$

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

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\cap B$ takové, že otevřená koule o poloměru se středem v
  $p$ sestává pouze z bodů
  $A\cap B$ pro dostatečně malý poloměr.
• Hranice (Zelená) – bod
  $q$, který je hraničním bodem
  $A\cap B$ sousedí s vnitřkem, pokud mezi
  $q$ a dalším bodem
  $r$ z
  $A\cap 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\cap B$, kromě
  $q$.
• Množina
  $A\cap 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.

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

Seznam trojůhelníků

• Jednoduchý
• Obsahuje redundantní informace o vrcholu

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

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

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íť

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ě

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

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ě

• 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)

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
• 

Bézierovo dělení

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)$

Nepravidelné B-spline dělení

• Catmull-Clark
• Generaluje Pravidelné B-Spline dělení
• 
• 

Mesh downsampling - Simplifikace

• 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)
    

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
  • 

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

• 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
    $\alpha +\beta >\pi$, 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í

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é

Free-form deformace (FFD)

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
  • 

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

Animované FFD

• Dvě varianty
  • Nástroj pohybující se kolem objektu – lokální deformace
  • Pohyb objektu uvnitř mřížky – globální deformace

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í.

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)$.
• 

De Casteljau FFD

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\ge 1$
    • $f^{\prime }(0)=0$,
      $f^{\prime }(1)=0$

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

• 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í

• 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í

• 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

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$

Kvadriky

• Elipsoid (koule)
• Válec
• Hyperboloid (Kužel)
• Paraboloid
• Torus

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$

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

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{array}{rl}{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{array}$$
• 
• 

Metaballs

• Omezení potenciálové funkce, nahrazení exponenciály
• $\alpha$ - měřítko
  
  $$\begin{array}{r}D(r_i)=\{\begin{array}{ll}\alpha (1-\frac{3r_i^2}{R_i^2})& 0\le r_i\le R_i/3\\ \frac{3\alpha }{2}(1-\frac{r_i}{R_i}{)}^2& R_i/3\le r_i\le R_i\\ 0& R_i\le r_i\end{array}\end{array}$$
•