Implicit surface reconstruction from point clouds
Johan Huysmans · Document Server@UHasselt (UHasselt) · 2006
Punt gebaseerde modellen worden meer en meer gebruikt in grafische toepassingen. Dit komt enerzijds door de lage kost van kwalitatief goede 3D scanners, welke een hoge resolutie puntenwolk van een object genereren. Anderzijds is de steeds toenemende complexiteit van modellen verantwoordelijk voor de toenemende populariteit van punten als visualizatieprimitieven. Bij deze zeer complexe modellen zal een driehoek gemiddeld minder dan een pixel op het scherm innemen, waardoor punten als visualizatie-primitieven aantrekkelijker worden. Het cre¨eren van digitale modellen is dan ook vaak interessanter te laten gebeuren door middel van een ingescanned object dan met behulp van traditionele tools, zowel kwalitatief als de tijd die ervoor nodig is. Een bekend voorbeeld is het Digital Michelangelo Project [LPC+00], waarbij men het David standbeeld van Michelangelo heeft gedigitalizeerd met behulp van laser scanners. Het nadeel van punten als representatie-primitieve is dat een puntenwolk een discrete set van punten is, dit wil zeggen dat er maar een eindig aantal punten zijn om een object voor te stellen. Vaak is echter een continue, waterdichte representatie van een object gewenst, voor een natuurlijke manipulatie en visualizatie van dit object. Over deze conversie van een discrete naar continue representatie handelt deze thesis, waarbij de continue representatie wordt voorgesteld door impliciete functies die de gegeven puntenwolk zo goed mogelijk benaderen. Om deze conversie tot een goed einde te brengen, wordt gebruik gemaakt van twee veronderstellingen: • De puntenwolk beschrijft alleen de contouren van het object en is niet volumetrisch. • De topologie van het object is goed genoeg bevat door de puntenwolk, zodat een correcte reconstructie van de topologie door impliciete functies mogelijk is. Het beoordelen van de kwaliteit van een gereconstrueerd model is zowel objectief als subjectief. Objectief kan de kwaliteit van de reconstructie gemeten worden door de afsiii tand van de functie tot elk datapunt te meten. Deze afstand kan op verschillende manieren gemeten worden. Indien de euclideaanse afstand gebruikt wordt, wordt het verschil gereduceerd tot een verschil tussen twee punten in de ruimte waarbij geen rekening wordt gehouden met de vorm van het object. Dit wordt wel gedaan bij de algebraische afstand. Hierbij wordt de afstand van een punt tot de functie gelijk gesteld aan de waarde van de functie in dit punt. Deze werkwijze kan echter grote variaties geven wanneer de functie zeer ongelijk verspreid is over verschillende dimensies. Dit probleem werd opgelost door Taubin, waarbij de algebraische afstand wordt gedeeld door de gradient van de functie op dit punt, om zo een consistentere afstandmetriek te bekomen. Subjectief hangt de kwaliteit van de reconstructie vooral af van de visualizatie, waarbij vooral de gladheid, of dus de orde van continue afleidbaarheid van de globale functie, van het gereconstrueerde object belangrijk is. Ook het behoud van lokale eigenschappen, zoals scherpe randen, hoeken of lokale variaties in de topologie, of juist het wegwerken ervan, zijn belangrijke factoren voor subjectieve kwaliteitsbeoordeling. Voor het visualizeren van de resulterende model zullen we, in tegenstelling tot de technieken uit de literatuur waarbij het gereconstrueerde model gevisualizeerd wordt dmv triangulatie en forward rendering, het model visualizeren met behulp van raytracing [Gla89]. Door gebruik te maken van lokale, tweede orde, impliciete functies is een algebraische intersectieberekening mogelijk, waardoor iteratieve intersectiealgoritmes [Har93] vermeden kunnen worden. Het eerste deel van deze samenvatting zal zich concentreren op het reconstructieproces, waarbij de meest gebruikte technieken kort besproken worden, namelijk surface splats, radial basis functions, moving least squares en multi-level partitioning of unity implicits. In het tweede deel wordt de implementatie besproken, waarbij de moeilijkheden en gebruikte oplossingen geanalyseerd worden. Een surface splat is een punt, voorzien van een volume en normaal. Dit kan bijvoorbeeld een bol of ellips zijn. Surface splatting is een techniek waarbij men de punten wil vervangen door een aantal splats, die dan overlappen zodat ze het volledige oppervlak innemen, om zo een continue representatie van de puntenwolk te verkrijgen. Dit proces moet zorgvuldig gebeuren, want het na¨ıef laten groeien van alle splats resulteert in een kwalitatief slechte reconstructie, wat zich uit als artifacten tijdens de visualizatie [WS05]. Er zijn technieken ontwikkeld die een optimale splat distributie genereren, gebruik makend van ellipsen als splats omdat deze zich goed kunnen aanpassen aan de onderliggende topologie van de puntenwolk. In een post-processing stap worden alle splats nog eens gecontroleerd op redundancy, bijvoorbeeld splats die volledig worden bedekt door andere splats kunnen verwijderd worden. Indien het behoud van scherpe randen vereist is, worden iv de splats uitgebreid zodat ze ook een aantal vlakken bezitten, welke dan de splitsvlakken zijn die de scherpe rand voor stellen. Het voordeel van surface splats is dat deze eenvoudig te visualizeren zijn [RL00], ook op GPU’s [BK03, Bot05], wat rendering tegen interactieve framerates mogelijk maakt op bestaande hardware. Het nadeel van deze techniek is dat er zeer weinig controle is over de continuiteit van het resulterende oppervlak en dat reconstructie-eigenschappen zo goed als onbestaande zijn. Radial Basis Functions is een algemene data-approximatietechniek die steunt op het gebruik van radiale basis functies. Een radiale basisfunctie is een functie, gecentreerd rond een bepaald punt, waarvan het resultaat van deze functie, toegepast op een ander punt, rotatie-onafhankelijk is. Een voorbeeld van zo’n functie is een gaussiaanse functie. Door op elk punt van de puntenwolk zo’n radiale basisfunctie te plaatsen, kan men met behulp van enkele andere parameters, een globale functie contrueren die de gegeven datapunten zo goed mogelijk benaderd. De kwaliteit van de benadering wordt dan gemeten door de afstand van de functie tot elk datapunt te meten, dmv de radiale basisfuncties in deze punten. Indien al deze afstanden nul zijn, is een interpolatie gerealiseerd. Een complicatie met deze techniek is dat er een triviale oplossing voor dit probleem bestaat. Namelijk de nul-functie, een functie die over heel zijn domein de waarde nul teruggeeft, waardoor de afstand van de functie tot elk datapunt nul is, wat een perfect resultaat zou zijn. Om deze onzinnige oplossing te vermijden, worden er dan punten bijgeplaatst waar de resulterende functie niet nul is. Het approximatieprobleem wordt dus van de vorm: een nul voor alle datapunten en een andere waarde voor alle toegevoegde punten. Het genereren van deze extra punten moet zeer zorgvuldig gebeuren, want in sommige situaties kunnen deze gegenereerde punten dichter bij een ander datapunt liggen dan zichzelf, waardoor de resulterende globale impliciete functie artefacten zal vertonen [CBC+01]. Een nadeel van deze techniek is dat het computationeel zwaar is. Er moet een zeer groot stelsel worden opgelost, wat enkele uren in beslag kan nemen. Door het globale karakter van de resulterende functie, gekoppeld aan bepaalde continuiteitsvoorwaarden, zullen lokale eigenschappen van het te reconstrueren object verloren geraken. Een voordeel is dat deze technieken zeer goede reconstructie-eigenschappen bevat. Kleine fouten of gaten in het object zullen opgevuld worden door het globale karakter van de functie. Deze methode is dan ook geschikt voor het reconstrueren van modellen met artefacten [CBM+03]. Er zijn technieken ontwikkeld om deze techniek een meer lokaal karakter te geven. Het voordeel hiervan is dat lokale eigenschappen beter behouden blijven en er een snellere berekening mogelijk is, maar het inherente nadeel van deze lokaliteit is dat de goede globale v reconstructie-eigenschappen gedeeltelijk verloren gaan. Om deze globaliteit gedeeltelijk te behouden, wordt er geinterpoleerd tussen twee opeenvolgende dieptes in de hierarchische structuur, waarbij de vorige diepte zorgt voor globalere eigenschappen, en de andere voor details op een lokaler niveau [OBS03]. De Moving Least Squares variant van Levin [Lev98] probeert een puntenwolk te reconstrueren door op voor punt lokaal een functie te construeren, die de naburige punten approximeert. Dit is dus, in tegenstelling tot radial basis functions, een lokale techniek. Gegeven een data punt, wordt er een vlak in de buurt van dit punt berekend. Dit gebeurt door een minimalizatie van de gewogen kwadratische som van alle punten, waarbij het gewicht afneemt met de afstand tot de projectie van het datapunt op het vlak. De functie die de omgeving van dit punt approximeert, wordt hier dan voorgesteld als een functie over de hoogte van dit vlak. Nadien wordt voor alle datapunten de gewogen kwadratische som tussen het datapunt en de hoogtefunctie geminimaliseerd, waarbij het gewicht weer afhangt van de afstand van dit punt tot het beschouwde datapunt. Omdat de gewichten van elk punt afhangen van een functie die afneemt bij punten die verderaf liggen, kan men de ondersteunings-afstand van deze punten beperken zodat de punten die zo goed als geen als ge