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).

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.

					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.

Cal3d Werkt

Na weken van hier en daar wat experimenteren, rommelen en prullen met Cal3d dacht ik vanmiddag, nu stop ik niet meer tot het werkt. Het heeft me de rest van de dag gekost maar het is me eindelijk gelukt om animaties te renderen met mijn ray tracer.

Het laten aan mekaar vloeien van animaties heb ik nog niet helemaal door maar het belangrijkste is dat het werkt. Dus meet Cally en Bones.
Er zitten nog een paar foutjes in, bijvoorbeeld Cally heeft soms gaten in haar meshes waardoor het lijkt alsof ze beschoten is met een machinegeweer.

Framerates komen er nog aan.

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.

Status update

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!

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 :)

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.

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.

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.

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:

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, ...) .

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:

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!