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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

7. Я знаю больше, но не могу думать ни о чем из моей головы. Давно не делал этого.

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

Answer 2

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

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

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

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

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

Answer 5

развертка и обрезка широкой фазы + гйк узкой фазы