Het doorlopen van de bvh boom doe je, depth-first (i.t.t. breadth-first). In mensentaal, proberen eerst zo diep mogelijk af te dalen in de boom. De normale manier om zoiets te implementeren is recursief, eenvoudig en intuïtief. Het nadeel is dat er heel veel function call overhead is (er moet een heel grote call stack worden bijgehouden). Om het iteratief te doen kan je zelf een call stack bijhouden of zoals ik doe de knopen in het geheugen steken in de volgorde waarin ze moeten doorlopen worden. Nu heb je een lijst die je iteratief kan doorlopen. Omdat ik mijn scanner werkende heb gekregen onder Linux heb ik een schets bijgevoegd (best even vergroten voor de duidelijkheid).
Op deze manier doen we echter nog altijd teveel werk. Als bijvoorbeeld de boundingbox van knoop B wordt gemist heeft het geen zin om D en E nog te bezoeken. Daarom houden we per knoop een "skip pointer" bij die aangeeft naar welke knoop we moeten springen als de knoop gemist wordt. Dus bijvoorbeeld de skip pointer van B wijst naar C, dus als we B missen slaan we D en E over en springen we naar C.
Hoewel het concept simpel is heeft het me toch redelijk veel bloed, zweet en tranen gekost om dat in C++ vertaald te krijgen. Uiteindelijk werkt het dus tijd voor rendertijden!
| figuur | #driehoeken | #seconde |
|---|---|---|
| kegel | 32 | <1 |
| cilinder | 64 | <1 |
| bol | 480 | <1 |
| torus | 1024 | 1 |
| theepot | 4032 | 29 |
| konijntje | 5110 | 38 |
Hoewel het weeral net iets sneller is had ben ik wat teleurgesteld, gezien het veel werk had ik toch meer spectaculaire resultaten verwacht.
Er is nog wel wat ruimte voor verbetering, bijvoorbeeld de knopen zijn nu nog 32 bytes, het zou leuk zijn om dit te reduceren naar 16 bytes. Ook de driehoek-straal intersectie is wat aan de trage kant, hiervoor heeft Ares me verwezen naar de snellere methode van Möller en Trumbore.
Geen opmerkingen:
Een reactie posten