Analysis of collision detection algorithms in three-dimensional virtual environments

Nekvrytyi I.; Antonenko S.

doi:10.34185/1562-9945-4-153-2024-11

Автор(и)

Nekvrytyi I.
Antonenko S.

DOI:

https://doi.org/10.34185/1562-9945-4-153-2024-11

Ключові слова:

виявлення зіткнень, алгоритми 3D-ігор, комп'ютерна графіка, R-дерева, обмежувальні рамки, бенчмарк продуктивності, інновації, обробка моделей.

Анотація

Актуальність теми дослідження полягає у значній обчислювальній складності виявлення зіткнень у реальному часі у віртуальних середовищах, що часто забирає до 50% часу виконання програми, а в деяких випадках і більше. У реальних симуляціях тривимірні прототипи можуть бути дуже складними і містити тисячі примітивів. Тому розробка алгоритмів виявлення зіткнень у реальному часі для складних середовищ залишається актуальною науковою проблемою. Підтримка частоти кадрів не менше 30 кадрів в секунду має вирішальне значення для створення зручного для користувача симулятора в таких середовищах. Проблема виявлення зіткнень у віртуальних середовищах стає ще більш складною під час вузької фази. Широка фаза виявлення зіткнень відповідає за відсіювання пар об'єктів, які не зіткнуться через достатньо велику відстань між ними. Вузька фаза визначає, чи зіткнуться два об'єкти, якщо відстань між ними дозволяє таку можливість. У цій статті описано алгоритм виявлення зіткнень, який базується на структурі R-дерев вирівняних по осях обмежувальних границь (AABB) і використовує метод орієнтованого перетину обмежувальних границь (OAABB) для вирішення вузької фази виявлення зіткнень, яка знаходить перетини між двома об'єктами. Експериментальні результати демонструють, що алгоритм, представлений у цій статті, ідентифікує перетини зі значними швидкостями взаємодії. Експериментальні результати демонструють, що алгоритм, представлений у цій статті, ідентифікує перетини зі значними швидкостями взаємодії.

Посилання

Review of algorithms for 3D object collision detection. Access mode: https://www.inesc-id.pt/ficheiros/publicacoes/7101.pdf

Algorithms for broad-phase collision detection. Access mode: https://d2l.ai/chapter_computer-vision/bounding-box.html

Classical hierarchical collision detection scheme. Access mode: https://cgvr.cs.uni-bremen.de/papers/wscg03/wscg_ext.pdf

[Zachmann03] G. Zachman, and G. Knittel, "An Architecture for Hierarchical Col-lision Detection," Proceedings of WSCG' 2003, the 11th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2003, Czech Republic, 2003.

Efficient operations with R-trees. Access mode: https://www.bartoszsypytkowski.com/r-tree/

Object intersection search using R-trees. Access mode: https://www.researchgate.net/publication/236611860_A_Collision_Detection_Algorithm_for_Polygonal_Models_that_uses_Sequential_and_Parallel_Techniques_for_Improving_Performance

[Guige03] Guige, P. and Devillers, O., 2003. Fast and Robust Triangle-Triangle Overlap Test using Orientation Predicates. Journal of Graphics Tools, 8, 1, 25-42

Review of Siemens Kineo application. Access mode: https://plm.sw.siemens.com/en-US/plm-components/kineo/kineoworks/