Хорошая ускоряющая структура для сферы луча тестирует со сферами то перемещение
Я ищу надлежащую ускоряющую структуру, чтобы сделать тесты на пересечение сферы луча (в игре). следующие условия применяются:
- существует приблизительно 100 сфер и 100 лучей для тестирования друг против друга на кадр
- сферы перемещаются в каждый кадр, лучи - также
- могут быть лучи/сферы, добавил/удалил в каждом кадре (но большинство из них будет теми же промежуточными двумя кадрами, просто перемещенными немного),
- целая вещь находится в 3D
KD-дерево очень хорошо для тестов Пересечения лучом, но начиная с перемещения сфер, я должен был бы восстановить KD-дерево в каждом кадре, который является дорогостоящим
дерево октября легче поддержать, но очень неэффективный для тестов пересечения лучом.
100 лучей против 100 сфер, кажется, не очень, но я кодирую на очень низких ресурсах, таким образом, я ищу некоторое ускорение для этого
Кто-либо может дать мне некоторые подсказки на этом?
1 ответ
100x100 = 10k, оптимизированная грубая сила не кажется непоследовательной, особенно в том, что тест пересечения луча / сферы включает только сложение / умножение. Вы всегда можете предварительно вычислить весь нормализованный вектор луча перед основным циклом.
Если вы сделаете предположение, что вы живете в ограниченной вселенной и пространственная плотность сфер и лучей относительно однородна, вы можете использовать фиксированную пространственную сетку (фиксированное октаво-дерево) - что-то вроде сетки 16x16x16 ячеек, или more--, и:
- предварительно вычислить для каждой сферы, пересекающей ячейки (легко вычислить, требуется только несколько сложений и сравнений), сохранить в каждой ячейке список пересекающихся сфер,
- для каждого луча, в цикле: { {1}}
- вычислить список ячеек, пересекаемых лучом (метод, основанный на алгоритме Брезенхэма, может помочь)
- выполнить проверку пересечения для всех сфер в этом списке ячеек.
Таким образом, вам не нужно хранить лучи ни в каком дереве, только сферы. Эффективность этого метода зависит от соотношения размера ячейки / размера сферы, если у вас нет слишком большого разброса по размеру сферы, это может быть хорошим намеком.
Если сферы не пересекаются друг с другом и размер сфер минимален, вы даже можете связать список сфер в списке ячеек (соответствующий номер оставлен в качестве упражнения для читателя ...)
HTH