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

Question

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

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

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

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

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

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

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

Спасибо

РЕДАКТИРОВАТЬ: Хорошо, благодаря Floris, я нашел больше информации о деревьях AABB.Здесь есть старое обсуждение GameDev: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Похоже на хороший компромисс.

Окончательное РЕДАКТИРОВАНИЕ: Решено не изобретать велосипед.Вполне возможно, что библиотека физики пуль сделает все это за меня (в ней есть дерево AABB, вероятно, тоже очень хорошо оптимизированное).

Answer 1

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

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

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

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

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

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

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

Answer 2

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

OOBBTree (Orientated Bounding Box) было бы лучше его контрагентом.