Просмотр кода страницы Обнаружение столкновений

{{стиль статьи|дата=2023-02-27}}
'''Обнаруже́ние столкнове́ний''' ({{lang-en|Collision detection}}) — вычислительная проблема обнаружения [[Пересечение|пересечений]] между собой двух или более объектов. Тема чаще всего связана с её использованием в [[Физический движок|физических движках]], [[Компьютерная анимация|компьютерной анимации]] и [[Робототехника|робототехнике]]. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о ''коллекторе контакта'' (набор пересечения точек)<ref>Ericson, Christer. Real-time Collision Detection. Elsevier, 2005, p. 13.</ref>. Реакция на столкновение (что происходит, когда столкновение обнаружено) зависит от конкретного моделируемого процесса. В алгоритмах обнаружения столкновений широко применяются понятия из линейной алгебры и вычислительной геометрии. Алгоритмы обнаружения столкновений являются одной из основных составляющих физики трёхмерных [[Компьютерная игра|компьютерных игр]].

== Обзор ==
[[Файл:Billiards balls.jpg|right|200px|thumb|Классическая задача теории обнаружения столкновений — столкновения бильярдных шаров]]
Функционирование физической модели подразумевает проведение физических экспериментов, например игры в [[бильярд]]. Физика сталкивающихся бильярдных шаров хорошо описана [[Физика твёрдого тела|физикой твёрдого тела]] и теорией [[Абсолютно упругий удар|абсолютно упругого удара]]. Начальные условия задаются абсолютно точными физическими характеристиками бильярдного стола и шаров, а также изначальными координатами шаров. Имея заданное ускорение шара «[[Пул (бильярд)#Шары|битка]]» (предположительно появившегося в результате удара игрока кием по битку), мы хотим вычислить точные траектории движения, скорости и места остановки всех шаров с помощью компьютерной программы. [[Физический движок]], моделирующий бильярд, будет состоять из нескольких компонентов, один из которых будет отвечать за точное вычисление столкновений между шарами. Этот компонент является примером нестабильной части модели — небольшие ошибки в вычислениях столкновений будут приводить к значительным изменениям в результатах — конечных положениях шаров на столе.
[[Файл:Fighter hitbox.svg|мини|upright|Пример хитбокса атакующего персонажа в [[файтинг]]е. Зелёная зона показывает коллизию персонажа, красная зона показывает зону наносимого урона.]]
{{anchor|Хитбокс}}Компьютерные игры предъявляют к физическим движкам примерно те же требования, за исключением некоторых существенных отличий. В то время как моделирование физических опытов требует создания максимально точного математического аппарата, описывающего реальный мир, компьютерные игры нуждаются в физике лишь правдоподобно выглядящей, но при этом вычисляемой в [[Реальное время|режиме реального времени]], пусть и грубо. Компромиссы допускаются, пока это устраивает игрока и имеет приемлемый ''визуальный'' реализм. Поэтому тело, которое проверяется на столкновение, — так называемый '''хитбокс''' или '''коллайдер''' — проще, чем [[трёхмерная модель]] персонажа.
== Обнаружение столкновений в физических симуляциях ==
Физические движки отличаются способами, которыми они реагируют на столкновения. Некоторые используют [[Деформируемое тело|гибкость материалов]] для вычисления силы, возникающей в результате столкновения и влияющей на результат столкновения в последующие временные интервалы, что достаточно затратно с точки зрения вычислительных ресурсов. Некоторые модели вычисляют аппроксимированное время столкновения с помощью линейной интерполяции, после чего «откатывают» состояние сцены на некоторый момент времени и просчитывают столкновение на основе законов сохранения энергии.

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

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

Другими словами, реализации физических моделей обычно делятся на два пути: 

# определение столкновения [[апостериори]],
# [[априори|априорный]] подход (обнаружение до происхождения столкновения). 

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

=== Различия апостериорного и априорного подходов ===
В случае апостериорного подхода просчёт модели реализуется через просчёт состояний сцены через небольшие промежутки времени, в каждый из которых происходит проверка на наличие [[пересечение множеств|пересекающихся]] объектов или располагающихся столь близко, что можно их считать пересекающимися. На каждом шаге моделирования создаётся список пересекающихся тел, позиции и траектории этих тел «корректируются» с учётом факта произошедшего столкновения. Этот подход называется апостериорным, поскольку по сути непосредственный точный момент столкновения упускается и обнаруживается уже через некоторое время после того, как он произошёл (или за некоторое время до того, в зависимости от алгоритма).

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

Из апостериорного подхода проистекают его основные достоинства. Алгоритму не нужно манипулировать значительным количеством физических переменных — его исходными данными является простой список физических тел, результатом является подмножество тел пересекающихся. Алгоритму не приходится иметь дело с учётом сил трения, упругих или — ещё хуже — неупругих столкновений, а также просчитывать изменение внутреннего состояния [[Деформируемое тело|деформируемых тел]]. Кроме того, апостериорный алгоритм по сути проще на одно измерение, так как в априорном подходе приходится иметь дело с дополнительной осью — временем, от чего избавлен подход апостериорный.

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

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

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

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

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

На уровне грубого определения столкновений целью является нахождение объектов, которые потенциально могут пересекаться. Эти пары потребуют дальнейшего анализа. Один из таких алгоритмов был разработан {{не переведено 2|Лин, Минг Чье|Минг Чье Лин|en|Ming C. Lin|Ming Chieh Lin}} из [[Калифорнийский университет в Беркли|Калифорнийского университета в Беркли]]<ref>{{cite web |url= http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html |title= Lin-Canny Closest Features Algorithm |author= {{не переведено 2|Лин, Минг Чье|Минг Чье Лин|en|Ming C. Lin|Ming Chieh Lin}} |publisher= [[Калифорнийский университет в Беркли]] |datepublished= 1996-01-31 |access-date= 2011-07-29 |lang= en |archive-url= https://www.webcitation.org/663fFZxj2?url=http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html |archive-date= 2012-03-10 |url-status= live }}</ref>, предложившей применение метода ограничивающих параллелепипедов, направляющие вектора ребер которых коллинеарны векторам базиса декартовой системы координат, для всех N тел сцены. Позже эти ограничивающие параллелепипеды стали известны как [[Axis-aligned bounding box]] (AABB).

Каждый параллелепипед представляется тройкой отрезков, например <math>I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]</math>. Распространённым алгоритмом для обнаружения столкновений ограничивающих параллелепипедов является алгоритм «[[Sweep and prune]]» ({{lang-ru|охватить и отбросить}}; {{lang-ru|охватить и обрезать}})<ref>{{cite web|url=http://www.gamedev.ru/code/terms/SAP|title=Sweep And Prune|publisher=[[GameDev.ru]]|datepublished=2007-08-30|access-date=2009-07-08|description=Описание алгоритма с примерами программного кода|lang=ru|archive-url=https://web.archive.org/web/20121015135308/http://www.gamedev.ru/code/terms/SAP|archive-date=2012-10-15|url-status=live}}</ref>. Очевидно, что два таких параллелепипеда <math>I_1 \times I_2 \times I_3</math> и <math>J_1 \times J_2 \times J_3</math> пересекаются тогда и только тогда, когда <math>I_1</math> пересекается с <math>J_1</math>, <math>I_2</math> пересекается с <math>J_2</math> и <math>I_3</math> пересекается с <math>J_3</math>. Предполагается, что если от одной временной итерации до следующей <math>I_k</math> и <math>J_k</math> пересекаются, то весьма вероятно, что они будут по-прежнему пересекаться и на следующей итерации. Также, если они не пересекались на предыдущей итерации, весьма вероятно, что не будут пересекаться и на следующей.

Итак, проблема сводится к итерационному контролю от «кадра» к «кадру» за тем, которые из отрезков пересекаются. Имеются три списка интервалов (по одному на каждую из осей координат), и все три одинаковой длины, так как длина каждого равна <math>n</math>, по числу объектов сцены и, соответственно, их ограничивающих параллелепипедов. Каждому из списков соответствует матрица <math>M _{n \times n}</math>, элементы <math>m_{ij}</math> которой равны 1 или 0. <math>m_{ij} = 1</math> — в случае, если отрезки <math>i</math> и <math>j</math> пересекаются, и <math>m_{ij} = 0</math>, если нет.

Допустим, матрица <math>M _{n \times n}</math> остаётся практически неизменной от одной итерации к следующей. Чтобы это использовать, список отрезков содержится в виде помеченных крайних точек. Каждый элемент списка располагает координатами крайней точки и уникальным номером, идентифицирующим отрезок. Список сортируется по координатам, и матрица обновляется в соответствующем порядке. Несложно убедиться, что указанный алгоритм будет обеспечивать достаточно высокую производительность, если конфигурация ограничивающих параллелепипедов не меняется значительно за одну итерацию.

В случае [[Деформируемое тело|деформируемых тел]], например просчёта физической модели ткани, нет возможности использовать более специфичный метод — алгоритм парного исключения, описанный ниже, и лучшим методом становятся алгоритмы, использующие подход «''n''-body pruning».

Если на скорость физических тел сцены может быть наложено ограничение максимального значения, тогда пары объектов могут удаляться из списка кандидатов на столкновения, исходя из их начальной дистанции друг от друга и размера шага временной итерации <math>\Delta t</math>.

=== Попарное сокращение ===
После того, как пара объектов сцены выбрана для дальнейшего изучения, требуется более детальная проверка на наличие факта столкновения. Во многих приложениях некоторые из объектов (если их геометрическая конфигурация относительно постоянна, то есть они не подлежат сильной деформации) описываются набором малоразмерных примитивов, в основном треугольников. То есть имеется два множества треугольников <math>S={S_1,S_2,\dots,S_n}</math> и <math>T={T_1,T_2,\dots,T_n}</math> (для простоты предполагается, что мощность множеств равна).

Очевидным методом проверки тел на столкновение является проверка всех упорядоченных пар <math>(S_j, T_k)</math> треугольников на столкновение. Однако сложность такой проверки составляет <math>\operatorname{O}(n^2)</math>, что крайне неэффективно. Возникает необходимость по возможности воспользоваться «отбрасывающим» алгоритмом для сокращения числа пар треугольников, нуждающихся в проверке.

Наиболее широко применяемым семейством алгоритмов является метод ''иерархических ограничивающих объёмов''. В качестве предварительного шага для каждого объекта (в нашем примере это <math>S</math> и <math>T</math>) вычисляется и ставится в соответствие иерархия ограничивающих объектов. После чего на каждой временно́й итерации, когда требуется проверить наличие столкновения между объектами <math>S</math> и <math>T</math>, ограничивающие объёмы используются для сокращения количества треугольников, попадающих под проверку. Одним из самых простых видов ограничивающего объёма является сфера.

Для множества треугольников <math>E</math> можно вычислить [[Ограничивающая сфера|ограничивающую сферу]] <math>B(E)</math>. Существует несколько способов выбора <math>B(E)</math>, принципиально лишь, что сфера <math>B(E)</math> полностью охватывает множество треугольных примитивов <math>B(E)</math> и одновременно мала настолько, насколько это возможно.

При определении наличия столкновения тел <math>S</math> и <math>T</math> возможно в первую очередь вычислить сферы <math>B(S)</math> и <math>B(T)</math>. Очевидно, что если эти сферы не пересечены, то не пересечены и <math>S</math> и <math>T</math>. Однако это ненамного более эффективно, нежели алгоритм «''n''-body pruning».

Пусть <math>E={E_1,E_2,\dots,E_m}</math> — множество треугольников. Тогда его можно разбить на две части: <math>L(E):={E_1,E_2,\dots,E_{m/2}}</math> и <math>R(E):={E_{m/2+1},\dots,E_{m-1},E_m}</math>. Подобным образом можно разбить <math>S</math> и <math>T</math> и предварительно вычислить ограничивающие сферы <math>B(L(S)),B(R(S))</math> и <math>B(L(T)),B(R(T))</math>.

Расчёт на то, что эти ограничивающие сферы значительно меньше, нежели <math>B(S)</math> и <math>B(T)</math>. И, если, к примеру, <math>B(S)</math> и <math>B(L(T))</math> не пересекаются, то не имеют смысла проверки пересечений треугольников множества <math>S</math> с треугольниками из <math>L(T)</math>.

В ходе предварительных вычислений можно рассмотреть каждое физическое тело, представленное в виде множества треугольников, и декомпозировать его в виде [[Двоичное дерево|двоичного дерева]], в котором узлами (нодами) <math>N</math> будут множества треугольников, а их потомками — <math>L(N)</math> и <math>R(N)</math>. Для каждого узла этого дерева можно предварительно рассчитать ограничивающую сферу <math>B(N)</math>. В таком случае, когда настанет необходимость проверки столкновения очередной пары тел, их заранее рассчитанные бинарные деревья ограничивающих сфер могут быть использованы для исключения значительной части из подлежащих проверке множеств составляющих их треугольников.

Множество дополнительных реализаций «древовидных» алгоритмов получается при выборе других стереометрических объектов в качестве ограничивающих объёмов, нежели сфер. При выборе параллелепипеда, ориентированного параллельно осям системы измерений ({{lang-en|axis-aligned bounding box}}), получаются так называемые AABB-деревья ({{lang-en|AABB-Trees}}). OBB-деревья (или ''ОOBB-деревья'') получаются при использовании параллелепипеда, ориентированного согласно собственной системе координат объекта. Некоторые из деревьев проще обновлять в случае изменений основного объекта. Некоторые деревья могут работать с примитивами более высокого порядка, такими как [[сплайн]]ы, вместо элементарных треугольников.

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

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

Ранние работы в этой области обозначили методы [[Теорема разделяющей оси|разделяющей плоскости]]. Два треугольника по существу сталкиваются только тогда, когда не могут быть разделены плоскостью, проходящей через три вершины. Это так, если треугольники <math>{v_1,v_2,v_3}</math> и <math>{v_4,v_5,v_6}</math>, где каждый <math>v_j</math> вектор в <math>\mathbb R^3</math>, тогда можно выбрать три вершины — <math>v_i,v_j,v_k</math>, провести плоскость через все три и проверить, является ли плоскость разделяющей. Если любая из таких плоскостей является разделяющей, значит, треугольники не пересекаются; и пересекаются, если, напротив, ни одна из них разделяющей не является. Всего таких плоскостей получается 20.

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

С тех пор были разработаны лучшие методы. На данный момент доступны очень быстрые алгоритмы на нахождения ближайших точек поверхности двух выпуклых многогранных тел. В 1993 г. М. Ч. Лин в своей диссертации<ref>{{статья |заглавие=Efficient Collision Detection for Animation and Robotics (thesis) |издательство=[[Калифорнийский университет в Беркли]] |ссылка=ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/thesis.pdf |access-date=2011-07-29 |язык=en |тип=journal |автор={{не переведено 2|Лин, Минг Чье|Минг Чье Лин|en|Ming C. Lin|Ming Chieh Lin}} |год=1993|url-status=dead}}</ref> использовала вариацию [[симплекс-метод]]а из [[Линейное программирование|линейного программирования]]. В дальнейшем [[алгоритм Гилберта-Джонсона-Кёрти|алгоритм Гилберта—Джонсона—Кёрти]] сменил этот подход. Эти [[алгоритм]]ы приближаются к постоянному времени вычисления при последовательном применении к парам неподвижных или медленно движущихся тел, когда используются с начальными данными из предыдущей итерации обнаружения столкновений.

Следствием всех этих достижений стала возможность эффективного обнаружения столкновений в реальном времени для тысяч движущихся тел на типовом [[персональный компьютер|персональном компьютере]] или [[Игровая консоль|игровой консоли]].

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

В данных ситуациях желательно сокращение (отбрасывание): как «n-body pruning», так и попарное сокращение. Однако этим алгоритмам требуется время для вычислений и учёт типов движений, используемых в базовой физической системе.

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

В качестве примера рассмотрим два треугольника, движущихся во времени: <math>{v_1(t),v_2(t),v_3(t)}</math> и <math>{v_4(t),v_5(t),v_6(t)}</math>. В любой момент времени эти два треугольника могут быть проверены на пересечение с использованием двадцати плоскостей, о которых говорилось выше. Тем не менее процесс можно улучшить, так как эти двадцать плоскостей могут быть отслежены во времени. Если <math>P(u,v,w)</math> является плоскостью, которая проходит сквозь точки <math>u,v,w</math> в <math>\mathbb R^3</math>, то это значит, что доступны двадцать плоскостей для отслеживания. Каждая плоскость должна быть отслежена по отношению к трём вершинам, это даёт шестьдесят значений для отслеживания. Использование корневого поиска для этих шестидесяти функций вычисляет точное время столкновения для двух заданных треугольников и для двух заданных траекторий. Если траектории вершин считаются линейными полиномами (многочленами) в <math>t</math>, то тогда окончательные шестьдесят функций являются кубическими полиномами, и в этом исключительном случае является возможным найти точное время столкновения, используя формулу для кубических корней. Некоторые специалисты в численном анализе полагают, что использование формулы для кубических корней не является численно столь устойчивым, как использование поиска корней для полиномов.

=== Пространственное разбиение ===
Альтернативные алгоритмы можно сгруппировать по факту использования ими {{не переведено 2|Пространственное разбиение|пространственного разбиения|en|Space partitioning|Space partitioning}}, к которому относятся [[Двоичное разбиение пространства|BSP-деревья]], [[Октодерево|октодеревья]] и другие подобные подходы. Если применяемый алгоритм пространственного разбиения разделяет сцену с объектами на набор областей и если два объекта находятся в разных областях, то они не проверяются на пересечения. Так как BSP-деревья могут быть предварительно обсчитанными, этот подход хорошо подходит для обработки стен и других неподвижных препятствий в играх. Эти алгоритмы разбиения пространства, как правило, старее описанных выше алгоритмов.

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

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

Трёхмерные игры используют методы пространственного разбиения для «n-body pruning» и долгое время использовали для проверки попарных пересечений одну или несколько [[Ограничивающая сфера|ограничивающих сфер]] для одного трёхмерного объекта. Точные проверки проводились очень редко, за исключением игр, пытающихся относительно точно имитировать реальность. Но даже в этих случаях точные проверки на пересечение проводятся не всегда, а лишь в самых важных с точки зрения игры местах и/или ситуациях.

Исходя из того, что играм не нужно точно имитировать реальность, стабильность не является критически важной. Почти все игры используют [[#Различия априорного и апостериорного подходов|апостериорные методы]] обнаружения столкновений, и столкновения часто решаются путём применения очень простых правил. Например, если виртуальный персонаж «проваливается» в стену, он может быть просто перемещён назад, в его последнюю известную «правильную» позицию. Некоторые игры вообще не проводят обнаружения столкновений, а просто замеряют расстояние, пройденное персонажем, и если это расстояние равно или превышает некое заданное расстояние, которое он может пройти (например, длина комнаты — от стены до стены), то не дают ему двигаться далее.

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

Надёжный симулятор обнаружения и решения столкновений — это такой симулятор, который будет реагировать на любые входные данные разумно. Исходя из апостериорного подхода к обнаружению столкновений, можно предположить, что в [[Автосимулятор|гоночной игре]] игрок, разогнавшись на большой скорости на автомобиле, врежется в препятствие типа стены и система обнаружения столкновений обнаружит столкновение уже после того, как оно произошло, а в это время автомобиль уже будет «погружен» в стену или будет даже «падать в бесконечную пустоту», называемую «чёрный ад», «синий ад» либо «зелёный ад», в зависимости от доминантного цвета в [[Графический движок|графическом движке]]. Поэтому механизм апостериорного обнаружения столкновений должен корректным образом решать подобные ситуации. Одним из решений подобных ситуаций является концепция «непрерывного обнаружения столкновений» ({{lang-en|Continuous Collision Detection}}).<ref>{{cite web|url=http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf|title=Continuous Collision Detection and Physics|author=Erwin Coumans|publisher=[[Sony Computer Entertainment]]|datepublished=2005-08|access-date=2011-07-30|lang=en|format=[[PDF]]|archive-url=https://www.webcitation.org/663fGkOgJ?url=http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf|archive-date=2012-03-10|url-status=dead}}</ref>

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://web.archive.org/web/20110728131635/http://www.tsarevitch.org/ozcollide/ OZCollide] — свободная, быстрая и кроссплатформенная библиотека обнаружения столкновений
* [http://gamma.cs.unc.edu/research/collision/ Веб-сайт University of North Carolina at Chapel Hill], посвящённый исследованию обнаружения столкновений
* [http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances/ Статья] на сайте профессора Стивена Кэмерона ({{lang-en|Steven Cameron}}) из [[Оксфордский университет|Оксфордского университета]], посвящённая обнаружениям столкновений
* [http://demonstrations.wolfram.com/HowToAvoidACollision/ How to Avoid a Collision] — статья Джорджа Бека ({{lang-en|George Beck}}), [[Wolfram Demonstrations Project]]
* {{cite web|url=http://www.gamedev.ru/code/articles/?id=4194|title=Collision detection (определение столкновений)|author=IvanVR1|publisher=[[GameDev.ru]]|datepublished=2002-06-21|access-date=2011-07-29|archive-url=|archive-date=|url-status=live}}

[[Категория:Физические движки]]
[[Категория:Вычислительная физика]]
[[Категория:Робототехника]]
[[Категория:Компьютерная анимация]]
[[Категория:Механизмы компьютерных игр]]