Лучший алгоритм эффективного обнаружения столкновений между объектами

Я в замешательстве. Не путайте, так как не хотите делать 6 тестовых программ, чтобы увидеть, какой алгоритм является лучшим. Поэтому я подумал, что попрошу моих экспертов-друзей здесь, в SO, чтобы дать мне преимущество от их опыта.

Сценарий представляет собой трехмерную сцену с потенциально довольно большой площадью по сравнению с размерами объектов внутри нее. На сцене есть потенциально тысячи объектов. Объекты варьируются от 10 до 10 единиц, но не больше (или меньше). Объекты, как правило, группируются вместе, но эти кластеры могут потенциально появляться в любом месте сцены. Все объекты динамичны и движутся. Кластеры, как правило, движутся вместе, но когда они делают, их скорости могут быть не одинаковыми все время. Там также рассмотрена статическая геометрия. Хотя существует большое количество динамических объектов, в сцене также есть некоторые статические объекты (статические объекты имеют тенденцию быть на один или два порядка больше, чем динамические объекты).

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

Итак, в моих исследованиях я могу использовать один из:

(1) Octree (2) Loose Octree (3) Линейный Octree (+ свободный) (4) Дерево KD (5) Дерево BSP (6) Хеширование

До сих пор (6) - единственный, который я пробовал. Это на самом деле абсолютно превосходно с точки зрения скорости (8192 столкновений элементов проверено под 1 мс в моей системе), если объекты в сцене в среднем равномерно распределены. Это не такой хороший алгоритм, если все объекты попадают в меньшую область, что, я полагаю, возможно.

Есть ли у кого-нибудь представление о том, какой из них использовать, или какие-нибудь трюки, которые я могу использовать для ускорения? Я думаю, что, что бы ни случилось, я могу просто использовать отдельное дерево BSP для статической геометрии. Я полагаю, что здесь наиболее важны динамические "сферы". Примечание: нет CUDA, это только процессор: p.

Спасибо

EDIT: Хорошо, благодаря Флорису, я нашел дополнительную информацию о деревьях AABB. Здесь есть старая дискуссия о GameDev: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Похож на хороший компромисс.

Final EDIT: решил не изобретать велосипед. Возможно, библиотека физики пули сделает все это для меня (в ней есть дерево AABB, возможно, очень хорошо оптимизировано).

Ответ 1

Отличный вопрос.

У вас в основном сложный компромисс между:

Скорость полной фазы обнаружения столкновений
Накладные расходы на обновление/поддержание структуры данных по мере перемещения объектов

Плохая новость в том, что из-за этого нет "идеального" ответа - он будет действительно зависеть от множества разных факторов, уникальных для вашей ситуации. BSP, например, быстро растут для 1. когда они предварительно вычисляются с большой статической плоской геометрией, что объясняет, почему они были настолько распространены в ранних играх FPS.

Моя личная догадка заключается в том, что в вашем случае, вероятно, будет лучше работать свободное дерево AABB (Axis Aligned Bounding Box) с разумным количеством объектов (5-10?) в каждом ограничительном блоке нижнего уровня. Причины:

У вас довольно большое/разреженное пространство с кластерами объектов. Деревья AABB, как правило, хороши для этого, так как вы можете вырезать множество уровней, которые вам в противном случае нужны.
Вы принимаете совершенные сферы. Сферические испытания на сферу очень дешевы, поэтому вы можете легко сделать 10-45 тестов для каждого нижнего уровня - node. В основном N ^ 2 отлично подходит для малых значений N: -)
Выравнивание оси делает обновление дерева намного проще, а тесты пересечения намного дешевле большинства альтернатив. Поскольку вы предполагаете грубо сферические объекты, я не думаю, что вы выиграете от ориентированных ограничивающих прямоугольников (что только реально дает вам преимущество, если у вас много длинной/тонкой фигур при смежных углах).
Предоставляя ограничивающие поля свободным и содержащим разумное количество объектов, вы уменьшаете вероятность того, что движение любого отдельного объекта выведет его за пределы AABB. Если это не произойдет, вам не нужно обновлять дерево. Это сэкономит вам много времени на обновление дерева. Когда это произойдет, расширьте границу с небольшим отрывом, чтобы вам не пришлось снова повторно расширять следующий кадр - помните, что большинство движений имеет тенденцию к продолжению в одном направлении для нескольких кадров!

Извините за слегка пушистый ответ, но я надеюсь, что это даст вам некоторые полезные идеи/вещи, которые нужно учитывать!

Ответ 1

Ответ 2