Front-To-Back Traversal & Culling

Op aanraden van Ares heb ik front-to-back traversal en culling in mijn ray tracer geïmplementeerd. Hoewel de principes niet moeilijk zijn zal ik voor de niet ingewijden een korte uitleg geven.

Front-to-back traversal komt erop neer dat we onze BVH hierarchy proberen te doorlopen in de volgorde zoals we de hierarchy "zien" vanuit de straal. In mijn oude code werd er gewoon altijd eerst links doorlopen en dan rechts. Het plaatje zou alles moeten verduidelijken.



Front-to-back traversal doet in principe nog altijd hetzelfde werk als eerst links en dan rechts doorlopen. Het wordt pas interessant wanneer we dit gaan gebruiken voor "culling".

Het idee hier is dat wanneer we in Box 1 een intersectie met een driehoek hebben gevonden en daarna berekenen we de intersectie met Box 2 dan vinden we dat deze verder ligt. Aangezien alles wat in Box 2 zit dan ook verder zit moeten we dat niet meer bekijken.



In de bovenstaande figuur moeten we de inhoud van Box 2 niet meer controleren dat bespaart ons 2 straal/driehoek intersecties of grofweg de helft van het werk (herinner dat straal/driehoek intersecties veel duurder zijn dan straal/boundingbox intersecties, in mijn implementatie ruw geschat een factor 7 a 8). Dit is natuurlijk niet altijd zo maar er zullen veel gevallen zijn waar we maar 1 van de 2 boxen moeten helemaal testen en dus maar de helft van het werk doen.

Dat geeft ons dan de volgende statistieken:

					BVH STATS WITH FTB TRAVERSAL AND CULLING
					scene	#triangles	#tris/ray	#box/ray	build (s)	render (s)
					ulm box	492	3.09	31.11	0	2
					classroom	9K	6.53	157.5	0	9
					office	34K	7.42	98.17	0	6
					cabin	219K	11.29	210.65	0	12
					armadillo	345K	1.15	30.86	2	2
					atrium2	559K	10.89	211.72	2	12
					conference	987K	6.73	199.95	4	10
					cruiser	3.64M	16.87	171.12	16	10
					dragon	7.22M	0.8	24.59	24	2

Wat duidelijk opvalt in vergelijking met de vorige post is dat het aantal straal/driehoek intersecties voor sommige scenes tot de helft is gezakt, als dat geen mooi bewijs is dat de implementatie werkt! Dit uit zich ook in de rendertijden die voor het gros van de scenes gehalveerd is.

Ik denk persoonlijk dat ik bijna alles uit deze simpele BVH met median split structuur gehaald heb wat eruit te halen valt en dat het tijd is voor de zwaardere middelen. Tenzij Ares maandag nog enkele tips heeft :)

Nieuwe Aura's

Voor mijn aura's heb ik het rgb kleurmodel veranderd naar het hsv kleurenmodel. Door de parameter h (hue) aan te passen kan ik nu het kleurenverloop in de afbeelding mooi laten van variëren van groen tot rood. Een groene pixel heeft (relatief) weinig werk gekost, een rode pixel heeft veel werk gekost.

Er is niet direct nut hiervan in mijn thesis maar het is wel handig voor het debuggen en optimaliseren. En ik heb mooie prentjes voor op mijn blog :p











Het aantal driehoek/straal intersecties was fout in mijn vorige posts, ik maakte hier een gewogen gemiddelde van het aantal driehoek/straal intersecties en het aantal boundingbox/straal intersecties. De volgende cijfers zijn wel correct voor de standaardimplementatie:

			BVH STATS WITH STANDARD IMPLEMENTATION
			scene	#triangles	#tris/ray	#box/ray	build (s)	render (s)
			ulm box	492	3.48	34.2	0	3
			classroom	9K	11.39	198.75	0	12
			office	34K	12.82	118.52	0	8
			cabin	219K	23.1	258.6	1	16
			armadillo	345K	2.66	55.17	2	5
			atrium2	559K	14.73	245.1	3	22
			conference	987K	10.61	234.6	6	21
			cruiser	3.64M	35.62	356.23	23	33
			dragon	7.22M	2.28	65.1	38	4

Er is duidelijk iets mis met deze tabel maar gelukkig zijn de waarden wel leesbaar. De tabelondersteuning in blogger is echt wel crappy.

Status Update

De eerste status update sinds 2 weken. Zoals jullie ondertussen allemaal weten is het maandag dus een afspraak met Ares.

Eerst en vooral moet ik deze week verder werken aan mijn BVH's, concreet moet ik het doorlopen van de hierarchie optimaliseren. Een eerste optimalisatie is het front to back doorlopen van de hierarchy, hierdoor is de eerste hit meteen ook de juiste. Een tweede optimalisatie is culling, hier probeer je delen van de boom gewoon over te slaan bij traversal. Voorlopig ga ik niet meer kijken naar mijn SAH implementatie todat de BVH volledig op punt staat.

Om de performantiewinst van mijn optimalisaties te bepalen is het belangrijk om genoeg gegevens te verzamelen in mijn ray tracer. Om die gegevens te visualiseren ga ik een apart tooltje maken dat prachtige aura's maakt.

De fouten in de plaatjes van mijn OpenGL tool komen volgens Ares waarschijnlijk omdat ik geen z-buffer gebruik en door backface culling. Normaal zou ik dat probleem in korte tijd moeten kunnen fixen.

OpenGL Tool

Deze week is het redelijk rustig geweest wegens enkele andere deadlines. Nu het weekend is kunnen we terug een beetje proberen op kruissnelheid te komen.

Na een maand BVH's te coden en te debuggen ben ik dat een beetje beu dus tijd om de Cal3d library werkende te krijgen dacht ik zo. Helaas de cal3d library werkt nog altijd niet :( Er is ook een positieve kant aan. Om te controleren of de fout ligt bij de Cal3d code waar ik aan bezig ben of aan mijn eigen ray tracer heb ik een toolje geschreven om mijn scenes ook te renderen met rasterisatie. Wie tijd teveel heeft kan het eens nalezen op Wikipedia.

Concreet maak ik hiervoor gebruik van de OpenGL API. Na slechts één tutorial door te nemen is het al gelukt om iets redelijk deftig te schrijven. Met deftig bedoel ik, voor mij werkt het goed genoeg. In sommige plaatjes zitten wel foutjes, waarom weet ik niet.

De Soda scene gerendered met mijn tooltje:



Wat ik er nog zou willen insteken is het visualiseren van bounding boxes en stralen.

Presentaties

Gisterennamiddag en deze namiddag heeft elke thesisstudent van de graphics groep een korte presentatie gehouden over het onderwerp van zijn thesis mezelf inclusief. Ik was redelijk zenuwachtig maar uiteindelijk is de presentatie vlot verlopen, mijn t-shirt kon je wel uitwringen achteraf :) Helaas kan ik mijn presentatie niet online zetten omdat blogger alleen maar afbeeldingen toelaat.

EDIT: Dankzij een nuttige tip van Davy staan nu ook mijn slides online.

Ik heb veel gestolen met mijn ogen maar 1 idee van Frederic De Pourcq vond ik heel cool namenlijk "aura's". Dan heb ik het niet over aura's in de context van energievelden leren zien, chakra's en andere kwakzalverij. Het idee is om elke pixel te kleuren naargelang de hoeveelheid werk die nodig was om die pixel te berekenen, met hoeveelheid werk bedoel ik dan straal/driehoek intersecties.

Het idee is veel beter dan tabellen opstellen (zoals ik een paar posts geleden deed) omdat je nu direct een visuele indruk krijgt van de complexiteit van een scene en de kwaliteit van een versnellingsstructuur. Zo'n aura geeft alleen maar een visuele indruk en is geen rigoureus bewijs voor kwaliteit e.d. maar het is wel handig.

Daarnet heb ik het zelf in mijn ray tracer proberen te integreren, in sommige plaatjes zitten wat foutjes maar het idee is er wel, misschien kan ik zo een verklaring vinden voor de slechte rendertijd van de attrium scene.

Hoe dieproder de kleur van een pixel heeft des te meer werk heeft het gekost om die pixel te berekenen. Ideaal zouden we afbeeldingen willen met lokaal een beetje rood maar overwegend zwart.

Het aura van het Attrium:


De Ulm box


De Soda hall

De office scene

de classroom

de asian dragon
armadillo

Ik ga het in mijn ray tracer laten zitten met conditional compilation, zo kan ik het er terug uithalen wanneer ik wens. Mijn inziens gaat dit nog heel handig zijn bij het debuggen van versnellingsstructuren.

Benchmarks

Zoals gisteren beloofd enkele benchmarks op een resolutie van 1024 x 1024 pixels zodat we eens deftig kunnen vergelijken met andere implementaties.

Scene	#driehoeken	Tijd (seconden)	#intersecties/straal
Ulm box	492	3	9.55
Classroom	9250	14	44.519
Office	34.000	8	25.78
Soda	141.636	12	52.11
Cabin	219.435	17	48.08
Armadillo	345.944	4	8.57
Atrium	559.992	1215	111.27
Conference	721.945	15	30.296
Cruiser	3.636.291	24	73.01
Asian Dragon	7.219.045	5	10.15

Om een obscure reden rendert het atrium nog altijd veel langer als de rest van de scenes. Zoals Ares reeds voorspeld had is het aantal driehoek/straal intersecties sterk gedaald.

De build time voor de versnellingsstructuren is niet bijgerekend daarom zal ik deze een van de volgende dagen ook posten.

Bounding Volumes Part IV

Na mijn gesprek met Ares heb ik ter experiment een simpelere referentieimplementatie gebouwd van mijn bounding volume hierarchy. In deze nieuwe implementatie houd ik de 2 kindknopen naast elkaar bij in een array. Door opnieuw te implementeren heb ik een aantal bugs gevonden in mijn boundingbox code: elke boundingbox bevatte sowieso de oorsprong, met als gevolg dat de meetste bounding boxes veel te groot waren. Verder heb ik nog een paar kleine aanpassingen gedaan in mijn code. Het resultaat is dat mijn code 2 ordegroottes sneller is !!!! Halleluja, ik vermoed dat het aan mijn bounding boxes ligt maar dat kan ik niet met zekerheid zeggen omdat ik ook in mijn median split algoritme aanpassingen heb gedaan.

Het geeft een wrang gevoel wetende dat je meer dan een week verspild heb aan een nutteloze implementatie. De les: eerst een simpel algoritme bouwen en dan gradueel verfijnen in plaats van een superoptimale implementatie maken die nooit werkt omdat je toch de complexiteit niet kan beheersen! Deze quote van Ken Thompson (B language, UNIX, Plan 9) vat perfect mijn dag samen: "One of my most productive days was throwing away 1000 lines of code.".

En de rendertijden:

figuur	#driehoeken	#seconde
office	34000	<>
soda hall	141.636	1
cabin	219.435	1
armadillo	345.944	1
attrium	559.992	104
asian dragon	7219045	1
conference	987.522	1
cruiser	3.636.291	2

en de plaatjes (cruiser, conference, dragon, attrium, armadillo):





De eerlijkheid gebied me te zeggen dat het bouwen van de bvh tree ook een paar secondjes kost.

Morgen zal ik deze allemaal renderen op een resolutie van 1024x1024 pixels zodat we eens deftig kunnen vergelijken.

Waarom het attrium zo traag rendert weet ik nog niet.