Schrijven

Ondertussen is mijn volledige implementatie klaar en zijn de resultaten binnen. Op dit moment ben ik volop bezig met het schrijven van mijn thesistekst. Op de inleiding en conclusie na is de eerste draft zo goed als klaar. Hopelijk kan ik morgen mijn eerste draft naar enkele chinese vrijwilligers sturen die alles grondig zullen nalezen.

Motion Decomposition Part 4

Ondertussen staan we op ongeveer een maand van de deadline. Dat betekent dat ik ondertussen al bezig ben met het schrijven en het verzamelen van resultaten. De resultaten van de motion decomposition techniek zijn er ook al maar deze lijken wat tegen te vallen. Het blijkt dat deze techniek een pak trager is dan alle andere bestudeerde technieken.

De volgende tabel geeft de framerates voor onze 9 testanimaties:

Animatie	FPS
Cally1	5.24
Cally2	4.87
Cally3	3.33
Skeleton1	11.89
Skeleton2	7.38
Skeleton3	12.98
Paladin1	1.97
Paladin2	2.77
Paladin3	3.16

In vergelijking met de andere technieken is dit een pak trager. De reden hiervoor is het hoog aantal bounding box en driehoek testen zoals te zien in de volgende tabel (#BBox = aantal bbox testen, #TLBBox = aantal bbox testen in de top level tree, #LLBBox = aantal bbox testen in de locale trees, #Cluster = Aantal local level trees):

Animatie	#Clusters	#BBox/#Hit	#Tri/#Hit	#TBBox/#Hit	#LBBox/#Hit	RenderTime	TopTime	LocalTime
Cally1	33	166	85	38	127	0.19	0.014	0.16
Cally2	33	135	86	41	129	0.21	0.015	0.17
Cally3	33	161	77	38	122	0.20	0.015	0.17

Ik ben volop aan het uitzoeken of het probleem ligt bij mijn code of dat de techniek fundamenteel slechter is. Hoewel ik vermoed dat het aantal driehoek testen sowieso te hoog ligt.

Motion Decomposition Part 3

Alweer een tijdje geleden sinds mijn laatste bericht. Dat betekent niet dat ik heb stilgezeten. Ondertussen is het me gelukt om de techniek van Günther correct te implementeren. Dit heeft een tijdje langer geduurd dan gepland maar ik heb wat last gehad van bugs.

Tegen de verwachtingen in is deze techniek niet zo snel als rebuilds of refits. Mijn code moet nog een beetje geoptimaliseerd worden maar ik weet niet of het hieraan ligt. Op het eerste zicht lijkt het dat er een pak meer BoundingBox testen worden uitgevoerd bij deze techniek. Dit ga ik nog wat verder onderzoeken.

Voorlopig kunnen we renderen aan volgende framerates:

• Cally Animaties (3342 driehoeken, 37 botten): 7 fps
• Paladin Animaties (3422 driehoeken, 54 botten): 3 - 5 fps
• Skeleton Animaties (4604 driehoeken, 23 botten): 7 - 11 fps

Hieruit kunnen we al uit besluiten dat de performantie afhankelijk is van het aantal botten.

Animaties voor Analyse

Om een grondige analyse uit te voeren heb ik verschillende 9 animatiesequenties gemaakt. De sequenties zijn een combinatie van 3 modellen (cally/skeleton/paladin) en 3 bewegingen (wandelen/lopen/freestyle). Hierop kan ik dan de 3 verschillende algoritmes loslaten.

Al deze animaties zijn gemaakt met mijn eigen raytracer met een resolutie van 512 bij 512 pixels. Framerates schommelen tussen de 15 en 25 fps.

Packet Ray Tracing

Zoals gezegd een tabel met de benchmark van de packet implementatie. Deze implementatie is nog niet optimaal (nog geen frustum culling) maar omdat het tijd wordt om een analyse te doen moet ik mijn implementatie afronden. Hiermee zal ik het dus moeten doen:



Er is geen optimale pakketgrootte voor elke scene maar de beste lijken 4x4, 8x8 en 16x16. Voor te grote pakketten is er minder coherentie tussen de rays in een pakket en daalt de performantie voor alle scenes. De speedups zijn wel bevredigend en schommelen tussen 2.5 en 4.

Begin Analyse

De kogel is door de kerk, voor mijn thesis zal ik 3 technieken bespreken voor het renderen van animaties:

1. Rebuild (elk frame herbouwen van de versnellingsstructuur)
2. Refit (elk frame aanpassen van de versnellingsstructuur)
3. Fuzzy (1 versnellingsstructuur bouwen voor alle frames)

Met de implementatie van de Fuzzy structuur ben ik nog niet helemaal rond maar de andere zijn al klaar.

Om het allemaal wat sneller te laten gaan heb ik mijn ray tracer omgebouwd naar een packet ray tracer. Dat geeft een significante snelheidswinst, benchmarks zal ik weldra posten.

Om een grondige analyse te doen beschik ik over 3 verschillende modellen:

1. Cally (37, 3342 driehoeken)
   
2. Skeleton (23 botten, 4604 driehoeken)
   
3. Paladin (58 botten, 3422 driehoeken)
   

En voor deze 3 modellen heb ik 3 verschillende animaties gedefinieerd:

1. Walking (rustig wandelen en wuiven)
   
2. Jogging (joggen en een pijl afvuren)
   
3. Freestyle (een funky beweging)
   

Elk met net iets meer "beweging". Met 3 modellen en 3 animaties kunnen we 9 verschillende testcases maken voor de 3 algoritmes.

Om het allemaal wat sneller te laten gaan zal ik de filmpjes maken met een resolutie van 512 x 512 pixels. Om op te warmen zijn er hier al 3:

Cally Walking

Paladin Jogging

Skeleton Freestyle

Alle animaties zijn gerenderd op 512 x 512 pixels met framerates tussen de 15 en 25 frames per seconde.

Motion Decomposition part 2

Dankzij de hulp van Johannes Günther ben ik al een stuk verder met de implementatie van de door hem beschreven techniek. Het gaat niet zo snel als gehoopt maar ik kan natuurlijk niet van hem verwachten dat hij mijn emails onmiddelijk beantwoord.

Het scheiden van de beweging in 2 componenten is ondertussen gelukt en ook de fuzzy boxes kunnen gebouwd worden. Hieronder zie je de restbeweging waarover we de fuzzy boxes bouwen.

Om aan elke driehoek een bot te koppelen berekenen we het gemiddelde bot. Dit is niet altijd optimaal zoals te zien is aan de handen. Beter zou zijn om een exhaustieve zoektocht te doen tot alle beweging minimaal is.


Boven zie je de fuzzy boxes van de vertices. Om de fuzzy boxes te bereken nemen we random 1000 samples per vertex.

Het einde van de tunnel (implementatie) komt in zicht!

Planning 2e semester

Aangezien de deadline voor de thesis dichterbij komt wordt het tijd om een planning op te stellen voor mijn werkzaamheden voor de rest van het semester:

Week 12
* Afwerken van de techniek van guenther.

Week 13
* Afwerken van de techniek van guenther.
* Compileren van een lijst met de analyses die ik wil doen.
* Begin analyse van de technieken.

Week 14
* Analyse van de technieken.

Week 15
* Analyse van de technieken
* Survey van niet onderzochte technieken.

Week 16
* Op vakantie dus geen thesis.

Week 17
* Schrijven van de thesis.

Week 18
* Schrijven van de thesis.

Week 19
* Schrijven van de thesis.

Week 20
* Schrijven van de thesis.

Week 21
* blok/buffer

Week 23
* blok/buffer

Week 24
* 1e examenweek

Week 25
* 2e examenweek/deadline thesis (17 juni)

De deadline lijkt nog lang maar tot mijn grote verbazing/schrik is er niet zoveel tijd meer om nog veel werk te verzetten. Nog 4 weken voor de paasvakantie om echt werk te doen en na de paasvakantie zal er intensief moeten geschreven worden. Hiervoor had ik op 6 weken gerekend maar het zal moeten gebeuren in 4 weken aangezien ik graag nog wat zou blokken voor mijn andere vakken.

Motion Decomposition part 1

Nog steeds bezig met het implementeren van de techniek uit de paper van Günther (Die conceptueel wel duidelijk beschreven is maar waar er weinig gezegd wordt over de implementatiekant van de zaak). Ik ben deze week bezig geweest met een poging om de beweging op te delen in 2 componenten:

• Affine motion: "globale beweging" van het karakter waarbij elke mesh wordt beïnvloed door 1 dominant bot.
• Residual motion: beweging onder invloed van de andere botten, deze beweging is het meest uitgesproken rond de gewrichten waar de "huid" sterk wordt beïnvloed door verschillende botten.

De som van deze 2 componenten is dan de originele beweging. Helaas is dit nog niet helemaal zonder bugs :( Een paar beeldjes om het duidelijk te maken.

Boven zie je de affine motion. Elke mesh wordt beïnvloed door 1 bot. Vooral aan de gewrichten zie je gaten in de mesh. Dit komt omdat rond de gewrichten de meshes worden beïnvloed door meerdere botten terwijl er hier maar invloed is van 1 bot.

Hier zie je de restbeweging. Hier heb je alleen de invloed van de andere botten. Zoals je ziet is het plaatje niet helemaal correct. Sommige delen van de mesh maken een veel te grote swing!

Het probleem zit bij de berekening van de bot/mesh relatie. We kennen een mesh toe aan een bot als de meerderheid van zijn punten het meest wordt beïnvloed door dat bot. Sommige punten worden echter veel meer beïnvloed door een ander bot. Dus deze punten waren beter toegekend aan een ander bot. Dit zijn de punten die worden "meegetrokken" met een ander bot in de mesh.

Een bewijs voor deze redenering wordt hierboven getoond. Hier hebben we punten van de mesh die sterk worden beïnvloed door een ander bot niet mee getransformeerd. Dan zie je een beeld dat meer lijkt op wat we eigenlijk willen bekomen.

De oplossing is volgens mij om in plaats van voor elke mesh een dominant bot te berekenen een dominant bot te berekenen voor elk punt van de mesh. Dus een veel fijnere methode.

Dat wil niet zeggen dat moesten we de methode toepassen op de "foute" restbeweging we een fout beeld zouden renderen. De fuzzy boxes gaan wel heel inefficiënt zijn voor de punten met grote uitwijking. Hoewel het interessant is om te onderzoeken of dit heel veel gaat verschillen in de globale framerate. Dus de vraag is: hoe groot is de invloed van foute bot/mesh toekenningen op de methode?

Hier volgt zeker nog een part 2!

Status Update

Weeral maandag dus meeting met Ares. Een beetje gediscussieerd over mijn "transformatieproblemen" met de Cal3d library en enkele nuttige tips hierover gehad. Verder bezig geweest over het verder verloop van het semester.

De deadline is 17 juni en ik moet 6 weken voorzien om mijn thesis te schrijven. Dit betekent dat ik nog maar tot eind april heb om met de echte inhoud van mijn thesis bezig te zijn. Nog maar een kleine 2 maanden dus! Daarom wordt het tijd om:

• Te beslissen welke technieken ik nog wil onderzoeken en hierin een definitieve keuze te maken.
• Een inhoudsopgave schrijven om een idee te krijgen van de structuur van de tekst.
• Beslissen welke analyses ik wil doen, hiervoor moet ik volgens Ares ook enkele weken voorzien. Het is belangrijker om een grondige analyse te hebben dan een implementatie van verschillende technieken.
• Een planning maken voor de rest van het semester!

Er moet ook nog een paper geschreven worden maar dat kan ik ook doen tijdens het schrijven van mijn thesis.

Interfacen met Cal3d

Door de jobfairs, werkjes en andere afleidingen is mijn thesis wat blijven liggen. Vanaf dit weekend ga ik daar terug verandering inbrengen en weer intensief aan mijn thesis werken! Ik heb niet helemaal stilgezeten dus hier volgt een kleine update.

Ondertussen ben ik nog altijd bezig met het implementeren van de techniek uit de paper van Günther. Voor de karakteranimaties gebruik ik de open-source Cal3d library. Omdat ik Cal3d wil gescheiden houden van mijn eigen code ben ik aan een "interface" aan het werken tussen de ray tracer en Cal3d.

Het is al mogelijk om skeletinformatie en boundingbox informatie uit Cal3d te halen en hier enkele coole animaties mee te renderen. Met de transformaties zit ik nog wat in knoop, hier vrees ik dat ik eens een goed boek zal moeten zoeken over character animation.

De deadline voor de thesis is 17 juni, dat lijkt nog heel ver, maar Ares heeft me aangeraden een planning te maken en eens na te denken over een inhoudsopgave voor mijn thesis. Dus daar zal ik me ook mee bezig houden dit weekend.

Begin 2e semester

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.

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