Most találtam, de nem hagyhatom szó nélkül.
http://sirkan.iit.bme.hu/dokeos/courses/VIFO4319/work/49428093401b6bvh_raytrace.pdf
A GPU implementáció szempontjából a kd-fa jó választást jelent, miután az utóbbi években a
grafikus hardver számítási kapacitása elérte a hozzá szükséges szintet. A legújabb hardvereket
megel z en ugyanis problémát jelentett, hogy a fa bejárása rekurzív, ezért stacket igényel,
ami a GPU-n nem áll rendelkezésre.
page 14
Egy tévedés lapul meg a szövegben. Ezt írja: a fa bejárása rekurzív, ezért stacket igényel,
Nos nem.
Hogyan lehetséges egy közönséges CG shaderrel rekurzíót írni? A kulcsszó: ugrási cím, mint textúra koordináta.
Generáljunk két textúrát, amiben majd egy pixelen tárolódik a fa ágait jelképező befoglaló doboz min és max értéke, vagyis a két sarka. Egy ilyen doboz ezzel a két vektorral egyértelműen meghatározható.
Járjuk be a CPU-n a fát a hagyományos módszerrel, közben tároljuk le a boxok min és max vektorait lineárisan, vagyis sorba a két textúrába.
A textúra koordinátát növeljük, miután letároltuk a vektorokat, de még mielőtt elágazna a fa. Hogy miért? Mert az elágazásból visszatérve még egy vektort le kell tárolni. Ez az ágat lezáró vektor egy harmadik textúrába kerül, de ugyan arra a textúra koordinátára, mint a doboz vektorai. Ez a harmadik textúra pixel xy/red green/ komponense fogja azt a globális textúra koordinátát tárolni, amit az elágazásból visszatérve kapunk. Ez az adott ág vége a textúrában.
És ennyi a lényeg. Amikor fut a shader, akkor előveszi a befoglaló doboz két vektorát, meghatározza, hogy az adott ray metszi azt, vagy nem, majd ha nem metszi, akkor előveszi az ugrási textúra koodinátát a harmadik textúrából, és onnan folytatja a keresést.
Levágta az ágat, rekúrzíven működik a shader, mindenféle stack -nélkül, tehát ezt nem kell a rekúrzió eléréséhez.
Vannak még részletek, de a lényeg ennyi.
A harmadik textúra z /blue/ értéke tárolhatja azt, hogy egy levélhez ért az ág, és itt már háromszögekkel kell számolni. A háromszögek adatai néhány újabb textúrában tárolódnak, vertexek, az előre kiszámolt élnormálok és a tangens-vektorok a textúrázáshoz.
/ Érdemes újraolvasni, mert többször átírtam. Az első verzió több helyen érthetetlen. Lehet hogy ez is? /