3D szkenneléssel előállított pontfelhő és annak feldolgozási lehetőségei Dr. Tomán Henrietta, Dr. Kunkli Roland

3D szkenneléssel előállított pontfelhő és annak feldolgozási lehetőségei Dr. Tomán Henrietta, Dr. Kunkli Roland Készült: 2015.09.30.

A tananyag elkészítését "Az élettudományi- klinikai felsőoktatás gyakorlatorientált és hallgatóbarát korszerűsítése a vidéki képzőhelyek nemzetközi versenyképességének erősítésére" TÁMOP 4.1.1.C-13/1/KONV-2014-0001 számú projekt támogatta. A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósult meg.

1

TARTALOMJEGYZÉK

5. 3D SZKENNELÉSSEL ELŐÁLLÍTOTT PONTFELHŐ ÉS ANNAK FELDOLGOZÁSI LEHETŐSÉGEI ...............................................................................................................................3 5.1.

Elméleti alapok ..................................................................................................................3

5.1.1.

Pontfelhő ....................................................................................................................3

5.1.2.

Háromszögháló ..........................................................................................................4

5.1.3.

Adatszerkezetek pontfelhők reprezentációjához ........................................................6

5.1.4.

Gráfelméleti alapok ....................................................................................................7

5.2.

Háromszöghálók és azok paraméterezhetősége ................................................................9

5.2.1.

Háromszögháló létrehozása és feldolgozása ............................................................10

5.2.2.

Optimális háromszögháló.........................................................................................16

5.2.3.

Háromszöghálók parametrizálása ............................................................................17

5.3.

Simítási technikák ...........................................................................................................18

5.3.1.

Zajszűrés ..................................................................................................................19

5.3.2.

Hálólefedés ...............................................................................................................21

5.4.

Hatékony háromszögháló, áthálózási technikák .............................................................22

5.4.1.

Lokális szerkezeti tulajdonságok .............................................................................22

5.4.2.

Globális szerkezeti tulajdonságok ............................................................................24

5.4.3.

Voronoi diagram, Delaunay háromszögelés ............................................................24

5.4.4.

Háromszög alapú áthálózás ......................................................................................26

5.5.

Differenciálgeometriai alapismeretek .............................................................................32

5.5.1.

Görbeelméleti alapok ...............................................................................................33

5.5.2.

Felületelméleti alapok ..............................................................................................35

5.5.3.

Differenciálgeometriai vizsgálatok diszkrét esetekben ............................................39

TESZTKÉRDÉSEK .......................................................................................................................42 FELHASZNÁLT SZAKIRODALOM ..........................................................................................44

2

5. 3D SZKENNELÉSSEL ELŐÁLLÍTOTT PONTFELHŐ ÉS ANNAK FELDOLGOZÁSI LEHETŐSÉGEI

A 3D szkennelési technika jelenlegi fejlettsége már lehetővé teszi az egyre inkább növekvő számú, nagyon színes és érdekes alkalmazását, többek között a véges elemes szimulációt vagy a filmbeli speciális effekteket említve. A napjainkban végbemenő rohamos technikai fejlődés biztosítja annak a lehetőségét, hogy a 3D szkennelési eljárást egyre több olyan területen is alkalmazni tudják, ahol nagy precizitásra van szükség (pl. mérnöki tevékenység, orvostudomány, minőségellenőrzés). A 3D szkennelés eredményeként nyert pontfelhő, majd az abból származtatott felületmodell esetén, ha az eredeti modell igazán valósághű másolatát szeretnénk előállítani, akkor a technológiából most még származó hibák miatt további utómunkákra van egyelőre szükségünk (pl. zajszűrés, esetlegesen keletkező lyukak eltávolítása, simítás). Ebben a fejezetben a teljes szkennelési folyamat főbb alkotóelemeit, a legfontosabb javítási műveleteket tárgyaljuk és azok matematikai hátterét világítjuk meg. 5.1.

Elméleti alapok

Mivel a szkennelés során a pontfelhők és azok háromszöghálói központi szerepet játszanak, ezért először áttekintjük a főbb fogalmakat és technikákat, amelyek az ilyen jellegű diszkrét adatok tárolásával és feldolgozásával kapcsolatosak. Megvizsgáljuk a különböző adatszerkezetek használhatóságát pontfelhők esetén, illetve megmutatjuk, hogy a háromszögháló milyen szorosan kapcsolódik a gráfelmélethez. 5.1.1. Pontfelhő Pontfelhők létrehozására több lehetőség is kínálkozik, melyek közül az egyik legelterjedtebb, tipikus megoldás a 3D-s szkennelés. (Pontfelhőt szoftver által is elő tudunk állítani, pl. CAD modell pontfelhővé alakításakor.) A 3D szkennerek nagy mennyiségű 3D adat összegyűjtését teszik lehetővé néhány másodperc alatt. A szkennelési eljárás eredményeként kapott pontfelhőt a következőképpen definiálhatjuk:

3

A P pontfelhő olyan 3D pontok rendezetlen halmaza, melyek egy objektum szkennelésekor állnak elő, és ezen objektum felületét reprezentálják.

1. ábra: Szkennelés után kapott pontfelhő Matematikailag, egy pontfelhőre tekinthetünk úgy, mint olyan pontok halmaza, amelyeket elegendő sűrűséggel mintavételeztek egy kompakt (azaz korlátos és zárt), összefüggő sima felületből. Valójában minden elméleti vizsgálat esetén, amely pontfelhőkön ható algoritmusra vonatkozik, feltételeket kell szabnunk a mintavételezés sűrűségével kapcsolatban. Különben lehetetlen garantálni az eredeti objektum geometriájának és topológiájának megőrzését. A gyakorlatban a matematikai nézőpont gyakran túl idealisztikus. A pontfelhő pontjait ugyanis bizonyos hibával mérjük, aminek eredményeként inkább csak felülethez közeli pontokat kapunk, mint arra pontosan illeszkedőket. Továbbá a mintavételezés sűrűsége nagyon változó lehet, attól függően, hogy hogyan szkennelték be az objektumot. Ezen felismerések jelentősen bonyolítják a pontfelhőket feldolgozó algoritmusokat és azok vizsgálatát. 5.1.2. Háromszögháló A pontfelhőkre alkalmazott egyik legalapvetőbb művelet a háromszögelés, melynek eredményeként egy háromszögháló jön létre. Az eljárás során a szomszédos pontokat kötjük össze konzisztens módon, ezáltal összefüggőségi információval látva el a pontfelhőt. 4

A térbeli háromszögháló egy nagyon általános definícióját az alábbiak szerint adhatjuk meg: Egy S kompakt felület T háromszöghálója olyan 3D térbeli háromszögekből áll, amelyekre teljesül, hogy: -

bármely két háromszög vagy legfeljebb egy közös csúcsban metszi egymást, vagy egy közös él mentén,

-

az összes T-beli háromszög uniója összefüggő térbeli halmaz.

2. ábra: Térbeli háromszögháló A különböző alkalmazásokban egy objektum felületéről mintavételezett pontfelhőkkel foglalkozunk, és ehhez az esethez a fenti definíció túl általános, ugyanis az megengedi az önmagába metszést is. Ezért az alábbi megszorítással kell élnünk: egy felületi háromszögháló esetén a következő tulajdonságokat várjuk el: -

az olyan háromszögek, amelyek egy közös csúccsal rendelkeznek, háromszöglegyezőt alkotnak, amely homeomorf egy körrel,

-

minden él legfeljebb két háromszöghöz tartozik.

5

3. ábra: A megszorításoknak megfelelő háromszögháló 5.1.3. Adatszerkezetek pontfelhők reprezentációjához Az adatszerkezet kiválasztása mindig több szempont együttes mérlegelése alapján történik meg. Először is, a leendő adatszerkezetnek a lehető leghatékonyabban kell támogatnia azokat a műveleteket, amelyekre majd szükségünk lesz. Másodszor, a döntés meghozatala előtt figyelembe kell venni a memóriaszükségletet, míg végül, amit néha kihagynak, ott van az implementáció és a kezelhetőség kérdése is. Az alkalmazástól függően, ezen szempontok fontosságát mérlegelve, más-más adatszerkezet választása lehet optimális. 5.1.3.1.

Szabályos rács

A szabályos rács adatszerkezet a teret egyenlő oldalú négyzetes cellákra osztja. Ez a síkbeli négyzetrács közvetlen kiterjesztése, és egy 3D mátrixszal reprezentálható. A legegyszerűbb módszer egy ilyen 3D mátrix implementációjához, ha 3D tömbként tároljuk le, ahol a mátrix minden egyes eleméhez a memória egy részét rendeljük hozzá. Alkalmazástól függően, a mátrix elemei tartalmazhatnak mutatókat, vagy kézenfekvő módon a mátrix elemei lehetnek logikai értékek, azt mutatva, hogy az a cella üres-e (0) vagy sem (1). Ekkor egy pont hozzáadását vagy törlését nagyon egyszerűen lehet implementálni. 5.1.3.2.

Ritka mátrix reprezentáció

Mivel a pontfelhő általában differenciálható sokaságot reprezentál, így ebben az esetben a szabályos rács gyakran nagyon ritka, azaz a celláknak csak egy töredéke tartalmaz néhány pontot. Ezért indokolt, a memóriafogyasztás problémájának megoldása miatt, hogy csak a nem-

6

üres cellákat tároljuk. A ritka mátrix reprezentáció a nem-üres cellák indexeit és a hozzátartozó elemek értékeit tárolja egy listában. Bár ez a reprezentáció jelentősen csökkenti a naiv szabályos rács implementáció memóriaigényét, ekkor a műveletek válnak nagyon költségessé. Például, annak eldöntéséhez, hogy egy cella üres-e, az egész listát végig kell keresni. 5.1.3.3.

Hash tábla

Hash tábla adatszerkezetet választva egyesíthetjük a ritka mátrix reprezentáció alacsony memóriaszükségletét a szabályos rács reprezentáció gyorsaságával. Az indexekre vonatkozó hash függvény használatával a 3D mátrix reprezentációt egy sokkal kisebb méretű hash táblára lehet egyszerűsíteni, ugyanis a hash függvény egy olyan leképezés, mely tetszőleges hosszúságú jelsorozatot adott hosszúságú jelsorozatra képez le. 5.1.4. Gráfelméleti alapok A gráfelmélet nagyon sok digitális geometriai feldolgozó algoritmus esetében játszik fontos szerepet, főként pontfelhők feldolgozása esetén. Ekkor ugyanis a pontfelhő, illetve a háromszögháló összefüggőségét gráfok felhasználásával reprezentálhatjuk. A későbbiek során a gráfelméleti fogalmak ismerete a pontfelhő háromszögelése, a simítás és a határvonal kibővítése során is hasznos lehet. 5.1.4.1.

A legfontosabb gráfelméleti fogalmak

Königsberg a Pregel nevű folyó két partján terül el, az egyes városrészeket 7 db híd köti össze az alábbi 4. ábra szerint. Olyan útvonalat szerettek volna tervezni, hogy a helybeliek a saját lakásukból elindulva, és minden hídon csak egyszer áthaladva, hazatérhessenek. Euler az alábbi egyszerűsített modell (5. ábra) segítségével bebizonyította, hogy ilyen útvonal nem lehetséges, megteremtve ezzel a gráfelmélet alapjait.

7

4. ábra: A königsbergi hidak [1]

5. ábra: A kapcsolódó gráfmodell

Gráfnak nevezzük pontok és élek együttes halmazát, ahol az élek pontokat kötnek össze, illetve az élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik. A gráf pontjait csúcspontoknak vagy egyszerűen csúcsoknak nevezzük. Ha az éleket irányítással is ellátjuk, akkor irányított gráfról beszélünk. A gráf egy pontjába összefutó élek számát a pont fokszámának nevezzük. Például a königsbergi gráfban az A csúcs fokszáma 5, a B, C és D csúcsé pedig 3. Két csúcs szomszédos, ha éllel vannak összekötve. Hasonlóan, két él akkor szomszédos, ha van közös csúcsuk. Ha két csúcs között több él húzódik, akkor párhuzamos, vagy többszörös élről beszélünk. Ha egy él végpontjai megegyeznek, akkor hurokélről beszélünk (6. ábra).

6. ábra: Többszörös él és hurokél A gráf egyszerű, ha sem párhuzamos élet, sem hurokélet nem tartalmaz. Teljes gráfnak nevezzük azokat a gráfokat, amelyeknek minden csúcsa a gráf összes többi csúcsával össze van kötve (7. ábra). A gráf akkor összefüggő, ha bármely csúcsából bármely más csúcsába élek mentén el lehet jutni (8. ábra). Egy összefüggő gráfot szeparálhatónak nevezünk, ha van olyan csúcsa, amelyet (a 8

hozzátartozó élekkel együtt) eltávolítva a megmaradó gráf már nem összefüggő. Ekkor ezt a csúcsot vágó-csúcsnak hívjuk.

7. ábra: Egyszerű és teljes gráf

8. ábra: Összefüggő és nem összefüggő gráf

Útnak nevezzük a gráf egymáshoz csatlakozó éleinek olyan sorozatát, amely egyetlen csúcson sem halad át egynél többször. Vonalnak nevezzük a gráf csúcsainak és éleinek azt a sorát, amelyben az élek a megfelelő csúcsokat kötik össze és az élek nem ismétlődnek.

9. ábra: Út, vonal és kör Euler-vonal esetén a vonalban a gráf minden éle és minden pontja szerepel. A königsbergi hidak problémájának megoldása azt jelenti, hogy abban a gráfban nincs Euler-vonal. Körnek nevezzük a kezdőpontjába visszatérő utat (9. ábra). A gráfokat másféle modell alapján is leírhatjuk: például egy a csúcsok halmazán értelmezett bináris relációként, vagy mátrixok segítségével. Ha adott egy n csúcspontú gráf, akkor a következőképpen definiálhatjuk az 𝑛𝑛 × 𝑛𝑛-es szomszédsági mátrixát: a mátrix a ij eleme 1, ha az i. és a j. csúcs között van él, és 0, ha nincs. 5.2.

Háromszöghálók és azok paraméterezhetősége

Amint adott pontfelhő esetén a megfelelő modellt keressük a minél optimálisabb háromszöghálóhoz, azonnal felvetődik az interpoláció vagy approximáció dilemmája. Vajon a modellnek az adott elemeket kell tartalmaznia (azaz a háromszögháló csúcsai az eredeti ponthalmazból kerüljenek ki), vagy csak az alakját kellene közelítenie (a háromszögháló közel van az eredeti pontokhoz, de nem feltétlenül tartalmazza azokat). 9

5.2.1. Háromszögháló létrehozása és feldolgozása A 3D szkennelési technika napjainkban már számos területen eredményesen használható. Ezen szóba jöhető felhasználási lehetőségek közül most egy klasszikus 3D szkennelési alkalmazást, a Reverse Engineering technológiát tárgyaljuk részletesebben, ugyanis ebben megtalálhatóak a pontfelhőkre, illetve a háromszöghálókra alkalmazható legrelevánsabb operátorok. Manapság már egyre inkább közkedvelt a Reverse Engineering technológia (fordított mérnöki tevékenység). Ez az az eljárás, melynek során a 3D pontfelhőt CAD modellé alakítjuk, lehetővé téve egy olyan objektum reprodukcióját, amelyből csak egy fizikai prototípus áll rendelkezésre, vagy egy már létező termék továbbfejlesztését biztosítva. A CAD/CAM rendszerek ugyan rendelkeznek pontfelhők beolvasását és kezelését támogató modullal, de ezek egy bizonyos méret felett már nem adnak elfogadható megoldást. A Reverse Engineering egyértelmű célja, hogy a fizikai objektum analizálható vagy módosítható modelljét hozza létre. A folyamat során a következő főbb lépéseket emelhetjük ki: 5.2.1.1.

Adatok kinyerése

Ez az első lépés a fizikai objektum beszkennelésére vonatkozik, mely magában foglalja a szkenner beállítását, a kalibrációt és az objektum előkészítését. A határvonal kiterjesztése számos algoritmus alapvető előfeldolgozó lépése. Ez magában foglalja a pontfelhő határpontjainak beazonosítását és ezen pontoknak 3D poligonokba történő rendezését. Ezek a határral kapcsolatos információk hasznosak lehetnek a lyukak eltüntetésénél, a szkennelési folyamatot, a vizualizációt, a háromszögesítést és a felületillesztést is befolyásolva.

10

10. ábra: Szkennelés után kapott pontfelhő 5.2.1.2.

Regisztráció, zajszűrés

Az objektumok beszkenneléséhez az esetek döntő többségében nem elegendő egyetlen szkennelés. A rejtettebb, mélyebben található részek esetében több nézőpontból is el kell végezni a szkennelési folyamatot, majd ezeket a részeredményeket egyetlen pontfelhőben egyesítenünk kell. Ezt nevezzük regisztrációs lépésnek. Ennek végrehajtása különösen nehéznek bizonyulhat deformálódó felszín esetén, például amikor megváltozik a modell arckifejezése vagy elmozdul az eredeti helyéről. 5.2.1.3.

Háromszögelés

Ahogyan azt a korábbiakban már láthattuk, ezen lépés során egy felületi háromszöghálót (11. ábra) hozunk létre a kapott pontfelhő pontjaiból (10. ábra).

11

11. ábra: A pontfelhőből előállított háromszögháló A háromszögelés problémája esetén általában nincs definiálva, hogy a megoldásnak milyennek kellene lennie. Mivel az eredeti felületet csak véges sok pontban ismerjük, így a keresett megoldás nem egyértelmű. Ezen tény ellenére, nyilvánvaló, hogy a végeredményként kapott háromszöghálónak jól kell közelítenie az eredeti felületet, mind geometriai, mind topológiai értelemben. Az olyan alkalmazásokat, mint a vizualizáció, a véges elemes vizsgálat vagy a rapid prototyping (gyors prototípuskészítés), hatékonyan végrehajthatjuk már az objektum háromszögháló reprezentációján is. Ezekben az esetekben nincs feltétlenül szükség a teljes eljárásra, elegendő lehet annak csupán az első három lépése is. 5.2.1.4.

Simítás, lyukak eltávolítása, egyszerűsítés

Előfordulhat, hogy a folyamat első három lépésének eredményeként kapott háromszögháló az alulmintavételezett részek vagy a zaj miatt lyuka(ka)t is tartalmaz. Ahhoz, hogy az ezt követő 12

szegmentációs lépést pontosan végre tudjuk hajtani, szükségünk lehet a háromszögháló simábbá tételére, illetve a hiányzó adatok kitöltésére. Simítás Pontfelhő és háromszögháló esetén a simítás egy nagyon fontos és gyakran használt művelet. A simítási módszerek csökkentik a magas frekvenciájú zajokat, ezáltal javítva a különböző módon származtatott alakjellemzők pontosságát, például a felületi normálisok és a görbületek esetén. A simítás a pontfelhő (újra)háromszögelésének feladatát, illetve a felületillesztést is könnyebbé teszi. Újrahálózás Az eredeti, szkenneléssel képzett hálóknak még rengeteg csúcsa van. Ezért praktikus okokból (pl. a későbbiekben szükséges számítási kapacitás visszaszorítása miatt) nagyon fontos a csúcsok számának csökkentése (a hálóadatok szűkítése). Általában azért végzünk újrahálózást, hogy a számos újrahálózási feltétel valamelyikét teljesítsük. Ezen feltételek közül például az egyik legalapvetőbb, hogy a csúcsok és a háromszögek számának csökkentését a kapott modell alakjának az eredetihez való minél közelebbi hasonlóságának megőrzése mellett kell elvégeznünk. Szintén az újrahálózás célja lehet a háló szabályosabbá tétele.

13

12. ábra: A csúcsok számának csökkentése után kapott háromszögháló Másik népszerű újrahálózási kérdés a háromszögháló négyszöghálóvá való átalakítása, illetve az újrahálózási eljárást használjuk még a lyukak betöltési folyamatánál is. Térhálóbeli lyukak betöltése A hálóbeli lyukak betöltésének problematikája azért lényeges, mert minden ilyen jellegű rendszer korlátozott hozzáféréssel bír az objektumok üreges részeihez. Még a nagyon óvatos szkennelési eljárások során is számos olyan lyuk maradhat, ami az objektumok árnyékoltabb részeihez tartozik. Ebből kifolyólag már eddig is nagyon sok megoldási javaslat született a lyukak kitöltésére. Először is megjegyezhetjük, hogy az előjeles távolságfüggvény approximációjával képzett hálók automatikusan kitöltik a lyukakat, így nem szükséges utólagos lyuk kitöltési technika alkalmazása. A probléma valójában a következő: a lyukak nem igazán jól azonosíthatóak. Ebből következik, hogy ezeken a részeken sem a feltérképezés, sem a tárolás minőségének további javítása nem lehetséges. A lyukakat tartalmazó háló esetében az a legfőbb cél, hogy a háló többi részének a megváltoztatása nélkül töltsük ki a lyukakat. 14

A háromszögháló méretének csökkentése (szimplifikáció) meggyorsíthatja a későbbi lépéseket is, ugyanis kevesebb memóriahasználatra lesz szükségünk. Itt kell megemlíteni azt is, hogy az adott alkalmazástól függően a negyedik lépés megelőzheti a harmadikat, ugyanis a simítási és az egyszerűsítési eljárást már közvetlenül a pontfelhőn is végrehajthatjuk. 5.2.1.5.

Szegmentálás

A szegmentálási lépés azt a bonyolult problémát próbálja meg megoldani, hogy meghatározza a háromszögháló azon összefüggő tartományait, régióit, amelyeket később majd egyetlen felületdarabbal lehet közelíteni a rekonstruált CAD modellben (13. ábra).

13. ábra: Szegmentálás végeredménye [4] A szegmentálás ezáltal a folytonossági hiányok, lyukak feltérképezésében is hasznos eszköz lehet. 5.2.1.6.

Felületillesztés, esztétikai lépések

A felületillesztő lépés során egy-egy folytonos felülettel látunk el minden egyes szegmentált régiót.

15

14. ábra: A teljes folyamat végeredménye Végül a kapott eredmény még esztétikusabbá tehető a felületek között előírt számos feltétel (másod-, illetve harmadrendű folytonosság) teljesítésével. 5.2.2. Optimális háromszögháló Az eredeti pontokra illesztett háromszöghálókat (interpoláció esetén) úgy érdemes kialakítani, hogy a lehető legrövidebb távolságok adódjanak, és a háromszögek oldalai mentén a görbületi gradiensek megváltozása lehetőleg minél lineárisabb legyen. A probléma számítógéppel történő megoldására a Delaunay-háromszögelés adja meg a választ, ugyanis ennek a módszernek, illetve megfelelő módosításaival lehet a legalkalmasabb pontpárok megkeresésével automatizálni a háló kialakítását. 5.2.2.1.

Delaunay-háromszögelés

A Delaunay-háromszögelés a komputergrafikában és a térinformatikában meghatározóan fontos felületgeneráló algoritmus, amely két- vagy háromdimenziós pontfelhő esetén a pontokra illesztett optimális háromszögek csúcsait határozza meg. A kétdimenziós esetben azokat a pontpárokat keressük, amely segítségével majd síkbeli háromszöghálót hozunk létre. 16

Ekkor az optimális Delaunay-háromszögháló megtalálására sokféle eljárás létezik, viszont minden algoritmusra jellemzőek a következő tulajdonságok: -

a kapott háromszögek köré írt körei üresek, azaz azokon belül nem található meg a pontfelhőnek egyetlen további eleme sem, legfeljebb maguk a körök tartalmazhatnak maximum 4 pontot,

-

szabályos háromszögek kialakítására törekednek, ugyanis a háromszögek legkisebb belső szögét maximalizálják (Delaunay-feltétel).

A Delaunay-háromszögek keresésekor a legfontosabb lépés az első feltétel garantálása, azaz el kell tudnunk dönteni, hogy egy újabb, negyedik pont a vizsgált háromszög köré írható körén kívül helyezkedik-e el. Ezt a problémát könnyen meg tudjuk oldani, ha megvizsgáljuk egy 4×4-es mátrix determinánsát, amelynek elemei a 4 pont síkbeli koordinátáitól függenek. Pozitív értéket kapva az adott háromszög nem tekinthető Delaunay-háromszögnek, ugyanis ilyen esetben a negyedik pont a körön belül helyezkedik el. Az ennél általánosabb, térbeli optimális háromszögháló problematikájáról, a Delaunayháromszögek és a Voronoi-cellák közötti kapcsolatról, illetve az optimális háromszögháló megkeresésére kifejlesztett algoritmusokról és azok lehetséges implementációiról bővebb leírást az 5.4. alfejezetben találhatunk. 5.2.3. Háromszöghálók parametrizálása Röviden megfogalmazva, a parametrizációk valójában a síknak a 3D-s térre történő leképezései. Ezeknek a megfeleltetéseknek nagy jelentősége van a mérnöki tevékenységek, CAGD és komputergrafika számos alkalmazási területén. A parametrizációk meglévő eszközt jelentenek olyan alkalmazások esetén, mint például a felületillesztés, textúra leképezés, hálózás és újrahálózás (meshing, remeshing), sűrítés és felületapproximáció, CAD modellek javítása és spline felületek újraparaméterezése. A leggyakorlatiasabb célokat figyelembe véve, a parametrizáció ideális esetben egy kölcsönösen egyértelmű megfeleltetés, mely folytonos inverzzel rendelkezik, és nem metszi önmagát. A 3D felületek összes lehetséges paraméterezései közül azok a legérdekesebbek és a leginkább vizsgáltak, amelyek vagy a szöget, vagy a területet megőrzik (mindkettőt általában nem tudják). Jól ismert példák ilyen parametrizációkra a térképészetben használt projekciók. A sztereografikus projekció a legrégebbi szögtartó leképezés, 17

amelyet már több mint 2000 éve ismernek. Ezzel ellentétben, egészen a 18. századig kellett várni az első területtartó projekció felfedezésére (Heinrich Lambert). A digitális geometriai feldolgozó alkalmazásokban egy felületet gyakran egy általános háromszöghálóval jelenítenek meg. Ezeknek a hálóknak a parametrizációi szakaszonként lineáris függvények, amelyek a 2D-beli háromszögeket 3D-beli háromszögeknek feleltetik meg. Az alkalmazásoktól függően ezeknek a parametrizációknak különböző fontos tulajdonságai lehetnek, pl.: a szögek megtartása, vagy a textúra megnyúlás minimalizálása. Az elmúlt években rengeteg algoritmust fejlesztettek ki a háló parametrizációk kiszámítására, nagyon eltérő futási időkkel és feltételrendszerekkel. Az eljárások már akár a lehetséges bemeneti paraméterekben is különbözhetnek, más-más topológia definiálása esetén lehet őket alkalmazni. A célfeltételeket tekintve is nagyon változó a helyzet: a szögek, a távolságok vagy a területek minimális változására törekednek, vagy optimális esetben mindháromra egyszerre. Néha ezekre az algoritmusokra háló kisimítási (mesh flattening) módszerek néven is hivatkoznak. 5.3.

Simítási technikák

Amint az előző részben láthattuk, a simítás pontfelhők és háromszöghálók esetén is kiemelkedően fontos és ezáltal gyakran használt művelet. Az 15. ábrán a korábban bemutatott térbeli háromszögháló (2. ábra) simítás utáni eredménye látható. Matematikailag a hálósimítás a háromszöghálón értelmezett 𝑓𝑓: 𝑆𝑆 → 𝑅𝑅 𝑑𝑑 simító függvény fogalmával és annak kiszámításával áll kapcsolatban. E szerint a nagyon általános formula szerint a hálósimítás a geometriai feldolgozás

egy alapvető eszköze. Az 𝑓𝑓 függvényt rugalmasan tudjuk megválasztani aszerint, hogy például a

csúcsok pozícióit, a textúra koordinátákat vagy a csúcsok elmozdulását írja le, így az itt bevezetett technikák hálóparametrizációra, izotropikus újrahálózásra, lyuk betöltésére és háló deformációra is felhasználhatóak lesznek.

18

15. ábra: Simítás eredménye 5.3.1. Zajszűrés A felületek nyers pontokból történő rekonstrukciójának kérdése lényegében megoldottnak tekinthető. Valójában már számos, kereskedelemben is előforduló eszköz van, amely beolvassa az objektumokat és rekonstruálja a felületüket. Azonban az így előállított rekonstruált felület sokszor nagyon sima a szkenner belső zajtalanító folyamatának (zajszűrés) és a különböző képek összesítésének (regisztráció) eredményeként. A pontosság csökkenése nyilvánvaló abban az értelemben, hogy minden végeredményül kapott objektum letisztultnak és simának látszik, láthatóan elvesztve a szemcsésségét és textúráját. A hálósimítás két különböző aspektusát tekinthetjük: a zajszűrést és a lefedést. A zajszűrést arra használjuk, hogy az 𝑓𝑓 függvényből eltávolítsuk a magas frekvenciájú zajt. A legtöbb esetben az 𝑓𝑓

függvény a csúcsok pozícióit jelöli, amelyeket a szkennelés folyamata során megzavarhatnak a magas frekvenciájú zajok. A zajszűrés (magas frekvenciák) és a teljes alak megtartásának feltétele (alacsony frekvenciák) megköveteli a frekvenciák és az alul-áteresztő szűrők fogalmának általánosítását diszkrét háromszöghálókon alkalmazott függvények esetében. A hálók esetén definiált Fourier transzformációk és diffúziós filterek fogalmát is bevezethetjük. A Fourier transzformáció a jel frekvencia spektrumának elemzésére alkalmazott klasszikus eszköz. A Fourier transzformáció az egyváltozós 𝑓𝑓: 𝑅𝑅 → 𝐶𝐶 függvényt képezi le az f (x) térbeli tartománybeli reprezentációjából a frekvencia tartománybeli F(ω) reprezentációjára. Ezáltal 19

lehetőséget nyújt például az alul-áteresztő szűrők hatékony implementációjához. Ehhez először az egyváltozós f (x) függvény Fourier transzformáción alapuló alul-áteresztő szűrőjét vesszük, majd ezt követően tudjuk általánosítani ezeket a jelfeldolgozási fogalmakat háromszögháló esetén is. 5.3.1.1.

Alul-áteresztő szűrők

Általánosan megfogalmazva, a szűrő-technika lényege nem más, mint hogy a cellák értékeit lokálisan befolyásoljuk. Ez a gyakorlatban azt jelenti, hogy a módosítani kívánt cellákon végigfuttatunk egy mozgóablakot, és az ebbe az ablakba eső cellák értékeiből egy statisztikai mutatót számolunk ki, amit az aktuális középső cellába, annak eredeti értéke helyére írunk be. Ez általában egy súlyozott átlagoláshoz hasonlítható. Az együtthatók kiválasztásától függ, hogy ezzel tényleg valamilyen átlagot számítunk ki, vagy ezáltal éppen a kilógó értékeket nagyítjuk fel még jobban. Ezt a szűréshez használt együtthatókat tartalmazó mátrixot kernelnek nevezzük. Az egyik leggyakrabban használt szűrő-technika az alul-áteresztő szűrők (low-pass filter) alkalmazása, amelyek az adott pont környezetének átlagát adják meg. Ezek segítségével az átlagoló, simító hatást olyan értelemben érhetjük el, hogy ha egy adott érték bármelyik irányban (fölfelé vagy lefelé) jelentősen eltér a környezetében találhatóaktól, akkor az alul-áteresztő szűrő eredményeként az már belesimul a környezetébe. Nagy segítséget nyújthat egy alul-áteresztő szűrő használata (azt akár többször is, egymás után alkalmazva) egy túl zajos, érdes felület esetén. Ezzel együtt ennek azonban annyi hátránya lehet, ahogyan azt már korábban is felvetettük, hogy ezáltal a modell részletgazdagsága is csökken. Az alul-áteresztő szűrőknek számos különböző típusa létezik attól függően, hogy a súlyozást milyen módszer alapján valósítják meg. Ezek közül a legegyszerűbb választás, ha minden súly megegyezik (ekkor a térbeli mozgóátlagot kapjuk meg), de a súlyokat csökkenhetjük a távolsággal arányosan is, vagy alkalmazhatunk valamilyen hatványfüggvényt is, esetleg Gauss görbét (Gauss kernel). Ezzel ellentétben a felül-áteresztő szűrők (high-pass filter) éppen az átlagtól már korábban is eltérő értékeket még inkább felerősítik. Ezen szűrők alkalmazása a modell kontúrjának meghatározásakor lehetnek hasznosak, ám ezzel együtt a hibákat is jobban kiemelik. A teljes 1D Fourier keretrendszer ezután általánosítható a (diszkrét) sokaság felületén értelmezett 𝑓𝑓: 𝑆𝑆 → 𝑅𝑅 függvényekre. A sokaság harmonikussága biztosítja a Fourier transzformáció egy 20

természetes általánosítását folytonos és diszkrét sokaság felületeire. Ez lehetővé teszi az ideális alul-áteresztő szűrést az ω max egzakt vágási frekvenciát használva. Ez az eljárás sajnos sok alkalmazás esetén túl költséges, mivel a potenciálisan nagyon nagy Laplace mátrix ehhez szükséges sajátvektor felbontását numerikusan túl bonyolult kiszámítani. 5.3.1.2.

Diffúziós folyamat

Egy kevésbé költséges és ezáltal jóval praktikusabb eljárás a diffúziós folyamat. Ez az eljárás a magas frekvenciák csillapításával hozható kapcsolatba, egy Gauss kernellel megszorozva őket, ellentétben a korábbiakkal, amikor minden, adott küszöb feletti frekvenciát azonnal levágtunk. A diffúziós folyamat egy matematikailag jól értelmezhető modell az adott f (x; t) jel simításának időtől függő folyamatára. A diffúziós folyamat által számos fizikai folyamatot lehet leírni (többek között a hődiffúziót vagy a Brown mozgást). A diffúziós folyamatot valamely diffúziós egyenlettel modellezhetjük. Például ha f (x; t) jelöli a t hőmérsékletet az x pontban, akkor az egyenlet a testen belüli tartós hődiffúziót írja le, ezért hőegyenletnek is nevezik. A diffúziós egyenletet továbbá sokaság felületén értelmezett 𝑓𝑓: 𝑆𝑆 → 𝑅𝑅 függvény simítására is tudjuk alkalmazni.

5.3.2. Hálólefedés A diffúziós folyamat elsődleges alkalmazása a magas frekvenciájú zajok eltávolítása az alacsony frekvenciák megőrzése mellett. Ezzel ellentétben, a hálólefedés a lehető legjobban kisimítja a függvényt, azért, hogy pl. a lehető legsimább felület lefedést vagy a lehető legsimább alakdeformációt kapjuk meg. A lehető legsimább kifejezés azt jelenti, hogy bizonyos lefedési energiákat minimalizálni kell, jellemzően a görbületek és a magasabb rendű deriváltak esetében. Megmutatható, hogy a hálólefedés közvetlenül számolja az iteratív zajszűrő folyamatok határfelületeit, ami megmutatja az összefüggést a két megközelítés között. Össszefoglalásképpen tehát elmondhatjuk, hogy három különböző, de szorosan összefüggő eljárást tudunk alkalmazni sokaság, illetve háromszög felületek simítására. A sokaság harmónikussága biztosítja a Fourier transzformáció egy elegáns általánosítását felületi háromszöghálók esetén, bár számítási igénye a legtöbb alkalmazás esetén túl sok. Míg a diffúziós folyamatok elsődlegesen a magasabb frekvenciájú zajokat távolítják el az alacsony frekvenciájúak megtartása mellett, addig ezzel ellentétben, a felület lefedési eljárás célja a lehető 21

legsimább alakzatok kiszámítása. Az nyilvánvalóan az alkalmazástól függ, hogy valójában hogyan mérhetjük a simaságot vagy lefedettséget. A diffúziós és magasabb rendű Laplace folyamatokat könnyű implementálni, továbbá hatékony eszközt nyújtanak a magas frekvenciájú zajok kiszűrésére. A felület lefedés kiszámítja a lehető legsimább felületet, amelyet a hozzákapcsolódó simítási folyamatok határfelületei alkotnak. Itt érdemes megjegyeznünk, hogy általában elegendő csak az izotropikus, illetve lineáris simítási technikákkal foglalkozni, hiszen könnyebb értelmezhetőségük mellett a legtöbb alkalmazás esetén már ezek is megfelelő eredményt adhatnak. 5.4.

Hatékony háromszögháló, áthálózási technikák

Különböző modellezési problémáknál, illetve szimulációs feladatoknál gyakran szükség van arra, hogy javítsuk valamilyen módon annak a poligonhálónak a minőségét, amely által felületünk reprezentált. Emiatt újabb és újabb algoritmusok látnak napvilágot, amelyek segítségével ez az ún. „áthálózás” hatékonyan, az elvárt céloknak megfelelően valósítható meg. Ilyenkor természetesen olyan új poligonháló megalkotására törekszünk az eredetit felhasználva, amely azt kellően jól approximálja, azaz közelíti (a hibahatár sok esetben függ attól, hogy milyen jellegű problémához szeretnénk majd felhasználni az új hálót), és megfelel bizonyos minőségi elvárásoknak. Elsődleges cél szokott lenni ezeknél a módszereknél a bemenetként szolgáló poligonháló egyszerűsítése, komplexitásának csökkentése a hatékonyabb feldolgozhatóság érdekében. Egy további cél a már említett minőségemelés, hogy a gyorsaság mellett kifinomultabb igényeknek, specializált szoftverekben való felhasználhatóságnak is eleget tegyen a modellünk. Minőség alatt itt olyan tulajdonságokat értünk, mint a mintavételezés sűrűsége, szabályosság, méret, vagy éppen a poligonhálót alkotó sokszögek formája. 5.4.1. Lokális szerkezeti tulajdonságok Egy poligonháló lokális szerkezetét olyan adatokkal tudjuk leírni, mint pl. a poligon típusa, alakja. Az alábbiakban néhány ilyen tulajdonságra részletesen is kitérünk. A legtöbb esetben az a célunk az áthálózásnál, hogy elérjük, hogy a poligonok háromszögek vagy négyszögek legyenek. Fontos megjegyezni, hogy a két szerkezet nem annyira idegen egymástól. Négyszögekből könnyen generálhatóak háromszöglapok az átlóval történő kettévágás 22

nyomán. Ha háromszöglapjaink vannak, akkor a súlypont, valamint az élek felezőpontjai által egy háromszöget három négyszöggé tudunk bontani. Egy másik megoldásnál egy háromszög esetén a csúcsokat összekötjük a súlyponttal, majd elhagyjuk az eredeti háromszögek éleit.

16. ábra: Háromszöghálóról négyszöghálóra való áttérés két lehetséges módja. Fontos észrevennünk, hogy a 16. ábra jobb oldalán szemléltetett módszernél a létrejött négyszögek csúcsai nem feltétlenül illeszkednek egy síkra. (Az ilyen négyszögeket „térbeli négyszög”-ként szokta említeni a szakirodalom. Ezeket a modellezőprogramok általában egy színnel árnyalják, habár legtöbbször biztosak lehetünk abban, hogy megtörne rajtuk a fény.) Alakjuk szerint megkülönböztetünk izotropikus, illetve anizotropikus elemeket. Azt mondhatjuk, hogy az izotropikus elemek alakja minden irányban „egyenletesen változik”, ennélfogva ideális esetben háromszögeknél a szabályos háromszöget, négyszögeknél a négyzetet várjuk el.

17. ábra: A bal oldalon alacsony, a jobb oldalon magas izotrópiájú elemek láthatók. 23

Ez a tulajdonság mérhető, háromszögek esetében pl. tekinthetjük a köré írható köre sugarának és a legrövidebb oldal hosszának hányadosát. Az izotropikus elemek szerepe kiemelten fontos bizonyos numerikus alkalmazásoknál, míg anizotropikus elemeket használva sokszor kevesebbel és hatékonyabban is tudunk approximálni, mintha izotropikusokat használnánk. Egy másik fontos tényező az elemsűrűség. Uniform elosztás esetén a felületen egyenletesen oszlanak el a sokszögek, ellenkező esetben egyszerűen azt mondjuk, hogy az elosztás nem uniform. Előfordul, hogy a nagyobb görbülettel bíró területeknél több háromszögre van szükség a megfelelő minőség elérése érdekében. 5.4.2. Globális szerkezeti tulajdonságok Egy háromszögháló egy csúcsát regulárisnak nevezzük, ha hat (belső csúcs esetén), illetve négy (a felület határán elhelyezkedő csúcs esetén) szomszédja van. Négyszögháló esetében ez a két szám rendre négy és három. A nem reguláris csúcsokat irregulárisnak nevezzük. Egy háló globális szerkezetét tekintve lehet reguláris, irreguláris, szemireguláris, illetve erősen reguláris. Irreguláris hálók esetében nem tapasztalható semmilyen szabályosság, regularitás. Szemireguláris hálót akkor kaphatunk, ha egy durva bemeneti poligonhálót valamilyen reguláris subdivision módszerrel osztunk további részekre. A subdivision felületekről kiváló összefoglalót nyújt a SIGGRAPH 2000 nevű konferencián tartott kurzus [9]. Ezeket leginkább a multirezolúciós analízis és modellezés képes jól felhasználni. Erősen reguláris hálóban a legtöbb csúcs reguláris, a szemireguláristól annyiban különbözik, hogy nem szükséges, hogy valamilyen subdivision módszerrel jussunk el az eredményig. Ezeknek numerikus szimulációknál vehetjük legnagyobb hasznát. Végezetül egy háló akkor reguláris, ha minden csúcsa is az. Nagy előnye az ilyen tulajdonságú hálóknak, hogy egy kétdimenziós tömb segítségével könnyen reprezentálhatóak, így igen hatékony munkavégzést tesznek lehetővé. 5.4.3. Voronoi diagram, Delaunay háromszögelés Amikor poliéderhálókat készítünk, vagy szeretnénk azokat áthálózni, mindkét címben említett fogalom fontos szerepet kaphat, lássuk tehát kicsit részletesebben, miről is van szó. 24

Legyen 𝑃𝑃 ∈ ℝ𝑘𝑘 , 𝑃𝑃 = {𝑷𝑷1 , 𝑷𝑷2 , … , 𝑷𝑷𝑛𝑛 } pontok egy halmaza, ahol 𝑘𝑘 értéke 2 vagy 3. Ekkor egy 𝑷𝑷𝑖𝑖

pont Voronoi tartománya a következőképpen definiált:

𝑉𝑉𝑡𝑡 (𝑷𝑷𝑖𝑖 ) = {𝑿𝑿 ∈ ℝ𝑘𝑘 : ‖𝑿𝑿 − 𝑷𝑷𝑖𝑖 ‖ < �𝑿𝑿 − 𝑷𝑷𝑗𝑗 �, ∀𝑖𝑖 ≠ 𝑗𝑗}

Ez szemléletesen azt jeleni, hogy azok a 𝑃𝑃-beli pontok tartoznak egy pont tartományába,

amelyek a halmaz pontjai közül hozzá vannak a legközelebb. Az így definiált régiók ℝ𝑘𝑘 egy felosztását adják, az egyes tartományok élei pedig felfeszítik a 𝑃𝑃 ponthalmaz Voronoi diagramját. A diagram duális szerkezetével pedig a Delaunay háromszögeléshez jutunk.

18. ábra: Kékkel a Voronoi diagramot, míg pirossal a Delaunay háromszögelést láthatjuk. Érdekes megfigyelnünk, hogy a háromszögelés megmutatja a ponthalmaz konvex burkát is egyben. Fontos fogalom még a fentieken túl a háromszögelés bizonyos halmazra való leszűkítése, melyet síkban és térben is értelmezhetünk. A 19. ábrán azt láthatjuk, hogy a zölddel jelzett halmazra, azaz egy görbére szűkítjük le a háromszögelést, annak azon éleit tekintjük, melyekhez tartozó duális Voronoi diagram élek metszik a tekintett görbét.

25

19. ábra: Pirossal a leszűkített háromszögelést láthatjuk, zölddel az annak alapját adó halmazt, kékkel az eredeti háromszögelést. Ez a gondolat térben is általánosítható, ekkor egy 𝑆𝑆 halmazra való leszűkítés azt jelenti, hogy a térbeli Delaunay háromszögeléshez tartozó azon háromszöglapokat tekintjük csak, amelyeknek Voronoi diagramhoz tartozó duális éleinek metszete az 𝑆𝑆 halmazzal nem üres.

5.4.4. Háromszög alapú áthálózás

Olyan izotropikus hálót célzó algoritmusokkal fogunk ebben az alfejezetben foglalkozni, amelyek háromszögek konstrukcióján alapulnak. A legtöbb a következő három nagy csoport valamelyikébe sorolható: mohó, inkrementális, illetve variációs algoritmusok.

20. ábra. Izotropikus előállítást célzó algoritmus be- és kimenete. Érdemes megfigyelni, hogy a szabályos háromszögek árán fontos részleteket is elveszíthetünk (orr területe). 26

21. ábra. Balra szintén egy izotropikus előállítást célzó algoritmus bemenete, jobbra a kimenete látható. Az alul lévő két ábra egy közelebbi nézőpontból mutatja ugyanazt a két modellt, hogy jobban látszódhassanak a részletek. 5.4.4.1.

Boissonat és Oudot mohó algoritmusa

Az alapötlete az algoritmusnak egy 3D Delaunay háromszögelés finomításán és szűrésén alapszik. Minden egyes finomítási lépésben a bemeneti felület egy tekintett pontja a háromszögelés részévé válik. Az újabb és újabb pont annak a folyamatnak a mentén választódik ki, melynek során tekintjük az 𝑆𝑆 bemeneti felület aktuálisan felépített Voronoi diagrammal vett

metszéspontjait. Más szóval, a Voronoi diagram a bemeneti felület feltérképezésére szolgál a finomítási folyamat során. A szűrési folyamat abból áll, hogy mindig frissítjük a háromszögelést, leszűkítve azt 𝑆𝑆-re. Ezt a leszűkítést 𝐷𝐷𝐷𝐷𝑙𝑙𝑆𝑆 (𝑃𝑃)-vel fogjuk jelölni a továbbiakban. A pszeudokód

ismertetése előtt fontos, hogy tisztázzunk néhány további alapvető fogalmat. 27

Egy felületi Delaunay gömbön olyan, 𝑆𝑆-re eső középponttal rendelkező gömböt értünk, mely 𝐷𝐷𝐷𝐷𝑙𝑙𝑆𝑆 (𝑃𝑃) egy lapja köré írható. Mivel ilyen tulajdonságú gömbből egy adott lapot tekintve több is

létezhet, emiatt a jelölés egyértelműsítése végett 𝐺𝐺𝑙𝑙 = 𝐺𝐺(𝑪𝑪𝑙𝑙 , 𝑟𝑟𝑙𝑙 ) fogja jelenteni azt, amelyik a leszűkített háromszögelés 𝑙𝑙 lapjához tartozik, 𝑪𝑪𝑙𝑙 a középpontja, 𝑟𝑟𝑙𝑙 pedig a sugara. Síkban

természetesen gömbök helyett körökről beszélünk.

Egy 𝑂𝑂 objektum 𝐾𝐾𝑡𝑡 (𝑂𝑂) középtengelyét azok a pontok alkotják, amelyeknek több, mint egy legközelebbi pontja van 𝑂𝑂 határvonalával.

22. ábra: Ebben a síkbeli esetben pirossal a kék objektum középtengelye látható. Azt a gömböt, amelynek a középpontja erre a tengelyre illeszkedik, és amelyet tartalmaz teljes egészében az objektum, középgömbnek fogjuk nevezni. Az 𝑂𝑂 objektum egy 𝒀𝒀 pontjának a

középtengelytől való távolságát 𝑑𝑑𝑘𝑘 (𝒀𝒀)-nal fogjuk jelölni. Az algoritmus során 𝐷𝐷𝐷𝐷𝑙𝑙𝑆𝑆 (𝑃𝑃)-t finomítjuk, a felületi Delaunay gömbök sugarát hasonlítva a fent említett 𝑑𝑑𝑘𝑘 távolságok

figyelembevételével. Esetünkben az objektumunkat az 𝑆𝑆 bemeneti felület pontjainak komplementer halmaza fogja alkotni.

Az algoritmusunk bemeneti adataként szükséges megadnunk csúcsok egy 𝑃𝑃 halmazát, annak

𝐷𝐷𝐷𝐷𝐷𝐷(𝑃𝑃) háromszögelését, illetve utóbbi 𝑆𝑆-re való leszűkítését, ahol 𝑆𝑆 a kiindulási felületünk.

Lapok egy 𝐿𝐿 halmazára is szükségünk lesz, ebben gyűjtjük össze 𝐷𝐷𝐷𝐷𝑙𝑙𝑆𝑆 (𝑃𝑃) úgynevezett „rossz”

lapjait. Egy 𝑙𝑙 lap „rosszasága” azt jelenti, hogy 𝐵𝐵𝑙𝑙 = (𝑪𝑪𝑙𝑙 , 𝑟𝑟𝑙𝑙 ) felületi Delaunay gömbjére 𝑟𝑟𝑙𝑙 > 𝜙𝜙(𝑪𝑪𝒍𝒍 ) teljesül, ahol 𝜙𝜙 egy felhasználó által definiált, 𝑆𝑆 fölött értelmezett, valós értékű és 128

Lipschitz tulajdonságú függvény. A kezdő 𝑃𝑃 ponthalmazunkat úgy tudjuk meghatározni, hogy tekintünk három kellően közel lévő pontot 𝑆𝑆 minden csatlakozó komponenséről. Ezután az algoritmust az alábbi pszeudokóddal írhatjuk le. mohó_algoritmus() amíg 𝑳𝑳 nem üres

tekintsünk egy 𝒍𝒍 ∈ 𝑳𝑳 elemet

𝑪𝑪𝒍𝒍 legyen 𝒍𝒍 duális élének és 𝑺𝑺-nek a metszépontja

vegyük be 𝑪𝑪𝒍𝒍 -t a 𝑷𝑷 pontjai közé

frissítsük 𝑫𝑫𝑫𝑫𝑫𝑫(𝑷𝑷)-t

frissítsük 𝑫𝑫𝑫𝑫𝒍𝒍𝑺𝑺 (𝑷𝑷)-t

frissítsük az 𝑳𝑳 halmazt is úgy, hogy

távolítsuk el 𝑳𝑳 azon lapjait, amelyek többé már nem elemei 𝑫𝑫𝑫𝑫𝒍𝒍𝑺𝑺 (𝑷𝑷)-nek

adjuk hozzá 𝑳𝑳-hez 𝑫𝑫𝑫𝑫𝒍𝒍𝑺𝑺 (𝑷𝑷) új „rossz” lapjait

Megmutatható, hogy 𝜙𝜙 alkalmas megválasztásával az algoritmus véges sok lépésben véget ér. 5.4.4.2.

Inkrementális algoritmus

Az algoritmusnak célhosszúságot kell adnunk az élekre vonatkozóan, a hosszabb élek darabolásával, a csúcsok áthelyezésével dolgozva fog megoldást szolgáltatni a problémára, igyekezvén elérni, hogy a kimenet minden élének hossza megközelítőleg a választott legyen. Inkrementális_algoritmus(célhossz) also

= 4/5 * célhossz

felso = 4/3 * célhossz ciklus i = 0-tól 10-ig 1-gyel hosszú_élek_vágása(felső)

rövid_élek_törlése(alsó, felső) szomszédok_számának_kiegyenlítése( ) simítási_szűrő_alkalmazása( ) felületre_vetítés( ) 29

23. ábra: Az inkrementális algoritmus által használt módosítások balról jobbra haladva a következők. Él törlése, él kettéosztása, élek cseréje, csúcs áthelyezése. Az algoritmus lépései a következők: Inkrementális_algoritmus(célhossz) also

= 4/5 * célhossz

felso = 4/3 * célhossz ciklus i = 0-tól 10-ig 1-gyel hosszú_élek_vágása(felső)

rövid_élek_törlése(alsó, felső) szomszédok_számának_kiegyenlítése( ) simítási_szűrő_alkalmazása( ) felületre_vetítés( ) Lássuk,

hogy az

algoritmusban

említett

lépések

részletesebben

mit

jelentenek.

A

hosszú_élek_vágása(felső) függvény az éppen aktuális háló minden élét megvizsgálja. Ha egy él hossza nagyobb, mint a „felső” nevű változóban megadott küszöbérték, az adott él két új élre bomlik, ennélfogva kettő helyett négy háromszögünk lesz. Pszeudokóddal tehát: hosszú_élek_vágása(felső)

amíg létezik olyan e él, amire hossz(e) > felső vágd el e-t a középpontjánál

30

A rövid_élek_törlése(alsó, felső) függvény töröl minden olyan élt, amelyiknek a hossza az „alsó” nevű küszöbértéknél kisebb. Egy egyszerű törléssel azonban keletkezhetnek olyan élek, amelyek hossza nagyobb lenne „felső” értékénél, azaz ellene dolgoznánk az előbb vázolt függvénynek. Éppen emiatt a függvényben végrehajtunk a törlés előtt egy vizsgálatot, s ha a keletkező él hosszabb lenne az elvártnál, a törlés nem valósul meg. rövid_élek_törlése(alsó,felső) amíg létezik olyan e él, amire hossz(e) < alsó e két végpontja legyen A és B, A-ból induló élek legyenek t[1],…,t[n] törlés_rendben = igaz ciklus i = 1-től n-ig 1-gyel

ha a B-t és t[n]-t összekötő él > felső, akkor törlés_rendben = hamis

ha törlés_rendben = igaz, akkor töröld

az

e

élt

úgy,

hogy

az

A

csúcsot

B-be

mozgatod e mentén A szomszédok_számának_kiegyenlítése( ) függvény kiegyenlíti az egyes csúcsok szomszédjainak számában mutatkozó egyenetlenségeket, a szemléltetett élcserék megvalósítása által. A cél(c) függvény értéke belső csúcsnál hat, míg peremen lévő csúcs esetében négy. Az algoritmus megvizsgálja, hogy az élcserével vagy anélkül érhető el kisebb eltérés, s eszerint cselekszik az alábbi pszeudokód szerint. szomszédok_számának_kiegyenlítése ( ) ciklus minden e élre legyenek

A,

B,

C,

D

az

e

élhez

tartozó

két

háromszög csúcsai eltérés_előtte = abs(szomszédok_száma(A)-cél(A)) + abs(szomszédok_száma(B)-cél(B)) + abs(szomszédok_száma(C)-cél(C)) + abs(szomszédok_száma(D)-cél(D)) csere( e ) //e innentől eddig nem létező él! 31

eltérés_utána

= abs(szomszédok_száma(A)-cél(A)) + abs(szomszédok_száma(B)-cél(B)) + abs(szomszédok_száma(C)-cél(C)) + abs(szomszédok_száma(D)-cél(D))

Ha eltérés_előtte <= eltérés_utána, akkor csere( e ) A simítási_szűrő_alkalmazása( ) függvény egy iteratív simítási szűrőt alkalmaz a hálónkon. Ha 𝑷𝑷 a hálónk egy pontja, és 𝒏𝒏 az ott értelmezett normálvektor, továbbá 𝑆𝑆(𝑷𝑷) jelöli 𝑷𝑷 1

szomszédjainak a halmazát, tekintsük a 𝑸𝑸 = |𝑆𝑆(𝑷𝑷)| ∑𝑷𝑷𝒊𝒊 ∈𝑆𝑆(𝑷𝑷) 𝑷𝑷𝒋𝒋 pontot. Ezt felhasználva a simítási lépés a következőképpen történik.

simítási_szűrő_alkalmazása ( ) ciklus minden C csúcsra Q[C]

legyen

a

C

szomszédjaiból

álló

ponthalmaz

tömegközéppontja ciklus minden C csúcsra legyen

P[C]

és

n[C]

a

pontok

pozíciói

és

a

normálvektorok P[C] = Q[C] + < n[C],(P[C]-q[C]) * n[C] > A fenti függvény a pontokhoz tartozó érintősíkon határoz meg az eredeti pont helyett egy újat, ezt még vissza kell vetítenünk a felületre, ezt valósítja meg a felületre_vetítés( ) függvényünk. Léteznek természetesen négyszögháló alapján működő algoritmusok is, de ezekre, valamint az említett variációs algoritmusokra a fejezet keretei között nem térünk ki most részletesebben. 5.5.

Differenciálgeometriai alapismeretek

Ebben az alfejezetben megismerkedünk azokkal az alapfogalmakkal, amelyek lehetővé teszik felületek olyan lokális tulajdonságainak vizsgálatát, melyek témánk szempontjából kiemelt fontossággal bírnak. A differenciálgeometria a matematikának az az ága, amely ezekhez az elemzésekhez biztosít hathatós eszközöket. A könnyebb megértés érdekében néhány fogalmat 32

először síkgörbék kapcsán vezetünk be, a későbbiekben pedig ezt követi a felületekkel kapcsolatos ismeretanyag. 5.5.1. Görbeelméleti alapok A görbékkel való közelebbi ismerkedésünket kezdjük egy nagyon egyszerű példával, és képzeljük el, hogy egy kisgyermek a frissen festett falra, filctollal girbegurba alakzatot rajzol. Ekkor a falon, a mozgó tollhegy nyomán egy görbe jelenik meg. Ha a fal síkját ellátjuk egy koordinátarendszerrel, s minden időpillanatban tekintjük az origóból a toll hegye által mutatott pontba mutató helyvektort, máris létrehoztunk egy adott (idő)intervallumon értelmezett vektorértékű függvényt, mely elvezethet minket az általánosított görbefogalomig. 5.5.1.1.

Parametrizált görbék

Görbén olyan alakzatot fogunk érteni, amelyet elő lehet állítani egy 𝒈𝒈: [𝑎𝑎, 𝑏𝑏] → ℝ2 vektorértékű

függvény képeként.

24. ábra: Görbe paraméteres előállítása A 𝒈𝒈(𝑡𝑡) = (𝑥𝑥(𝑡𝑡), 𝑦𝑦(𝑡𝑡))𝑇𝑇 , 𝑡𝑡 ∈ [𝑎𝑎, 𝑏𝑏] ⊂ ℝ jelölést alapul véve megköveteljük azt is, hogy az 𝑥𝑥(𝑡𝑡) és

𝑦𝑦(𝑡𝑡) ún. koordinátafüggvények 𝑡𝑡 szerint folytonosan differenciálhatóak legyenek. Ezt a fajta konstrukciót a görbe paraméteres előállításának nevezzük.

Adott 𝑡𝑡 paraméter esetén a 𝒈𝒈′(𝑡𝑡) = (𝑥𝑥′(𝑡𝑡), 𝑦𝑦′(𝑡𝑡))𝑇𝑇 vektort a görbe 𝒈𝒈(𝑡𝑡) pontjában értelmezett

érintővektorának nevezzük. Ha az előző példánkat vesszük alapul, akkor amennyiben a 𝑡𝑡

paraméter az időt jelöli, úgy az érintővektor a 𝑡𝑡 időpillanathoz tartozó sebességvektornak felel

meg. Vizsgálódásaink során feltesszük, hogy parametrizált görbénk reguláris, azaz bármely 33

𝑡𝑡 ∈ [𝑎𝑎, 𝑏𝑏] esetén igaz, hogy az első derivált „nem tűnik el”, azaz 𝒈𝒈′(𝑡𝑡) ≠ 𝟎𝟎 (ahol 𝟎𝟎 a nullvektort jelöli). A görbe 𝑡𝑡 paraméterértékhez tartozó 𝒈𝒈(𝑡𝑡) pontjában értelmezett normálvektorának az 𝒏𝒏(𝑡𝑡) = 𝒈𝒈′ (𝑡𝑡)⊥ /‖𝒈𝒈′(𝑡𝑡)⊥ ‖ vektort nevezzük, ahol ⊥ az origó körüli 90 fokos (pozitív irányú)

elforgatást jelöli.

Fontos megjegyeznünk, hogy mivel a görbe maga egy függvény képeként áll elő, eltérő paraméterezés esetén is kaphatjuk ugyanazt az eredményt. Például a 𝒈𝒈1 (𝑡𝑡) = (𝑡𝑡, 𝑡𝑡)𝑇𝑇 és a

𝒈𝒈2 (𝑡𝑡) = (𝑡𝑡 3 , 𝑡𝑡 3 )𝑇𝑇 függvények ugyanazt a görbét határozzák meg 𝑡𝑡 ∈ [0,1] esetén, pontosabban a

(0,0)𝑇𝑇 és (1,1)𝑇𝑇 végpontú szakaszt. Viszont fontos észrevennünk, hogy általában egy adott 𝑡𝑡

helyen vett helyettesítési értékek ilyenkor már nem lesznek ugyanazok a két görbe esetén, azaz 𝒈𝒈1 (𝑡𝑡) ≠ 𝒈𝒈2 (𝑡𝑡). Ezt a problémát kiküszöbölhetjük egy átparaméterezés segítségével, az 𝑢𝑢(𝑡𝑡) = = 𝑡𝑡 3

választással

elérhetjük,

hogy

𝒈𝒈1 �𝑢𝑢(𝑡𝑡)� = 𝒈𝒈1 (𝑡𝑡 3 ) = 𝒈𝒈2 (𝑡𝑡)

teljesüljön.

A

differenciálgeometria olyan tulajdonságokat vizsgál, amelyek függetlenek a paraméterezés megválasztásától, ilyen például az ívhossz és a görbület. 5.5.1.2.

Ívhossz

Jogosan merül fel bennünk az igény, hogy meg tudjunk mérni, milyen „hosszú” egy adott görbe, egy mozgó pont pályája esetén mekkora a megtett út. Egy 𝒈𝒈: [𝑎𝑎, 𝑏𝑏] → ℝ2 görbe [𝑐𝑐, 𝑑𝑑] ⊂ [𝑎𝑎, 𝑏𝑏] 𝑑𝑑

intervallumhoz tartozó ívének hosszát ℎ(𝑐𝑐, 𝑑𝑑) = ∫𝑐𝑐 ‖𝒈𝒈′(𝑡𝑡)‖ 𝑑𝑑𝑑𝑑 módon számolhatjuk ki. Érdemes

észrevennünk, hogy a képletben megjelent az érintővektor, amiről már volt szó az előbbiekben. 𝑡𝑡

Ez lehetőséget ad arra, hogy az ívhosszt az 𝑚𝑚 = 𝑚𝑚(𝑡𝑡) = ∫𝑎𝑎 ‖𝒈𝒈′(𝑢𝑢)‖ 𝑑𝑑𝑑𝑑 átparaméterezés segítségével bevezessük paraméterként a következők szerint. 𝑏𝑏

Legyen H a teljes görbe ívhossza, azaz 𝐻𝐻 = ℎ(𝑎𝑎, 𝑏𝑏) = ∫𝑎𝑎 ‖𝒈𝒈′(𝑡𝑡)‖ 𝑑𝑑𝑑𝑑. Ekkor a görbe előállítható

𝒈𝒈2 : [0, 𝐻𝐻] → ℝ2 , 𝑡𝑡 ↦ 𝒈𝒈2 (𝑡𝑡) = 𝒈𝒈(𝑚𝑚−1 (𝑡𝑡)) alakban is, s így 𝒈𝒈2 egy adott 𝑡𝑡 paraméterértékhez

tartozó 𝒈𝒈2 (𝑡𝑡) pontja és a görbe 𝒈𝒈2 (0) kezdőpontja között mért ívhossz éppen 𝑡𝑡-vel fog megegyezni.

Látni fogjuk, hogy bár a görbéknél ez mindig kivitelezhető, hasonló ügyeskedés felületek esetén már nem feltétlenül valósítható meg.

34

5.5.1.3.

Görbület

A görbülettel szemléletesen szólva azt mérhetjük, hogy egy görbe egy adott pontban egy egyeneshez viszonyítva mekkora mértékben „görbül”. Legyen adott egy ívhossza szerint paraméterezett, reguláris 𝒈𝒈 görbe, ekkor annak egy 𝒈𝒈(𝑚𝑚) pontjában mérhető görbületét a

𝜅𝜅(𝑚𝑚) = ‖𝒈𝒈’’(𝑚𝑚)‖ képlettel határozhatjuk meg. Amennyiben nem teljesül az ívhossz szerinti paraméterezettség, a fentiekben ismertetett átparaméterezéssel ezt biztosítani tudjuk. A görbület a 𝒈𝒈’’(𝑚𝑚) = 𝜅𝜅(𝑚𝑚)𝒏𝒏(𝑚𝑚) formula alapján is kiszámolható, ezzel kapcsolatot teremtve egy adott

pontbéli érintővektor deriváltja és az ott értelmezett normálvektor között. Ahogy azt elvárjuk, ha egy görbe minden pontjában a görbülete nulla, akkor szükségszerűen egy szakasszal van dolgunk. Ha viszont egy síkgörbe minden pontjában ugyanakkora (nem nulla) görbülettel bír, akkor biztosan körívről van szó. Térben ennek a feltételnek a hengeres csavarvonal felel meg. A görbület szoros kapcsolatban áll a simulókör fogalmával is. Egy adott pontban értelmezett simulókör olyan kör, amely legjobban közelíti a görbét a pont környezetében, meghatározni pedig a következőképpen tudjuk. Tekintsünk a görbénk három pontját, legyenek ezek 𝒈𝒈(𝑡𝑡− ), 𝒈𝒈(𝑡𝑡) és 𝒈𝒈(𝑡𝑡+ ), ahol 𝑡𝑡− < 𝑡𝑡 < 𝑡𝑡+ . Legyen továbbá 𝑘𝑘(𝑡𝑡− , 𝑡𝑡, 𝑡𝑡+ ) az erre a három pontra

egyértelműen illeszkedő kör. Ekkor a 𝑡𝑡 paraméterértékhez tartozó 𝒈𝒈(𝑡𝑡) görbepontban értelmezett

𝑘𝑘(𝑡𝑡) simulókör: 𝑘𝑘(𝑡𝑡) = lim𝑡𝑡− ,𝑡𝑡+→𝑡𝑡 𝑘𝑘(𝑡𝑡− , 𝑡𝑡, 𝑡𝑡+ ). A simulókör sugara a 𝒈𝒈(𝑡𝑡) pontban az ott érvényben lévő görbület reciproka. 5.5.2. Felületelméleti alapok A görbék esetében a görbület és az ívhossz nemcsak a paraméterezéstől független, hanem merev mozgások során sem változik meg. Hasonló tulajdonságokat fogunk vizsgálni felületek esetében is. Felületeket többféle módon határozhatunk meg, beszélhetünk implicit, vagy az előzőekben ismertetetthez hasonló paraméteres megadási módról, de ahogy a 3D rekonstrukciós eljárások esetében sokszor lenni szokott, poligonhálóval közelített felületekkel kell dolgoznunk. Ebben az alfejezetben a paraméteres előállítást vesszük górcső alá, és az ennek ismeretében számolható néhány fontosabb differenciálgeometriai tulajdonságot.

35

5.5.2.1.

Parametrizált felületek

A konstrukcióhoz az elgondolás a már a görbéknél ismertetetthez teljesen hasonló. Felületek esetén nem egy valós intervallumot képezünk ℝ2 -be (vagy ℝ3 -ba) egy vektorértékű függvénnyel,

hanem az ℝ2 egy részhalmazát ℝ3 -ba. A felületek ilyen függvények képeként fognak előállni. Egy egyszerűbb példának hozhatjuk itt az 𝒇𝒇𝑠𝑠 : [0,1] × [0,1] → ℝ3 , (𝑢𝑢, 𝑣𝑣) ↦ 𝒇𝒇(𝑢𝑢, 𝑣𝑣) = (3, 𝑢𝑢, 𝑣𝑣)𝑇𝑇

függvény képeként előálló felületet, ami nem más, mint egy [𝑦𝑦, 𝑧𝑧] koordinátasíkkal párhuzamos négyzet.

25. ábra: Az origó középpontú gömb paraméteres előállításához felhasznált szögek. Még egy példaként említhetjük az 𝑂𝑂(𝑥𝑥0 , 𝑦𝑦0 , 𝑧𝑧0 ) középpontú, 𝑟𝑟 sugarú gömb előállítását.

𝒇𝒇𝑔𝑔 : [0, 2𝜋𝜋] × [0, 𝜋𝜋] → ℝ3 , (𝜃𝜃, 𝜙𝜙) ↦ 𝒇𝒇𝒈𝒈 (𝜃𝜃, 𝜙𝜙) = (𝑅𝑅 cos 𝜃𝜃 cos 𝜙𝜙 , 𝑅𝑅 sin 𝜃𝜃 cos 𝜙𝜙 , 𝑅𝑅 sin 𝜃𝜃)𝑇𝑇

Ezekben az esetekben is megfigyelhetjük, hogy az egyes koordinátákat külön függvényekkel állítjuk

elő,

azaz

általánosan

egy

parametrizált

felületet

mindig

𝒇𝒇(𝑢𝑢, 𝑣𝑣) = (𝑥𝑥(𝑢𝑢, 𝑣𝑣), 𝑦𝑦(𝑢𝑢, 𝑣𝑣), 𝑧𝑧(𝑢𝑢, 𝑣𝑣))𝑇𝑇 formában fogunk tudni leírni.

Érdemes szót ejteni azokról a görbékről, amelyeket úgy kapunk, hogy az egyik paramétert rögzítjük, míg a másikat futni hagyjuk a teljes paramétertartományon. Azaz, ha tekintjük pl. a

𝒈𝒈: [0, 𝜋𝜋] → ℝ3 , 𝜙𝜙 ↦ 𝒈𝒈(𝜋𝜋, 𝜙𝜙) = (𝑅𝑅 cos 𝜋𝜋 cos 𝜙𝜙 , 𝑅𝑅 sin 𝜋𝜋 cos 𝜙𝜙 , 𝑅𝑅 sin 𝜋𝜋)𝑇𝑇 görbét, a felület egy 36

ún. paramétervonalához jutunk. A földgömb esetén ezeknek a paramétervonalaknak a hosszúsági és a szélességi körök felelnek meg. 5.5.2.2.

Normál- és érintővektorok, ívhossz és felszín kiszámítása

A görbékhez hasonlóan felületek esetében is beszélhetünk adott pontbéli érintővektorról, azonban ebből nem csak egy létezik. A két legalapvetőbb a vizsgált ponton áthaladó paramétervonalak szerint értelmezett, a már említett módon definiált görbék adott pontbeli 𝑇𝑇

érintővektora szolgáltatja a megoldást. Ha az 𝒇𝒇(𝑢𝑢, 𝑣𝑣) = �𝑥𝑥(𝑢𝑢, 𝑣𝑣), 𝑦𝑦(𝑢𝑢, 𝑣𝑣), 𝑧𝑧(𝑢𝑢, 𝑣𝑣)� felületet vizsgáljuk annak 𝒇𝒇(𝑢𝑢0 , 𝑣𝑣0 ) pontjában, az egyes változók szerinti parciális deriváltak ezen a helyen vett helyettesítési értékei, azaz 𝐷𝐷1 𝒇𝒇(𝑢𝑢0 , 𝑣𝑣0 ) és 𝐷𝐷2 𝒇𝒇(𝑢𝑢0 , 𝑣𝑣0 ) adják meg a kérdéses két

vektort. Ha annak a paramétervonalnak a mentén vagyunk kíváncsiak az érintővektorra, amelyet az 𝑢𝑢 rögzítésével és a 𝑣𝑣 változásával nyerünk, úgy 𝐷𝐷2 𝒇𝒇(𝑢𝑢0 , 𝑣𝑣0 ) jelenti a megoldást, ellenkező

esetben 𝐷𝐷1 𝒇𝒇(𝑢𝑢0 , 𝑣𝑣0 ). Amennyiben ennek a két vektornak a vektoriális szorzata nem nullvektor, úgy azok egyértelműen meghatározva felfeszítik a felület érintősíkját a vizsgált pontban.

Ugyanennek a két vektornak a felhasználásával előállíthatjuk a pontbeli érintősík normálvektorát 𝐷𝐷 𝒇𝒇(𝑢𝑢 ,𝑣𝑣 )×𝐷𝐷 𝒇𝒇(𝑢𝑢 ,𝑣𝑣 )

(ami egyben a felület normálvektorát is jelenti): 𝒏𝒏(𝑢𝑢0 , 𝑣𝑣0 ) = ‖𝐷𝐷1 𝒇𝒇(𝑢𝑢0 ,𝑣𝑣0 )×𝐷𝐷2𝒇𝒇(𝑢𝑢0 ,𝑣𝑣0)‖. 1

0 0

2

0 0

Nem csak a két kitüntetett érintővektor határozható meg, hanem a fenti jelöléseket megtartva tetszőleges, 𝒊𝒊̌ = (𝑢𝑢𝑖𝑖 , 𝑣𝑣𝑖𝑖 )𝑇𝑇 irányba mutató is, az alábbi képlet alapján:

Az

𝒇𝒇: 𝛺𝛺 ⊂ ℝ2 → ℝ3 ,

𝐷𝐷1 𝑥𝑥(𝑢𝑢0 , 𝑣𝑣0 ) 𝐷𝐷2 𝑥𝑥(𝑢𝑢0 , 𝑣𝑣0 ) 𝒊𝒊 = �𝐷𝐷1 𝑦𝑦(𝑢𝑢0 , 𝑣𝑣0 ) 𝐷𝐷2 𝑦𝑦(𝑢𝑢0 , 𝑣𝑣0 )� 𝒊𝒊̌ 𝐷𝐷1 𝑧𝑧(𝑢𝑢0 , 𝑣𝑣0 ) 𝐷𝐷2 𝑧𝑧(𝑢𝑢0 , 𝑣𝑣0 )

(𝑢𝑢, 𝑣𝑣) → 𝒇𝒇(𝑢𝑢, 𝑣𝑣) = �𝑥𝑥(𝑢𝑢, 𝑣𝑣), 𝑦𝑦(𝑢𝑢, 𝑣𝑣), 𝑧𝑧(𝑢𝑢, 𝑣𝑣)�

𝐷𝐷1 𝑥𝑥 meghatározott felület Jacobi-mátrixán a 𝐽𝐽 = �𝐷𝐷1 𝑦𝑦 𝐷𝐷1 𝑧𝑧 �

𝐸𝐸 𝐺𝐺

𝑇𝑇

függvény

által

𝐷𝐷2 𝑥𝑥 𝐷𝐷2 𝑦𝑦� mátrixot értjük. Az 𝐴𝐴1 = 𝐽𝐽𝑇𝑇 𝐽𝐽 = 𝐷𝐷2 𝑧𝑧

𝐹𝐹 � mátrix szintén nevezetes, ezt a szorzatot a felület első alapformájának nevezzük. 𝐴𝐴1 𝐻𝐻

segítségével könnyen meghatározhatjuk egy, a felületen futó görbe ívhosszát. Ha tekintjük a paramétertartomány egy 𝒈𝒈𝑝𝑝 : [𝑎𝑎, 𝑏𝑏] → 𝛺𝛺, 𝑡𝑡 → 𝒈𝒈𝑝𝑝 (𝑡𝑡) = (𝑢𝑢(𝑡𝑡), 𝑣𝑣(𝑡𝑡)) görbéjét, ennek a felületen a 𝒈𝒈𝑓𝑓 : [𝑎𝑎, 𝑏𝑏] → ℝ3 , 𝑡𝑡 → 𝒈𝒈𝑓𝑓 (𝑡𝑡) = 𝒇𝒇(𝒈𝒈𝑝𝑝 (𝑡𝑡)) térgörbe felel meg, melynek ívhossza: 37

𝑏𝑏

𝑇𝑇

𝑙𝑙(𝑎𝑎, 𝑏𝑏) = � �(𝑢𝑢′ (𝑡𝑡), 𝑣𝑣 ′ (𝑡𝑡))𝐴𝐴1 �𝑢𝑢′ (𝑡𝑡), 𝑣𝑣 ′ (𝑡𝑡)� 𝑑𝑑𝑑𝑑 = 𝑏𝑏

𝑎𝑎

= � �𝐸𝐸 (𝑢𝑢′ (𝑡𝑡))2 + 2𝐹𝐹 (𝑢𝑢′ (𝑡𝑡)𝑣𝑣 ′ (𝑡𝑡)) + 𝐺𝐺(𝑣𝑣′(𝑡𝑡))2 𝑑𝑑𝑑𝑑 𝑎𝑎

Az első alapformával a 𝛺𝛺 paramétertartomány egy 𝐻𝐻 részhalmazához tartozó felületdarab felszínét is könnyen meghatározhatjuk az alábbi képlet segítségével.

𝐴𝐴 = � �|𝐴𝐴1 | 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 = � �𝐸𝐸𝐸𝐸 − 𝐹𝐹 2 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 5.5.2.3.

𝐻𝐻

𝐻𝐻

Görbületmérés a felületen

Ahhoz, hogy a felület egy pontjában meghatározzuk a görbületet, először egy felületen futó görbére fogjuk azt kiszámolni. Az eddigi jelöléseinket megtartva a már ismertetett módon a felület egy P (𝑢𝑢0 , 𝑣𝑣0 )𝑇𝑇 pontjában előállíthatjuk a paramétertér-beli 𝒊𝒊̌ = (𝑢𝑢𝑖𝑖 , 𝑣𝑣𝑖𝑖 )𝑇𝑇 irány mentén

kapható érintővektort, 𝒊𝒊 = 𝐽𝐽 𝒊𝒊̌ módon. A jelzett pontban számolható normálgörbület nem más,

mint annak a síkgörbének a pontban mért görbülete, amelyet úgy kapunk, hogy az 𝒊𝒊 vektor és a felület 𝑷𝑷 pontjához tartozó normálvektora által meghatározott síkkal elmetsszük a felületet 𝑷𝑷-n 𝑒𝑒 keresztül. Kiszámítási módja az alábbi, ahol 𝐴𝐴2 = � 𝑓𝑓

(𝐷𝐷 𝐷𝐷 𝒇𝒇𝑻𝑻 )𝒏𝒏 (𝐷𝐷1 𝐷𝐷2 𝒇𝒇𝑻𝑻 )𝒏𝒏 𝑓𝑓 � ∶= � 1 1 𝑻𝑻 �a 𝑔𝑔 (𝐷𝐷1 𝐷𝐷2 𝒇𝒇 )𝒏𝒏 (𝐷𝐷2 𝐷𝐷2 𝒇𝒇𝑻𝑻 )𝒏𝒏

felület ún. második alapformája (amely most természetesen a P pontban értelmezendő). 𝜅𝜅𝑛𝑛 (𝒊𝒊̌) =

𝒊𝒊̌𝑻𝑻 𝐴𝐴2 𝒊𝒊̌ 𝑒𝑒 𝑢𝑢𝑖𝑖 2 + 2𝑓𝑓 𝑢𝑢𝑖𝑖 𝑣𝑣𝑖𝑖 + 𝑔𝑔𝑣𝑣𝑖𝑖 2 = 𝒊𝒊̌𝑻𝑻 𝐴𝐴1 𝒊𝒊̌ 𝐸𝐸 𝑢𝑢𝑖𝑖 2 + 2𝐹𝐹 𝑢𝑢𝑖𝑖 𝑣𝑣𝑖𝑖 + 𝐺𝐺𝑣𝑣𝑖𝑖 2

A fenti módon természetesen az 𝒊𝒊 vektor normálvektor körüli elforgatásával még több görbületi érték nyerhető. Ezek közül bizonyíthatóan mindig létezik egy legnagyobb és egy legkisebb,

melyeket rendre 𝜅𝜅1 -gyel és 𝜅𝜅2 -vel jelölünk, ezeket főgörbületeknek nevezzük. A hozzájuk tartozó érintővektorokat pedig főirányoknak hívjuk.

38

Euler egyik nagyon híres tétele rámutat, hogy tetszőleges normálgörbületet megkaphatunk a főirányok ismerete által a 𝜅𝜅𝑛𝑛 (𝒊𝒊̌) = 𝜅𝜅1 cos2 𝛼𝛼 + 𝜅𝜅2 sin2 𝛼𝛼 képlet segítségével, ahol 𝛼𝛼 a 𝒊𝒊

vektornak a 𝜅𝜅1 -hez tartozó főiránnyal bezárt szöge.

Több neves görbület is létezik még a differenciálgeometriában. Az egyik ilyen az átlaggörbület, amely nevéből következően a főgörbületek átlagát jelenti. Egy másik pedig a Gauss-görbület,

amely a főgörbületek szorzatát jelenti. Azokat a pontokat, amelyekben a Gauss-görbület negatív, a felület hiperbolikus pontjainak nevezzük (a pont környezetében a felület a nyeregfelülethez hasonló formájú). A pozitív értékkel bíró pontok az elliptikus pontok, ezeken a helyeken egyfajta lokális konvexitás figyelhető meg. A parabolikus pontok Gauss-görbülete nulla, ezek választják el egymástól az eltérő előjellel bíró régiókat a felületen.

26. ábra: A 𝑷𝑷1 pontban mérhető Gauss-görbület nulla, 𝑷𝑷2 -ben negatív, 𝑷𝑷3 -ban pozitív.

5.5.3. Differenciálgeometriai vizsgálatok diszkrét esetekben

A fentebb említett differenciálgeometriai tulajdonságok meghatározásához sok esetben elvárjuk, hogy a felületünk kellően sokszor differenciálható legyen, gondoljunk csak az egyes képletekben előforduló első vagy második deriváltakra. Nyilvánvaló, hogy a poligonhálók esetében azt a maga teljességében leíró, differenciálható függvény nem létezik. Azonban ilyen esetekben is 39

felmerül az igény, hogy valahogyan mégis képesek legyünk bizonyos tulajdonságok nyomára bukkanni, melyek jól jellemzik az adott poligonhálót differenciálgeometriai szempontból egyegy pont környezetében. Számtalan módszer született arra vonatkozóan, hogy hogyan lehet ezeket az értékeket a háló alapján jól közelíteni. Célunk tehát olyan értékek megtalálása, amelyek a háló egy adott pontjában nagyon hasonló eredményt mutatnak ahhoz, mintha egy hasonló formájú, de paraméteresen előállított felület adott pontjában számolnánk egy-egy tulajdonságot. Az alábbiakban a teljesség igénye nélkül bemutatjuk egy klasszikus példáját ennek a kérdéskörnek. 5.5.3.1.

Normálvektorok meghatározása

Nagyon

sok

grafikai

és

modellezési

feladatnál,

illetve problémánál

előkerülnek

a

normálvektorok, lássuk, milyen módszereink lehetnek ezek meghatározására konkrét csúcsok esetén. Ahogy a korábbiakban láttuk, egy folytonosan differenciálható függvény esetében ez nem jelenthet gondot, hiszen a parciális deriváltak vektoriális szorzataként egyből megfelelő irány kapható. Ha azonban nem áll rendelkezésre a felületet definiáló függvény, akkor hogyan dönthetjük el, milyen normálvektorral dolgozzunk? Ezt a dilemmát szemlélteti az alábbi, 27. ábra.

27. ábra: Normálvektor keresése

40

A nyíllal jelölt csúcsban keressük a normálvektort. Az ábrán berajzolt irányok közül kellene választanunk? Vagy esetleg egy negyedik irány lesz megfelelő? Az egyes háromszögek síkjához tartozó normálvektorok könnyen kiszámolhatók, hiszen egy 𝑨𝑨, 𝑩𝑩

és 𝑪𝑪 csúcsokkal rendelkező háromszöghöz 𝒏𝒏 = (𝑩𝑩 − 𝑨𝑨) × (𝑪𝑪 − 𝑨𝑨) adódik. Ha ismerjük egy adott 𝑷𝑷 csúcs esetében az abban a csúcsban találkozó háromszöglapok normálvektorait, egy egyszerű átlagszámítás segítségével gyorsan eljuthatunk egy sokszor kielégítő megoldásig.

Ezen az átlagszámításon túlmutat, ha bizonyos mennyiségek figyelembevételével súlyozzuk az egyes normálvektorokat. Egy ilyen súlyozás alapja lehet például az, ha azoknak a háromszögeknek a normálvektorait, amelyeknek nagyobb a területe, nagyobb súllyal látjuk el.

41

TESZTKÉRDÉSEK

Egyszerű választás Válassza ki a felsorolásból az egyetlen helyes választ. Ha egy kérdésre több választ is ad a kérdést nem értékeljük 1. Az alábbi eljárások közül melyik nem része a Reverse Engineering folyamatnak? A. zajszűrés B. szegmentálás C. 3D nyomtatás D. regisztáció 2. Egy háló egy belső csúcsát regulárisnak nevezzük, ha A. pontosan négy darab szomszédja van. B. legalább négy darab szomszédja van. C. legfeljebb négy darab szomszédja van. D. pontosan hat darab szomszédja van. 3. Egy felület adott pontban mért Gauss-görbülete A. a ponthoz tartozó főgörbületek átlaga. B. a ponthoz tartozó maximális és minimális normálgörbület különbsége. C. a ponthoz tartozó főgörbületek szorzata. D. mindig pozitív. 4. Az első alapforma A. a második alapforma inverzeként előállítható. B. a Jacobi-mátrix transzponáltjának és a Jacobi-mátrixnak a szorzataként előállítható. C. oszlopai a felület koordinátafüggvényeinek deriváltjai. D. szimmetrikus mátrix. Megoldókulcs: 1. C 2. D 42

3. A 4. B Többszörös választás 1. Az alábbi jelzők közül melyik vonatkozhat egy áthálózó algoritmusra? A. inkrementális B. reguláris C. irreguláris D. mohó Megoldókulcs: 1. A, D Igaz vagy hamis? 1. Az aluláteresztő szűrők az átlagtól eltérő értékeket erősítik fel. 2. Útnak nevezzük a gráf egymáshoz csatlakozó éleinek olyan sorozatát, amely egyetlen csúcson sem halad át egynél többször. 3. Az anizotropikus elemek alakja minden irányban egyenletesen változik. 4. A szegmentálás hasznos eszköz a lyukak feltérképezéséhez. 5. A szabályos rács adatszerkezet csak a nem-üres cellákat tárolja. Megoldókulcs: 1. H 2. I 3. H 4. I 5. H

43

FELHASZNÁLT SZAKIRODALOM

[1] Teo PAOLETTI. Leonard Euler's Solution to the Konigsberg Bridge Problem. Convergence: A Magazine of the Mathematical Association of America, 2006, Volume 3. http://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-thekonigsberg-bridge-problem, letöltés dátuma: 2015. szeptember 7. [2] Tim VOLODINE: Point Cloud Processing Using Linear Algebra And Graph Theory, K.U.Leuven, Leuven, Belgium, 2007. -ISBN 978-90-5682-857-8 [3] Julie DIGNE: Inverse geometry: from the raw point cloud to the 3D Surface: theory and algorithms, Ecole normale superieure de Cachan - ENS Cachan, France, 2010. [4] Oliver van KAICK, Noa FISH, Yanir KLEIMAN, Shmuel ASAFI, Daniel COHEN-OR: Shape Segmentation by Approximate Convexity Analysis, ACM Transactions on Graphics, 2014, Volume 34 Issue 1. [5] Mario BOTSCH, Leif KOBBELT, Mark PAULY, Pierre ALLIEZ, Bruno LEVY: NPoligon Mesh Processing. A K Peters/CRC Press, 2010. -ISBN 156 881 4267 [6] HOFFMANN Miklós, Topológia és differenciálgeometria, Eszterházy Károly Főiskola, Matematikai

és

Informatikai

Intézet,

Eger,

2011, http://www.tankonyvtar.hu/hu/tartalom/tamop425/0038_matematika_Hoffmann_Mikl os_-Topologia_es_differencialgeometria/index.html, letöltés dátuma: 2015. szeptember 1. [7] Jean-Daniel BOISSONNAT, Steve OUDOT. Provably Good Sampling and Meshing of Surfaces. Graphical Models, 2005, 67.5: 405–451. [8] Mario BOTSCH, Leif KOBBELT. A Remeshing Approach to Multiresolution Modeling. In: Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. ACM, 2004, p. 185–192. [9]

2000

SIGGRAPH

Full

Day

Course:

Subdivision

for

Modeling

and

Animation, http://www.mrl.nyu.edu/~dzorin/sig00course/, letöltés dátuma: 2015. szeptember 7. 44

45