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