Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Виявлення зіткнень (англ. collision detection) — назва групи математичних алгоритмів, які перевіряють зіткнення двох фізичних тіл. Термін «виявлення зіткнень» використовується в динамічних фізичних симуляціях, комп'ютерних іграх і в обчислювальній геометрії. Фізична симуляція, яка застосовується після виявлення зіткнення, називається «реакція на зіткнення» (англ. collision response). Алгоритми виявлення зіткнень є ключовими в різних фізичних симуляція та фізичних рушіях.
Огляд
В реальному житті зіткнення об'єктів трапляються дуже часто. Наприклад, для опису більярда, а саме для зіткнення більярдних кульок необхідно використовувати алгоритми виявлення зіткнень. Фізика руху більярдних кульок добре зрозуміла, вона описується за допомогою методик абсолютно твердого тіла та абсолютно пружного удару. Дається початковий опис ситуації із дуже точним фізичним описом більярдної дошки та кульок, початкова позиція всіх кульок. Також дається імпульс, прикладений до однієї кульки, який імовірно гадається гравцем, який б’є по кульці києм. Після цього за допомогою комп'ютерної програми, яка використовує алгоритми виявлення зіткнень, обчислюється траєкторія, точний рух та місця зупинки більярдних кульок. Програма для симуляції гри складалась би із кількох частин, одна із яких відповідала би за обчислення точних ударів між більярдними кульками. Числова симуляція даної гри є нестабільною: маленька похибка в будь-яких початкових параметрах чи обчисленнях призведе до суттєвого відхилення кінцевого результату. Комп'ютерні ігри мають подібні вимоги із єдиною дуже суттєвою відмінністю. В фізичних симуляція необхідна максимальна точність, яка може вимагати суттєвих апаратних ресурсів комп'ютера. Процес прорахунку виявлення зіткнень може тривати як завгодно довго. Комп'ютерні ігри є інтерактивними програмами реального часу, тому всі процеси і них мають проходити в режимі реального часу. Виявлення зіткнень в іграх має проходити максимально точно і в режимі реального часу. Компроміси можливі, але тільки до тих пір, поки результат моделювання задовольняє ігровий процес.
Виявлення зіткнень у фізичних моделюваннях
Фізичні симуляції відрізняються за способом, яким вони реагують на зіткнення. Деякі використовують м’якість матеріалу для обчислення сили, які і «вирішує» подальшу поведінку об’єктів. Саме так відбувається в реальному світі. Однак цей метод є має дуже складні розрахунки, які вимагають великої обчислювальної потужності комп’ютера. Крім того, багато тіл мають дуже незначну м’якість і при зіткненнях їхня пластична деформація є дуже незначною. Деякі методики фізичної симуляції оцінюють час зіткнення за допомогою лінійної екстраполяції, відміняють симуляцію і обчислюють зіткнення більш абстрактними методами законів збереження.
Деякі методи виконують ітерації лінійної екстраполяції (метод Ньютона), щоб обчислити час зіткнення із набагато більшою точністю, чим інша частина симуляції.
Після непружного зіткнення можуть виникати спеціальні стани ковзання та стани спокою. Для їх симуляції використовують так звані «обмежувачі» (англ. constrains). Обмежувачі унеможливлюють інерцію і таким чином уникають нестабільності. Реалізація стану спокою через використання графа сцени унеможливлює ковзання.
Другими словами, фізичні симуляції працюють по одному із двох методів:
- виявлення зіткнень проходить апостеріорно (після того, як виникло зіткнення);
- виявлення зіткнень проходить апріорно (до того, як виникло зіткнення).
Апостеріорні і апріорні алгоритми виявлення зіткнень
У випадку використання апостеріорного алгоритму фізична симуляція «рухається» маленькими часовими кроками. На кожному із кроків перевіряється, чи якісь об’єкти перетинаються або знаходяться настільки близько один до одного, що це можна вважати перетином. На кожному кроці створюється список всіх тіл, які перетинаються, і позиції та траєкторії цих об’єктів так чи інакше «фіксуються» для обчислення зіткнень. Цей метод називається апостеріорним (англ. a posteriori), тому що алгоритм фактично пропускає реальний момент зіткнення і фіксує його тоді, коли воно уже фактично відбулось і тоді, коли тіла, які зіткнулись, уже проникли одне в одного на ту чи іншу величину.
У випадку використання апріорного алгоритму створюється алгоритм виявлення зіткнень, який здатний дуже точно передбачити траєкторію фізичних тіл. Моменти зіткнень вираховуються із високою точністю і фізичні тіла ніколи не проникають одне в одного. Цей метод називається апріорним (англ. a priori), тому що алгоритм обчислює моменти зіткнення до того, як обновиться конфігурація фізичних тіл, тобто до фактичного зіткнення.
Основні переваги апостеріорного методу проявляються в наступному. Алгоритму виявлення зіткнень не потрібно обробляти велику кількість фізичних змінних і параметрів. На вхід алгоритму подається простий список фізичних тіл, а на виході алгоритм повертає список тіл, які пересікаються. Алгоритму виявлення зіткнень не потрібно «знати» про тертя, пружні удари чи, що гірше, непружні удари і пластичні тіла, які можуть деформуватися. Крім того, апостеріорні алгоритми на порядок простіші, чим апріорні. Апріорний алгоритм має «мати справу» із зміною часу, яка відсутня і апостеріорних алгоритмах. Із другої сторони, апостеріорні алгоритми викликають проблему «фіксації» кроку, коли взаємопроникнення тіл (які є фізично некоректні) мають бути скоректовані. Крім того, апостеріорні алгоритми за своїм принципом неточні і ніколи не зможуть досягнути «ідеальної» точності. Адже зіткнення тіл визначається лише тоді, коли воно відбулося, і за період часу від його виникнення до «виявлення» тіла встигнуть взаємопроникнути одне в одного. Щоб уникнути цього, необхідно зменшити час кроку «фіксації» до нескінченості, що є неможливим.
Перевагою апріорних алгоритмів є висока точність і стабільність. Є складним (але не повністю неможливим) відділення фізичної симуляції від алгоритму виявлення зіткнень.
Посилання
- Prof. Steven Cameron (Oxford University) web site on collision detection [ 12 жовтня 2007 у Wayback Machine.]
- How to Avoid a Collision [ 6 грудня 2009 у Wayback Machine.] by George Beck, .
- Basic collision detection in OpenGL [ 22 червня 2009 у Wayback Machine.].
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Viyavlennya zitknen angl collision detection nazva grupi matematichnih algoritmiv yaki pereviryayut zitknennya dvoh fizichnih til Termin viyavlennya zitknen vikoristovuyetsya v dinamichnih fizichnih simulyaciyah komp yuternih igrah i v obchislyuvalnij geometriyi Fizichna simulyaciya yaka zastosovuyetsya pislya viyavlennya zitknennya nazivayetsya reakciya na zitknennya angl collision response Algoritmi viyavlennya zitknen ye klyuchovimi v riznih fizichnih simulyaciya ta fizichnih rushiyah OglyadBilyardni kuli sho vdaryayut odna odnu ye klasichnim prikladom zastosovnim u galuzi viyavlennya zitknen V realnomu zhitti zitknennya ob yektiv traplyayutsya duzhe chasto Napriklad dlya opisu bilyarda a same dlya zitknennya bilyardnih kulok neobhidno vikoristovuvati algoritmi viyavlennya zitknen Fizika ruhu bilyardnih kulok dobre zrozumila vona opisuyetsya za dopomogoyu metodik absolyutno tverdogo tila ta absolyutno pruzhnogo udaru Dayetsya pochatkovij opis situaciyi iz duzhe tochnim fizichnim opisom bilyardnoyi doshki ta kulok pochatkova poziciya vsih kulok Takozh dayetsya impuls prikladenij do odniyeyi kulki yakij imovirno gadayetsya gravcem yakij b ye po kulci kiyem Pislya cogo za dopomogoyu komp yuternoyi programi yaka vikoristovuye algoritmi viyavlennya zitknen obchislyuyetsya trayektoriya tochnij ruh ta miscya zupinki bilyardnih kulok Programa dlya simulyaciyi gri skladalas bi iz kilkoh chastin odna iz yakih vidpovidala bi za obchislennya tochnih udariv mizh bilyardnimi kulkami Chislova simulyaciya danoyi gri ye nestabilnoyu malenka pohibka v bud yakih pochatkovih parametrah chi obchislennyah prizvede do suttyevogo vidhilennya kincevogo rezultatu Komp yuterni igri mayut podibni vimogi iz yedinoyu duzhe suttyevoyu vidminnistyu V fizichnih simulyaciya neobhidna maksimalna tochnist yaka mozhe vimagati suttyevih aparatnih resursiv komp yutera Proces prorahunku viyavlennya zitknen mozhe trivati yak zavgodno dovgo Komp yuterni igri ye interaktivnimi programami realnogo chasu tomu vsi procesi i nih mayut prohoditi v rezhimi realnogo chasu Viyavlennya zitknen v igrah maye prohoditi maksimalno tochno i v rezhimi realnogo chasu Kompromisi mozhlivi ale tilki do tih pir poki rezultat modelyuvannya zadovolnyaye igrovij proces Viyavlennya zitknen u fizichnih modelyuvannyahFizichni simulyaciyi vidriznyayutsya za sposobom yakim voni reaguyut na zitknennya Deyaki vikoristovuyut m yakist materialu dlya obchislennya sili yaki i virishuye podalshu povedinku ob yektiv Same tak vidbuvayetsya v realnomu sviti Odnak cej metod ye maye duzhe skladni rozrahunki yaki vimagayut velikoyi obchislyuvalnoyi potuzhnosti komp yutera Krim togo bagato til mayut duzhe neznachnu m yakist i pri zitknennyah yihnya plastichna deformaciya ye duzhe neznachnoyu Deyaki metodiki fizichnoyi simulyaciyi ocinyuyut chas zitknennya za dopomogoyu linijnoyi ekstrapolyaciyi vidminyayut simulyaciyu i obchislyuyut zitknennya bilsh abstraktnimi metodami zakoniv zberezhennya Deyaki metodi vikonuyut iteraciyi linijnoyi ekstrapolyaciyi metod Nyutona shob obchisliti chas zitknennya iz nabagato bilshoyu tochnistyu chim insha chastina simulyaciyi Pislya nepruzhnogo zitknennya mozhut vinikati specialni stani kovzannya ta stani spokoyu Dlya yih simulyaciyi vikoristovuyut tak zvani obmezhuvachi angl constrains Obmezhuvachi unemozhlivlyuyut inerciyu i takim chinom unikayut nestabilnosti Realizaciya stanu spokoyu cherez vikoristannya grafa sceni unemozhlivlyuye kovzannya Drugimi slovami fizichni simulyaciyi pracyuyut po odnomu iz dvoh metodiv viyavlennya zitknen prohodit aposteriorno pislya togo yak viniklo zitknennya viyavlennya zitknen prohodit apriorno do togo yak viniklo zitknennya Aposteriorni i apriorni algoritmi viyavlennya zitknen U vipadku vikoristannya aposteriornogo algoritmu fizichna simulyaciya ruhayetsya malenkimi chasovimi krokami Na kozhnomu iz krokiv pereviryayetsya chi yakis ob yekti peretinayutsya abo znahodyatsya nastilki blizko odin do odnogo sho ce mozhna vvazhati peretinom Na kozhnomu kroci stvoryuyetsya spisok vsih til yaki peretinayutsya i poziciyi ta trayektoriyi cih ob yektiv tak chi inakshe fiksuyutsya dlya obchislennya zitknen Cej metod nazivayetsya aposteriornim angl a posteriori tomu sho algoritm faktichno propuskaye realnij moment zitknennya i fiksuye jogo todi koli vono uzhe faktichno vidbulos i todi koli tila yaki zitknulis uzhe pronikli odne v odnogo na tu chi inshu velichinu U vipadku vikoristannya apriornogo algoritmu stvoryuyetsya algoritm viyavlennya zitknen yakij zdatnij duzhe tochno peredbachiti trayektoriyu fizichnih til Momenti zitknen virahovuyutsya iz visokoyu tochnistyu i fizichni tila nikoli ne pronikayut odne v odnogo Cej metod nazivayetsya apriornim angl a priori tomu sho algoritm obchislyuye momenti zitknennya do togo yak obnovitsya konfiguraciya fizichnih til tobto do faktichnogo zitknennya Osnovni perevagi aposteriornogo metodu proyavlyayutsya v nastupnomu Algoritmu viyavlennya zitknen ne potribno obroblyati veliku kilkist fizichnih zminnih i parametriv Na vhid algoritmu podayetsya prostij spisok fizichnih til a na vihodi algoritm povertaye spisok til yaki peresikayutsya Algoritmu viyavlennya zitknen ne potribno znati pro tertya pruzhni udari chi sho girshe nepruzhni udari i plastichni tila yaki mozhut deformuvatisya Krim togo aposteriorni algoritmi na poryadok prostishi chim apriorni Apriornij algoritm maye mati spravu iz zminoyu chasu yaka vidsutnya i aposteriornih algoritmah Iz drugoyi storoni aposteriorni algoritmi viklikayut problemu fiksaciyi kroku koli vzayemoproniknennya til yaki ye fizichno nekorektni mayut buti skorektovani Krim togo aposteriorni algoritmi za svoyim principom netochni i nikoli ne zmozhut dosyagnuti idealnoyi tochnosti Adzhe zitknennya til viznachayetsya lishe todi koli vono vidbulosya i za period chasu vid jogo viniknennya do viyavlennya tila vstignut vzayemoproniknuti odne v odnogo Shob uniknuti cogo neobhidno zmenshiti chas kroku fiksaciyi do neskinchenosti sho ye nemozhlivim Perevagoyu apriornih algoritmiv ye visoka tochnist i stabilnist Ye skladnim ale ne povnistyu nemozhlivim viddilennya fizichnoyi simulyaciyi vid algoritmu viyavlennya zitknen PosilannyaProf Steven Cameron Oxford University web site on collision detection 12 zhovtnya 2007 u Wayback Machine How to Avoid a Collision 6 grudnya 2009 u Wayback Machine by George Beck Basic collision detection in OpenGL 22 chervnya 2009 u Wayback Machine