Виявлення зіткнень (англ.collision detection) — назва групи математичних алгоритмів, які перевіряють зіткнення двох фізичних тіл. Термін «виявлення зіткнень» використовується в динамічних фізичних симуляціях, комп'ютерних іграх і в обчислювальній геометрії. Фізична симуляція, яка застосовується після виявлення зіткнення, називається «реакція на зіткнення» (англ.collision response). Алгоритми виявлення зіткнень є ключовими в різних фізичних симуляція та фізичних рушіях.
Огляд
Більярдні кулі, що вдаряють одна одну є класичним прикладом застосовним у галузі виявлення зіткнень.
В реальному житті зіткнення об'єктів трапляються дуже часто. Наприклад, для опису більярда, а саме для зіткнення більярдних кульок необхідно використовувати алгоритми виявлення зіткнень. Фізика руху більярдних кульок добре зрозуміла, вона описується за допомогою методик абсолютно твердого тіла та абсолютно пружного удару. Дається початковий опис ситуації із дуже точним фізичним описом більярдної дошки та кульок, початкова позиція всіх кульок. Також дається імпульс, прикладений до однієї кульки, який імовірно гадається гравцем, який б’є по кульці києм. Після цього за допомогою комп'ютерної програми, яка використовує алгоритми виявлення зіткнень, обчислюється траєкторія, точний рух та місця зупинки більярдних кульок. Програма для симуляції гри складалась би із кількох частин, одна із яких відповідала би за обчислення точних ударів між більярдними кульками. Числова симуляція даної гри є нестабільною: маленька похибка в будь-яких початкових параметрах чи обчисленнях призведе до суттєвого відхилення кінцевого результату.
Комп'ютерні ігри мають подібні вимоги із єдиною дуже суттєвою відмінністю. В фізичних симуляція необхідна максимальна точність, яка може вимагати суттєвих апаратних ресурсів комп'ютера. Процес прорахунку виявлення зіткнень може тривати як завгодно довго. Комп'ютерні ігри є інтерактивними програмами реального часу, тому всі процеси і них мають проходити в режимі реального часу. Виявлення зіткнень в іграх має проходити максимально точно і в режимі реального часу. Компроміси можливі, але тільки до тих пір, поки результат моделювання задовольняє ігровий процес.
Виявлення зіткнень у фізичних моделюваннях
Фізичні симуляції відрізняються за способом, яким вони реагують на зіткнення. Деякі використовують м’якість матеріалу для обчислення сили, які і «вирішує» подальшу поведінку об’єктів. Саме так відбувається в реальному світі. Однак цей метод є має дуже складні розрахунки, які вимагають великої обчислювальної потужності комп’ютера. Крім того, багато тіл мають дуже незначну м’якість і при зіткненнях їхня пластична деформація є дуже незначною. Деякі методики фізичної симуляції оцінюють час зіткнення за допомогою лінійної екстраполяції, відміняють симуляцію і обчислюють зіткнення більш абстрактними методами законів збереження.
Деякі методи виконують ітерації лінійної екстраполяції (метод Ньютона), щоб обчислити час зіткнення із набагато більшою точністю, чим інша частина симуляції.
Після непружного зіткнення можуть виникати спеціальні стани ковзання та стани спокою. Для їх симуляції використовують так звані «обмежувачі» (англ.constrains). Обмежувачі унеможливлюють інерцію і таким чином уникають нестабільності. Реалізація стану спокою через використання графа сцени унеможливлює ковзання.
Другими словами, фізичні симуляції працюють по одному із двох методів:
виявлення зіткнень проходить апостеріорно (після того, як виникло зіткнення);
виявлення зіткнень проходить апріорно (до того, як виникло зіткнення).
Апостеріорні і апріорні алгоритми виявлення зіткнень
У випадку використання апостеріорного алгоритму фізична симуляція «рухається» маленькими часовими кроками. На кожному із кроків перевіряється, чи якісь об’єкти перетинаються або знаходяться настільки близько один до одного, що це можна вважати перетином. На кожному кроці створюється список всіх тіл, які перетинаються, і позиції та траєкторії цих об’єктів так чи інакше «фіксуються» для обчислення зіткнень. Цей метод називається апостеріорним (англ.a posteriori), тому що алгоритм фактично пропускає реальний момент зіткнення і фіксує його тоді, коли воно уже фактично відбулось і тоді, коли тіла, які зіткнулись, уже проникли одне в одного на ту чи іншу величину.
У випадку використання апріорного алгоритму створюється алгоритм виявлення зіткнень, який здатний дуже точно передбачити траєкторію фізичних тіл. Моменти зіткнень вираховуються із високою точністю і фізичні тіла ніколи не проникають одне в одного. Цей метод називається апріорним (англ.a priori), тому що алгоритм обчислює моменти зіткнення до того, як обновиться конфігурація фізичних тіл, тобто до фактичного зіткнення.
Основні переваги апостеріорного методу проявляються в наступному. Алгоритму виявлення зіткнень не потрібно обробляти велику кількість фізичних змінних і параметрів. На вхід алгоритму подається простий список фізичних тіл, а на виході алгоритм повертає список тіл, які пересікаються. Алгоритму виявлення зіткнень не потрібно «знати» про тертя, пружні удари чи, що гірше, непружні удари і пластичні тіла, які можуть деформуватися. Крім того, апостеріорні алгоритми на порядок простіші, чим апріорні. Апріорний алгоритм має «мати справу» із зміною часу, яка відсутня і апостеріорних алгоритмах.
Із другої сторони, апостеріорні алгоритми викликають проблему «фіксації» кроку, коли взаємопроникнення тіл (які є фізично некоректні) мають бути скоректовані. Крім того, апостеріорні алгоритми за своїм принципом неточні і ніколи не зможуть досягнути «ідеальної» точності. Адже зіткнення тіл визначається лише тоді, коли воно відбулося, і за період часу від його виникнення до «виявлення» тіла встигнуть взаємопроникнути одне в одного. Щоб уникнути цього, необхідно зменшити час кроку «фіксації» до нескінченості, що є неможливим.
Перевагою апріорних алгоритмів є висока точність і стабільність. Є складним (але не повністю неможливим) відділення фізичної симуляції від алгоритму виявлення зіткнень.
