Лучший алгоритм для эффективного обнаружения столкновений между объектами
Я запутался. Что ж, не смущаюсь, даже если не хочу делать 6 тестовых программ, чтобы увидеть, какой алгоритм лучше. Поэтому я подумал, что попрошу своих друзей-экспертов здесь, в SO, поделиться со мной своим опытом.
Сценарий представляет собой трехмерную сцену с потенциально довольно большой площадью по сравнению с размерами объектов внутри нее. В сцене потенциально есть тысячи объектов. Объекты различаются по размеру от десятых долей единицы до примерно 10 единиц, но не больше (и не меньше). Объекты обычно сгруппированы вместе, но эти кластеры потенциально могут появиться в любом месте сцены. Все объекты динамичные и подвижные. Скопления имеют тенденцию двигаться вместе, но когда они это делают, их скорости могут не всегда быть одинаковыми. Также следует учитывать статическую геометрию. Хотя существует большое количество динамических объектов,в сцене также есть некоторые статические объекты (статические объекты обычно на один или два порядка больше, чем динамические объекты).
Теперь мне нужна пространственная структура данных для эффективного обнаружения столкновений для всех элементов в сцена. Было бы здорово, если бы алгоритм также поддерживал запрос видимости для конвейера рендеринга. Для простоты предположим, что обнаружение столкновений здесь является широкофазным (т.е. все динамические объекты представляют собой просто идеальные сферы).
Итак, в моем исследовании я могу использовать одно из:
(1) Octree (2) Свободное октодерево (3) Линейное октодерево (+ свободное) (4) Дерево КД (5) BSP-дерево (6) Хеширование
Пока (6) - единственный, который я пробовал. Это действительно превосходно с точки зрения скорости (в моей системе зафиксировано 8192 столкновения элементов за 1 мс), если объекты в сцене в среднем распределены равномерно. Это не такой уж хороший алгоритм, если все объекты объединяются в меньшую область, что, я полагаю, возможно.
Есть ли у кого-нибудь представление о том, какой из них использовать, или какие уловки я могу использовать, чтобы ускорить процесс? Я думаю, что бы ни случилось, я могу просто использовать отдельное дерево BSP для статической геометрии. Полагаю, меня больше всего волнуют динамические «сферы». Примечание: нет CUDA, это только CPU: стр.
Спасибо
РЕДАКТИРОВАТЬ: Хорошо, спасибо Флорису, я нашел дополнительную информацию о деревьях AABB. Здесь есть старое обсуждение GameDev: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/ . Похоже на хороший компромисс.
Final EDIT: Решил не изобретать велосипед. Возможно, библиотека физики пули сделает все это за меня (в ней есть дерево AABB, вероятно, тоже очень хорошо оптимизированное).