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

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

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

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оптимизация

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

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

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

На грубом уровне обнаружения столкновений цель состоит в том, чтобы найти пары объектов, которые потенциально могут пересечься. Эти пары потребуют дальнейшего анализа. Ранний высокопроизводительный алгоритм для этого был разработан Мином К. Линем из Калифорнийского университета в Беркли [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. Ориентированные деревья ограничивающих рамок называются OBBTree. Некоторые деревья легче обновлять, если изменяется базовый объект. Некоторые деревья могут содержать примитивы более высокого порядка, такие как сплайны, вместо простых треугольников. ${\displaystyle B(T)}$

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

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

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

Ранние работы в этой области включали методы « разделяющей плоскости ». Два треугольника сталкиваются по существу только тогда, когда их нельзя разделить плоскостью, проходящей через три вершины. То есть, если треугольники есть и где каждый является вектором в , то мы можем взять три вершины , найти плоскость, проходящую через все три вершины, и проверить, является ли это разделяющей плоскостью. Если какая-либо такая плоскость является разделяющей, то треугольники считаются непересекающимися. С другой стороны, если ни одна из этих плоскостей не является разделяющей плоскостью, то треугольники считаются пересекающимися. Таких самолетов двадцать. ${\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}}$

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

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

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

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

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

Здесь также желательно сокращение, как сокращение 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}$

Пространственное разделение

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

Ограничительные рамки

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

Сегменты центроида треугольника

Объект треугольной сетки обычно используется при 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)}$

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

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

Видеоигры

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

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

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

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

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

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

Хитбокс

Диалоговое окно отладки в Gearheads , управляющее хитбоксом объекта.

Хитбокс игрушки Gearheads , управляемый с помощью приведенного выше экрана.

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

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

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

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

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

Рекомендации

1. Тешнер, М.; Киммерле, С.; Гейдельбергер, Б.; Захманн, Г.; Рагхупати, Л.; Фурманн, А.; Кани, член парламента; Фор, Ф.; Магненат-Тальманн, Н.; Штрассер, В.; Волино, П. (2005). «Обнаружение столкновений деформируемых объектов». Форум компьютерной графики . 24 : 61–81. CiteSeerX  10.1.1.58.2505 . дои : 10.1111/j.1467-8659.2005.00829.x. S2CID  1359430.
2. Жауме, Дж; Галли, Р; Мас, Р; Маскаро-Оливер, М (1995) (1995). «Проверка столкновений в реальном времени для позиционирования трехмерных объектов в разреженных средах». Обработка изображений для вещания и видеопроизводства . Семинары по информатике. Обработка изображений для вещания и видеопроизводства; Спрингер-Верлаг. стр. 216–225. дои : 10.1007/978-1-4471-3035-2_18. ISBN 978-3-540-19947-2.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
3. Линь, Мин С. (1993). «Эффективное обнаружение столкновений в анимации и робототехнике (диссертация)» (PDF) . Калифорнийский университет, Беркли. Архивировано из оригинала (PDF) 28 июля 2014 г.
4. Колдуэлл, Дуглас Р. (29 августа 2005 г.). «Раскрытие тайн ограничивающей рамки». Центр инженерных исследований и разработок армии США, Центр топографической инженерии, исследовательский отдел, отдел генерации и управления информацией. Архивировано из оригинала 28 июля 2012 г. Проверено 13 мая 2014 г.
5. «Компоненты Amiga: MC68000 и специальные чипы Amiga» (Справочное руководство) (изд. 2.1). Глава 1. Архивировано из оригинала 17 июля 2018 г. Проверено 17 июля 2018 г. Кроме того, вы можете использовать системное оборудование для обнаружения столкновений между объектами и заставить вашу программу реагировать на такие столкновения.
6. "Хитбокс". Сообщество разработчиков Valve . Клапан . Проверено 18 сентября 2011 г.

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

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