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