Пространственные структуры данных для движущихся объектов?

Question

Мне было интересно, какая лучшая структура данных имеет дело с множеством движущихся объектов (сферы, треугольники, коробки, точки и т. Д.)? Я пытаюсь ответить на два вопроса: обнаружение Nearest Neighbor и Collsion.

Я понимаю, что традиционно структуры данных, такие как деревья R, используются для запросов ближайшего соседа, а Oct/Kd/BSP используются для задач обнаружения столкновений со статическими объектами или с очень небольшим количеством движущихся объектов.

Я просто надеюсь, что есть что-то еще, что лучше.

Я ценю всю помощь.

Answer 1

Ограничивающие сферы, вероятно, помогут вам со многими движущимися объектами; вы вычисляете квадрат радиуса объекта и отслеживаете его из центра. Если квадрат расстояния между центрами двух объектов меньше суммы квадратов радиусов двух объектов, то у вас есть потенциальное столкновение. Все сделано с квадратными расстояниями; нет квадратных корней.

Вы можете отсортировать ближайших соседей по минимальному квадрату расстояния между объектами. Разумеется, обнаружение столкновения может быть сложным, и с объектами, не имеющими сферической формы, Bounding Spheres не обязательно будет получать информацию о столкновениях, но это может сократить ваше дерево объектов, которое вам нужно сравнить для столкновения довольно хорошо.

Вам понадобится, конечно, отслеживать ЦЕНТР вашего объекта; и в идеале вы хотели бы, чтобы каждый объект был жестким, чтобы избежать необходимости пересчитывать размеры ограниченной сферы (хотя перерасчет не является особенно сложным, особенно если вы используете дерево жестких объектов, каждый со своей собственной ограничивающей сферой для объектов, которые являются нежесткими, но они усложняются).

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

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

Конечно, вам необходимо сделать фактическое обнаружение столкновений между вашими несферическими объектов, и это может быть не-t но вы значительно сократили количество возможных сравнений в этот момент.

В принципе, это двухуровневая система; первым является массив областей, в котором вы делаете грубую сортировку на своей сцене. Во-вторых, у вас есть расстояние между регионами; в котором вы собираетесь выполнять базовое обнаружение столкновений и помехи при столкновении на объектах, которые столкнулись.

Вероятно, есть место в этом виде алгоритма для использования деревьев в динамической области, чтобы выровнять размеры вашего региона, чтобы ваш регион не увеличивался слишком быстро с «переполненными» регионами; тем не менее, такая вещь нетривиальна, потому что с объектами разного размера ваш вид по плотности становится ... сложным, мягко говоря.

Answer 2

Одним из интересных методов для обнаружения столкновений является использование аксиально выровненных ограничивающих прямоугольников (AABB), организованных в специальной октетной структуре. Помощь AABB, потому что они делают вычисления грубого столкновения очень быстрыми, потому что вам нужно выполнить только до 6 сравнений.

Есть несколько трюков, которые следуют использовать со структурой октодерева:

1) Площадь ограничивающей которого узлом занимает должен быть вдвое больше, чем это было бы для нормального октодерева (где октодерево разбивает пространство без перекрытия). Поскольку каждый узел должен перекрывать половину области своих соседних узлов. Поскольку AABB может принадлежать только одному узлу, этот дополнительный размер и перекрытие позволяют ему оставаться в одном узле в течение более длительного периода времени.

2) Также в каждом узле - и, возможно, на каждом уровне иерархии - вы сохраняете ссылки на соседние узлы. Это будет включать в себя много дополнительного кода, но это позволит вам перемещать элементы между узлами в момент времени O (1), а не O (2logn).

Если октет занимает слишком много памяти, вы можете изменить его, чтобы использовать разреженную октетную структуру, сохраняя только дерево для частей игрового мира, в котором фактически содержатся объекты. Однако это означало бы, что вам придется выполнять больше вычислений для каждого кадра, когда сущности перемещаются по миру.

Некоторые другие идеи, которые вы можете попробовать вместо октетов, - использовать kd-дерево (я считаю, это правильное имя) или использовать AABB для построения структуры снизу вверх.

Деревья KD (из памяти) разделяют пространство, используя аксиально выровненные плоскости, таким образом, они хорошо подходят для использования с AABB.

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

(Это было некоторое время, так как я сделал этот вид пространственного кодирования для разработки игр.)

Answer 3

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

2. Движущийся объект имеет направление и скорость. Вы можете легко разделить сцену на две части, используя перпендикулярное разделение от направления движения объектов. Любой объект с неправильной стороны этого раздела не нужно проверять. Конечно, компенсируйте скорость другого объекта. Поэтому, если другой объект разумно медленный, вы можете легко вырезать его из дальнейших проверок.

3. Всегда упрощайте любую фигуру, которую вы испытываете, с чем-то вроде рамки с выравниванием по оси. Начальный тест на столкновение

4. Вы можете взять расстояние между вашим объектом и другим движущимся объектом плюс скорости. Если другой движущийся объект движется в одном и том же общем направлении с большей скоростью, вы можете исключить его из проверки.

5. Существует множество других оптимизаций в зависимости от формы объекта. Круги или квадраты или более сложные формы имеют определенную оптимизацию, которую вы можете делать во время перемещения.

6. Предполагая, что некоторые объекты останавливаются или могут перестать двигаться, вы можете отслеживать объекты, которые останавливаются. эти объекты могут быть обработаны как статические объекты, и поэтому проверки выполняются быстрее, и вы можете применить к ним все методы статической оптимизации.

7. Я знаю больше, но не могу думать ни о чем с головы. Не делал этого некоторое время.

Теперь, конечно, это зависит от того, как вы делаете обнаружение столкновения. Вы постепенно увеличиваете положение объекта на основе скорости и проверяете, как будто оно статично. Или вы компенсируете скорость, выдавливая форму и вычисляя начальные точки столкновения. Первый требует небольшого шага для быстро движущегося объекта. Последнее сложнее и дорого, но дает лучшие результаты. Также, если у вас есть вращающиеся объекты, тогда все становится немного сложнее.

Answer 4

развертки и подрезать широкие фазы + GJK узкого этап

Answer 5

RDC может быть полезным, особенно если ваши объекты редкими (не много пересечений).