Обнаружение столкновений — вычислительная задача обнаружения пересечения двух или более пространственных объектов, обычно объектов компьютерной графики. Она имеет приложения в различных областях вычислений, в первую очередь в компьютерной графике , компьютерных играх , компьютерном моделировании , робототехнике и вычислительной физике . Обнаружение столкновений — классическая задача вычислительной геометрии . Алгоритмы обнаружения столкновений можно разделить на работающие с 2D- или 3D-пространственными объектами. [1]
В физическом моделировании проводятся такие эксперименты, как игра в бильярд . [2] Физика отскакивания бильярдных шаров понимается под зонтиком движения твердого тела и упругих столкновений . [3] Будет дано начальное описание ситуации с очень точным физическим описанием бильярдного стола и шаров, а также начальных положений всех шаров. [4] На основе силы, приложенной к битку, компьютерная программа рассчитает траектории, точное движение и возможные места отдыха всех шаров. Программа для моделирования этой игры будет состоять из нескольких частей, одна из которых будет отвечать за расчет точных ударов между бильярдными шарами. Этот конкретный пример также оказывается плохо обусловленным : поскольку небольшая ошибка в любом расчете вызовет резкие изменения в конечном положении бильярдных шаров.
Видеоигры имеют схожие требования, с некоторыми существенными различиями. В то время как некоторые компьютерные симуляции должны имитировать физику реального мира как можно точнее, компьютерные игры должны имитировать физику реального мира приемлемым образом , в реальном времени и надежно. Компромиссы допускаются, пока полученная симуляция удовлетворяет игроков.
Физические симуляторы различаются по способу реакции на столкновение. Некоторые используют мягкость материала для расчета силы, которая разрешит столкновение в следующих временных шагах, как это происходит в реальности. Это очень загружает процессор для материалов с низкой мягкостью. Некоторые симуляторы оценивают время столкновения с помощью линейной интерполяции , откатывают моделирование и рассчитывают столкновение более абстрактными методами законов сохранения .
Некоторые повторяют линейную интерполяцию ( метод Ньютона ) для вычисления времени столкновения с гораздо большей точностью, чем остальная часть моделирования. Обнаружение столкновений использует временную когерентность, чтобы обеспечить еще более точные временные шаги без значительного увеличения нагрузки на ЦП, например, в управлении воздушным движением .
После неупругого столкновения могут возникнуть особые состояния скольжения и покоя, и, например, Open Dynamics Engine использует ограничения для их моделирования. Ограничения позволяют избежать инерции и, следовательно, нестабильности. Реализация покоя посредством графа сцены позволяет избежать дрейфа.
Другими словами, физические симуляторы обычно функционируют одним из двух способов: когда столкновение обнаруживается апостериори (после того, как произошло столкновение) или априори (до того, как произошло столкновение). В дополнение к различию апостериори и априори , почти все современные алгоритмы обнаружения столкновений разбиты на иерархию алгоритмов. Часто используются термины «дискретный» и «непрерывный», а не апостериори и априори .
В случае апостериори физическое моделирование продвигается на небольшой шаг, затем проверяется, пересекаются ли какие-либо объекты или визуально считаются пересекающимися. На каждом шаге моделирования создается список всех пересекающихся тел, а положения и траектории этих объектов «фиксируются» для учета столкновения. Этот метод называется апостериори, потому что он обычно пропускает фактический момент столкновения и улавливает столкновение только после того, как оно фактически произошло.
В методах априори есть алгоритм обнаружения столкновений, который сможет очень точно предсказать траектории физических тел. Моменты столкновения вычисляются с высокой точностью, и физические тела фактически никогда не проникают друг в друга. Это называется априори , потому что алгоритм обнаружения столкновений вычисляет моменты столкновения до того, как он обновит конфигурацию физических тел.
Основные преимущества апостериорных методов заключаются в следующем. В этом случае алгоритму обнаружения столкновений не нужно знать множество физических переменных; алгоритму подается простой список физических тел, и программа возвращает список пересекающихся тел. Алгоритму обнаружения столкновений не нужно понимать трение, упругие столкновения или, что еще хуже, неупругие столкновения и деформируемые тела. Кроме того, апостериорные алгоритмы на самом деле на одно измерение проще априорных алгоритмов. Априорный алгоритм должен иметь дело с переменной времени, которая отсутствует в апостериорной задаче.
С другой стороны, апостериорные алгоритмы вызывают проблемы на этапе «фиксации», где пересечения (которые физически некорректны) должны быть исправлены. Более того, если дискретный шаг слишком большой, столкновение может остаться незамеченным, что приведет к тому, что объект пройдет сквозь другой, если он достаточно быстрый или маленький.
Преимущества априорных алгоритмов — повышенная точность и стабильность. Трудно (но не невозможно) отделить физическую симуляцию от алгоритма обнаружения столкновений. Однако во всех случаях, кроме самых простых, задача предварительного определения момента столкновения двух тел (при наличии некоторых начальных данных) не имеет решения в замкнутой форме — обычно используется числовой поиск корней .
Некоторые объекты находятся в состоянии покоя , то есть в столкновении, но не отскакивают друг от друга и не взаимопроникают друг в друга, например, ваза, стоящая на столе. Во всех случаях состояние покоя требует особого подхода: если два объекта сталкиваются ( апостериори ) или скользят ( априори ), а их относительное движение ниже порогового значения, трение становится сцеплением , и оба объекта располагаются в одной ветви графа сцены .
Очевидные подходы к обнаружению столкновений для нескольких объектов очень медленные. Проверка каждого объекта по каждому другому объекту , конечно, будет работать, но слишком неэффективна, чтобы использовать ее, когда количество объектов вообще велико. Проверка объектов со сложной геометрией друг по другу очевидным способом, путем проверки каждой грани по каждой другой грани, сама по себе довольно медленная. Таким образом, были применены значительные исследования для ускорения проблемы.
Во многих приложениях конфигурация физических тел от одного временного шага к другому меняется очень мало. Многие объекты могут вообще не двигаться. Алгоритмы были разработаны таким образом, чтобы вычисления, выполненные на предыдущем временном шаге, можно было повторно использовать на текущем временном шаге, что приводит к более быстрому завершению вычисления.
На грубом уровне обнаружения столкновений цель состоит в том, чтобы найти пары объектов, которые потенциально могут пересекаться. Эти пары потребуют дальнейшего анализа. Ранний высокопроизводительный алгоритм для этого был разработан Мин С. Линем в Калифорнийском университете в Беркли [1], который предложил использовать выровненные по осям ограничивающие рамки для всех n тел в сцене.
Каждый ящик представлен произведением трех интервалов (т. е. ящик будет ). Обычный алгоритм обнаружения столкновений ограничивающих ящиков — это развертка и обрезка . Заметьте, что два таких ящика и пересекаются тогда и только тогда, когда , пересекается , пересекается и пересекается . Предполагается, что от одного временного шага к другому, если и пересекаются, то весьма вероятно, что на следующем временном шаге они все еще будут пересекаться. Аналогично, если они не пересекались на предыдущем временном шаге, то весьма вероятно, что они и дальше не будут пересекаться.
Таким образом, мы сводим задачу к отслеживанию, от кадра к кадру, какие интервалы пересекаются. У нас есть три списка интервалов (по одному для каждой оси), и все списки имеют одинаковую длину (поскольку длина каждого списка равна числу ограничивающих прямоугольников). В каждом списке каждый интервал может пересекать все другие интервалы в списке. Таким образом, для каждого списка у нас будет матрица нулей и единиц: равна 1, если интервалы и пересекаются, и 0, если они не пересекаются.
По нашему предположению, матрица, связанная со списком интервалов, останется по существу неизменной от одного временного шага к другому. Чтобы воспользоваться этим, список интервалов фактически поддерживается как список помеченных конечных точек. Каждый элемент списка имеет координату конечной точки интервала, а также уникальное целое число, идентифицирующее этот интервал. Затем мы сортируем список по координатам и обновляем матрицу по мере продвижения. Не так уж и сложно поверить, что этот алгоритм будет работать относительно быстро, если действительно конфигурация ограничивающих рамок не будет существенно меняться от одного временного шага к другому.
В случае деформируемых тел, таких как моделирование ткани, может оказаться невозможным использовать более конкретный алгоритм попарного отсечения, как обсуждается ниже, и лучшим вариантом будет алгоритм отсечения n тел.
Если можно установить верхнюю границу скорости физических тел в сцене, то пары объектов можно отсечь на основе их начального расстояния и размера временного шага.
После того, как мы выбрали пару физических тел для дальнейшего исследования, нам нужно более тщательно проверить столкновения. Однако во многих приложениях отдельные объекты (если они не слишком деформируемы) описываются набором более мелких примитивов, в основном треугольников. Итак, теперь у нас есть два набора треугольников, и (для простоты мы предположим, что каждый набор имеет одинаковое количество треугольников.)
Очевидным решением будет проверка всех треугольников против всех треугольников на предмет столкновений, но это подразумевает сравнения, что крайне неэффективно. Если возможно, желательно использовать алгоритм обрезки, чтобы сократить количество пар треугольников, которые нам нужно проверить.
Наиболее широко используемое семейство алгоритмов известно как метод иерархических ограничивающих объемов . В качестве шага предварительной обработки для каждого объекта (в нашем примере и ) мы вычислим иерархию ограничивающих объемов . Затем, на каждом временном шаге, когда нам нужно проверить наличие столкновений между и , иерархические ограничивающие объемы используются для сокращения количества пар рассматриваемых треугольников. Для простоты мы приведем пример с использованием ограничивающих сфер, хотя было отмечено, что сферы нежелательны во многих случаях. [ необходима цитата ]
Если — набор треугольников, мы можем предварительно вычислить ограничивающую сферу . Существует много способов выбора , мы только предполагаем, что — сфера, которая полностью содержит и является как можно меньшей.
Заранее мы можем вычислить и . Очевидно, что если эти две сферы не пересекаются (и это очень легко проверить), то не пересекаются и . Однако это не намного лучше, чем алгоритм обрезки n тел.
Если — это набор треугольников, то мы можем разделить его на две половины и . Мы можем сделать это с и , и мы можем вычислить (заранее) ограничивающие сферы и . Надежда здесь в том, что эти ограничивающие сферы намного меньше, чем и . И, если, например, и не пересекаются, то нет смысла проверять любой треугольник в против любого треугольника в .
В качестве предварительного вычисления мы можем взять каждое физическое тело (представленное набором треугольников) и рекурсивно разложить его в бинарное дерево , где каждый узел представляет набор треугольников, а его два дочерних узла представляют и . В каждом узле дерева мы можем предварительно вычислить ограничивающую сферу .
Когда приходит время проверить пару объектов на столкновение, можно использовать дерево их ограничивающих сфер для исключения множества пар треугольников.
Многие варианты алгоритмов получаются путем выбора чего-либо, отличного от сферы, для . Если выбрать ограничивающие рамки, выровненные по осям , то получатся AABBTrees. Ориентированные ограничивающие рамки называются OBBTrees. Некоторые деревья легче обновлять, если изменяется базовый объект. Некоторые деревья могут вмещать примитивы более высокого порядка, такие как сплайны, вместо простых треугольников.
После завершения обрезки у нас останется несколько пар кандидатов для проверки на предмет точного обнаружения столкновений.
Основное наблюдение заключается в том, что для любых двух выпуклых объектов, которые не пересекаются, можно найти плоскость в пространстве так, что один объект полностью лежит по одну сторону этой плоскости, а другой объект лежит по противоположную сторону этой плоскости. Это позволяет разрабатывать очень быстрые алгоритмы обнаружения столкновений для выпуклых объектов.
Ранние работы в этой области включали методы « разделяющей плоскости ». Два треугольника сталкиваются по существу только тогда, когда их нельзя разделить плоскостью, проходящей через три вершины. То есть, если треугольники являются и где каждый является вектором в , то мы можем взять три вершины, , найти плоскость, проходящую через все три вершины, и проверить, является ли она разделяющей плоскостью. Если любая такая плоскость является разделяющей плоскостью, то треугольники считаются непересекающимися. С другой стороны, если ни одна из этих плоскостей не является разделяющей плоскостью, то треугольники считаются пересекающимися. Существует двадцать таких плоскостей.
Если треугольники копланарны, этот тест не совсем успешен. Можно добавить несколько дополнительных плоскостей, например, плоскости, которые нормальны к ребрам треугольника, чтобы полностью решить проблему. В других случаях объекты, которые встречаются на плоской грани, обязательно должны также встречаться под углом в другом месте, поэтому общее обнаружение столкновений сможет найти столкновение.
С тех пор были разработаны лучшие методы. Доступны очень быстрые алгоритмы для поиска ближайших точек на поверхности двух выпуклых многогранных объектов. Ранняя работа Минг С. Лин [5] использовала вариацию симплексного алгоритма из линейного программирования . Алгоритм расстояния Гилберта-Джонсона-Кирти заменил этот подход. Эти алгоритмы приближаются к постоянному времени при многократном применении к парам неподвижных или медленно движущихся объектов, когда используются начальные точки из предыдущей проверки столкновения.
Конечным результатом всей этой алгоритмической работы является то, что обнаружение столкновений может эффективно осуществляться для тысяч движущихся объектов в режиме реального времени на обычных персональных компьютерах и игровых консолях.
Если большинство задействованных объектов фиксированы, что типично для видеоигр, для ускорения выполнения можно использовать априорные методы, использующие предварительные вычисления.
Здесь также желательно отсечение, как n -теловое, так и попарное, но алгоритмы должны учитывать время и типы движений, используемых в базовой физической системе.
Когда дело доходит до точного обнаружения парных столкновений, это сильно зависит от траектории, и для вычисления момента столкновения приходится использовать численный алгоритм поиска корня .
В качестве примера рассмотрим два треугольника, движущиеся во времени и . В любой момент времени два треугольника можно проверить на пересечение, используя двадцать плоскостей, упомянутых ранее. Однако мы можем сделать лучше, поскольку все эти двадцать плоскостей можно отслеживать во времени. Если плоскость проходит через точки в , то есть двадцать плоскостей для отслеживания. Каждую плоскость необходимо отслеживать по трем вершинам, это дает шестьдесят значений для отслеживания. Использование поиска корней на этих шестидесяти функциях дает точное время столкновения для двух заданных треугольников и двух заданных траекторий. Здесь мы отмечаем, что если траектории вершин предполагаются линейными многочленами в , то окончательные шестьдесят функций на самом деле являются кубическими многочленами, и в этом исключительном случае можно найти точное время столкновения, используя формулу для кубических корней. Некоторые численные аналитики предполагают, что использование формулы для кубических корней не так численно устойчиво, как использование поиска корней для многочленов. [ необходима цитата ]
Альтернативные алгоритмы сгруппированы под зонтиком пространственного разбиения , который включает октодеревья , двоичное разбиение пространства (или деревья BSP) и другие подобные подходы. Если разбить пространство на несколько простых ячеек, и если можно показать, что два объекта не находятся в одной ячейке, то их не нужно проверять на пересечение. Поскольку деревья BSP можно предварительно вычислить, этот подход хорошо подходит для обработки стен и неподвижных препятствий в играх. Эти алгоритмы, как правило, старше алгоритмов, описанных выше.
Для ускорения расчета обнаружения столкновений можно использовать ограничивающие объемы . Ограничивающий объем — это форма, которая охватывает интересующий объект, но для которой проще вычислять столкновения.
Ограничивающие боксы Axis-Align (AABB) и кубоиды популярны из-за своей простоты. [6] Ограничивающий бокс в видеоигре иногда называют Hitbox. Другие ограничивающие объемы, обычно используемые для обнаружения столкновений, включают Convex hull и Oriented Bounding Boxes (OBB) .
Ограничивающие объемы обычно используются на ранней (отсеченной) стадии обнаружения столкновений, так что необходимо подробно сравнивать только объекты с перекрывающимися ограничивающими объемами. [7] Вычисление столкновений или перекрытий между ограничивающими объемами требует дополнительных вычислений, поэтому для того, чтобы это принесло пользу, нам нужно, чтобы ограничивающий объем был относительно узким, а накладные расходы на вычисления, связанные со столкновениями, были низкими.
Когда пространство объектов, для которых мы вычисляем столкновение, является сложным, один ограничивающий объем может не обеспечить достаточно точного приближения, чтобы значительно сократить количество точных обнаружений столкновений, которые нам нужно выполнить. В таких случаях можно использовать иерархию ограничивающих объемов (BVH). BVH представляет собой древовидную структуру над набором ограничивающих объемов. BVH можно использовать с деформируемыми объектами, такими как ткань или мягкие тела, но иерархия объемов должна корректироваться по мере деформации формы. Для деформируемых объектов нам нужно беспокоиться о самостолкновениях или самопересечениях. BVH можно использовать и для этой цели. Столкновение между двумя объектами вычисляется путем вычисления пересечения между ограничивающими объемами корня дерева, поскольку есть столкновения, которые мы углубляемся в поддеревья, которые пересекаются. Точные столкновения между фактическими объектами или их частями (часто треугольниками треугольной сетки ) необходимо вычислять только между пересекающимися листьями [8] . Тот же подход работает для парных столкновений и самостолкновений.
Объект треугольной сетки обычно используется в моделировании 3D-тел. Обычно функция столкновения — это пересечение треугольника с треугольником или ограничивающая форма, связанная с сеткой. Центроид треугольника — это расположение центра масс, такое, что он будет балансировать на кончике карандаша. Для моделирования нужно только добавить измерение центроида к физическим параметрам. Учитывая точки центроида как в объекте, так и в цели, можно определить отрезок линии, соединяющий эти две точки.
Радиус-вектор центроида треугольника является средним арифметическим радиус-векторов его вершин. Таким образом, если его вершины имеют декартовы координаты , то центроид равен .
Вот функция для расстояния отрезка прямой между двумя трехмерными точками.
Здесь длина/расстояние сегмента — это регулируемый размер критерия «попадания» сегмента. По мере приближения объектов длина уменьшается до порогового значения. Эффективным геометрическим тестом становится треугольная сфера. Сфера с центром в центроиде может быть рассчитана на охват всех вершин треугольника.
Видеоигры должны делить свое очень ограниченное время вычислений между несколькими задачами. Несмотря на это ограничение ресурсов и использование относительно примитивных алгоритмов обнаружения столкновений, программисты смогли создать правдоподобные, хотя и неточные, системы для использования в играх. [ необходима цитата ]
Долгое время видеоигры имели очень ограниченное количество объектов для обработки, и поэтому проверка всех пар не была проблемой. В двумерных играх в некоторых случаях оборудование было способно эффективно обнаруживать и сообщать о перекрывающихся пикселях между спрайтами на экране. [9] В других случаях простое разбиение экрана на плитки и привязка каждого спрайта к перекрывающимся плиткам обеспечивает достаточную обрезку, а для парных проверок используются ограничивающие прямоугольники или круги, называемые хитбоксами , и считаются достаточно точными.
Трехмерные игры использовали пространственные методы разбиения для обрезки тел и долгое время использовали одну или несколько сфер на реальный 3D-объект для парных проверок. Точные проверки очень редки, за исключением игр, пытающихся близко имитировать реальность. Даже тогда точные проверки не обязательно используются во всех случаях.
Поскольку играм не нужно имитировать настоящую физику, устойчивость не является такой уж большой проблемой. Почти все игры используют апостериорное обнаружение столкновений, и столкновения часто разрешаются с помощью очень простых правил. Например, если персонаж оказывается врезанным в стену, его можно просто переместить обратно в его последнее известное хорошее местоположение. Некоторые игры вычисляют расстояние, на которое персонаж может переместиться до того, как он врезан в стену, и позволяют ему перемещаться только на это расстояние.
Во многих случаях для видеоигр аппроксимация персонажей точкой достаточна для обнаружения столкновений с окружающей средой. В этом случае двоичные деревья разбиения пространства предоставляют жизнеспособный, эффективный и простой алгоритм для проверки того, встроена ли точка в пейзаж или нет. Такая структура данных также может использоваться для изящной обработки ситуации «покоя», когда персонаж бежит по земле. Столкновения между персонажами и столкновения со снарядами и опасностями рассматриваются отдельно.
Надежный симулятор — это тот, который будет реагировать на любой ввод разумным образом. Например, если мы представим себе видеоигру о гоночных автомобилях на высокой скорости , от одного шага симуляции к другому, можно предположить, что автомобили будут продвигаться на значительное расстояние по гоночной трассе. Если на трассе есть неглубокое препятствие (например, кирпичная стена), не совсем маловероятно, что автомобиль полностью перепрыгнет через него, и это очень нежелательно. В других случаях «исправление», которого требуют апостериорные алгоритмы, реализовано неправильно, что приводит к ошибкам , которые могут застревать персонажей в стенах или позволять им проходить сквозь них и падать в бесконечную пустоту, где может быть или не быть смертельная бездонная яма , иногда называемая «черным адом», «синим адом» или «зеленым адом» в зависимости от преобладающего цвета. Это отличительные признаки неисправной системы обнаружения столкновений и физического моделирования. Big Rigs: Over the Road Racing — печально известный пример игры с неисправной или, возможно, отсутствующей системой обнаружения столкновений.
Хитбокс — это невидимая форма, обычно используемая в видеоиграх для обнаружения столкновений в реальном времени; это тип ограничивающего прямоугольника. Часто это прямоугольник (в 2D-играх) или кубоид (в 3D), который прикреплен к точке на видимом объекте (например, модели или спрайте) и следует за ней. Круглые или сфероидальные формы также распространены, хотя их по-прежнему чаще всего называют «коробками». Для анимированных объектов обычно прикрепляют хитбоксы к каждой движущейся части, чтобы обеспечить точность во время движения. [10] [ ненадежный источник? ]
Hitboxes используются для обнаружения "односторонних" столкновений, таких как удар кулаком или пуля. Они не подходят для обнаружения столкновений с обратной связью (например, удар о стену) из-за трудностей, с которыми сталкиваются как люди, так и ИИ в управлении постоянно меняющимися местоположениями hitboxes; такие виды столкновений обычно обрабатываются гораздо более простыми ограничивающими рамами, выровненными по осям . Игроки могут использовать термин "hitbox" для обозначения этих типов взаимодействий независимо от этого.
Hurtbox — это hitbox, используемый для обнаружения входящих источников урона. В этом контексте термин hitbox обычно зарезервирован для тех, которые наносят урон. Например, атака может быть нанесена только в том случае, если hitbox вокруг удара атакующего соприкасается с одним из hurtboxes противника на его теле, в то время как столкновение противостоящих hitboxes может привести к тому, что игроки будут обмениваться или отменять удары, а противостоящие hurtboxes не будут взаимодействовать друг с другом. Термин не стандартизирован в отрасли; некоторые игры меняют свои определения hitbox и hurtbox , в то время как другие используют только «hitbox» для обеих сторон.
Кроме того, вы можете использовать системное оборудование для обнаружения столкновений между объектами и заставить свою программу реагировать на такие столкновения.
![{\displaystyle I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/450c59ef778cb75d1ea83e0aed119f8d988cab8c)
