Konstrukcia kD-stromu (paralelne)

[pcmaster]

Znovu Caute.

Riesim dalsi principialny problem a rad by som o nom podiskutoval

Cital som viacero novsich paperov okolo GPU a kDstromov, no paralelnu konstrukciu riesi len malo z nich, aj to na CPU (Shevtsov, Soupikov, Kapustin, Eurographics 2007) a na GPU len jediny (Zhou, Hou, Wang, Guo, SIGGRAPH Asia 2008).

Problem s GPU konstrukciou je ten, ze je dost neprijemne si pisat memory manager, ktory bude (re)alokovat dane buffery, konkretne najvacsi problem vidim s bufferom pre indexy trojuholnikov v listoch, pretoze ako vsetci vieme, kazdy trojuholnik moze v kDstrome patrit do mnoho listov (na rozdiel od BVH, kde sa trojuholniky nesplituju). Ked chceme novu pamat, musime 'prerusit' kernel, zaalokovat novu pamat a potom pustit kernel znovu, co sa mi zda prilis narocne (mentalne aj programatorsky ).

Ja teda chcem zacat s takym seriovym kDtree konstrukcnym algoritmom, ktory bude pracovat s buffermi konstantnej dlzky. Pri BVH som problem bufferu pre uzly (vnutorne i listy) vyriesil implicitnym stromom (lavy potomok je hned za rodicom, pravy na implicitnom offsete dopocitatelnom z hlbky a maximalnej hlbky), co sa chystam pouzit aj pre kDstromy. Ze taketo stromy produkuju dost "riedke" buffery (kopec miesta sa vobec nevyuzije) ma teraz absolutne netrapi.

Takze, ako by ste navrhli riesit buffer pre indexy na trojuholniky v listoch kDstromu? Chcem to spravit rovnako ako v BVH -- kazdy list bude poznat len offset prveho indexu trojuholnika a pocet trojuholnikov. Indexy samotne su ulozene v jednom spojitom bufferi. Pri BVH nie je problem, ako som spominal, pretoze kazdy index je tam len raz. Pri kDstrome tam moze byt kazdy index mnohokrat a moj prvy napad je vyriesit to tak, ze zaalokujem "dostatocne velky" buffer na indexy a pri konstrukcii sa proste odmietnu take splity, ktore by viedli na prilis velky pocet duplicitnych indexov (cize by sa nezmestili do bufferu). To samozrejme nepovedie k najkvalitnejsim stromom, ale aspon sa mi to vlezie do pripravenej pamati. A bude sa to dat paralelizovat (podla toho paperu z roku 2008). Na traverzaciu pouzijem obycajny stack-based algoritmus.

Chapete ma?
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.