Хорошая структура ускорения для лучевых испытаний с движущимися сферами

Question

Я ищу подходящую структуру ускорения для проведения тестов пересечения лучевой сферы (в игре). применяются следующие условия:

- около 100 сфер и 100 лучей для сравнения друг с другом на кадр

- сферы движутся в каждом кадре, как и лучи

- в каждом кадре могут быть добавлены / удалены лучи / сферы (но большинство из них будут одинаковыми между двумя кадрами, только слегка сдвинуты)

- все в 3D

KD-Tree очень хорошо подходит для тестов пересечения лучей, но поскольку сферы движутся, мне придется перестраивать KD-Tree в каждом кадре, что обходится дорого

Октавное дерево проще в обслуживании, но очень неэффективно для испытаний на пересечение лучей.

100 лучей против 100 сфер, кажется, не много, но я кодирую на очень низких ресурсах, поэтому я ищу некоторое ускорение для этого

Кто-нибудь может дать мне несколько советов по этому поводу?

Answer 1

100x100 = 10k, оптимизированная грубая сила не кажется несогласованной, особенно в том, что тест пересечения луча / сферы включает только сложение / умножение. Вы всегда можете предварительно вычислить весь нормализованный вектор луча перед основным циклом.

Если вы предполагаете, что вы живете в ограниченной вселенной, а пространственная плотность сфер и лучей относительно однородна, вы можете использовать фиксированную пространственную сетку (фиксированное октавное дерево) - что-то вроде сетки ячеек 16x16x16 или ещё - и:

• предварительно вычислять для каждой сферы, пересекающей ячейки (легко вычислить, использовать только несколько сложений и сравнений), хранить в каждой ячейке список пересекающихся сфер,
• для каждого луча в цикле:
  • вычислить список ячеек, которые пересекает луч (метод, основанный на алгоритме Брезенхэма, мог бы добиться цели)
  • выполнить тест пересечения для всех сфер в этом списке ячеек.

Таким образом, вам не нужно хранить какой-либо луч в каком-либо дереве, только сферы. Эффективность этого метода зависит от соотношения размера ячейки / размера сферы, если у вас не слишком много дисперсии по размеру сферы, это может быть хорошим советом.

Если сферы не пересекаются друг с другом, а размер сферы минимален, вы даже можете связать список сфер в списке ячеек (соответствующее число оставлено читателю в качестве упражнения) ...

НТН