Szukam dobrego algorytmu przecięcia wiązki promieni-oktorów, który daje mi liście, przez które promień przechodzi w sposób iteracyjny. Planuję zaimplementować go na CPU, ponieważ nie chcę jeszcze nurkować w CUDA :)

W tej chwili mój Raycaster Voxel po prostu wykonuje 3D DDA (wersja Amanatides / Woo) na niehierarchicznej tablicy wokseli XxYxZ. Możesz sobie wyobrazić, że jest to dość kosztowne, gdy jest dużo pustej przestrzeni, jak pokazano na poniższym rysunku (jaśniejsza czerwień = więcej pracy :)):

Dowiedziałem się już, że istnieją dwa rodzaje algorytmów dla tego zadania:oddolny, który działa od liści z powrotem do góry igóra-dół, które jest podstawowym wyszukiwaniem w głębi.

Znalazłem już algorytm Revellesa z 2000 roku, nazwanyWydajny algorytm parametryczny dla przejścia przez ósemkę, który wygląda interesująco, ale jest dość stary. Jest to algorytm odgórny.

Najpopularniejszym podejściem oddolnym wydaje się byćK. Sung, A DDA Octree Traversal Algorithm dla Ray Tracing, Eurographics'91, North Holland-Elsevier, ISBN 0444 89096 3, str. 73-85. Problem polega na tym, że większość algorytmów przemierzania DDA Octree oczekuje, że ósemka ma jednakową głębokość, czego nie chcę - puste poddrzewa powinny być po prostu wskaźnikiem zerowym lub czymś podobnym.

W nowszej literaturze o Sparse Voxel Octrees udało mi się przeczytać (przede wszystkim)Praca Laine'a nad SVO, wszystkie one wydają się być oparte na jakiejś implementowanej przez GPU wersji DDA (styl Amanatides / Woo).

Oto moje pytanie: czy ktoś ma jakieś doświadczenie w implementacji podstawowego, bez zbędnych dodatków algorytmu skrzyżowania z okturnami promieniowymi? Co byś polecił?