3D-s számítógépes geometria 2. Háromszöghálók http://cg.iit.bme.hu/portal/node/312 https://www.vik.bme.hu/kepzes/targyak/VIIIAV01
Dr. Várady Tamás BME, Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék 3D-s számítógépes geometria
1
Tartalom • Háromszöghálók – bevezetés • 2D: Voronoi-diagram és Delaunay-háromszögelés, egyszerű algoritmusok • Háromszöghálók 3D-ben • További háromszögelő algoritmusok • Számítógépes reprezentáció • Hasznos könyvtárak
Bevezetés
2
Tesszelláció − általánosan1 Lineáris struktúrák létrehozása • csúcsok • egyenes élek gráfja • felületek tesszellációja – síklapok • tömör testek tesszellációja – térbeli primitív testek
Háromszöghálók - bevezetés
3
Háromszöghálók2 Alkalmazások • számítógépes grafika, számítógépes játékok, animáció, virtuális valóság • numerikus számítások, komplex egyenletrendszerek • szimuláció, véges-elemes eljárások • általában − orvosi és mérnöki alkalmazások • nincs szükség folytonos reprezentációra • folytonos reprezentáció nem használható Előnyök • egységes adatstruktúra • hatékony algoritmusok • hardver támogatás stb.
Háromszöghálók - bevezetés
4
Háromszöghálók3 • • • •
lokálisan körlap topológia (2-manifold) nem önmetsző, nem átlapoló folytonos és orientálható egyenletes és sima
Háromszöghálók - bevezetés
5
Háromszögháló algoritmusok4 Pontfelhők Tömör testek Háromszöghálók Felületek Görbehálózatok
Input: • • • •
2D-s és 3D-s pontfelhők pontfelhők + élek és él-hurkok → háromszögkitöltés háromszögháló → egyszerűsítés, újraháromszögelés, szépítés törött vonalas élek és „megvágott” (trimmelt) felületlapok Háromszöghálók - bevezetés
6
Háromszöghálók jellemzése5 Izotrópia: „egyenletes” élhosszak és „egyenletes” szögek Mértékek: • legkisebb szög • a körülírt kör és a belső érintőkör sugarának aránya • a leghosszabb oldal és a magasság aránya • a legrövidebb oldal és a körülírható kör sugarának aránya
min(a, b, c) r maximális, ha
a c b
r
a=b=c, 3 Háromszöghálók - bevezetés
7
2D: tesszellációs algoritmusok1 Delaunay háromszögháló (DT)
a körülírható körökben nincs más pont egyértelmű, ha nincsenek körnégyszögek egyenletes háromszögeloszlás maximalizálja a legkisebb szöget minimalizálja a legnagyobb körülírható kör sugarát minimalizálja a beírható körök sugarainak összegét
Belső pont vizsgálat
B
P
|P-O| < r (?) A
O
C
2D algoritmusok
8
2D: tesszellációs algoritmusok2 Voronoi diagram (VD) – tartományokra bontás „természetes” módon:
q ∈ V_cellai : |q-pi| < |q-p j|, j ≠ i q ∈ V_élij: |q-pi| = |q-p j| q ∈ V_csúcsijk : |q-pi| = |q-p j| = |q-pk| Duális gráfok: Voronoi diagram ↔ Delaunay-háromszögháló
D_csúcs ( pi ) ⇔ V_cellai D_háromszög ( pi p j pk ) ⇔ V_csúcsijk D_él ( pi p j ) ⇔ V_élij
2D algoritmusok
9
2D Delaunay: élcsere algoritmus Négy 2D-s algoritmus:
Élcsere (Delaunay) Inkrementális (Delaunay) „Oszd meg és uralkodj” (Delaunay) Söprő egyenes (Voronoi) 180-α
Élcsere algoritmus
input: tetszőleges háromszögelés konvex négyszögek vizsgálata ha szükséges, lokális élcsere (edge flipping) az eljárás mindig terminál – O(n2) lépés
Körnégyszög kritérium
α1 α
180-α1
szemben levő szögek összege: 180 első eset: α1+(180-α) > 180 → rossz átló második eset: α+(180-α1) < 180 → jó átló összekötés - mindig a nagyobb szögpár
2D algoritmusok
180-α
α
10
2D Delaunay: inkrementális algoritmus
Bowyer-Watson algoritmusa 1. óriás-háromszög az összes pont körül 2. pontok hozzáadása egyesével 3. körülírható körök meghatározása, amelyek tartalmazzák pi-t 4. ezen háromszögek törlése 5. a megmaradt poligon és a pi pont háromszögelése 6. óriás-háromszög törlése
O(n2) lépés, átlagosan 3n
2D algoritmusok
11
2D Voronoi: söprővonal algoritmus1 Fortune algoritmusa Söprő egyenes - balról jobbra Baloldal: félkész Voronoi diagram
mozgó hullámfront (beach line): parabola ívek sorozata parabolaív – pontok egyenlő távolságra egy pi ponttól (D_csúcs) és a söprő egyenestől Voronoi él: szomszédos parabolaívek metszéspontjainak sorozata
Két esemény:
Csúcs-esemény → új V_él Kör-esemény → új V_csúcs n log n lépésszám 2D algoritmusok
12
2D Voronoi: söprővonal algoritmus2
Csúcs-esemény ⇒ • új D_csúcs befűzése • új V_cella (parabola tágul) • új V_él (él szélesedik)
⇒
2D algoritmusok
Kör-esemény • parabola eltűnik, a V_cella elkészült • új V_csúcs befűzése • új V_él (növekszik) 13
Önálló feladatok** „Oszd meg és uralkodj” algoritmus Delaunay háromszöghálók előállításához Szemináriumi előadás és prototípus implementáció
2D algoritmusok
14
2D Delaunay: „Oszd meg és uralkodj” algoritmus
Cignoni et al. algoritmusa Pontok rekurzív kettéosztása koordináták szerint
Csoportok összekötése felfele haladva a gráfon
2 vagy 3 pontos csoportok (szakaszok és egyenesek)
Alapvonal behúzása Iteráció, amíg vannak jelöltek: Kétoldali „jelöltek” meghatározása Megfelelő jelölt kiválasztása Új vonal behúzása
n log n lépésszám
2D algoritmusok
15
3D háromszögelés1 Kiterjesztés görbült felületekre (Kós’99)
távolság: legrövidebb felületi görbeszakasz hossza általánosított Voronoi cellák és Delaunay háromszögek
Általánosított szögkritérium görbült négyszögekre
ha β + δ < α + γ → BD összekötés
3D háromszögelés
16
3D háromszögelés2 Gyakorlati elvárások:
általános topológia: nyitott vagy zárt felületek, lyukak zajos, nagyon egyenlőtlen eloszlású pontok nem projektálható, nem orientálható ponthalmazok
3D háromszögelés
17
3D háromszögelés3 Előfeldolgozás
octree lokális normálvektor becslés szomszédsági gráf
Lokális Delaunay-háromszögelés pontonként a normál síkban
A és C összekötése (?) – a négyszög szabály szerint: ABjCBj+1 szükség esetén Bj vagy Bj+1törlése lokális háromszöglegyező előállítása
Összeépítés 3D-ben
inkonzisztens háromszögek esetén: szavazás előfordulás szerint – 1, 2, 3
3D háromszögelés
v=1
v=2
v=3
18
3D háromszögelés4 - példák
3D háromszögelés
19
Háromszögelés kényszerekkel
Input:
Ouput:
ponthalmaz + rögzített élek és élhurkok
háromszögháló: legkisebb szög ≥ α0, leghosszabb él ≤ l0 (opcionális)
Iteratív eljárás
kezdeti Delaunay-szerű háromszögelés új határpontok beszúrása “rossz” háromszögek → belső pontok beszúrása, lokális korrekció
További algoritmusok
20
Vágott (trimmelt) lapok háromszögelése Szabadformájú felületek: [u,v] parametrikus tartomány Analitikus felületdarabok: létezik parametrikus reprezentáció Algoritmus: • [u,v] tartomány felosztása háromszögekre (szabályos háló) • 3D élek közelítése törtvonallal • élek visszavetítése [u,v]-be • félbevágott háromszögek újraháromszögelése • leképzés 2D → 3D • 3D háromszögháló szépítése
További algoritmusok
21
Implicit felületek háromszögelése1
Implicit felületek – parametrizáció általában nincs: F(x,y,z)=0 CT, MR mérések – voxel reprezentáció, cél: α ≥ konstans izofelület előállítása Háromszögelés – sétáló kockák (marching cubes) A skalár mező kiértékelhető a sarokpontokban
Sétáló négyzetek - 2D-s konfigurációk:
Adaptív finomítás célszerű
További algoritmusok
22
Implicit felületek háromszögelése2 3D ekvivalens konfigurációk
3D példa
További algoritmusok
23
Számítógépes reprezentáció1
Minimális információ
Cél: hatékony műveletek nagy háromszöghálókra
adott egy csúcs, él vagy lap - keressük a szomszédos csúcsokat, éleket, lapokat
Geometriai lekérdezések
lekérdezések átstruktúráló operációk (pl. csúcsbeszúrás, élkitörlés)
Topológiai lekérdezések
pontkoordináták, háromszögélek
koordináták, szögek, élhosszak környező pontok (adott sugáron belül) lokális normális- és görbületbecslés
Általános struktúra
n-oldalú lapok külső és belső hurkok (lyukak) Számítógépes reprezentáció
24
„Fél-él” (half-edge) adatstruktúra2
Irányított élpárok a lapok körül Orientált felületek
Csúcs adat:
egy (tetszőleges) kiinduló fél-él koordináták és egyéb információk (normális stb.)
Fél-él adat:
anyag (ha van) a baloldalon lyuk hurkok - fordított irányítás
kezdőpont pár („twin”, mindig létezik) lap (a háló szélén kitöltetlen) előző és/vagy következő fél-él
Lap adat:
egy (tetszőleges) fél-él a külső hurokból és egy-egy minden belső lyukból
Számítógépes reprezentáció
25
Ingyenes C++ könyvtárak OpenMesh (www.openmesh.org)
fél-él adatstruktúra általános- és háromszöghálókra hatékony „lightweight” könyvtár
CGAL (www.cgal.org)
Computational Geometry Algorithms Library rengeteg algoritmus 2D-ben és 3D-ben háromszögelés, lyukkitöltés, háló egyszerűsítés, háló finomítás, középtengelyek előállítása, Minkowski összeg, rekurzív felosztásos felületek, simítás, deformáció stb. könnyen bővíthető adatszerkezetek kapcsolat más könyvtárakhoz (Boost, GMP, BLAS, LAPACK, SciLab, Qt stb.) wrapper Pythonhoz
Háromszögelő könyvtárak
26
OpenMesh: példa1
Mesh = TriMesh/PolyMesh + Kernel + Traits Kernel: a belső tárolás módja (pl. ArrayKernel) Traits: az osztály testreszabása
koordináták, pontok stb. típusai plusz információk hozzárendelése az összetevőkhöz
struct MyTraits : public OpenMesh::DefaultTraits { VertexTraits { double area; }; }; typedef TriMesh_ArrayKernelT<MyTraits> MyMesh;
Háromszögelő könyvtárak
27
OpenMesh: példa2
Iterátorok - csúcsok, (fél-)élek és lapok „Cirkulátorok” - környező elemek
VertexFaceIter: csúcs körüli lapok cirkulátora
Példa: csúcs körüli lapok összterülete
for(MyMesh::VertexIter vi = mesh.vertices_begin(); vi != mesh.vertices_end(); ++vi) { vi->area = 0; for(MyMesh::VertexFaceIter fi = mesh.vf_iter(vi.handle()); fi; ++fi) vi->area += fi->area(); }
Háromszögelő könyvtárak
28
A következő előadás tartalma
háromszöghálók egyszerűsítése
csúcspontok klaszterezése inkrementális eljárások progresszív hálók egyenletes mintavételezés és újrahálózás
progresszív hálók normál vektorok és görbületek numerikus becslése háromszöghálók simítása
3D-s számítógépes geometria
29
Kiegészítés: a Voronoi söprővonal algoritmus adatstruktúrái
Voronoi csúcsok és élek: half-edge struktúra Események: prioritásos sor az x-koordináta alapján Hullámfront: kiegyensúlyozott bináris fa (y-rendezett) Levelek: ívet definiáló csúcs és mutató a kör-eseményekre Belső gráfcsúcsok (ívek / Voronoi élek találkozása): a definiáló csúcspár és mutató a megfelelő élre
p1
p1
p1, p2 p2
p2, p3
p2 p3
p3
(egy adott y-koordinátához tartozó ív könnyen visszakereshető) 2D algoritmusok
30