Het begin van een nieuw semester dus tijd om er terug in te vliegen. Helaas ben ik tijdens de blok wat lui geweest en heb ik niks gepresteerd voor mijn thesis. Tijd voor een inhaalbeweging dus.
Ik ben begonnen aan het implementeren van een 3e techniek voor het ray tracen van animaties. Deze wordt beschreven in de paper van Günther en is speciaal bedacht voor skinned animations (animaties met een skelet). Op de voorstelling van mijn tussentijdse resultaten heb ik gezegd dat ik de implementatie kon fixen op 6u. Helaas was dat een grove onderschatting van het werk :( Interfacen met Cal3d valt zwaar tegen en daar bovenop is ondertussen de homepage van Cal3d verdwenen van het internet. Gelukkig zit sommige documentatie ook mee in de tarball die je kan downloaden van gna.org.
In mijn huidige implementatie kan ik al bepalen welke meshes worden beïnvloed door wel botten. Daaruit bereken ik voor elke mesh een dominant bot, dit is het bot met de grootste invloed op de mesh. In het volgend filmpje zie je de meshes ingekleurd per bot, meshes met gelijke kleur horen bij hetzelfde bot.
woensdag 18 februari 2009
dinsdag 30 december 2008
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:
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.
dinsdag 16 december 2008
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:
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
zondag 14 december 2008
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:
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:
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.
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.
zaterdag 13 december 2008
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.
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.
vrijdag 5 december 2008
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).
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).
woensdag 26 november 2008
Bug Fix
Op aanraden van Ares heb ik een beetje tijd gespendeerd aan mijn "gaten in de meshes" bug zodat ik verder kan werken met een ray tracer waarvan ik 100% weet dat hij correct werkt.
Na een halve dag intensief zoeken heb ik de bug gevonden op een plaats waar ik het totaal niet verwachtte (zoals met alle bugs het geval is) in de code voor het bouwen van een bounding box van een driehoek:
min(a.z, b.z, b.z), max(a.z, b.z, c.z) // fout door stomme tikfout
min(a.z, b.z, c.z), max(a.z, b.z, c.z)) // correct
Het gevolg hiervan was dat een (klein) aantal bounding boxes fout werd berekend en daarom werden sommige driehoeken niet getest wat leidde tot gaten in de meshes. Gelukkig is dit probleem nu van de baan zoals volgende renders aantonen.
Een schokkerige versie van Achmed the dead terrorist :)
En de classroom scene met een perfecte muur achteraan
Verder waren niet al mijn berekende statistieken even nuttig, zoals bijvoorbeeld het aantal driehoek / straal intersecties per straal. Beter is om het aantal driehoek/straal intersecties te verdelen over stralen die iets geraakt hebben.
De bugfix heeft het aantal straal/driehoek intersecties iets verminderd, het belangrijkste is dat ik nu zeker weet dat alles correct werkt, nu kan ik mij focussen op rauwe performantie.
Na een halve dag intensief zoeken heb ik de bug gevonden op een plaats waar ik het totaal niet verwachtte (zoals met alle bugs het geval is) in de code voor het bouwen van een bounding box van een driehoek:
min
min
Het gevolg hiervan was dat een (klein) aantal bounding boxes fout werd berekend en daarom werden sommige driehoeken niet getest wat leidde tot gaten in de meshes. Gelukkig is dit probleem nu van de baan zoals volgende renders aantonen.
Een schokkerige versie van Achmed the dead terrorist :)
En de classroom scene met een perfecte muur achteraan
Verder waren niet al mijn berekende statistieken even nuttig, zoals bijvoorbeeld het aantal driehoek / straal intersecties per straal. Beter is om het aantal driehoek/straal intersecties te verdelen over stralen die iets geraakt hebben.
BVH STATS WITH FTB TRAVERSAL AND CULLING | |||||||||||
scene | #triangles | #tris/hit | #box/hit | build (s) | render (s) | ||||||
ulm box | 492 | 2.54 | 32.16 | 0 | 2 | ||||||
classroom | 9K | 3.9 | 118 | 0 | 9 | ||||||
office | 34K | 5.39 | 71.5 | 0 | 6 |
| |||||
cabin | 219K | 7.75 | 155 | 0 | 12 | ||||||
armadillo | 345K | 3.27 | 87.5 | 2 | 2 | ||||||
atrium2 | 559K | 8.54 | 142.9 | 2 | 12 | ||||||
conference | 987K | 4.17 | 145.8 | 6 | 11 | ||||||
cruiser | 3.64M | 12.6 | 137.5 | 23 | 10 | ||||||
dragon | 7.22M | 3.65 | 114 | 38 | 1 | ||||||
De bugfix heeft het aantal straal/driehoek intersecties iets verminderd, het belangrijkste is dat ik nu zeker weet dat alles correct werkt, nu kan ik mij focussen op rauwe performantie.
Abonneren op:
Posts (Atom)