Een nieuwe maandag dus een afspraak met Ares. Het belangrijkste onderwerp van ons gesprek was natuurlijk de veel te trage BVH. Na samen de tabel met statistieken te hebben bekeken heb ik van Ares de tip gekregen om toch maar eens naar mijn traversal code te kijken (de code die de boom doorloopt) omdat ik veel te veel driehoek/straal intersecties doe per straal.
Het 2e deel van ons gesprek ging over de draft van mijn presentatie van donderdag. Mijn presentatie heeft op dit moment veel weg van een opsomming terwijl ik één vloeiend verhaal zou moeten vertellen. Dus nog een beetje werk tegen donderdag.
Dus deze week debuggen en presentatie!
maandag 3 november 2008
zondag 2 november 2008
SAH bounding volume hierarchy
Het is me gelukt om mijn bounding volume hierarchy te bouwen met de surface area heuristic (SAH) zoals beschreven in de paper van Wald. Mijn code compileert maar daar is helaas alles mee gezegd. De rendertijden zijn geen verbetering t.o.v. de bvh met median split. Waarschijnlijk door een implementatiefout. Rijden met een Ferrari maar altijd voorbijgestoken worden door 2 pk'tjes.
Om de implementaties te kunnen vergelijken zijn 2 statistieken bijghouden in mijn bvh code: het aantal boundingbox/straal intersecties en het aantal driehoek/straal intersecties. Dit heb ik gedaan voor de 3 verschillende scenes. Het doel van een bvh is om het aantal driehoek/straal intersecties te verminderen ten koste van meer boundingbox straal intersecties omdat boundingbox/straal intersecties een pak goedkoper zijn dan driehoek/straal intersecties. Hoeveel "een pak" wil zeggen in mijn code moet ik nog uitzoeken.
Uit deze 2 statistieken heb ik het aantal het boundingbox intersecties per straal(#bbi/ray) en het aantal driehoek intersecties per straal (#tri/ray) berekend. Tussen equal partitioning en median partitioning zijn de verschillen groot, dit valt ook te merken in de snelheidswinst. Het verschil tussen SAH en median partitioning is veel kleiner, het aantal boundingbox intersecties daalt hier sterk maar het aantal driehoek intersecties blijft gelijk. Spijtig genoeg is dat het getal dat de performantie bepaalt (Ook de daling van het aantal boundingbox intersecties heeft een invloed maar minder uitgesproken).
Waarom ik nog niets merk van de snelheidswinst moet ik deze week nog uitzoeken, hopelijk voor mijn presentatie van donderdag :)
Om de implementaties te kunnen vergelijken zijn 2 statistieken bijghouden in mijn bvh code: het aantal boundingbox/straal intersecties en het aantal driehoek/straal intersecties. Dit heb ik gedaan voor de 3 verschillende scenes. Het doel van een bvh is om het aantal driehoek/straal intersecties te verminderen ten koste van meer boundingbox straal intersecties omdat boundingbox/straal intersecties een pak goedkoper zijn dan driehoek/straal intersecties. Hoeveel "een pak" wil zeggen in mijn code moet ik nog uitzoeken.
Uit deze 2 statistieken heb ik het aantal het boundingbox intersecties per straal(#bbi/ray) en het aantal driehoek intersecties per straal (#tri/ray) berekend. Tussen equal partitioning en median partitioning zijn de verschillen groot, dit valt ook te merken in de snelheidswinst. Het verschil tussen SAH en median partitioning is veel kleiner, het aantal boundingbox intersecties daalt hier sterk maar het aantal driehoek intersecties blijft gelijk. Spijtig genoeg is dat het getal dat de performantie bepaalt (Ook de daling van het aantal boundingbox intersecties heeft een invloed maar minder uitgesproken).
Waarom ik nog niets merk van de snelheidswinst moet ik deze week nog uitzoeken, hopelijk voor mijn presentatie van donderdag :)
dinsdag 28 oktober 2008
Ra2 werkt correct
Na veel vloeken is het gelukt om ra2 bestanden correct te renderen. Ik heb heel lang zitten zoeken in mijn camera code, Ares was zelfs zo vriendelijk om voorbeeldcode te mailen. Helaas zat daar het probleem helemaal niet :(.
Het probleem zat in mijn straal-driehoek intersectie, ik veronderstelde namenlijk dat de straal parameter t altijd groter was dan 0. Dit was echter niet altijd het geval zodat de dichtsbijzijnde driehoek vaak achter de camera lag. Hierdoor kreeg ik egaal gekleurde plaatjes omdat ik de muur achter de camera renderde.
Het probleem met de geheugenallocatie is ook getraced. Sommige scenes geven een slecht gebalanceerde boom (1 heel diepe tak) bij median split (ik weet nog niet waarom). Omdat het bouwen van zo'n boom recursief is moet er bij een heel diepe tak een diepe stack worden bijgehouden. Op een bepaald moment zegt mijn kernel dan nu is het genoeg en wil geen geheugen meer alloceren voor mijn stack. Ik kan de stack size vergroten (dirty hack) of eens in mijn code duiken (eleganter). We zullen voor de elegante weg kiezen :)
Nog wat problemen op te lossen maar hier toch al een voorsmaakje:
De classroom scene (9400 driehoeken 300 x 300 pixels) gerendered in 31 seconden:
De office scene (34.000 driehoeken 300 x 300 pixels) gerendered in 115 seconden:
De Soda hall (141.640 driehoeken 300 x 300 pixels) gerendered in 1736 seconden:
Deze scenes komen uit de MGF example scenes.
Het probleem zat in mijn straal-driehoek intersectie, ik veronderstelde namenlijk dat de straal parameter t altijd groter was dan 0. Dit was echter niet altijd het geval zodat de dichtsbijzijnde driehoek vaak achter de camera lag. Hierdoor kreeg ik egaal gekleurde plaatjes omdat ik de muur achter de camera renderde.
Het probleem met de geheugenallocatie is ook getraced. Sommige scenes geven een slecht gebalanceerde boom (1 heel diepe tak) bij median split (ik weet nog niet waarom). Omdat het bouwen van zo'n boom recursief is moet er bij een heel diepe tak een diepe stack worden bijgehouden. Op een bepaald moment zegt mijn kernel dan nu is het genoeg en wil geen geheugen meer alloceren voor mijn stack. Ik kan de stack size vergroten (dirty hack) of eens in mijn code duiken (eleganter). We zullen voor de elegante weg kiezen :)
Nog wat problemen op te lossen maar hier toch al een voorsmaakje:
De classroom scene (9400 driehoeken 300 x 300 pixels) gerendered in 31 seconden:
De office scene (34.000 driehoeken 300 x 300 pixels) gerendered in 115 seconden:
De Soda hall (141.640 driehoeken 300 x 300 pixels) gerendered in 1736 seconden:
Deze scenes komen uit de MGF example scenes.
maandag 27 oktober 2008
Status update
Het is alweer maandag dus een meeting met Ares en tijd voor een status update. Deze week ga ik mijn BVH proberen foutloos te laten werken met grote modellen (meer dan 90.000 driehoeken). Ik heb net een paar scenebestanden van Ares gekregen dus die kan ik allemaal proberen te renderen (sommige met meer dan 1 miljoen driehoeken).
Als alle problemen opgelost zijn met de implementatie is het tijd om BVH's te implementeren met de Surface Area Heuristic (SAH). Ik verwacht hier nog een ordegrootte performantiewinst.
Volgende week ook presentatie van de eerste resultaten dus tijd om een draft op te stellen tegen maandag zodat Ares die nog eens kan bekijken.
Als alle problemen opgelost zijn met de implementatie is het tijd om BVH's te implementeren met de Surface Area Heuristic (SAH). Ik verwacht hier nog een ordegrootte performantiewinst.
Volgende week ook presentatie van de eerste resultaten dus tijd om een draft op te stellen tegen maandag zodat Ares die nog eens kan bekijken.
zondag 26 oktober 2008
Ra2 Parser
Vandaag heb ik wat tijd gespendeerd aan het schrijven van een parser voor ra2 bestanden. Ra2 is het (binair) bestandsformaat dat gebruikt in de bwfirt ray tracing benchmark. Nu kan ik enkele scenebestanden gebruiken van Ares en de snelheid van mijn ray tracer vergelijken met die van professionals :)
Helaas is door het kunnen inladen een andere bug aan het licht gekomen. Voor grote bestanden crasht mijn ray tracer bij het bouwen van de bvh tree. Reden hiervoor is dat niet genoeg geheugen kan gealloceerd worden bij grote scenes.
Wat ik nog moet implementeren is het inlezen van files met vertexnormalen. Op dit moment bereken ik slechts 1 normaal per driehoek (door het vectorproduct te nemen van 2 zijden) wat aanleiding geeft to crappy shading.
De volgende scene is de "Ulm Box" een Duitse kopie van de bekende Cornell Box.
Helaas is door het kunnen inladen een andere bug aan het licht gekomen. Voor grote bestanden crasht mijn ray tracer bij het bouwen van de bvh tree. Reden hiervoor is dat niet genoeg geheugen kan gealloceerd worden bij grote scenes.
Wat ik nog moet implementeren is het inlezen van files met vertexnormalen. Op dit moment bereken ik slechts 1 normaal per driehoek (door het vectorproduct te nemen van 2 zijden) wat aanleiding geeft to crappy shading.
De volgende scene is de "Ulm Box" een Duitse kopie van de bekende Cornell Box.
donderdag 23 oktober 2008
Boundingbox intersection
Als code optimizen een drug is dan ben ik een junk. Eenmaal je begint met optimaliseren dan kan je niet meer stoppen. Door het profilen van mijn code heb ik vastgesteld dat de (huidige) bottleneck zit in mijn boundingbox intersection code.
De grootste kost in de intersection code is het maken van 3 delingen (delingen zijn een ordegrootte duurder dan vermenigvuldigingen) om de inverse x, y en z coordinaat van de straalrichting te berekenen. Omdat ik meerdere bounding boxes intersecteer met eenzelfde straal berekenen ik dus die 3 delingen telkens opnieuw. Het tweakje is om de inverse van de richting 1 keer te berekenen in de constructor van de straal en die daarna gewoon op te vragen bij de intersectietest. Eigenlijk voor de hand liggend maar soms is het moeilijk om het bos door de bomen nog te zien :)
Natuurlijk kan ik hiervoor geen enkele credit opstrijken maar heb ik dit trukje uit de volgende paper: "An Efficient and Robust Ray–Box Intersection Algorithm".
En dan natuurlijk de rendertijden:
Weeral een mooie verbetering, ik hoop dat ik nog veel van die trukjes kan blijven toepassen want anders vrees ik dat ik naar het straffer spul moet grijpen (SIMD, packet ray tracing, ...) .
De grootste kost in de intersection code is het maken van 3 delingen (delingen zijn een ordegrootte duurder dan vermenigvuldigingen) om de inverse x, y en z coordinaat van de straalrichting te berekenen. Omdat ik meerdere bounding boxes intersecteer met eenzelfde straal berekenen ik dus die 3 delingen telkens opnieuw. Het tweakje is om de inverse van de richting 1 keer te berekenen in de constructor van de straal en die daarna gewoon op te vragen bij de intersectietest. Eigenlijk voor de hand liggend maar soms is het moeilijk om het bos door de bomen nog te zien :)
Natuurlijk kan ik hiervoor geen enkele credit opstrijken maar heb ik dit trukje uit de volgende paper: "An Efficient and Robust Ray–Box Intersection Algorithm".
En dan natuurlijk de rendertijden:
| figuur | #driehoeken | #seconde |
|---|---|---|
| kegel | 32 | < 1 |
| cilinder | 64 | < 1 |
| bol | 480 | < 1 |
| torus | 1024 | 1 |
| theepot | 4032 | 10 |
| konijntje | 5110 | 13 |
Weeral een mooie verbetering, ik hoop dat ik nog veel van die trukjes kan blijven toepassen want anders vrees ik dat ik naar het straffer spul moet grijpen (SIMD, packet ray tracing, ...) .
woensdag 22 oktober 2008
Möller - Trumbore intersection test
Net de paper "Fast, Minimum Storage Ray Triangle Intersection" gelezen. De paper beschrijft een snelle test voor het berekenen van een straal - driehoek intersectie.
Het zoeken van een straal - driehoek intersectie komt neer op het oplossen van een stelsel van 3 vergelijkingen en 3 onbekenden. In mijn code berekende ik het stelsel eerst en controleerde ik daarna de oplossing. De Möller - Trumbore test lost ook dit stelsel op maar doet dit in verschillende stappen zodat tussendoor al beslist kan worden of er een intersectie is of niet zonder dat het hele stelsel moet opgelost worden.
Dit geeft dan de volgende rendertijden:
Een speedup van een kleine factor 2, bedankt Tomas en Ben!
Het zoeken van een straal - driehoek intersectie komt neer op het oplossen van een stelsel van 3 vergelijkingen en 3 onbekenden. In mijn code berekende ik het stelsel eerst en controleerde ik daarna de oplossing. De Möller - Trumbore test lost ook dit stelsel op maar doet dit in verschillende stappen zodat tussendoor al beslist kan worden of er een intersectie is of niet zonder dat het hele stelsel moet opgelost worden.
Dit geeft dan de volgende rendertijden:
| figuur | #driehoeken | #seconde |
|---|---|---|
| kegel | 32 | < 1 |
| cilinder | 64 | < 1 |
| bol | 480 | < 1 |
| torus | 1024 | 1 |
| theepot | 4032 | 18 |
| konijntje | 5110 | 23 |
Een speedup van een kleine factor 2, bedankt Tomas en Ben!
Abonneren op:
Posts (Atom)