Я ищу хороший алгоритм пересечения лучей-octree, который дает мне листы, через которые проходит луч в итерационный способ. Я планирую реализовать его на ЦП, так как пока не хочу погружаться в CUDA:)
На данный момент мой Voxel raycaster просто выполняет 3D DDA (версию Amanatides/Woo)на не-иерархический массив XxYxZ вокселей. Вы можете себе представить, что это довольно дорого, когда много свободного места, как показано на следующем рисунке (ярче красный = больше работы:)):
Я уже понял, что для этой задачи есть два типа алгоритмов:снизу-вверх , который работает от листа обратно вверх, и сверху-вниз , что в основном является глубинным-первым поиском.
Я уже нашел алгоритм Ревеллеса 2000 года, названныйЭффективный параметрический алгоритм обхода октодерева , который выглядит интересно, но довольно стар. Это алгоритм сверху-вниз.
Наиболее популярным подходом снизу-вверх, по-видимому, является К. Сунг, Алгоритм обхода октодерева DDA для трассировки лучей, Eurographics'91, North Holland-Elsevier, ISBN 0444 89096 3, p. 73-85. Проблема в том, что большинство алгоритмов обхода октодерева DDA предполагают, что октодерево будет иметь одинаковую глубину, а я не хочу, чтобы -пустые поддеревья были просто нулевым указателем или чем-то подобным.
В более поздней литературе о разреженных воксельных октодеревьях, которую мне удалось прочитать, (в первую очередь работа Лайна по SVO , все они, кажется, основаны на каком-то графическом процессоре-реализована версия DDA (Amanatides/Woo style).
Теперь, вот мой вопрос:есть ли у кого-нибудь опыт реализации базового,без-излишеств луча-алгоритм пересечения октодерева? Чтобы вы посоветовали?