Meeting thesisbegeleider

Vandaag de eerst meeting na de vakantie met mijn thesisbegleider (Ares Lagae) en ik weet al direkt wat te doen deze week :)

Om te beginnen zal ik een stapeltje papers moeten doornemen vooral over versnellingsstructuren en het ray tracen van hierarchische animaties. Ares heeft me aangeraden om eens te kijken naar de papers van Ingo Wald. Het is een heel pak maar de volgende lijken me op het eerste zicht relevant voor mijn thesis:

• On fast Construction of SAH based Bounding Volume Hierarchies
• Ray Tracing Animated Scenes using Coherent Grid Traversal
• On building fast kd-trees for ray tracing, and on doing that in O(N log N)
• Asynchronous BVH Construction for Ray Tracing Dynamic Scenes on Parallel Multi-Core Architectures
  
• An Evaluation of Parallel Grid Construction for Ray Tracing Dynamic Scenes

Ook op de homepage van Johannes Günther enkele interessante papers gevonden:

• Exploring the Use of Ray Tracing for Future Games
• Ray Tracing Animated Scenes using Motion Decomposition

De Cal3D library zal ik verder gebruiken in mijn thesis en zal ik dus verder moeten onderzoeken. Het zou leuk zijn als ik deze week de informatie uit deze library kan gebruiken om in een zelf geïmplementeerde scenegraph te steken.

Poser is betalende 3D rendersoftware voor het renderen van animaties, eens kijken of ik hier iets uit kan leren.

Een beetje tijd investeren om enkele tooltjes te schrijven om te renderen met OpenGL. Zo kan ik snel scenes of animaties renderen om te debuggen om deze dan later deftig te renderen met mijn ray tracer.

Veel werk voor de eerste week maar nu is het de moment om een voorsprong te nemen.

Paper: Interactive Ray Tracing of Skinned Animations

De paper "Interactive Ray Tracing of Skinned Animations" is een belangrijke basis om mijn thesis op te bouwen. Daarom lijkt het me aangewezen om de resultaten kort samen te vatten voor mezelf en anderen.

In mensentaal wil de titel zeggen: Het bliksemsnel ray tracen van figuurtjes met een skelet (waarop "huid" zit, nl. de skin) . Net omdat de figuurtjes een skelet hebben (botten en gewrichten) kunnen we dat uitbuiten om het bliksemsnel te doen.

De sleutel om ray tracing snel te maken is het gebruik van versnellingsstructuren (grids, kd-trees, BVHs (Bounding Volume Hierarchies), ...). Voor een statische scene kunnen we de tijd nemen om een efficiënte structuur te bereken maar voor een dynamische scene waarbij in principe in elk frame alles kan veranderen is dat niet haalbaar. Het herberekenen van de versnellingsstructuur is het kritische punt bij het ray tracen van dynamische scenes. We moeten een afweging maken tussen enerzijds een efficiente structuur en anderzijds een snelle berekening van de structuur.

Om ons "versnellingsstructuurprobleem" op te lossen laten we de bewegingen van onze karakters uiteenvallen in 2 componenten:

1. Coherente beweging: een beweging die alle punten van de scene ondergaan.
2. Restbeweging: de beweging van sommige punten lokaal.

Bijvoorbeeld een ventje dat op en neer springt en terwijl in zijn handen klapt. Alle punten gaan op en neer (coherente beweging) terwijl zijn handen lokaal nog andere dingen doen (restbeweging).

De restbeweging wordt behandeld door een fuzzy kd-tree, een kd-tree gebouwd over een fuzzy box. Een fuzzy box is een box groot genoeg zodat alle mogelijk lokale bewegingen erbinnen vallen. Concreet wordt er per bot een kd-tree gebouwd. Het nadeel van deze aanpak is dat we de animatie op voorhand moeten weten om de fuzzy boxes te dimensioneren. Het voordeel is dat we deze kd-tree nooit moeten herberekenen omdat we nu rekening houden met alle mogelijke bewegingen op voorhand. Over de botten worden ook bounding boxes gebouwd waarover op weer een andere kd-tree wordt gebouwd om de absolute beweging in rekening te brengen. Deze kd-tree wordt wel elk frame herberekend, dit is echter geen probleem omdat er maar een beperkt aantal botten zijn.

Om de fuzzy boxes niet te groot te maken kunnen we aan de gewrichten extra voorwaarden opleggen. Bewegingen die dan fysisch niet mogelijk zijn worden ook niet toegelaten in de animatie. Dit leidt tot significante snelheidswinsten.

In de paper wordt een potentieel interessante library gebruikt voor het modelleren van skeletten, de Cal3D library. Deze week eens verder bekijken.

Ook packet ray tracing moet ik eens verder doorspitten, dit is het bundelen van rays in pakketjes en die door de scene te tracen. Volgens de auteurs is dat een voorwaarde voor een high-performance ray tracer.

De auteurs hebben enkel getest met kd-trees. Misschien een interessante piste voor mijn thesis om het ook eens te proberen met grids en BVHs en dan de resultaten te vergelijken.

Profilen

Net de raytracer even door de gnu profiler gesleurd. De volgende matrixfuncties geinlined:

• float Matrix::operator()(int i, int j)
• float Matrix::operator()(int i, int j) const

dit geeft volgende tijden:

1. kegel in 6 seconden
2. cilinder in 11 seconden
3. bol in 82 seconden
4. torus in 177 seconden

2 functies inlinen geeft een gemiddelde verbetering van 40% !

De eerste plaatjes

Zoals een fiere vader de foto's van zijn eerste baby toont, toon ik hier de eerste renders van mijn raytracer. De raytacer is nog redelijk primitief/crappy. Het enige wat op dit moment mogelijk is is het lezen van obj files en die renderen vanuit een willekeurig camerastandpunt.

De dingen die ik in korte tijd nog wil implementeren zijn diffuse shading, het lezen van XML bestanden voor scènes, een scenegraph en een versnellingsstructuur.

De snelheid van de implementatie laat nog wat te wensen over zelfs al is het C++ dus daar moet ik nog wat aan sleutelen. Ik heb een paar plaatjes gerendered (300 x 300 pixels) met de camera gepositioneerd in het punt (3, 3, 3), kijkend in de richting (-1, -1, -1) en een cameraopeningshoek (fovy) van 60 graden. Het scherm staat op afstand 1 van de camera.

Een kegel opgebouwd uit 32 driehoeken gerendered in 10 seconden.

Een cilinder (64 driehoeken, 19 seconden)

Een bol (480 driehoeken, 149 seconden)

Een torus (donut) (1024 driehoeken, 321 s)

De "Utah teapot" (4032 driehoeken, 534 seconden) gerendered vanuit het standpunt (6,2,4) kijkend in de richting (-1, 0, -1), de up vector is (0,1,0).


Het "Stanford bunny" (5110 driehoeken, 704 seconden) gerendered vanuit het punt (5,7,5) kijkend in de richting (-1,-1,-1), de up vector is (0,1,0).

Het is de bedoeling om deze set van plaatjes als benchmark te gebruiken bij de verdere verfijning van mijn implementatie.

figuur	#driehoeken	#seconde
kegel	32	10
cilinder	64	19
bol	480	149
torus	1024	321
teepot	4032	534
konijntje	5110	704

De knoop doorhakken

Deze zomer last gehad van een verscheurende onzekerheid. Zoals jullie wel weten is het de bedoeling dat ik zelf een raytracer ga programmeren voor mijn thesis. Maar welke taal moet ik hiervoor kiezen: C of C++? Om performantieredenen vallen alle andere talen af tenzij OCaml (sneller dan C++) of misschien Lisp, maar dan zou ik waarschijnlijk ontoerekeningsvatbaar verklaard worden. Ik heb eindelijk mijn keuze gemaakt en door het nu on the record te zetten kan ik niet meer terugkrabbelen.

Vorig semester heb ik het bekende, klassieke en oerdegelijke boek van Kernighan & Ritchie "The C programming language" doorworsteld. Het eerste echte programmeerboek geschreven op een tutorialachtige wijze. C is niet echt een aanrader voor beginners maar vanaf het moment dat je het concept van pointers hebt begrepen weet je er alles van. C is een kleine, compacte en elegante taal.

Mijn eerste ervaring met C++ was van een andere orde. Het leek me een uitdaging om het project voor het vak Computer Graphics te implementeren in C++. Viel dat even tegen. C++ is een ordegrootte moeilijker, harder en pijnlijker dan Java. Gelukkig was Java een vergevingsgezinde partner. Nog nooit zo blij geweest om terug in Eclipse te zijn.

Dus eens proberen om een raytracer te schrijven in C. In C heb je 2 dingen: functies en datastructuren. Met deze 2 kom je al een eind op weg, je kan zelfs dingen als polymorfisme simuleren met function pointers. Maar "de jeugd van tegenwoordig is nog met weinig tevreden" geldt ook voor mij. Een taal moet een minimale ondersteuning hebben voor objectgeoriënteerd programmeren en Java heeft ons dat gul gegeven. Het is uiteindelijk gelukt om een raytracer te schrijven om bollen te renderen maar met veel te veel moeite. Ik had naar Eric S. Raymond moeten luisteren:

the more you can avoid programming in C the more productive you will be.

Nadat ik al eens in mijn voet had geschoten met C++ wilde ik het nog eens proberen. Tenslotte had ik nog een andere voet. C++ is een groot complex beest geeft zelfs Bjarne Stroustrup toe (geen wonder dat hij ondertussen kaal is). Formeel noemen noemen ze dat een multiparadigma programmeertaal. Na het boek "Accelerated C++" te hebben doorgenomen had ik al wat meer hoop, alhoewel ik weet dat het boek veel dingen verzwijgd. Toch heeft C++ enkele coole features/voordelen:

• Operator overloading, zou elke taal moeten hebben. Hierdoor zal ik misschien binnenkort Java scheef gaan bekijken.
  
• Referenties, geen gerommel met pointers (zoals in C) om call-by-reference te faken maar echte ondersteuning zoals in Java.
• Meervoudige overerving, voor sommige problemen kan dit echt wel een elegante oplossing zijn. Hoewel sommigen beweren dat dit je een rechtstreeks ticket naar de hel koopt.
• Qt, de C++ library van Trolltech, niet zo uitgebreid als de Java API maar veel beter gedocumenteerd als bijvoordeeld The Gimp Toolkit voor C.

Dus on the record: C++ it is. Voorlopig heb ik mijn andere voet er nog niet afgeschoten en hink ik nog altijd fluitend door het leven. Misschien kan ik over een paar dagen al enkele plaatjes tonen van mijn (crappy) C++ raytracer.

Nog enkele motiverende C++ quotes om af te sluiten:

C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do, it blows away your whole leg. (Bjarne Stroustrup, maker van C++)

There are only two things wrong with C++: The initial concept and the implementation. (Bertrand Meyer, maker van Eiffel)

If C++ has taught me one thing, it's this: Just because the system is consistent doesn't mean it's not the work of Satan. (Andrew Plotkin)

If you think C++ is not overly complicated, just what is a protected abstract virtual base pure virtual private destructor and when was the last time you needed one? (Tom Cargill)

Raytracing voor beginners

Zoals eerder beloofd (een paar dagen zijn 2 maanden geworden) zal ik vandaag voor de niet-ingewijden (proberen) uit te leggen wat raytracing is.

Wat is het?
Raytracing is een algoritme om met de computer mooie plaatjes te maken. In computerterminologie wordt dit renderen genoemd. Rasterisation bijvoorbeeld is een ander algoritme dat momenteel gebruikt wordt in computer games en geïmplementeerd is op grafische kaarten.
Het plaatje hieronder is niet echt maar gemaakt met raytracing. Voor meer verbluffende plaatjes gemaakt met raytracing zie de pov-ray hall of fame.

Hoe werkt het?
Het principe is zeer simpel. Om te beginnen hebben we een scène nodig waarvan we een plaatje willen maken, een plaats van waaruit we kijken (het oog, de camera, ...) en het scherm waarop we het plaatje willen tonen.

Om onze scène op het scherm te krijgen "schieten" we een straal (ray) door elke pixel van ons scherm in de scène. We zoeken het dichtsbijzijnde snijpunt met een object uit de scène en geven de pixel de kleur van ons object. We herhalen dit voor alle pixels van het scherm. Nu staat er op het scherm een mooi plaatje van onze scène.

Dit simpel en elegant algoritme is makkelijk te implementeren in computersoftware. Er is echter een zeer fundamenteel probleem, het algoritme is heel traag. Het probleem is het vinden van het snijpunt van de straal en een object uit onze scène. Hiervoor moeten we elk object controleren op snijding met onze straal. In de praktijk zijn alle objecten uit onze scène meestal opgebouwd uit kleine driehoekjes, als je de foto van het konijntje hieronder vergroot dan zie je dat duidelijk. In computer graphics noemen we die modellen meshes (draadmodellen).

Een klein rekenvoorbeeldje om het meer concreet te maken. Stel we willen een plaatje maken van het Stanford Bunny, dit lieve konijntje is opgebouwd uit ongeveer 70.000 driehoekjes. Als we een plaatje willen maken van 1000 x 1000 pixels dan moeten we een straal schieten door 1 miljoen pixels (1000 x 1000 = 1 miljoen). Elke straal moeten we controleren op snijding met elk driehoekje, dit geeft ons 1000 x 1000 x 70.000 = 70 miljoen controles. Als elke controle 1 microseconde (1 miljoenste van een seconde) duurt dan duurt het 70 miljoen * 1 microseconde = 70 seconden = 1.166 minuten voor het hele plaatje. Ter vergelijking in een computer game wordt er gerendered aan 25 beeldjes per seconde dus 0,04 seconden per beeldje.

Conclusie: raytracing is enkel voor geduldige mensen :)

Uiteraard zijn er verschillende technieken ontwikkeld om dit veel sneller te doen maar anno 2008 is dit algoritme nog altijd veel te traag om bijvoorbeeld te gebruiken in computer games. In juni dit jaar hebben enkele Intel werknemers het bekende spel Quake 4 omgebouwd zodat de beeldjes worden gerendered met raytracing. Om 15.2 beeldjes per seconde te renderen zijn er 16 processoren nodig. Voor meer info zie dit artikel.

Mocht het allemaal niet duidelijk zijn laat dan een reactie achter.