Een klein eureka moment...

Ik ben verheugd u te verkondigen dat mijn algoritme zich voor het eerst gedraagt zoals ik verwacht dat zich gedraagt :-).
Aanvankelijk dacht ik dat het probleem zich wel zou bevinden bij het omzetten naar het frequentie domein. Dat heb ik dan ook volledig nagegaan en elke stap van het algoritme in debugmode bekeken. Nu de stap die ik telkens oversloeg was het berekenen van het verschil met de vorige waarden. Nu daar zat nu net het probleem. Omdat ik initieel alle frequentietermen op 0.0 zette werd in de eerste adaptieve stap de nieuwe waarden met 0.0 vergeleken. Daar zit nu net het probleem want stel dat we een volledig wit (1,1,1) blokje hebben dan is de DCT daarvan een 8 in de linkerbovenhoek en 0 elders. Nu omdat 8-0 hoogstwaarschijnlijk het grootste verschil zal zijn, wordt dit blokje als eerste gekozen, terwijl het volledig effen is.

Hieronder de resultaten. Bovenaan zien we het beeld dat pbrt geeft met 1,4M stralen, daaronder staat het beeldje dat mijn algoritme geeft. Bij de buddha zien we dat de ruis op de sokkel en de buddha zelf gevoelig lager ligt dan bij de standaard ray-tracer. Nogmaals daaronder staat de verdeling van het aantal stralen. We zien duidelijk dat het algoritme nu correct de plaatsen met meer ruis detecteert en bijgevolg daar meer stralen schiet.
Bij de glazen bol zien we dat de caustic en de zachte rand meer samples krijgen (zoals te verwachten valt).

Het is al weer een tijd geleden dat ik hier nog eens gepost heb.
Het heeft nogal wat voeten in de aarde gehad maar ik heb nu een correct werkende basis implementatie.

Eerst nog even kort herhalen wat het algoritme juist doet:

• In een eerste stap wordt het beeld opgedeeld in vakjes van 8x8 pixels. Naar analogie met jpeg-algoritmes.


• Vervolgens wordt een eerste bemonstering genomen van het beeldje. (In mijn geval neem ik 128 (8x8x2) samples. Dit komt overeen met 2 samples per pixel. Dit doe ik om toch zeker elke pixel van het beeldje minstens 2 samples te hebben).


• In de derde stap wordt voor elk blokje de DCT (Discrete Cosinus Transformatie toegepast). De waarde (=het verschil met de vorige benadering) wordt op maximum gezet omdat we nog geen vorige benadering hebben. (dus eigenlijk komt elk blokje nog minstens 1x aan de beurt in het iteratieve stadium).


• Vanaf hier begint het iteratieve proces:


• Het blokje met de grootste waarde wordt genomen.


• Neem X samples op dat blokje.


• Bereken de DCT op de nieuwe pixelwaarden.


• Bereken het verschil met de vorige benadering. Als er een groot verschil is, is dit een indicatie dat pixelwaarden veel gewijzigd zijn, dus dat er waarschijnlijk nog meer samples nodig zijn. Daarom krijgt het blokje in dat geval een grote waarde. In het andere geval wanneer de cosinustermen weinig van elkaar verschillen krijgt het blokje een kleine waarde.




• Het iteratieve proces stopt wanneer de maximale waarde over alle blokjes kleiner is dan een bepaalde stopconditie of wanneer een vooraf bepaald aantal stralen verdeeld zijn.

Het algoritme zoals het nu geïmplementeerd is verschilt in een aantal opzichten van wat Bolin & Meyer doen:

• Het grootste verschil is dat mijn implementatie los staat van elke mogelijke sampler. Dat betekend dat mijn algoritme ook perfect werkt bij random sampling e.a. Bij Bolin & Meyer wordt strak vastgehouden aan vast sample patroon per blokje. Dat heeft op zich dezelfde nadelen als een vast samplepatroon per pixel. Hun samplepatroon neemt tevens veel samples op de rand van het blokje zodat eigenlijk veel samples meermaals worden genomen in naburige blokjes. Zij hebben die keuze gemaakt omdat ze dan voor elk blokje dezelfde transformatiematrix kunnen gebruiken.


• Verder wordt bij Bolin & Meyer voor elk blokje alle samples expliciet bijgehouden. Dat zorgt bij een groot aantal stralen al snel tot een paar Mb aan geheugen. De samples worden bijgouden omdat bij het berekenen van de DCT transformatie een least square fit wordt toegepast op alle samples van het blokje en die moet dus ook telkens opnieuw berekend worden. Ik daarentegen neem de cosinustransformatie van de pixelwaarden. Dat heeft als voordeel dat de samples niet meer hoeven bijgehouden te worden en dat er geen matrices hoeven bijgehouden te worden. Het nadeel is dat samples niet exact worden gebruikt omdat ze reeds samengevoegd zijn in een pixel.

Een aantal resultaten: (Boven zien we telkens het prentje en onder de verdeling van het aantal samples)

Bij een diffuus beeldje en een puntlichtbron krijgen we een goed resultaat:

Vorderingen implementatie

Na de presentatie van vorige week (de slides zijn hier te vinden) ben ik verder gegaan met de implementatie van mijn ray tracer.
Ik heb nog verschillende problemen met de representatie in het frequentie domein. Het beeld wordt opgedeeld in blokken van 8x8 pixels en wordt voorgesteld in het frequentie domein adhv 64 cosinus termen. Wanneer er te weinig samples in een blok genomen worden draait het algoritme in de soep wanneer de cosinus termen geëvalueerd worden. In de paper wordt voorgesteld om het aantal cosinus termen te verhogen telkens er 2 à 3 samples bijkomen. Ik heb die extra moeilijkheid omzeild door geen omzetting te doen naar het frequentie domein voordat ik 128 samples heb genomen per 8x8 blok. Wat betekent dat er genoeg informatie is om het blokje adhv 64 cosinus termen voor te stellen. Dit komt overeen met 2 samples per pixel en heeft als voordeel dat er geen blokken zullen zijn die te weinig samples krijgen.
Doordat ik een vast sample patroon per blok gebruik kan ik de matrices die nodig zijn om de transformatie naar het frequentie domein uit te voeren, voor elk blok hergebruiken. Voorlopig bereken ik 1000 matrices in een pre-processing stap. Dit heeft als nadeel dat er maximaal 1128 samples per 8x8 pixels kunnen genomen worden maar wat een groter nadeel is het geheugen gebruik: 1000*64*64 = 4 096 000 doubles die in het geheugen moeten worden opgeslagen enkel voor de transformatie naar frequentiedomein.

Waarom adaptieve raytracing?

Klassieke raytracing, zoals het typisch in een cursus Computer Graphics wordt aangeleerd:


Gebruiker Hendrik van Wikipedia.

Een straal vertrekt van de Camera en gaat door een pixel van het beeld (Image) tot het op een object terecht komt. Vanaf dat punt worden dan één of meerdere schaduw stralen (shadow ray) geschoten naar de lichtbron(nen).


Het probleem met dergelijke techniek is dat we veel stralen per pixel moeten gaan schieten om ruis en aliasing problemen te verwijderen.


De beeldjes zijn gegenereerd met pbrt:
Beeldje 1: 1 straal per pixel: 7,8 Seconden, 131.000 stralen.
Beeldje 2: 4 stralen per pixel: 32 Seconden, 532.000 stralen.
Referentie: 128 stralen per pixel: 1003 Seconden, 17.000.000 stralen


We willen het aantal stralen zo laag mogelijk houden. Op positie 1 zien dat we al een goede benadering hebben voor de eigenlijke kleur. Hier meer stralen naar schieten heeft niet veel zin omdat extra stralen weinig bijdragen tot een verbetering van het kleur op die pixel. Op positie 2 daarentegen is duidelijk nog heel veel ruis te zien. Adaptief bemonsteren bestaat er nu in posities zoals 2 te detecteren en daar meer samples te nemen.

Literatuurstudie

De voorbije twee weken heb ik een aantal papers gelezen en een groot stuk van het pbrt-handboek. Een lijst met papers die ik gelezen heb met daarbij een korte beschrijving is hier te vinden.

Ik heb ook definitief beslist om mijn thesis in C++ te programmeren en om pbrt als basis te gebruiken.

Ik ga mij deze week nog verder verdiepen in het samplen in het frequentie domein. Ik moet ook eens uitzoeken of het wel mogelijk is om een module te schrijven daarvoor in pbrt.

Inleidende Sessie C++

De inleidende sessie was best wel leerrijk. De algemene trend was, hoewel de meeste code werkte, er toch behoorlijk wat fouten gemaakt werden. De ene fout al erger dan de andere. We krijgen de modeloplossing van het werkje en kunnen dit gebruiken als template voor onze (thesis)klassen.

Eerste meeting met Peter

Ik heb van Peter een lijst met een aantal meer basic papers en een aantal meer aanvullende papers gekregen. De meeste van die papers heb ik gevonden. Een aantal vind ik enkel op de ACM website maar deze zal ik maandag dan in de pcklas gaan downloaden. Ik zal voor elk paper een samenvatting van een paar lijnen maken.

Verder hebben we een aantal praktische zaken afgehandeld (die ook grotendeels aan bod zijn gekomen in de inleidende sessie van prof Dutré).

Een aantal voorbereidingswerkzaamheden.

Vandaag heb ik een aantal voorbereidingen getroffen:

Omdat een referentielijst één van de belangrijkste elementen is voor een wetenschappelijk geschrift zal ik proberen consequent een lijst bij te houden van gebruikte boeken, papers, websites en tools. De lijst is hier te vinden.

Omdat ik niet één van die studenten wil zijn die in mei door een harddisk crash of dergelijke alles verliest heb ik een svn repository aangemaakt. Het is ook altijd handig om vorige versies te kunnen aanspreken. De toestand van de code, verslagen, ... en alle vorige versies is te vinden op mijn thesis SVN.

In de loop van volgende week zal ik hier een samenvatting zetten van de 2 papers.

Een maand verder

We zijn nu weeral een maand verder. Veel is er niet veranderd maar ik ben het boek over c++ aan het lezen (50%) en ben mij aan het inwerken in pbrt. Ik heb het programma aan de praat gekregen. Een handige hulp daarbij was hier te vinden.

Vergadering van 07/07/2008 16:00: Overlopen van hoe en wat er allemaal verwacht wordt. Ik moet beginnen met het kiezen van een onderwerp daarvoor heb ik van Ares 2 papers gekregen om van te beginnen. (Multidimensional Adaptive Sampling and Reconstruction for Ray Tracing en A Perceptually Based Adaptive Sampling Algorithm).
Verder moet ik mijn kennis van C++ een beetje bijschaven mbv Accelerated C++: Practical Programming by Example. Maar dus eerst een kopie van het boek zien te bemachtigen. Andere nuttige info bij karl meerbergen
Om geen onnodig werk te doen en onder het motto "Buy the best, Build the rest" zou ik best starten van een bestaande RT, bv: pbrt.
Ten slotte zijn er nog een waslijst warnings:

• Begin tijdig
• Verzorg zelf de communicatie
• Richtlijn is 900 werkuren (+/- 40 uur per week als de vakanties en blok/examens geschrapt worden)
• 1000$ Tip: maak een kalender

Edit: Het handboek "Accelerated C++: Practical Programming by Example" is hier te downloaden.