Что такое «поля расстояния» и как они применимы к обнаружению столкновений?

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

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

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

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

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

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

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

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

Какие поля расстояния?

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

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

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

Существуют разные способы расчета расстояния, типичные подходы включают в себя:

• Манхэттенское расстояние (обычно используется при обработке изображений).
• Евклидово расстояние .

Как это применимо в обнаружении столкновений?

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