Обнаружение столкновений

Термин в информатике

Обнаружение столкновений — это вычислительная задача обнаружения пересечения двух или более объектов в виртуальном пространстве. Точнее, она занимается вопросами, если , когда и где пересекаются два или более объекта. Обнаружение столкновений — это классическая задача вычислительной геометрии с приложениями в компьютерной графике , физическом моделировании , видеоиграх , робототехнике (включая автономное вождение ) и вычислительной физике . Алгоритмы обнаружения столкновений можно разделить на работающие с 2D- или 3D-пространственными объектами. ^[1]

Обзор

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

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

Точное определение точек контакта на поверхностях обоих объектов также необходимо для вычисления физически точного ответа на столкновение . Сложность этой задачи возрастает с уровнем детализации представлений объектов: чем сложнее модель, тем больше вычислительные затраты. ^[3]

Обнаружение столкновений часто включает динамические объекты, добавляя временное измерение к расчетам расстояния. Вместо того, чтобы просто измерять расстояние между статическими объектами, алгоритмы обнаружения столкновений часто стремятся определить, приведет ли движение объектов к точке времени, когда их расстояние равно нулю — операция, которая добавляет значительные вычислительные издержки. ^{[4] [3]}

При обнаружении столкновений с участием нескольких объектов наивный подход потребовал бы обнаружения столкновений для всех парных комбинаций объектов. По мере увеличения числа объектов число требуемых сравнений быстро растет: для объектов необходимы тесты пересечения с наивным подходом. Этот квадратичный рост делает такой подход вычислительно дорогим по мере увеличения. ^{[4] [5]} ${\displaystyle n}$ ${n(n-1)}/{2}$ ${\displaystyle n}$

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

Обычно используемый подход к ускорению требуемых вычислений заключается в разделении процесса на две фазы: широкую фазу и узкую фазу . ^{[4] [6]} Широкая фаза направлена ​​на ответ на вопрос о том, могут ли объекты столкнуться, используя консервативный, но эффективный подход для исключения пар, которые явно не пересекаются, что позволяет избежать ненужных вычислений.

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

Широкая фаза

Эта фаза направлена ​​на быстрый поиск объектов или частей объектов, для которых мы можем быстро определить, что дальнейшая проверка на столкновение не требуется. Полезным свойством такого алгоритма является то, что он чувствителен к выходным данным . В контексте обнаружения столкновений это означает, что временная сложность обнаружения столкновений пропорциональна количеству объектов, которые находятся близко друг к другу. Ранним примером этого является I-COLLIDE ^[5] , где количество узкофазных проверок на столкновение было где — количество объектов, а — количество объектов в непосредственной близости. Это значительное улучшение по сравнению с квадратичной сложностью наивного подхода. ${\displaystyle O(n+m)}$ ${\displaystyle n}$ ${\displaystyle m}$

Пространственное разбиение

Альтернативные алгоритмы сгруппированы под зонтиком пространственного разбиения , который включает октодеревья (для 3D), квадродеревья (для 2D), двоичное разбиение пространства (или деревья BSP) и другие подобные подходы. Если разбить пространство на несколько простых ячеек, и если два объекта могут быть показаны не в одной ячейке, то их не нужно проверять на пересечение. Поскольку деревья BSP могут быть предварительно вычислены, этот подход хорошо подходит для обработки стен и неподвижных препятствий в играх. Эти алгоритмы, как правило, старше, чем алгоритмы, описанные выше.

Использование временной согласованности

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

На грубом уровне обнаружения столкновений цель состоит в том, чтобы найти пары объектов, которые потенциально могут пересекаться. Эти пары потребуют дальнейшего анализа. Ранний высокопроизводительный алгоритм для этого был разработан Мин С. Линем в Калифорнийском университете в Беркли [1], который предложил использовать выровненные по осям ограничивающие рамки для всех n тел в сцене.

Каждый ящик представлен произведением трех интервалов (т. е. ящик будет ). Обычный алгоритм обнаружения столкновений ограничивающих ящиков — это развертка и обрезка . Заметьте, что два таких ящика и пересекаются тогда и только тогда, когда , пересекается , пересекается и пересекается . Предполагается, что от одного временного шага к другому, если и пересекаются, то весьма вероятно, что на следующем временном шаге они все еще будут пересекаться. Аналогично, если они не пересекались на предыдущем временном шаге, то весьма вероятно, что они и дальше не будут пересекаться. ${\displaystyle I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]}$ ${\displaystyle I_{1}\times I_{2}\times I_{3}}$ ${\displaystyle J_{1}\times J_{2}\times J_{3}}$ ${\displaystyle I_{1}}$ ${\displaystyle J_{1}}$ ${\displaystyle I_{2}}$ ${\displaystyle J_{2}}$ ${\displaystyle I_{3}}$ ${\displaystyle J_{3}}$ ${\displaystyle I_{k}}$ ${\displaystyle J_{k}}$

Таким образом, мы сводим задачу к отслеживанию, от кадра к кадру, какие интервалы пересекаются. У нас есть три списка интервалов (по одному для каждой оси), и все списки имеют одинаковую длину (поскольку длина каждого списка равна числу ограничивающих прямоугольников). В каждом списке каждый интервал может пересекать все другие интервалы в списке. Таким образом, для каждого списка у нас будет матрица нулей и единиц: равна 1, если интервалы и пересекаются, и 0, если они не пересекаются. ${\displaystyle n}$ ${\displaystyle n\times n}$ ${\displaystyle M=(m_{ij})}$ ${\displaystyle m_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

По нашему предположению, матрица, связанная со списком интервалов, останется по существу неизменной от одного временного шага к другому. Чтобы воспользоваться этим, список интервалов фактически поддерживается как список помеченных конечных точек. Каждый элемент списка имеет координату конечной точки интервала, а также уникальное целое число, идентифицирующее этот интервал. Затем мы сортируем список по координатам и обновляем матрицу по мере продвижения. Не так уж и сложно поверить, что этот алгоритм будет работать относительно быстро, если действительно конфигурация ограничивающих рамок не будет существенно меняться от одного временного шага к другому. ${\displaystyle M}$ ${\displaystyle M}$

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

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

Попарная обрезка

После того, как мы выбрали пару физических тел для дальнейшего исследования, нам нужно более тщательно проверить столкновения. Однако во многих приложениях отдельные объекты (если они не слишком деформируемы) описываются набором более мелких примитивов, в основном треугольников. Итак, теперь у нас есть два набора треугольников, и (для простоты мы предположим, что каждый набор имеет одинаковое количество треугольников.) ${\displaystyle S={S_{1},S_{2},\dots ,S_{n}}}$ ${\displaystyle T={T_{1},T_{2},\dots ,T_{n}}}$

Очевидным решением будет проверка всех треугольников против всех треугольников на предмет столкновений, но это подразумевает сравнения, что крайне неэффективно. Если возможно, желательно использовать алгоритм обрезки, чтобы сократить количество пар треугольников, которые нам нужно проверить. ${\displaystyle S_{j}}$ ${\displaystyle T_{k}}$ ${\displaystyle n^{2}}$

Наиболее широко используемое семейство алгоритмов известно как метод иерархических ограничивающих объемов . В качестве шага предварительной обработки для каждого объекта (в нашем примере и ) мы вычислим иерархию ограничивающих объемов . Затем, на каждом временном шаге, когда нам нужно проверить наличие столкновений между и , иерархические ограничивающие объемы используются для сокращения количества пар рассматриваемых треугольников. Для простоты мы приведем пример с использованием ограничивающих сфер, хотя было отмечено, что сферы нежелательны во многих случаях. ^{[ необходима цитата ]} ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$

Если — набор треугольников, мы можем предварительно вычислить ограничивающую сферу . Существует много способов выбора , мы только предполагаем, что — сфера, которая полностью содержит и является как можно меньшей. ${\displaystyle E}$ ${\displaystyle B(E)}$ ${\displaystyle B(E)}$ ${\displaystyle B(E)}$ ${\displaystyle E}$

Заранее мы можем вычислить и . Очевидно, что если эти две сферы не пересекаются (и это очень легко проверить), то не пересекаются и . Однако это не намного лучше, чем алгоритм обрезки n тел. ${\displaystyle B(S)}$ ${\displaystyle B(T)}$ ${\displaystyle S}$ ${\displaystyle T}$

Если — это набор треугольников, то мы можем разделить его на две половины и . Мы можем сделать это с и , и мы можем вычислить (заранее) ограничивающие сферы и . Надежда здесь в том, что эти ограничивающие сферы намного меньше, чем и . И, если, например, и не пересекаются, то нет смысла проверять любой треугольник в против любого треугольника в . ${\displaystyle E={E_{1},E_{2},\dots ,E_{m}}}$ ${\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}}$ ${\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle B(L(S)),B(R(S))}$ ${\displaystyle B(L(T)),B(R(T))}$ ${\displaystyle B(S)}$ ${\displaystyle B(T)}$ ${\displaystyle B(S)}$ ${\displaystyle B(L(T))}$ ${\displaystyle S}$ ${\displaystyle L(T)}$

В качестве предварительного вычисления мы можем взять каждое физическое тело (представленное набором треугольников) и рекурсивно разложить его в бинарное дерево , где каждый узел представляет набор треугольников, а его два дочерних узла представляют и . В каждом узле дерева мы можем предварительно вычислить ограничивающую сферу . ${\displaystyle N}$ ${\displaystyle L(N)}$ ${\displaystyle R(N)}$ ${\displaystyle B(N)}$

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

Многие варианты алгоритмов получаются путем выбора чего-либо, отличного от сферы, для . Если выбрать ограничивающие рамки, выровненные по осям , то получатся AABBTrees. Ориентированные ограничивающие рамки называются OBBTrees. Некоторые деревья легче обновлять, если изменяется базовый объект. Некоторые деревья могут вмещать примитивы более высокого порядка, такие как сплайны, вместо простых треугольников. ${\displaystyle B(T)}$

Иерархия ограничивающего объема

Когда пространство объектов, для которых мы вычисляем столкновение, является сложным, один ограничивающий объем может не обеспечить достаточно точного приближения, чтобы значительно сократить количество точных обнаружений столкновений, которые нам нужно выполнить. В таких случаях можно использовать иерархию ограничивающих объемов (BVH). BVH представляет собой древовидную структуру над набором ограничивающих объемов. BVH можно использовать с деформируемыми объектами, такими как ткань или мягкие тела, но иерархия объемов должна корректироваться по мере деформации формы. Для деформируемых объектов нам нужно беспокоиться о самостолкновениях или самопересечениях. BVH можно использовать и для этой цели. Столкновение между двумя объектами вычисляется путем вычисления пересечения между ограничивающими объемами корня дерева, поскольку есть столкновения, которые мы углубляемся в поддеревья, которые пересекаются. Точные столкновения между фактическими объектами или их частями (часто треугольниками треугольной сетки ) необходимо вычислять только между пересекающимися листьями. ^[7] Тот же подход работает для парных столкновений и самостолкновений.

Узкая фаза

Объекты, которые не могут быть окончательно разделены в широкой фазе, передаются в узкую фазу. В этой фазе рассматриваемые объекты находятся относительно близко друг к другу. Тем не менее, сначала предпринимаются попытки быстро определить, необходимо ли полное пересечение. Этот шаг иногда называют средней фазой. ^[4] После того, как эти тесты пройдены (например, пара объектов может столкнуться), более точные алгоритмы определяют, пересекаются ли эти объекты на самом деле. Если это так, узкая фаза часто вычисляет точное время и место пересечения.

Ограничивающие объемы

Быстрый способ потенциально избежать ненужных дорогостоящих вычислений — проверить, пересекаются ли ограничивающие объемы, охватывающие два объекта. Если нет, нет необходимости проверять фактические объекты. Однако если ограничивающие объемы пересекаются, необходимо выполнить более дорогостоящие вычисления. Для того чтобы тест ограничивающего объема имел ценность, необходимо сбалансировать два свойства: a) стоимость пересечения ограничивающего объема должна быть низкой и b) ограничивающий объем должен быть достаточно плотным, чтобы количество «ложноположительных» пересечений было низким. Ложноположительное пересечение в этом случае означает, что ограничивающий объем пересекается, а фактические объекты — нет. Различные типы ограничивающих объемов предлагают различные компромиссы для этих свойств.

Ограничивающие параллелепипеды с выравниванием по осям (AABB) и кубоиды популярны благодаря своей простоте и быстрой проверке пересечения. ^[8] Ограничивающие объемы, такие как ориентированные ограничивающие параллелепипеды (OBB) , K-DOP и выпуклые оболочки, предлагают более точное приближение к замкнутой форме за счет более сложной проверки пересечения.

Ограничивающие объемы обычно используются на ранней (отсеченной) стадии обнаружения столкновений, так что только объекты с перекрывающимися ограничивающими объемами необходимо сравнивать подробно. ^[9] Вычисление столкновений или перекрытий между ограничивающими объемами требует дополнительных вычислений, поэтому для того, чтобы это принесло пользу, нам нужно, чтобы ограничивающий объем был относительно узким, а накладные расходы на вычисления, связанные со столкновениями, были низкими.

Точное парное обнаружение столкновений

После завершения обрезки у нас останется несколько пар кандидатов для проверки на предмет точного обнаружения столкновений.

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

Ранние работы в этой области включали методы « разделяющей плоскости ». Два треугольника сталкиваются по существу только тогда, когда их нельзя разделить плоскостью, проходящей через три вершины. То есть, если треугольники являются и где каждый является вектором в , то мы можем взять три вершины, , найти плоскость, проходящую через все три вершины, и проверить, является ли она разделяющей плоскостью. Если любая такая плоскость является разделяющей плоскостью, то треугольники считаются непересекающимися. С другой стороны, если ни одна из этих плоскостей не является разделяющей плоскостью, то треугольники считаются пересекающимися. Существует двадцать таких плоскостей. ${\displaystyle {v_{1},v_{2},v_{3}}}$ ${\displaystyle {v_{4},v_{5},v_{6}}}$ ${\displaystyle v_{j}}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle v_{i},v_{j},v_{k}}$

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

С тех пор были разработаны лучшие методы. Доступны очень быстрые алгоритмы для поиска ближайших точек на поверхности двух выпуклых многогранных объектов. Ранняя работа Минг С. Лина ^[10] использовала вариацию симплексного алгоритма из линейного программирования . Алгоритм расстояния Гилберта-Джонсона-Керти заменил этот подход. Эти алгоритмы приближаются к постоянному времени при многократном применении к парам неподвижных или медленно движущихся объектов, когда используются начальные точки из предыдущей проверки столкновения.

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

Априорная обрезка

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

Здесь также желательно отсечение, как n -теловое, так и попарное, но алгоритмы должны учитывать время и типы движений, используемые в базовой физической системе.

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

В качестве примера рассмотрим два треугольника, движущиеся во времени и . В любой момент времени два треугольника можно проверить на пересечение, используя двадцать плоскостей, упомянутых ранее. Однако мы можем сделать лучше, поскольку все эти двадцать плоскостей можно отслеживать во времени. Если плоскость проходит через точки в , то есть двадцать плоскостей для отслеживания. Каждую плоскость необходимо отслеживать по трем вершинам, это дает шестьдесят значений для отслеживания. Использование поиска корней на этих шестидесяти функциях дает точное время столкновения для двух заданных треугольников и двух заданных траекторий. Здесь мы отмечаем, что если траектории вершин предполагаются линейными многочленами в , то окончательные шестьдесят функций на самом деле являются кубическими многочленами, и в этом исключительном случае можно найти точное время столкновения, используя формулу для кубических корней. Некоторые численные аналитики предполагают, что использование формулы для кубических корней не так численно устойчиво, как использование поиска корней для многочленов. ^{[ необходима цитата ]} ${\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}$ ${\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}$ ${\displaystyle P(u,v,w)}$ ${\displaystyle u,v,w}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}$ ${\displaystyle t}$

Треугольные центроидные сегменты

Объект треугольной сетки обычно используется в моделировании 3D-тел. Обычно функция столкновения — это пересечение треугольника с треугольником или ограничивающая форма, связанная с сеткой. Центроид треугольника — это расположение центра масс, такое, что он будет балансировать на кончике карандаша. Для моделирования нужно только добавить измерение центроида к физическим параметрам. Учитывая точки центроида как в объекте, так и в цели, можно определить отрезок линии, соединяющий эти две точки.

Радиус-вектор центроида треугольника — это среднее арифметическое радиус-векторов его вершин. Так что если его вершины имеют декартовы координаты , то центроид равен . ${\displaystyle (x_{1},y_{1},z_{1})}$ ${\displaystyle (x_{2},y_{2},z_{2})}$ ${\displaystyle (x_{3},y_{3},z_{3})}$ ${\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}$

Вот функция для расстояния отрезка прямой между двумя трехмерными точками. ${\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}$

Здесь длина/расстояние сегмента — это регулируемый размер критерия «попадания» сегмента. По мере приближения объектов длина уменьшается до порогового значения. Эффективным геометрическим тестом становится треугольная сфера. Сфера с центром в центроиде может быть рассчитана на охват всех вершин треугольника.

Использование

Обнаружение столкновений в компьютерном моделировании

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

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

После неупругого столкновения могут возникнуть особые состояния скольжения и покоя, и, например, Open Dynamics Engine использует ограничения для их моделирования. Ограничения позволяют избежать инерции и, следовательно, нестабильности. Реализация покоя посредством графа сцены позволяет избежать дрейфа.

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

Апостериори(дискретный) противаприори(непрерывно)

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

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

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

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

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

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

Видеоигры

Видеоигры должны делить свое очень ограниченное время вычислений между несколькими задачами. Несмотря на это ограничение ресурсов и использование относительно примитивных алгоритмов обнаружения столкновений, программисты смогли создать правдоподобные, хотя и неточные, системы для использования в играх. ^{[ необходима цитата ]}

Долгое время видеоигры имели очень ограниченное количество объектов для обработки, и поэтому проверка всех пар не была проблемой. В двухмерных играх в некоторых случаях оборудование было способно эффективно обнаруживать и сообщать о перекрывающихся пикселях между спрайтами на экране. ^[11] В других случаях простое разбиение экрана на плитки и привязка каждого спрайта к перекрывающимся плиткам обеспечивает достаточную обрезку, а для парных проверок используются ограничивающие прямоугольники или круги, называемые хитбоксами , и считаются достаточно точными.

Трехмерные игры использовали пространственные методы разбиения для обрезки тел и долгое время использовали одну или несколько сфер на реальный 3D-объект для парных проверок. Точные проверки очень редки, за исключением игр, пытающихся близко имитировать реальность. Даже тогда точные проверки не обязательно используются во всех случаях. ${\displaystyle n}$

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

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

Надежный симулятор — это тот, который будет реагировать на любой ввод разумным образом. Например, если мы представим себе видеоигру о гоночных автомобилях на высокой скорости , от одного шага симуляции к другому, можно предположить, что автомобили будут продвигаться на значительное расстояние по гоночной трассе. Если на трассе есть неглубокое препятствие (например, кирпичная стена), не совсем маловероятно, что автомобиль полностью перепрыгнет через него, и это очень нежелательно. В других случаях «исправление», которого требуют апостериорные алгоритмы, реализовано неправильно, что приводит к ошибкам , которые могут застревать персонажей в стенах или позволять им проходить сквозь них и падать в бесконечную пустоту, где может быть или не быть смертельная бездонная яма , иногда называемая «черным адом», «синим адом» или «зеленым адом» в зависимости от преобладающего цвета. Это отличительные признаки неисправной системы обнаружения столкновений и физического моделирования. Big Rigs: Over the Road Racing — печально известный пример игры с неисправной или, возможно, отсутствующей системой обнаружения столкновений.

Хитбокс

Хитбокс — это невидимая форма, обычно используемая в видеоиграх для обнаружения столкновений в реальном времени; это тип ограничивающего прямоугольника. Часто это прямоугольник (в 2D-играх) или кубоид (в 3D), который прикреплен к точке на видимом объекте (например, модели или спрайте) и следует за ней. Круглые или сфероидальные формы также распространены, хотя их по-прежнему чаще всего называют «коробками». Для анимированных объектов обычно прикрепляют хитбоксы к каждой движущейся части, чтобы обеспечить точность во время движения. ^{[12] [ ненадежный источник? ]}

Hitboxes используются для обнаружения "односторонних" столкновений, таких как удар кулаком или пуля. Они не подходят для обнаружения столкновений с обратной связью (например, удар о стену) из-за трудностей, с которыми сталкиваются как люди, так и ИИ в управлении постоянно меняющимися местоположениями hitboxes; такие виды столкновений обычно обрабатываются гораздо более простыми ограничивающими рамами, выровненными по осям . Игроки могут использовать термин "hitbox" для обозначения этих типов взаимодействий независимо от этого.

Hurtbox — это hitbox, используемый для обнаружения входящих источников урона. В этом контексте термин hitbox обычно зарезервирован для тех, которые наносят урон. Например, атака может быть нанесена только в том случае, если hitbox вокруг удара атакующего соприкасается с одним из hurtboxes противника на его теле, в то время как столкновение противостоящих hitboxes может привести к тому, что игроки будут обмениваться или отменять удары, а противостоящие hurtboxes не будут взаимодействовать друг с другом. Термин не стандартизирован в отрасли; некоторые игры меняют свои определения hitbox и hurtbox , в то время как другие используют только «hitbox» для обеих сторон.

Смотрите также

• Реакция на столкновение
• Тестирование попаданий
• Ограничивающий объем
• Физика игры
• Алгоритм расстояния Гилберта-Джонсона-Кирти
• Усовершенствование портала Минковского
• Физический движок
• Алгоритм Любачевского–Стиллингера
• Физика тряпичной куклы

Ссылки

1. Teschner, M.; Kimmerle, S.; Heidelberger, B.; Zachmann, G.; Raghupathi, L.; Fuhrmann, A.; Cani, M.-P.; Faure, F.; Magnenat-Thalmann, N.; Strasser, W.; Volino, P. (2005). "Обнаружение столкновений для деформируемых объектов". Computer Graphics Forum . 24 : 61–81. CiteSeerX  10.1.1.58.2505 . doi :10.1111/j.1467-8659.2005.00829.x. S2CID  1359430.
2. Гудман, Джейкоб Э.; О'Рурк, Джозеф; Тот, Чаба Д., ред. (2018). "39". Справочник по дискретной и вычислительной геометрии. Дискретная математика и ее приложения (3-е изд.). Бока-Ратон Лондон Нью-Йорк: CRC Press, Taylor & Francis Group, книга Chapman & Hall. ISBN 978-1-4987-1139-5.
3. Эндрюс, Шелдон; Эрлебен, Кенни; Фергюсон, Захари (2022-08-02). «Моделирование контакта и трения для компьютерной графики». Курсы SIGGRAPH '22 . ACM: 1–172. doi :10.1145/3532720.3535640. ISBN 978-1-4503-9362-1.
4. Хадап, Сунил; Эберле, Дэйв; Волино, Паскаль; Лин, Минг К.; Редон, Стефан; Эриксон, Кристер (2004-08-08). "Обнаружение столкновений и запросы близости". Курсы SIGGRAPH '04 . ACM: 15. doi :10.1145/1103900.1103915. ISBN 978-1-4503-7801-7.
5. Cohen, Jonathan D.; Lin, Ming C.; Manocha, Dinesh; Ponamgi, Madhav (1995). "I-COLLIDE: интерактивная и точная система обнаружения столкновений для крупномасштабных сред". I3D '95: Труды симпозиума 1995 года по интерактивной 3D-графике . ACM Press: 189–ff. doi :10.1145/199404.199437. ISBN 978-0-89791-736-0.
6. Акенин-Мёллер, Томас; Хейнс, Эрик; Хоффман, Нати; Пеше, Анджело; Иваницкий, Михал; Хиллэр, Себастьян (2018). Рендеринг в реальном времени. Книга А.К. Петерса (4-е изд.). Бока-Ратон, Лондон, Нью-Йорк: CRC Press, Taylor & Francisco Group. ISBN 978-1-138-62700-0.
7. Клосовски, Джеймс Т.; Хелд, Мартин; Митчелл, Джозеф С.Б.; Совизрал, Генри; Зикан, Карел (1998). «Эффективное обнаружение столкновений с использованием иерархий ограничивающих объемов k-DOP». Труды IEEE по визуализации и компьютерной графике . 4 (1). IEEE: 21–36. doi :10.1109/2945.675649.
8. Колдуэлл, Дуглас Р. (2005-08-29). «Раскрытие тайн ограничивающей рамки». Центр исследований и разработок инженеров армии США, Центр топографической инженерии, Исследовательский отдел, Отделение генерации и управления информацией. Архивировано из оригинала 28-07-2012 . Получено 13-05-2014 .
9. Gan B, Dong Q (2022). «Улучшенный оптимальный алгоритм обнаружения столкновений гибридного иерархического ограничивающего прямоугольника». Evolutionary Intelligence . 15 (4): 2515–2527. doi :10.1007/s12065-020-00559-6.
10. Лин, Мин С (1993). "Эффективное обнаружение столкновений для анимации и робототехники (диссертация)" (PDF) . Калифорнийский университет в Беркли. Архивировано из оригинала (PDF) 28 июля 2014 г.
11. "Components of the Amiga: The MC68000 and the Amiga Custom Chips" (Reference manual) (ред. 2.1). Глава 1. Архивировано из оригинала 2018-07-17 . Получено 2018-07-17 . Кроме того, вы можете использовать системное оборудование для обнаружения столкновений между объектами и заставить свою программу реагировать на такие столкновения.
12. "Hitbox". Сообщество разработчиков Valve . Valve . Получено 18 сентября 2011 г.

Внешние ссылки

• Веб-сайт исследования обнаружения столкновений Университета Северной Каролины в Чапел-Хилл
• Веб-сайт профессора Стивена Кэмерона (Оксфордский университет) по обнаружению столкновений
• Как избежать столкновения, Джордж Бек, Wolfram Demonstrations Project .
• Ограничительные рамки и их использование
• Теорема о разделяющей оси
• Unity 3D Столкновение
• Годо Физика Столкновение