| Русский Русский | English English |
Главная Archive
23 | 09 | 2023

DOI: 10.14489/vkit.2017.06.pp.025-030

Емельянов А. И., Клименко А. С., Клименко С. В., Ротков С. И.
(c. 25-30)

Аннотация. Дано описание алгоритма детектирования столкновений между виртуальными объектами и точного физического моделирования контактных взаимодействий между ними. Представлены способы определения поверхностей объектов. Алгоритм основан на адаптивном рекурсивном делении области потенциального контакта между объектами. Доказана возможность параллелизации алгоритма и его эффективного выполнения на современных графических процессорах.

Ключевые слова:  детектирование столкновений; имитационное моделирование; параллельные вычисления на графических процессорах.


Emelyanov A. I., Klimenko A. S., Klimenko S. V., Rotkov S. I.
(pp. 25-30)

Abstract. This paper describes an algorithm for detecting collisions between virtual objects, for accurate physical modeling of contact interactions between them. The surface of each object can be determined by the most convenient way – polygonal meshes, analytic functions, etc. The algorithm is based on an adaptive recursive division of areas of potential contact between objects. He has a good ability to parallelize that enables efficient execution on its modern multiprocessor systems, particularly on graphics processors. Rapid progress of computer hardware nowadays, especially progress of graphics accelerators, allows to consider again approaches, which had been considered as too costly before. A collision detection algorithm, presented in the paper is one of them. In spite of that from the formal point of view it is quite costly it has very good parallelization abilities. So, on a hardware platform with a proper number of processing cores (for example, on a power graphics accelerator) this algorithm performance can be enough for real time tasks. The algorithm is based on recursive subdivision of potential contact regions. During this process adaptive recursive AABB (Axis-Aligned Bounding Box) trees approximating areas of existing contact between objects are created. The algorithm interacts with each scene object via a uniform abstract interface that provides answer to the question: if a specified spatial point is located outside the object or not? Each kind of objects implements this test in the way that is the most optimal for it. The algorithm provides result as a set of points approximating found contact areas. Each point of this set is supplemented by properties of surfaces that have found contacting at this point, such as normals, friction factors and so on. Density of the output point set depends on the predefined minimal size of AABB tree leaf (this parameter directly influences the detection precision and the cost as well). This kind of output is convenient for physically based collision response. The algorithm keeps the robustness if scene objects take deformations during modeling.

Keywords: Collision detection; Simulation; Parallel computing on graphics processing units.


А. И. Емельянов, А. С. Клименко (Институт физико-технической информатики, Протвино, Московская обл., Россия)
С. В. Клименко, С. И. Ротков (Нижегородский государственный архитектурно-строительный университет, Нижний Новгород, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript



A. I. Emelyanov, A. S. Klimenko (Institute of Computing for Physics and Technology, Protvino, Moscow region, Russia)
S. V. Klimenko, S. I. Rotkov (Nizhny Novgorod State University of Architecture and Civil Engineering, Nizhniy Novgorod, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript



1.Gottschalk S., Lin M. С., Manocha D. ObbTree: A Hierarchical Structure for Rapid Interference Detection // In Proc. of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH – 96). New York: ACM, 1996. P. 171 – 180. doi: 10.1145/237170.237244


1. Gottschalk S., Lin M. С., Manocha D. (1996). ObbTree: a hierarchical structure for rapid interference detection. In Proc. of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH – 96). (pp. 171-180). New York: ACM. doi: 10.1145/237170.237244
2. Van Den Bergen G. (1997). Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools, 2(4), pp. 1-13. doi: 10.1080/10867651.1997.10487480


Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:


и заполните  ФОРМУ 

Отправляя форму вы даете согласие на обработку персональных данных.



This article  is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:


and fill out the  FORM  




Rambler's Top100 Яндекс цитирования