Thesispresentatie

Op de kloof tussen kerst en nieuwjaar heb ik eindelijk toch wat tijd kunnen maken om mijn blog eens up te daten. Inhoudelijk heb ik een dikke week niks meer gepresteerd maar ik heb nog niks kunnen zeggen over mijn thesispresentatie :)

De slides van de presentatie kan vinden bij slideshare.

Over het algemeen waren Ares (mijn begeleider) en prof. Dutré tevreden over het geleverde werk al had het nog iets meer mogen zijn. Maar de eerste kleine resultaten zijn er toch al. Toch waren er enkele terechte opmerkingen:

• Ik heb me teveel gefocused op rauwe performantie, het is veel belangrijker om met relatieve cijfers te komen zodat je kan vergelijken tussen verschillende methodes. Algoritmische optimalisaties primeren boven architectuur specifieke optimalisaties.
• Ik kan wel zeggen dat A beter is dan B maar daarvoor moeten harde wetenschappelijke bewijzen voor zijn. Mijn aanpak moet iets wetenschappelijker: meer gegevens verzamelen om vermoedens te kunnen staven.
• Een tip van Bart Adams: Het is interessant om te achterhalen welke scenes het beste presteren bij welke structuur. Het zou leuk zijn dat mijn ray tracer een scene kan analyseren en dan @runtime een algoritme selecteren. Hiervoor zou ik moeten achterhalen of er überhaupt al een taxonomie is voor scenes in computer graphics.

Dus nog veel werk voor het 2e semester. Het plan is om in de blok ook nog te werken, hopelijk kan ik er zo snel mogelijk terug in vliegen.

Refitting

Het is me gelukt om enkele dynamische scene te renderen met behulp van refitting. Het idee van refitting is om de versnellingsstructuur te behouden maar telkens de bounding boxes te herberekenen zodat die telkens terug correct aansluiten op de driehoeken. Het is een zeer simpele methode en robuuste methode, het nadeel hiervan is dat de versnellingsstructuur per frame iets slechter wordt.

Alles staat nog niet op punt maar ik kan al enkele beeldjes renderen die ik morgen kan laten zien op mijn thesispresentatie :) De scenes komen uit de Utah Animation Repository en worden gebruikt als benchmarks in de paper "Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies" van Wald en Shirley. Dit is tevens de paper die de refitting techniek beschrijft.

De lopende Ben scene:

De hand scene:

De fairy forest scene:

De wooddoll scene:

Het Fairy Forrest is de mooiste maar ook de meest complexe scene dus die is het interessants om te bespreken. De scene bestaat uit 174117 driehoeken, 20 frames en is gerendered zoals steeds op een resolutie van 1024 x 1024 pixels. De totale tijd per frame kunnen we opsplitsen:

• Inladen van de driehoeken: ~15 ms
• Refitten van de BVH: ~3 ms
• Renderen: ~2.6s tot ~13.24s
  
• Exporteren naar PNG: ~20 ms

Zoals verwacht wordt de kwaliteit slechter in vergelijking met het eerste frame. De refits zijn wel bijna gratis. Deze techniek is volgens mij wel zeer geschikt om de restbeweging (bijvoorbeeld rond te gewrichten) op te vangen bij beweging van menselijke anatomie.

Nieuwe Benchmarks

Zoals gisteren beloofd enkele nieuwe benchmarks, het bouwen van een versnellingsstructuur is sterk verbeterd en ook het renderen gaat weeral iets sneller.



Verder iets over mijn "renderbox" want ik lanceer al een heel semester rendertijden zonder te vermelden op welk type processor. In mijn computer zit een Intel E6600 Dual Core processor (2.4GHz kloksnelheid met 4Mb cache en 4Gb dual channel geheugen), hiervan gebruik ik slechts één core voor te renderen, de andere dient om reddit/programming te lezen en naar last.fm te luisteren terwijl ik wacht op mijn renders.

Ondertussen kan ik ook animaties renderen met de Cal3D library, hier een gehaaste Cally (opgebouwd uit 3342 driehoeken):

Elke frame (resolutie 1024 x 1024) neemt de volgende tijd in beslag:

• Het bouwen van de versnellingsstructuur: 0.01 a 0.02 seconden.
• Het ray tracen van het frame: ~0.25 seconden.
• Het saven van het frame naar png formaat: ~0.15 seconden.
  

Gemiddeld genomen geeft dit een framerate van 2.5 frames/seconde, als ik het converteren naar png buiten beschouwing laat dan bekomen we een framerate van 3.52 frames/seconde. Nog altijd redelijk amateuristisch maar in mijn implementatie is nog ongeloofelijk veel mogelijkheid tot optimalisatie :)

Gunther maakt in zijn paper gebruik van muli-level loose kd-trees met 4x4 ray packets en haalt een framerate van 10 seconden voor de Cally scene op een AMD Opteron 2.4GHz processor. De Cally animatie hier is wel niet helemaal gelijk aan de scene die Gunther gebruikt.

Ik maak hier niet gebruik van de specifieke anatomie maar herbouw de datastructuur voor elk frame zoals beschreven in de paper van Wald. Hoewel ik eigenlijk informatie "weggooi" heb ik het gevoel dat deze techniek er als beste zal uitkomen in vergelijking met de andere (nog niet geimplementeerde technieken). De redenen:

• De techniek is algemeen en kan alle soorten dynamiek in een scene aan van coherent (joggende Cally) tot incoherent (exploderende Cally).
• Het algoritme zoals gepresenteerd door Wald is bliksemsnel, terwijl de versnellingsstructuren van uitstekende kwaliteit zijn.
• Het algoritme schaalt zeer goed, één core kan bijvoorbeeld de versnellingsstructuur berekenen terwijl de andere core rendert.
  

Status Update

Het is alweer een tijdje geleden dat ik nog geblogd heb maar de laatste 2 weken voor de kerstvakantie zijn traditioneel "deadline" weken, iedereen verwacht iets. Maandag een afspraak gehad met Ares. Daar hebben we besloten dat de BVH versnellingsstructuur robuust, correct en snel genoeg is, althans voor dit semester. Volgend semester is het tijd voor de zware middelen om het laatste beetje performantie eruit te persen. Nu ga ik mijn aandacht concentreren op verschillende technieken, specifiek voor animaties.

Met de beperkte tijd die ik heb kunnen besteden aan mijn thesis heb ik het bouwen van een BVH gedeeltelijk geherimplementeerd. Vroeger werkte dit algoritme rechtstreeks op een lijst van pointers naar driehoeken, nu werkt het algoritme op een lijst van driehoek id's (gewoon een lijst van ints). Verder probeer ik zoveel mogelijk gebruik te maken van algoritmes uit STL algorithm. Deze zijn veel robuuster, efficienter en meer getest dan mijn eigen code (In programmeren geldt niet: "Wat je zelf doet doe je beter" maar "Wat je zelf doet is meestal een pak slechter"). De reden voor deze implementatie is het geheugengebruik. Grote scenes zoals Cruiser (~ 3.6M driehoeken) en Asian Dragon (~ 7M driehoeken) gaven problemen op computers met klein geheugen gewoonweg omdat er niet genoeg geheugen kan gealloceerd worden voor het bouwen van de versnellingsstructuur.

Met de rest van de tijd heb ik het build algoritme zoals beschreven door Wald geoptimaliseerd. Rendertijden volgen omdat ik momenteel niet aan het werken ben op mijn "renderbox".

Verder is er volgende week een presentatie gepland om mijn voorlopige resultaten voor te stellen, dus wordt het tijd om eens te reflecteren over dit semester.

Binned SAH build

Geen afspraak met Ares deze week maar wel een kleine doorbraak: het is me gelukt om een BVH-tree op te bouwen met SAH (Surface Area Heuristic). Strikt gezien gaat het om een benadering van de SAH zoals beschreven in de paper van Wald: "On fast Construction of SAH-based Bounding Volume Hierarchies".

Het idee is om de driehoeken in een een aantal "emmers" te verdelen en dan alle scheidingsvlakken tussen deze emmers te bekijken als mogelijk "split" vlak. Alle driehoeken langs de linkerkant van dat vlak komen dan in de linkerdeelboom, alle driehoeken langs de rechterkant van dat splitvlak komen dan in de rechterdeelboom. We kiezen het splitvlak zo dat de kost:

kost = ( #driehoeken_links * oppervlak_links ) + (#driehoeken_rechts * oppervlak_rechts)

minimaal is.



In mijn implementatie gebruik ik 16 emmers (bins) en dat geeft de volgende statistieken:

Het renderen begint snel te gaan maar zou uiteindelijk toch nog ruwweg een factor 4 naar omhoog moeten (met packet ray tracing, SSE extension, ...). Het algoritme om de bvh tree te bouwen is nog veel te traag in vergelijking met de paper van Wald (een factor 10 - 20).