Обнаруже́ние столкнове́ний (англ. Collision detection) — вычислительная проблема обнаружения пересечений между собой двух или более объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о коллекторе контакта (набор пересечения точек)[1]. Реакция на столкновение (что происходит, когда столкновение обнаружено) зависит от конкретного моделируемого процесса. В алгоритмах обнаружения столкновений широко применяются понятия из линейной алгебры и вычислительной геометрии. Алгоритмы обнаружения столкновений являются одной из основных составляющих физики трёхмерных компьютерных игр.
Функционирование физической модели подразумевает проведение физических экспериментов, например игры в бильярд. Физика сталкивающихся бильярдных шаров хорошо описана физикой твёрдого тела и теорией абсолютно упругого удара. Начальные условия задаются абсолютно точными физическими характеристиками бильярдного стола и шаров, а также изначальными координатами шаров. Имея заданное ускорение шара «битка» (предположительно появившегося в результате удара игрока кием по битку), мы хотим вычислить точные траектории движения, скорости и места остановки всех шаров с помощью компьютерной программы. Физический движок, моделирующий бильярд, будет состоять из нескольких компонентов, один из которых будет отвечать за точное вычисление столкновений между шарами. Этот компонент является примером нестабильной части модели — небольшие ошибки в вычислениях столкновений будут приводить к значительным изменениям в результатах — конечных положениях шаров на столе.
Компьютерные игры предъявляют к физическим движкам примерно те же требования, за исключением некоторых существенных отличий. В то время как моделирование физических опытов требует создания максимально точного математического аппарата, описывающего реальный мир, компьютерные игры нуждаются в физике лишь правдоподобно выглядящей, но при этом вычисляемой в режиме реального времени, пусть и грубо. Компромиссы допускаются, пока это устраивает игрока и имеет приемлемый визуальный реализм. Поэтому тело, которое проверяется на столкновение, — так называемый хитбокс или коллайдер — проще, чем трёхмерная модель персонажа.
Физические движки отличаются способами, которыми они реагируют на столкновения. Некоторые используют гибкость материалов для вычисления силы, возникающей в результате столкновения и влияющей на результат столкновения в последующие временные интервалы, что достаточно затратно с точки зрения вычислительных ресурсов. Некоторые модели вычисляют аппроксимированное время столкновения с помощью линейной интерполяции, после чего «откатывают» состояние сцены на некоторый момент времени и просчитывают столкновение на основе законов сохранения энергии.