Implicit surface reconstruction from point clouds

Abstract

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 gewicht hebben niet beschouwd worden. Dit leidt tot volledig lokale berekening, die computationeel ook minder zwaar is omdat niet alle punten beschouwd moeten worden. Moving Least Squares technieken worden vaak gebruikt om een puntenwolk te verbeteren. Zo gebeurt het vaak dat scanners meerdere scans maken van een model en dat er op de punten die de scanner teruggeeft een kleine fout zit. Hierdoor zit er veel redundancy in de puntenwolk, maar de punten komen niet perfect overeen omdat ze een kleine meetfout bevatten. Door Moving Least Squares toe te passen kan men deze punten vervangen door punten die op de lokaal gereconstrueerde functies liggen, waarbij men het aantal punten kan verminderen en de meetfouten kan tenietdoen. De techniek wordt ook vaak gebruik om een goede verdeling van de punten over het object te krijgen. Sommige functies hebben een topologie dat door weinig punten bevat kan worden, terwijl er voor andere functies veel meer punten zijn om de topologie goed te kunnen vatten. Vaak wordt uit een Moving Least Squares reconstructie van een puntenwolk een nieuwe puntenwolk gegenereerd die het originele model effici¨enter bevat [ABCO+03]. Het nadeel van deze techniek is dat scherpe randen verloren gaan, omdat men alle punten in de omgeving gaat beschouwen wat ervoor zal zorgen dat de scherpe rand lichtjes gebogen zal zijn. Dit is vaak een ongewenst effect. Door zeer zorgvuldige analyse van de punten die worden gebruikt bij de reconstructie, kan men scherpe randen detecteren en reconstrueren, wat computationeel echter zwaarder is [FCOAS03]. vi Multi-level Partitioning of Unity Implicits [OBA+03] is een reconstructiemethode gebaseerd op de wiskundige techniek genaamt Partitioning of Unity. Hierbij wordt een domein onderverdeeld in verscheidene subdomeinen voorzien van een gewicht die samen het oorspronkelijke domein volledig bedekken en waarbij geldt dat het totale gewicht voor elk punt net 1 is. Toegepast op oppervlaktereconstuctie betekent dit dat men het oorspronkelijke domein gaat opsplitsen in een aantal cellen, waarbij vervolgens alle punten in een cel worden gefit door een functie die gekozen wordt uit een set van functies. De approximatiefout van een functie geassocieerd aan een cel bepaalt of het algoritme stopt of recursief voortgaat. Zoals eerder aangegeven wordt de functie om te fitten gekozen uit een set van functies. Het grote voordeel hiervan is dat men zich effici¨enter kan aanpasssen aan de lokale topologie van het te reconstrueren object. Door een aantal eigenschappen van de punten in een cel te analyzeren, zoals de spatiale en normaalverdeling van de punten, wordt beslist door welke functie deze punten gefit worden. Hierdoor worden sneller betere resultaten bekomen dan wanneer er altijd door dezelfde functie wordt gefit. Als implementatie is een reconstructie techniek ge¨ımplementeerd, waarna het gereconstrueerde model gevisualizeerd wordt met behulp van raytracing. De originele puntenwolk wordt door een ruimtelijke onderverdelingstechniek onderverdeeld in kleine cellen, waarbij de punten in een cel benaderd worden door een functie, gekozen uit een set van mogelijke fitting-functies. Als ruimtelijke onderverdelingstechniek is gebruik gemaakt van een kDboom, met spatiale mediaan als splitsingsheuristiek. De set van mogelijke fitting-functies wordt ingevuld door algemene en bivariate kwadrieken. Gebaseerd op de lokale distributie van de punten in een cel wordt een van deze twee functies gekozen om de punten in een cel te benaderen. Eenmaal een model gereconstrueerd is, bestaat dit model uit impliciete functies als primitieven in plaats van punten. Dit gereconstrueerde model wordt gevisualizeerd door middel van raytracing, tegen bijna interactieve renderingtijden. Enkele mogelijke problemen met het raytracen worden geanalyzeerd, namelijk de densiteit van de punten en de berekening van een geldig intersectiepunt. De gebruikte intersectie-algoritmen worden ook beschreven. Uiteindelijk worden resultaten van de implementatie besproken en geanalyzeerd aan de hand van statistische informatie die tijdens het reconstrueren en visualizeren van de modellen werd bijgehouden.