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: