Обнаружение столкновений в вычислительной геометрии

Введение

Термин в информатике
обнаружение столкновений в вычислительной геометрии

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

Обзор

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

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

Физические симуляторы различаются по способу реагирования на столкновения. Некоторые используют мягкость материала для вычисления силы, которая разрешает столкновение в последующих шагах времени, подобно тому, как это происходит в реальности. Это очень ресурсоемко для процессора при работе с материалами с низкой мягкостью. Другие симуляторы оценивают время столкновения с помощью линейной интерполяции, откатывают симуляцию и рассчитывают столкновение, используя более абстрактные методы, основанные на законах сохранения. Некоторые используют итерации линейной интерполяции (метод Ньютона) для вычисления времени столкновения с гораздо большей точностью, чем остальная часть симуляции. Обнаружение столкновений использует временную когерентность, чтобы обеспечить еще более мелкие шаги по времени без существенного увеличения нагрузки на процессор, например, в системах управления воздушным движением. После неупругого столкновения могут возникать особые состояния скольжения и состояния покоя, и, например, Open Dynamics Engine использует ограничения для их моделирования. Ограничения исключают инерцию и, следовательно, нестабильность. Реализация состояния покоя с помощью графа сцен позволяет избежать смещения. Иными словами, физические симуляторы обычно работают одним из двух способов: когда столкновение обнаруживается a posteriori (после его возникновения) или a priori (до его возникновения). Помимо различия между a posteriori и a priori, почти все современные алгоритмы обнаружения столкновений организованы в иерархию алгоритмов. Часто вместо терминов a posteriori и a priori используются термины "дискретный" и "непрерывный".

A posteriori (дискретное) против a priori (непрерывное)

В случае a posteriori физическое моделирование продвигается на небольшой шаг, после чего проверяется, пересекаются ли какие-либо объекты или кажутся пересекающимися. На каждом шаге моделирования создается список всех пересекающихся тел, а положения и траектории этих объектов "фиксируются" для учета столкновения. Этот метод называется a posteriori, поскольку он обычно пропускает фактический момент столкновения и обнаруживает столкновение только после того, как оно произошло. В априорных методах используется алгоритм обнаружения столкновений, способный с высокой точностью предсказывать траектории физических тел. Моменты столкновения вычисляются с высокой точностью, и физические тела никогда не проникают друг в друга. Это называется априорным, потому что алгоритм обнаружения столкновений рассчитывает моменты столкновения до обновления конфигурации физических тел. Основные преимущества методов a posteriori заключаются в следующем. В этом случае алгоритму обнаружения столкновений не требуется учитывать множество физических переменных; алгоритму передается простой список физических тел, и программа возвращает список пересекающихся тел. Алгоритму обнаружения столкновений не нужно понимать трение, упругие столкновения или, что еще хуже, неупругие столкновения и деформируемые тела. Кроме того, алгоритмы a posteriori по сути на одно измерение проще, чем алгоритмы a priori. Алгоритму a priori необходимо учитывать переменную времени, которой нет в задаче a posteriori. С другой стороны, алгоритмы a posteriori вызывают проблемы на этапе "фиксации", когда необходимо исправить пересечения (которые физически некорректны). Кроме того, если дискретный шаг слишком велик, столкновение может остаться незамеченным, в результате чего объект может пройти сквозь другой, если он достаточно быстрый или маленький. Преимущества априорных алгоритмов – повышенная точность и стабильность. Отделить физическое моделирование от алгоритма обнаружения столкновений сложно (но не невозможно). Однако во всех случаях, кроме самых простых, задача определения времени столкновения двух тел (при заданных начальных данных) не имеет аналитического решения – обычно используется численный метод поиска корней. Некоторые объекты находятся в состоянии покоящегося контакта, то есть в столкновении, но не отскакивают и не проникают друг в друга, например, ваза, стоящая на столе. Во всех случаях покоящийся контакт требует специальной обработки: если два объекта сталкиваются (a posteriori) или скользят (a priori), и их относительное движение ниже определенного порога, трение переходит в трение покоя, и оба объекта располагаются в одной и той же ветке графа сцены.

In the a posteriori case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called a posteriori because it typically misses the actual instant of collision, and only catches the collision after it has actually happened. In the a priori methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called a priori because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies. The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. An a priori algorithm must deal with the time variable, which is absent from the a posteriori problem. On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small. The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical root finder is usually involved. Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph.

Оптимизация

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

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

Во многих приложениях конфигурация физических тел от одного временного шага к следующему меняется незначительно. Многие объекты могут вообще не перемещаться. Алгоритмы были разработаны таким образом, чтобы вычисления, выполненные на предыдущем временном шаге, можно было повторно использовать на текущем, что обеспечивает более быстрое завершение расчетов. На уровне грубого обнаружения столкновений задача состоит в поиске пар объектов, которые потенциально могут пересекаться. Эти пары потребуют дальнейшего анализа. Одним из первых высокопроизводительных алгоритмов для этого был разработан Мингом С. Лином в Калифорнийском университете в Беркли, который предложил использовать ориентированные по осям ограничивающие прямоугольники (bounding boxes) для всех n тел в сцене. Каждый прямоугольник представлен произведением трех интервалов (то есть прямоугольник будет выглядеть как ). Распространенным алгоритмом обнаружения столкновений ограничивающих прямоугольников является метод "прометание и отсечение" (sweep and prune). Обратите внимание, что два таких прямоугольника, и , пересекаются тогда и только тогда, когда пересекается , пересекается и пересекается . Предполагается, что от одного временного шага к следующему, если и пересекаются, то весьма вероятно, что они будут пересекаться и на следующем шаге. Аналогично, если они не пересекались на предыдущем шаге, то, скорее всего, не будут пересекаться и в дальнейшем. Таким образом, мы сводим задачу к отслеживанию, от кадра к кадру, того, какие интервалы пересекаются. У нас есть три списка интервалов (по одному для каждой оси), и все списки имеют одинаковую длину (поскольку каждый список имеет длину , равную количеству ограничивающих прямоугольников). В каждом списке каждый интервал может пересекаться со всеми остальными интервалами в этом списке. Следовательно, для каждого списка у нас будет матрица из нулей и единиц: равна 1, если интервалы и пересекаются, и 0, если они не пересекаются. Согласно нашему предположению, матрица, связанная со списком интервалов, останется практически неизменной от одного временного шага к следующему. Чтобы использовать это, список интервалов фактически хранится как список помеченных конечных точек. Каждый элемент списка содержит координату конечной точки интервала, а также уникальное целое число, идентифицирующее этот интервал. Затем мы сортируем список по координатам и обновляем матрицу в процессе сортировки. Несложно поверить, что этот алгоритм будет работать относительно быстро, если конфигурация ограничивающих прямоугольников действительно не меняется существенно от одного временного шага к следующему. В случае деформируемых тел, таких как симуляция ткани, может быть невозможно использовать более специфичный алгоритм попарного отсечения, как обсуждается ниже, и алгоритм отсечения n тел будет наилучшим решением. Если можно установить верхнюю границу на скорость физических тел в сцене, то пары объектов можно отсечь на основе их начального расстояния и размера временного шага.

In many applications, the configuration of physical bodies from one time step to the next changes very little. Many of the objects may not move at all. Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster completion of the calculation. At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect. Those pairs will require further analysis. An early high performance algorithm for this was developed by Ming C. Lin at the University of California, Berkeley , who suggested using axis aligned bounding boxes for all n bodies in the scene. Each box is represented by the product of three intervals (i. e., a box would be ). A common algorithm for collision detection of bounding boxes is sweep and prune. Observe that two such boxes, and intersect if, and only if, intersects , intersects and intersects It is supposed that, from one time step to the next, if and intersect, then it is very likely that at the next time step they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to. So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length , the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an matrix of zeroes and ones: is 1 if intervals and intersect, and 0 if they do not intersect. By our assumption, the matrix associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we sort the list by coordinates, and update the matrix as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next. In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an n body pruning algorithm is the best that can be done. If an upper bound can be placed on the velocity of the physical bodies in a scene, then pairs of objects can be pruned based on their initial distance and the size of the time step.

Паральная обрезка

После того, как мы выбрали пару физических тел для дальнейшего исследования, нам нужно тщательнее проверять столкновения. Однако во многих приложениях отдельные объекты (если они не слишком деформируемы) описываются набором меньших примитивов, в основном треугольников. Итак, теперь у нас есть два набора треугольников, и (для простоты будем считать, что каждый набор содержит одинаковое количество треугольников). Очевидное решение – проверить все треугольники на предмет столкновений со всеми треугольниками , но это потребует сравнений, что крайне неэффективно. Если возможно, желательно использовать алгоритм отсечения, чтобы уменьшить количество пар треугольников, которые необходимо проверять. Наиболее широко используемое семейство алгоритмов известно как метод иерархических ограничивающих объемов. В качестве предварительного этапа обработки для каждого объекта (в нашем примере, и ) мы вычислим иерархию ограничивающих объемов. Затем, на каждом шаге времени, когда нам нужно проверить столкновения между и , иерархические ограничивающие объемы будут использоваться для уменьшения количества рассматриваемых пар треугольников. Для простоты приведем пример с использованием ограничивающих сфер, хотя отмечено, что сферы нежелательны во многих случаях. Если – это набор треугольников, мы можем предварительно вычислить ограничивающую сферу . Существует множество способов выбора , мы лишь предполагаем, что – это сфера, которая полностью содержит и при этом имеет минимальный размер. Заранее мы можем вычислить и . Очевидно, если эти две сферы не пересекаются (и это очень легко проверить), то и с также не пересекаются. Однако это не намного лучше, чем алгоритм отсечения для n тел. Если – это набор треугольников, то мы можем разделить его на две половины, и . Мы можем сделать это для и , и вычислить (заранее) ограничивающие сферы и . Надежда заключается в том, что эти ограничивающие сферы значительно меньше, чем и , и если, например, и не пересекаются, то нет смысла проверять ни один треугольник из с каким-либо треугольником из . В качестве предварительного вычисления мы можем взять каждое физическое тело (представленное набором треугольников) и рекурсивно разложить его в двоичное дерево, где каждый узел представляет собой набор треугольников, а его два дочерних узла представляют и . На каждом узле дерева мы можем предварительно вычислить ограничивающую сферу . Когда придет время проверять пару объектов на столкновение, их деревья ограничивающих сфер могут быть использованы для исключения многих пар треугольников. Многие варианты алгоритмов получаются путем выбора чего-то отличного от сферы для . Если выбирать ограничивающие ящики, выровненные по осям, то получатся AABBTrees. Ориентированные деревья ограничивающих ящиков называются OBBTrees. Некоторые деревья легче обновлять, если изменяется базовый объект. Некоторые деревья могут вмещать примитивы более высокого порядка, такие как сплайны, вместо простых треугольников.

Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, and (for simplicity, we will assume that each set has the same number of triangles.) The obvious thing to do is to check all triangles against all triangles for collisions, but this involves comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check. The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (in our example, and ) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between and , the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases. If is a set of triangles, we can pre calculate a bounding sphere There are many ways of choosing , we only assume that is a sphere that completely contains and is as small as possible. Ahead of time, we can compute and Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do and This is not much better than an n body pruning algorithm, however. If is a set of triangles, then we can split it into two halves and We can do this to and , and we can calculate (ahead of time) the bounding spheres and The hope here is that these bounding spheres are much smaller than and And, if, for instance, and do not intersect, then there is no sense in checking any triangle in against any triangle in
As a precomputation, we can take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node represents a set of triangles, and its two children represent and At each node in the tree, we can pre compute the bounding sphere
When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles. Many variants of the algorithms are obtained by choosing something other than a sphere for If one chooses axis aligned bounding boxes, one gets AABBTrees. Oriented bounding box trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as splines instead of simple triangles.

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

После того, как мы закончим отсечение, у нас останется несколько пар кандидатов для проверки точного обнаружения столкновений. Важное наблюдение состоит в том, что для любых двух выпуклых объектов, не пересекающихся, можно найти плоскость в пространстве, такую что один объект полностью лежит по одну сторону этой плоскости, а другой – по противоположную. Это позволяет разработать очень быстрые алгоритмы обнаружения столкновений для выпуклых объектов. Первые работы в этой области были связаны с методами "разделяющих плоскостей". Два треугольника сталкиваются, по сути, только тогда, когда их нельзя разделить плоскостью, проходящей через три вершины. То есть, если треугольники – и , где каждый – вектор в , то мы можем выбрать три вершины, , найти плоскость, проходящую через все три вершины, и проверить, является ли эта плоскость разделяющей. Если хотя бы одна такая плоскость является разделяющей, то треугольники считаются непересекающимися. С другой стороны, если ни одна из этих плоскостей не является разделяющей, то треугольники считаются пересекающимися. Существует двадцать таких плоскостей. Если треугольники лежат в одной плоскости, этот тест не всегда дает точный результат. Можно добавить дополнительные плоскости, например, нормальные к ребрам треугольника, чтобы полностью решить проблему. В других случаях объекты, соприкасающиеся плоской гранью, неизбежно должны соприкасаться под углом в другом месте, поэтому общая система обнаружения столкновений сможет обнаружить столкновение. Со временем были разработаны более совершенные методы. Существуют очень быстрые алгоритмы для нахождения ближайших точек на поверхности двух выпуклых многогранников. Ранние работы Минга Линя использовали вариант симплекс-алгоритма из линейного программирования. Алгоритм расстояния Гилберта-Джонсона-Кирти превзошел этот подход. Эти алгоритмы приближаются к постоянному времени при многократном применении к парам неподвижных или медленно движущихся объектов, если использовать исходные точки из предыдущей проверки столкновения. Конечным результатом всех этих алгоритмических разработок является то, что обнаружение столкновений может быть эффективно выполнено для тысяч движущихся объектов в реальном времени на обычных персональных компьютерах и игровых консолях.

Once we're done pruning, we are left with a number of candidate pairs to check for exact collision detection. A basic observation is that for any two convex objects which are disjoint, one can find a plane in space so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This allows the development of very fast collision detection algorithms for convex objects. Early work in this area involved "separating plane" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are and where each is a vector in , then we can take three vertices, , find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes. If the triangles are coplanar, this test is not entirely successful. One can add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision. Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by Ming C. Lin used a variation on the simplex algorithm from linear programming. The Gilbert Johnson Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow moving objects, when used with starting points from the previous collision check. The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

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

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

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

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

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

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

Центроидные сегменты треугольника

Треугольная сетка обычно используется в 3D-моделировании тел. Как правило, функция обнаружения столкновений представляет собой перехват треугольника с треугольником или ограничивающую форму, связанную с сеткой. Центроид треугольника – это центр масс, точка, в которой он будет балансировать на кончике карандаша. Для симуляции достаточно добавить размерность центроида к физическим параметрам. Зная центроиды как объекта, так и цели, можно определить отрезок прямой, соединяющий эти две точки. Вектор положения центроида треугольника равен среднему значению векторов положения его вершин. Таким образом, если его вершины имеют декартовы координаты , и , то центроид равен . Вот функция для вычисления расстояния между отрезками прямой, соединяющими две 3D-точки. Здесь длина/расстояние отрезка является настраиваемым критерием "попадания", определяющим размер отрезка. По мере сближения объектов длина уменьшается до порогового значения. Треугольник, представленный сферой, становится эффективным тестом геометрии. Сферу, центрированную в центроиде, можно масштабировать так, чтобы она охватывала все вершины треугольника.

Видеоигры

Видеоигры должны распределять свое крайне ограниченное вычислительное время между множеством задач. Несмотря на это ограничение ресурсов и использование относительно примитивных алгоритмов обнаружения столкновений, программисты смогли создать убедительные, хотя и неточные, системы для использования в играх. Долгое время в видеоиграх было небольшое количество объектов для обработки, поэтому проверка всех пар не представляла собой проблемы. В двухмерных играх в некоторых случаях аппаратное обеспечение могло эффективно обнаруживать и сообщать о перекрывающихся пикселях между спрайтами на экране. В других случаях простое разбиение экрана на тайлы и привязка каждого спрайта к тайлам, с которыми он пересекается, обеспечивало достаточную отсечку, а для попарных проверок использовались ограничивающие прямоугольники или окружности, называемые hitboxes, которые считались достаточно точными. В трехмерных играх для отсечения тел использовались методы пространственного разделения, и долгое время для попарных проверок применялись одна или несколько сфер для каждого реального 3D-объекта. Точные проверки крайне редки, за исключением игр, стремящихся к реалистичной симуляции. Даже в этом случае точные проверки не всегда используются. Поскольку игры не обязаны имитировать реальную физику, стабильность не является столь важной проблемой. Почти все игры используют обнаружение столкновений a posteriori, а столкновения часто разрешаются с помощью очень простых правил. Например, если персонаж оказывается встроенным в стену, его можно просто вернуть в последнее известное корректное положение. Некоторые игры рассчитывают расстояние, на которое персонаж может переместиться, прежде чем попасть в стену, и разрешают ему двигаться только на это расстояние. Во многих случаях для видеоигр достаточно приближать персонажей к точке для обнаружения столкновений с окружением. В этом случае деревья двоичного разделения пространства предоставляют работоспособный, эффективный и простой алгоритм для проверки, находится ли точка внутри сцены или нет. Такая структура данных также может быть использована для корректной обработки ситуации "положения покоя", когда персонаж бежит по земле. Столкновения между персонажами, а также столкновения со снарядами и опасностями обрабатываются отдельно. Надежный симулятор – это тот, который адекватно реагирует на любой ввод. Например, представим себе видеоигру с высокоскоростными гонками. От одного шага симуляции к другому автомобили могут значительно продвинуться по трассе. Если на трассе есть небольшое препятствие (например, кирпичная стена), вполне возможно, что автомобиль полностью перепрыгнет через него, что крайне нежелательно. В других случаях "исправление", требуемое алгоритмами a posteriori, реализовано некорректно, что приводит к ошибкам, которые могут застревать персонажей в стенах или позволять им проходить сквозь них и падать в бесконечную пустоту, где может быть или не быть смертельная бездонная пропасть, иногда называемая "черным адом", "синим адом" или "зеленым адом", в зависимости от преобладающего цвета. Это признаки неисправной системы обнаружения столкновений и физической симуляции. Big Rigs: Over the Road Racing – печально известный пример игры с неисправной или, возможно, отсутствующей системой обнаружения столкновений.

Video games have to split their very limited computing time between several tasks. Despite this resource limit, and the use of relatively primitive collision detection algorithms, programmers have been able to create believable, if inexact, systems for use in games. For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between sprites on the screen. In other cases, simply tiling the screen and binding each sprite into the tiles it overlaps provides sufficient pruning, and for pairwise checks, bounding rectangles or circles called hitboxes are used and deemed sufficiently accurate. Three dimensional games have used spatial partitioning methods for body pruning, and for a long time used one or a few spheres per actual 3D object for pairwise checks. Exact checks are very rare, except in games attempting to simulate reality closely. Even then, exact checks are not necessarily used in all cases. Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use a posteriori collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far. In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, binary space partitioning trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately. A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed racecar video game, from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in bugs that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly bottomless pit, sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. Big Rigs: Over the Road Racing is an infamous example of a game with a failing or possibly missing collision detection system.

Hitbox (англ.)

Hitbox – это невидимая форма, обычно используемая в видеоиграх для обнаружения столкновений в реальном времени; это тип ограничивающего прямоугольника. Чаще всего это прямоугольник (в 2D играх) или кубоид (в 3D), который прикреплен к точке на видимом объекте (например, модели или спрайте) и следует за ней. Круглые или сфероидальные формы также распространены, хотя их всё ещё чаще называют «коробками». Для анимированных объектов обычно используются hitboxes, прикрепленные к каждой движущейся части, чтобы обеспечить точность во время движения. Недостоверный источник: дата=март 2018.

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