dinsdag 18 november 2008

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 

classroom 

9K 

6.53 

157.5 

office 

34K 

7.42 

98.17 

 

cabin 

219K 

11.29 

210.65 

12 

armadillo 

345K 

1.15 

30.86 

atrium2 

559K 

10.89 

211.72 

12 

conference 

987K 

6.73 

199.95 

10 

cruiser 

3.64M 

16.87 

171.12 

16 

10 

dragon 

7.22M 

0.8 

24.59 

24 



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

Geen opmerkingen: