Как смешивать обычное обнаружение столкновений и обнаружение столкновений на основе дерева квадрантов?

У меня есть quadtree для всех статических объектов столкновения, который отлично работает как для обнаружения столкновений, так и для raycasting.

Однако, поскольку у меня также есть нестатические объекты столкновения, когда я использую raycast, я хотел бы включить их в качестве возможных объектов столкновения для луча.

Каким будет лучший (с точки зрения производительности) способ добиться этого? Мои текущие идеи:

1) клонируйте quadtree, добавьте нестатические объекты, затем используйте их для raycast

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

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

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

Если это имеет значение, я использую Java


java collision-detection quadtree
person Ben Ezard    schedule 11.12.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

В 1) Клонирование дерева квадрантов, вероятно, очень дорого, если у вас более 10 объектов, поэтому я бы не стал этого делать.

2) Почему бы просто не сохранить список нестатических объектов? Просто добавьте все объекты в дерево (я не понимаю, почему разделение является проблемой) и после расчета удалите их из дерева.

В 3) Это довольно дорого, если у вас много нестатических объектов, но, вероятно, самое дешевое решение, если у вас их очень мало.

Еще несколько идей:

4) Создайте второе дерево квадрантов для нестатических объектов и выполните обнаружение столкновений (аналогично 5)). После столкновения просто выбросьте второе дерево.

5) Если разделение узлов действительно проблематично, как насчет использования PH-Tree? Это похоже на дерево квадрантов, но оно ведет себя намного более статично, чем дерево квадрантов (никакая вставка/удаление никогда не изменит более одного узла (кроме создания дополнительного удаления одного пустого узла).

6) В зависимости от того, насколько быстры ваши нестатические объекты, вы можете использовать «дерево движущихся объектов» (просто погуглите, есть несколько специальных структур). Если объекты не слишком быстрые, PH-Tree снова может быть хорошим выбором, у него есть специальный метод перемещения/обновления.

person TilmannZ    schedule 13.12.2016