Bounding Volume Hierarchies deel 3

Het is alweer even geleden dat ik nog eens kon bloggen over wat vooruitgang, vandaag komt daar verandering in. Gisterennacht om 00:45 is het gelukt om mijn nieuwe bvh implementatie werkende te krijgen en ongeveer 10 minuten geleden is het gelukt om ze sneller te laten werken dan de oude implementatie.

Het doorlopen van de bvh boom doe je, depth-first (i.t.t. breadth-first). In mensentaal, proberen eerst zo diep mogelijk af te dalen in de boom. De normale manier om zoiets te implementeren is recursief, eenvoudig en intuïtief. Het nadeel is dat er heel veel function call overhead is (er moet een heel grote call stack worden bijgehouden). Om het iteratief te doen kan je zelf een call stack bijhouden of zoals ik doe de knopen in het geheugen steken in de volgorde waarin ze moeten doorlopen worden. Nu heb je een lijst die je iteratief kan doorlopen. Omdat ik mijn scanner werkende heb gekregen onder Linux heb ik een schets bijgevoegd (best even vergroten voor de duidelijkheid).



Op deze manier doen we echter nog altijd teveel werk. Als bijvoorbeeld de boundingbox van knoop B wordt gemist heeft het geen zin om D en E nog te bezoeken. Daarom houden we per knoop een "skip pointer" bij die aangeeft naar welke knoop we moeten springen als de knoop gemist wordt. Dus bijvoorbeeld de skip pointer van B wijst naar C, dus als we B missen slaan we D en E over en springen we naar C.

Hoewel het concept simpel is heeft het me toch redelijk veel bloed, zweet en tranen gekost om dat in C++ vertaald te krijgen. Uiteindelijk werkt het dus tijd voor rendertijden!

figuur	#driehoeken	#seconde
kegel	32	<1
cilinder	64	<1
bol	480	<1
torus	1024	1
theepot	4032	29
konijntje	5110	38

Hoewel het weeral net iets sneller is had ben ik wat teleurgesteld, gezien het veel werk had ik toch meer spectaculaire resultaten verwacht.

Er is nog wel wat ruimte voor verbetering, bijvoorbeeld de knopen zijn nu nog 32 bytes, het zou leuk zijn om dit te reduceren naar 16 bytes. Ook de driehoek-straal intersectie is wat aan de trage kant, hiervoor heeft Ares me verwezen naar de snellere methode van Möller en Trumbore.

Status update

Er is ondertussen een week verstreken sinds de laatste post. Helaas heb ik nog altijd geen vooruitgang te melden :( Het implementeren van een geheugenefficiënte layout is een tijdrovende en moeilijk te debuggen karwei. Ik voel me op dit moment dan ook redelijk gefrustreerd.

Vandaag ook bij Ares langsgeweest en we hebben afgesproken dat ik deze week zal blijven verder debuggen aan mijn code voordat ik nieuwe gronden aanboor.

Een klein experimentje

Daarnet even met Ares aan het praten over g++ optimization levels. Hiermee geef je aan de compiler mee dat hij moet proberen je code zo optimaal mogelijk te compileren. Dus heb ik bij wijze van experiment alles gecompileerd met de flag -O3 (optimization leven 3, het meetst geoptimaliseerd). Dan krijg ik de volgende rendertijden:

figuur	#driehoeken	#seconde
kegel	32	<1
cilinder	64	1
bol	480	1
torus	1024	3
theepot	4032	37
konijntje	5110	54

Grosso modo een factor 3 snelheidswinst door 3 karakters te typen: -O3 !

In een van de besproken papers renderen ze een scene van 804 driehoeken in 0.7 seconden, de regel van 3 leert ons dat ze 1024 driehoeken renderen in 1.12 seconden (Ik veronderstel hier een lineair verband, in de praktijk is dit logaritmisch). Ik kan momenteel 1024 driehoeken renderen in 30 seconden bij een resolutie van 1024 x 1024 (In van één mijn vorige posts was ik mis bij mijn vergelijking omdat ik daar renderde in een resolutie van 300 x 300). Dat is een factor 27 trager dan hun implementatie. Nog wat werk af te leggen :)

Status update

Het is weeral maandag dus een afspraak met Ares en een nieuwe status update.

Waar ik me deze week vooral mee bezig zal houden is het efficiënter herimplementeren van mijn versnellingsstructuur (BVH). Concreet wil dit zeggen:

• Zorgen voor een kleinere memory footprint van mijn BVH nodes. Elke cache miss / memory access is duur.
  
• Het bannen van virtuele functies en polymorphism omdat je hier ten eerste de overhead hebt van de function call (virtuele functies kan je niet inlinen omdat je pas @runtime weet welke functie je moet aanroepen, duh) en de pointer naar de VTABLE is extra geheugengebruik.
• Bij BVH traversel proberen recursie te vermijden. Dus zelf voor compiler spelen en een eigen stack bijhouden.
  

Dat betekent pijnlijk genoeg geschreven code weggooien. Ares heeft me doorverwezen naar de phd van, u raadt het al Ingo Wald, voor verdere referentie.

Als ik dan alles terug draaiende heb gekregen, na lange uren van frustratie om uit te zoeken waarom alles niet compileert, dan is het tijd om een SAH-based BVH te implementeren.

Verder hebben we beslist om Cal3d integraal te gebruiken in mijn raytracer en als extra bestandsformaat ra2 van bwfirt te gebruiken.

Paper: On fast construction of SAH-based bounding volume hierarchies.

Alweer een paper van Ingo Wald deze keer: "On fast construction of SAH-based bounding volume hierarchies". De paper onderzoekt een methode om bij dynamische scenes voor elk frame de versnellingsstructuur terug op te bouwen.

De methode bouwt rond een verzameling driehoeken T een bounding box en neemt van deze bounding box de langste zijde. Die zijde wordt dan onderverdeeld door K equidistante vlakken. Hierdoor verkrijgen we K+1 bins (emmers) van gelijke breedte. Gegeven deze K bins B1 ... Bk dan zijn er K - 1 manieren om de verzameling driehoeken T hierover te verdelen in 2 partities. Bijvoorbeeld als K = 4 dan kunnen we de driehoeken verdelen in T_left = { B1, B2 } en T_right = { B3, B4 }.

Omdat er K-1 mogelijke partitioneringen (teken maar) zijn moeten we deze allemaal uitproberen. We evalueren vervolgens voor elke mogelijkheid een kostenfunctie (wederom de SAH of Surface Area Heuristic) en weerhouden de partitionering met de laagste kost. Van deze 2 partities nemen we dan de bounding box die we terug recursief gaan opsplitsen.

Normaal als je N driehoeken hebt dan kan je de bounding boxes daarvan op 2^N - 2 mogelijke manieren partitioneren. In dit algoritme proberen we maar K-1 mogelijkheden. Het gevolg hiervan is dat het algoritme veel sneller is dan de standaardmanier (alle 2^N-2 mogelijkheden beschouwen). Er is ook een keerzijde aan de medaille, omdat we slechts K-1 mogelijkheden beschouwen doen we een benadering. Als gevolg hiervan is onze BVH ook slechts een benadering van diegene die we zouden vinden met de standaardmethode. De auteurs verzekeren echter dat het snelheidsverlies bij het renderen slechts een paar procenten is.

Een interessante paper vooral voor de besproken techniek die ik uitendelijk zelf ook eens zal proberen te implementeren. Verder geven de auteurs nog enkele build times (tijd nodig om de structuur op te bouwen) en rendertimes. Allemaal op "general purpose" hardware, namenlijk een 8 core 2.6Ghz Clovertown met 8 keer 2Gb ramgeheugen. De definitie van "general purpose" hardware is toch net iets anders in Utah in vergelijking met Leuven.

Paper: Ray tracing deformable scenes using dynamic bounding volume hierarchies

Vandaag een beetje tijd gehad om een paper te lezen. Het is de paper "Ray tracing deformable scenes using dynamic bounding volume hierarchies" geworden wederom van onze goede vriend Ingo Wald.

De paper beschrijft eerst een algoritme om BVH's (Bounding Volume Hierarchies) op te bouwen volgens de "surface area heuristic" (SAH). Tot op vandaag is dit nog altijd de beste heuristiek om een versnellingsstructuur mee te bouwen. De auteurs geven ook een tabel met rendertijden voor BVH's gebouwd met de object median, de spatial median en de SAH. De eerste 2 zitten ook al in mijn eigen implementatie. De auteurs kunnen met de spatial median (ook median split genoemd) een scene renderen van 804 driehoeken in 0.7 seconden. Dit is ongeveer vergelijkbaar met mijn torus (1024 driehoeken) die ik render in 10 seconden, mijn ray tracer is dus een factor 14 trager.

De grote snelheidswinst is grotendeels te wijten aan het gebruik van ray packets. In ray packets worden rays gebundeld en worden die bundels in de scene getraced. Het is duurder om een packet door een scene te tracen dan een enkele straal maar we kunnen die duurdere kost wel spreiden over verschillende stralen. Dus de kost per straal is goedkoper.

Om met dynamische scenes rekening te houden worden de bounding boxes telkens vervormd, de bounding volume hierarchy blijft hetzelfde. Hoewel de kwaliteit van de BVH verslechterd per update is de performantieimpact niet veel slechter.

Deze paper is vooral nuttig om zijn techniek om rays sneller door een BVH te tracen en om zijn rendertijden. Nu heb ik een paar richtwaarden om de performantie van mijn ray tracer mee te evalueren.

Bounding Volume Hierarchies (BVH) part deux

Geprobeerd om median split te implementeren en het werkte van de eerste keer! Mijn computer kijkt heel dankbaar omdat ik hem deze keer geen schop tegen zijn ******* heb verkocht.

Median split komt erop neer dat we de bounding box nemen van een aantal objecten en hiervan het middelpunt berekenen. Als het middelpunt van een object voor het middelpunt van de box ligt (volgens een bepaalde as) dan steken we het in de linkerdeelboom anders in de rechter. Dit blijven we iteratief doen todat we geen objecten meer hebben om te verdelen.

Het deleten van de hierarchy lukt ook, ik krijg geen double free errors en volgens Valgrind is er ook geen geheugen dat verloren gaat.



Nu verkrijgen we de volgende rendertijden:

figuur	#driehoeken	#seconde
kegel	32	1
cilinder	64	1
bol	480	4
torus	1024	10
theepot	4032	162
konijntje	5110	209

De plaatjes zijn nog altijd hetzelfde dus die post ik niet.