Paper: On fast construction of SAH-based bounding volume hierarchies.

Alweer een paper van Ingo Wald deze keer: "On fast construction of SAH-based bounding volume hierarchies". De paper onderzoekt een methode om bij dynamische scenes voor elk frame de versnellingsstructuur terug op te bouwen.

De methode bouwt rond een verzameling driehoeken T een bounding box en neemt van deze bounding box de langste zijde. Die zijde wordt dan onderverdeeld door K equidistante vlakken. Hierdoor verkrijgen we K+1 bins (emmers) van gelijke breedte. Gegeven deze K bins B1 ... Bk dan zijn er K - 1 manieren om de verzameling driehoeken T hierover te verdelen in 2 partities. Bijvoorbeeld als K = 4 dan kunnen we de driehoeken verdelen in T_left = { B1, B2 } en T_right = { B3, B4 }.

Omdat er K-1 mogelijke partitioneringen (teken maar) zijn moeten we deze allemaal uitproberen. We evalueren vervolgens voor elke mogelijkheid een kostenfunctie (wederom de SAH of Surface Area Heuristic) en weerhouden de partitionering met de laagste kost. Van deze 2 partities nemen we dan de bounding box die we terug recursief gaan opsplitsen.

Normaal als je N driehoeken hebt dan kan je de bounding boxes daarvan op 2^N - 2 mogelijke manieren partitioneren. In dit algoritme proberen we maar K-1 mogelijkheden. Het gevolg hiervan is dat het algoritme veel sneller is dan de standaardmanier (alle 2^N-2 mogelijkheden beschouwen). Er is ook een keerzijde aan de medaille, omdat we slechts K-1 mogelijkheden beschouwen doen we een benadering. Als gevolg hiervan is onze BVH ook slechts een benadering van diegene die we zouden vinden met de standaardmethode. De auteurs verzekeren echter dat het snelheidsverlies bij het renderen slechts een paar procenten is.

Een interessante paper vooral voor de besproken techniek die ik uitendelijk zelf ook eens zal proberen te implementeren. Verder geven de auteurs nog enkele build times (tijd nodig om de structuur op te bouwen) en rendertimes. Allemaal op "general purpose" hardware, namenlijk een 8 core 2.6Ghz Clovertown met 8 keer 2Gb ramgeheugen. De definitie van "general purpose" hardware is toch net iets anders in Utah in vergelijking met Leuven.