3D modelování a datové struktury

Note	Mnohoúhelníkové a trojúhelníkové sítě: datové struktury, modelování, ~~filtrování~~, změna struktury sítě, zjednodušování sítě. Implicitní a parametrické reprezentace a modelování (SDF, CSG, B-Rep). PA010

Mnohoúhelníkové a trojúhelníkové sítě

Základní pojmy

Geometrie

Mění jí deformace.
Např. to, kde jsou body.
Zahrnuje zakřivení (curvature), plochu (area), vzdálenosti mezi body, atd. [1]

Topologie

Nemění ji deformace.
Např. to jak jsou body propojené.
Sousednost (neighborhood), souvislost (connectedness), adjacency. atd. [1]

Obrázek 1. Topology [7]

Topological manifold

Prostor/útvar, který lokálně připomíná (je homeomorfní) $n$ -dimenzionální Euklidovský prostor. [1] [4]

$n$ -manifold je takový topologický manifold, kde okolí každého bodu je homeomorfní s $n$ -dimenzionálním Euklidovským prostorem. [4]

Manifoldy jsou typicky fyzikálně validní a efektivní (např. pomocí half-edge).

Souřadnicový prostor $R^{n}$ je $n$ -manifold.
Libovolný diskrétní prostor je 0-manifold.
Kruh je 1-manifold.
Torus (donut) a Kleinova láhev je 2-manifold (povrch).
Každý povrch je 2-manifold až na neuzavřené hrany. [1]
$n$ -dimenzionální koule je $n$ -manifold.

Orientability / orientace

Orientable surfaces allow consistent definition of clockwise and counter-clockwise orientation.

We can define front/back or inner/outer side.

In non-orientable surfaces, the orientation can change after running through a surface loop.

— PA010

Příklad 1. Möbiova páska a Kleinova láhev

Möbiova páska je neorientovatelná, protože po oběhnutí pásu se změní orientace.

Kleinova láhev je orientovatelná, protože po oběhnutí láhve se orientace nezmění.

Möbiova páska Kleinova láev

Elementy topologie

Vertices (vertexy / vrcholy) (V)
Edges (hrany) (E)
Faces (stěny) (F)
Genus (G)
Edge loops (L)
Boundary edge loops (rings, R)
Shells (S)

Genus

Počet "děr" v povrchu.
Počet "držadel" v povrchu.

Počet skupin křivek, které nelze stáhnout do bodu.

Genus of an orientable surface is the maximum number of cuttings along nonintersecting simple closed curves without separating it.

— PA010

Tip	Podle Wikipedie je genus česky rod plochy.

Tip	Je to maximální počet těch řezů. Následující povrch[6] jde rozdělit podél červené křivky na dva, ale neuvažujeme ji, protože chceme nejvyší možný počet řezů, které povrch nerozdělí.

Boundary edge loops / rings

Edge loops uvnitř stěn, které nejsou vnějšími hranicemi objektu.

"Díry" ve stěnách, ale není to genus.

$R = L - F$

Shells (S)

Spojené komponenty povrchu (množiny stěn).

Eulerova charakteristika / Euler-Poincaré formula

Eulerova charakteristika $χ$ popisuje topologický prostor či geometrický útvar $M$ . Je to topologický invariant — nezmění se jakkoli je tento útvar pozohýbán.

χ (M) = V - E + F (bez d \overset{e}{ˇ} r) χ (M) = V - E + F - R = 2 \cdot (S - G) (s d \overset{e}{ˇ} rami)

Important

Pro libovolný mnohostěn (polyhedron) bez děr je $χ = 2$ .

Important

Pro uzavřený 2-manifoldní trojúhelníkový mesh:

Každý trojúhelník má 3 hrany a každá hrana je sdílena dvěma trojúhelníky, takže $E = \frac{3}{2} F$ .

Tip	Intuitivně: pokud jsme neúsporní, pak máme tři hrany pro každý trojúhelník ( $3 F$ ), každou hranu ale "přilepíme" k nějakému dalšímu trojúhelníku, takže každou hranu máme zbytečně dvakrát ( $2 E$ ), proto $3 F = 2 E$ , tedy $E = \frac{3}{2} F$ .

Z Euler-Poincaré plyne, že

V = 2 + E - F = 2 + \frac{3}{2} F - F = 2 + \frac{1}{2} F \sim \frac{1}{2}

Tedy platí poměr $E : F : V = 3 : 2 : 1$ .
Tedy průmeřný vertex degree (počet hran, které vycházejí z vertexu) je $2 \cdot \frac{E}{V} \sim 6$ .

Tip	Každá hrana (ve 2-manifoldu) přispívá k degree právě dvou vertexů, protože někde začíná a končí. Kdybychom sečetli degree všech vertexů, dostali bychom $2 E$ , proto $2 E \sim 6 V$ .

Simplex

Nejjednodušší polytop (generalizace mnohoúhelníku, mnohostěnu, atd.). Generalizace trojúhelníku v libovolné dimenzi:

0D — bod
1D — úsečka
2D — trojúhelník
3D — tetraedr
4D — 5-cell (5nadstěn)

Datové struktury

Seznam trojúhelníků / list of triangles (polygon soup)

Jednoduchý, ale obsahuje redundantní informace. Neříká nic o sousednosti.

Indexed face set

Vrcholy trojúhelníků jsou dány pomocí indexů do pole vertexů. Méně redundantní, ale neříká nic o sousednosti.

Adjacency matrix

Matice vertexů říkající, zda-li je mezi vertexy hrana. Nijak nereprezentuje faces.

Corner table / tabulka rohů

Pro každý vertex udává sousední rohy. Fajn, pokud nás zajímá sousednost vertexů. Trochu redundantní. Použitelná jen pro trojúhelníkové sítě.

$c . v$ — vertex rohu,
$c . t$ — trojúhelník rohu,
$c . n$ — následující roh trojúhelníku,
$c . p$ — předchozí roh trojúhelníku,
$c . o$ — opačný roh v sousedním trojúhelníku (opačný roh kdyby to byl quad).
$c . r$ — "pravý" roh v sousedním trojúhelníku,
$c . l$ — "levý" roh v sousedním trojúhelníku.

Half-edge data structure

Použitelná pro 2-manifoldy. Poskytuje rychlé hledání sousednosti. Umožňuje efektivní modifikace meshů.

record HalfEdge // e.g. e
{
    Vertex Start { get; set; } // e.g. A
    // NB: End is optional since you can easily access Twin.Start.
    Vertex End { get; set; } // e.g. B
    HalfEdge Twin { get; set; }

    HalfEdge Next { get; set; }
    // NB: Prev is optional since you can easily access Next.Next.
    HalfEdge Prev { get; set; }
    Face Face { get; set; }
}

Modelování

Important

Tahle sekce má docela průnik s otázkou Modelování 3D postav.

Boundary representation model (B-rep)

Modelování objektů pomocí jejich hranic — boundaries (hrany, stěny, atd.).

Polygonální síť / mesh

Síť trojúhelníků. Hrany jsou vždy rovné. Potřebuje velké množství polygonů na hladké povrchy.

B-spline plochy

Vertexy řídící sítě slouží k aproximaci křivek. Nedokáže popsat libovolnou topologii.

Topologická validita

B-rep model splňuje Euler-Poincaré formuli. (Což neimplikuje, že je 2-manifold.)
Sousedící faces mají stejnou orientaci.
Žádné faces "nevisí" ven z modelu.

Geometrická validita

Numerické chyby v geometrii (např. v pozicích vertexů) mohou způsobit konflikty mezi topologickou a geometrickou informací. [1]

Např.: Rovnice rovin tvrdí, že hrana je uvnitř objektu, ale topologie říká, že je mimo něj.

Eulerovy operátory

Operátory zachovávající Euler-Poincaré formuli. Jsou dostatečné pro konstrukci užitečných meshů. Pracují s 6 parametry: $V$ — vertices, $E$ — edges, $F$ — faces, $H$ — components, $S$ — shells, $G$ — genus. [1] [8]

Note	Zdá se, že $H$ — components je ekvivalentní $R$ — rings.

Ač Eulerových operátorů se dá zadefinovat mnoho, v praxi stačí:

Operátor Popis

Operátor	Popis
`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

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 / regularized boolean operators

Reprezentace těles pomocí booleovských operací. Regularizované značí, že výsledek je vždy platné 2-manifold těleso.

AND - průnik $\cap^{*}$
OR - sjednocení $\cup^{*}$
SUB - rozdíl $∖^{*}$

Regularizace vypadá tak, že nejprve je provedena booleovská operace, poté je vypočítán interior a následně closure. [9]

Interior point $p$ tělesa $S$ je takový bod, že existuje $r$ takové, že otevřená koule s poloměrem $r$ a středem v $p$ obsahuje jen body z $S$ .
Exterior point $p$ tělesa $S$ je takový bod, že existuje $r$ takové, že otevřená koule s poloměrem $r$ a střem v $p$ nemá žádný průnik s $S$ .
Interior tělesa $S$ je množina všech jeho interior pointů.
Exterior tělesa $S$ je množina všech jeho exterior pointů.
Boundary tělesa $S$ je množina bodů, které nejsou ani interior ani exterior tělesa $S$ .
Clusure tělesa $S$ je sjednocení jeho interior a boundary.

Tip	Otevřená koule je koule bez povrchu. Tedy právě ty body, které jsou jejím "vnitřkem".

Obrázek 2. Schéma interior and a boundary tělesa

A \cap B

[1]

Obrázek 3. Příklad regularizovaného průniku [1]

Global deformations (Alan Barr)

Mění tvar celého meshe. Obvykle jednoduché a snadno implementovatelné. Jsou fajn při modelování.

Translace,
Rotace,
Škálování / scale,
Zkosení / shear,
Tapering / zúžení — nekonstantní škálování,

Obrázek 4. Tapering in 3ds Max
Twisting / screw / šroubování — nekonstantní rotace okolo osy,

Obrázek 5. Twisting in 3ds Max
Bending / ohýbání — ohnutí rozsahu vertexů okolo daného bodu o daný úhel.

Obrázek 6. Bending in Blender

Free-form deformations (FFD)

Lokální deformace vertexů v dané "kleci" / mřížce / lattice — Bezierově objemu.

Vyrob FFD mřížku (Bezierův objem).
"Umísti" do objemu objekt, který chceš deformovat.
Deformuj mřížku (hýbej s jejími body).
Transformuj vertexy v mřížce podle změn v FFD prostoru.

Má řadu rozšíření s různými tvary mřížky.

Změna struktury sítě

Important

Modifikace meshů mají značný přesah do otázky Křivky a povrchy a taky Pokročilá počítačová grafika

Překlápění hrany / edge flip

Lokální změna, která nahradí hranu $(b, c)$ hranou $(a, d)$ . Trojúhelníky $(a, b, c)$ a $(b, d, c)$ se stanou $(a, d, c)$ a $(a, b, d)$ . [1]

Rozdělení hrany / edge split

Lokální změna přidávající další vertex a hrany mezi dva trojúhelníky, které tak rozdělí na čtyři. [1]

Zhroucení grany / edge collapse

Lokální změna, která nahrazuje hranu vrcholem. [1]

Upsampling / subdivision

Globální změna, která rozdělí jedno primitivum (trojúhelník / quad) na více. Vyhlazuje mesh dělením na menší kousky. [1]

Downsampling / decimation / simplification

Globální redukce množství primitiv. Často využívá edge collapse.

Regularization / mesh resampling

Globální upráva s cílem zlepšit kvalitu meshe, např.: tvar trojúhelníků a četnost vertexů. [1]

Isotropic remeshing

Algoritmus pro regularizaci meshů. Opakuje čtyři kroky:

Rozděl hrany delší než $4/3$ průměrné délky.
Zhruť hrany kratší než $4/5$ průměrné délky.
Překlop hrany, pokud to zlepší stupeň vrcholu (ideální je 6).
Vycentruj vrcholy.

Zlepšuje rychlost některých algoritmů, eliminuje podlouhlé trojúhelníky, které se blbě renderují, zlepšuje subdivision, ale nejde použít vždy a může vést ke ztrátě detailů (řeší Adaptive remeshing). [1]

Implicitní reprezentace a modelování

Když máme objekt definovaný polévkou matematických symbolů místo hromádky trojúhelníků. Jinými slovy máme jednu nebo více reálných funkcí, které klasifikují body v prostoru.

Rovina

Dána bodem $p$ a normálou $N$ , ohraničuje poloprostor. Vzdálenost bodu od roviny je dána (za předpokladu, že $N$ je normalizovaná):

f (x) = (x - p) \cdot N

Kvadriky / kvadratické plochy

Elipsoid (třeba koule): $\frac{x ^{2}}{a ^{2}} + \frac{y ^{2}}{b ^{2}} + \frac{z ^{2}}{c ^{2}} = 1$ ,

Obrázek 7. An ellipsoid by Sam Derbyshire
Hyperboloid (třeba kužel): $\frac{x ^{2}}{a ^{2}} + \frac{y ^{2}}{b ^{2}} - \frac{z ^{2}}{c ^{2}} = 1$ ,

Obrázek 8. A one-sheeted hyperboloid by Sam Derbyshire
Válec (cylinder): $\frac{x ^{2}}{a ^{2}} + \frac{y ^{2}}{b ^{2}} = 1$ ,

Obrázek 9. A cylinder by Sam Derbyshire
Paraboloid (třeba miska): $\frac{x ^{2}}{a ^{2}} + \frac{y ^{2}}{b ^{2}} - z = 0$ ,

Obrázek 10. A paraboloid by Sam Derbyshire

Kvartiky / kvartické plochy

Torus (donut): $(x^{2} + y^{2} - R)^{2} + z^{2} - r^{2} = 0$ .

Obrázek 11. A torus

Distance surfaces

Tělesa lze definovat pomocí vzdálenosti od jiných entit:

Sphere: $d (x, point) = r$ ,
Cylinder / capsule: $d (x, line) = r$ ,
Torus: $d (x, circle) = r$ ,
Generalized cylinder: $d (x, curve) = r$ ,
Offset surface: $d (x, surface) = r$ .

kde $d (x, A)$ je nejmenší vzdálenost bodu $x$ od entity $A$ . [2]

Constructive solid geometry (CSG)

Umožňuje kombinovat implicitní objekty pomocí logických operací. Předpokládáme, že pokud $f (x, y, z) < 0$ pak je bod uvnitř objektu daném $f$ . Tato metoda nezachovává $C^{1}$ spojitost. Pro dva objekty $f$ a $g$ : [2]

Sjednocení: $min (f, g)$ ,
Průnik: $max (f, g)$ ,
Rozdíl: $max (f, - g)$ .
Komplement: $- f$ .

Bloby (kapky)

Součet několika Gaussových křivek. [2]

r_{i}^{2} (x, y, z) f (x, y, z) f (x, y, z) = (x - x_{i})^{2} + (y - y_{i})^{2} + (z - z_{i})^{2} = - 1 + i \sum exp (- B_{i} \cdot \frac{r _{i}^{2} ( x , y , z )}{R _{i}^{2}} + B_{i}) = - 1 + i \sum D (r_{i})

kde:

$B_{i}$ je "blobbiness",
$R_{i}$ je poloměr blobu v klidu,
$D (r_{i})$ je Gaussova křivka,
$r_{i}$ je funkce poloměru kapky.

Metaballs

Podobné blobům, ale nepoužívá exponenciální funkci. Organicky se "slévající" koule. [2]

D (r_{i}) = ⎩ ⎨ ⎧ α (1 - \frac{3 r _{i}^{2}}{R _{i}^{2}}) \frac{3 α}{2} (1 - \frac{r _{i}}{R _{i}})^{2} 0 0 \leq r_{i} \leq R_{i} /3 R_{i} /3 \leq r_{i} \leq R_{i} R_{i} \leq r_{i}

Obrázek 12. Metaballs by SharkD

Zdroje

[1] Byška, Furmanová, Kozlíková, Trtík: PA010 Intermediate Computer Graphics (podzim 2021)
[2] Sochor: PA010 Intermediate Computer Graphics (podzim 2020)
[3] Moje poznámky z PA010 (podzim 2020)
[4] Wikipedia: Topological manifold
[5] Konrad Polthier: Imaging maths - Inside the Klein bottle
[6] Saul Schleimer: Notes on the complex of curves
[7] Topology vs. Geometry
[8] Ian Stroud: Boundary Representation Modelling Techniques
[9] Interior, Exterior and Closure
[10] Representational validity of boundary representation models
[11] Bilateral Normal Filtering for Mesh Denoising