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

Емельянов А. И., Клименко А. С., Клименко С. В., Ротков С. И.
ДЕТЕКТИРОВАНИЕ СТОЛКНОВЕНИЙ ДЛЯ ЗАДАЧ ИНТЕРАКТИВНОГО ВЗАИМОДЕЙСТВИЯ ВИРТУАЛЬНЫХ ОБЪЕКТОВ (Окончание)
(c. 25-30)

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

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

Emelyanov A. I., Klimenko A. S., Klimenko S. V., Rotkov S. I.
COLLISION DETECTION ISSUES FOR INTERACTION OF VIRTUAL OBJECTS (Continuation)
(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.