|
DOI: 10.14489/vkit.2017.05.pp.039-044
Емельянов А. И., Клименко А. С., Клименко С. В., Ротков С. И.
ДЕТЕКТИРОВАНИЕ СТОЛКНОВЕНИЙ ДЛЯ ЗАДАЧ ИНТЕРАКТИВНОГО ВЗАИМОДЕЙСТВИЯ ВИРТУАЛЬНЫХ ОБЪЕКТОВ
(c. 39-44)
Аннотация. Дано описание алгоритма детектирования столкновений между виртуальными объектами и точного физического моделирования контактных взаимодействий между ними. Представлены способы определения поверхностей объектов. Алгоритм основан на адаптивном рекурсивном делении области потенциального контакта между объектами. Доказана возможность параллелизации алгоритма и его эффективного выполнения на современных графических процессорах.
Ключевые слова: детектирование столкновений; имитационное моделирование; параллельные вычисления на графических процессорах.
Emelyanov A. I., Klimenko A. S., Klimenko S. V., Rotkov S. I.
COLLISION DETECTION ISSUES FOR INTERACTION OF VIRTUAL OBJECTS
(pp. 39-44)
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.
А. И. Емельянов, PhD, А. С. Клименко (Институт физико-технической информатики, Протвино, Московская обл., Россия)
С. В. Клименко, С. И. Ротков (Нижегородский государственный архитектурно-строительный университет, Нижний Новгород, Россия) 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
2. Van Den Bergen G. Efficient Collision Detection of Complex Deformable Models using AABB Trees // Journal of Graphics Tools. 1997. V. 2, № 4. P. 1 – 13.
3. Cohen J., Lin M. С., Manocha D., Ponamgi M. I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments // In Proc. of 1995 Symp. Interactive 3D Graphics Conference (I3D – 95), Monterey, California, USA, April 09 – 12 1995. New York: ACM, 1995. P. 189 – 196.
4. Preparata F. P., Shamos M. I. Computational Geometry: an Introduction. New York: Springer-Verlag, 1985. 398 p.
5. Lin M. C., Canny J. F. A Fast Algorithm for Incremental Distance Computation // In IEEE Conf. on Robotics and Automation (ICRA – 1991), 9 – 11 April 1991. IEEE, 1991. P. 1008 – 1014.
6. Lin M. C. Efficient Collision Detection for Animation and Robotics // PhD thesis, Department of Electrical Engineering and Computer Science. University of California, Berkeley, 1993. 294 p.
7. Naylor B., Amanatides J., Thibault W. Merging BSP Trees Yield Polyhedral Set Operations // In Proc. of Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH – 1990), Dallas, TX, USA. New York: ACM, 1990. V. 24, № 3. P. 115 – 124.
8. Samet H. Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods. Addison Wesley, 1989. 18 p.
9. Ahuja N., Chien R. T., Bridwell N. Interference Detection and Collision Avoidance among Three Dimension Objects // In Proc. of the First AAAI Conference on Artificial Intelligence (AAAI – 80), Stanford, California, August 18 – 21 1980. Stanford, 1980. P. 44 – 48.
10. Hayward V. Fast Collision Detection by Recursive Decomposition of a Manipulator Workspace // In Proc. of the IEEE International Conference on Robotics and Automation, San Francisco, CA, 7 – 10 April 1986. IEEE, 1986. V. 2. P. 1044 – 1049. doi: 10.1109/ROBOT.1986.1087620
11. Duff T. Interval Arithmetic and Recursive Subdivision for Implicit Functions and Constructive Solid Geometry // In Proc. of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH – 92). New York: ACM, 1992. V. 26, № 2. P. 131 – 138. doi: 10.1145/142920.134027
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). New York: ACM, pp. 171 – 180. 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
3. Cohen J., Lin M. С., Manocha D., Ponamgi M. (1995). I-COLLIDE: An interactive and exact collision detection system for large-scale environments. In Proc. of 1995 Symp. Interactive 3D Graphics Conference (I3D – 95). (pp. 189-196). Monterey, California, USA, April 09 – 12 1995. New York: ACM. doi: 10.1145/199404.199437
4. Preparata F. P., Shamos M. I. (1985). Computational geometry: an introduction. New York: Springer-Verlag.
5. Lin M. C., Canny J. F. (1991). A fast algorithm for incremental distance computation. In IEEE Conf. on Robotics and Automation (ICRA – 1991), 9 – 11 April 1991, (pp. 1008-1014).
6. Lin M. C. (1993). Efficient collision detection for animation and robotics. PhD thesis, Department of Electrical Engineering and Computer Science. University of California, Berkeley.
7. Naylor B., Amanatides J., Thibault W. (1990). Merging BSP trees yield polyhedral set operations. In Proc. of Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH – 1990), Dallas, TX, USA. New York: ACM, 24(3), pp. 115-124. doi: 10.1145/97879.97892
8. Samet H. (1989). Spatial data structures: quadtree, octrees and other hierarchical methods. Addison Wesley.
9. Ahuja N., Chien R. T., Bridwell N. (1980). Interference detection and collision avoidance among three dimension objects. In Proc. of the First AAAI Conference on Artificial Intelligence (AAAI – 80), (pp. 44-48). Stanford, California, August 18 – 21 1980.
10. Hayward V. (1986). Fast collision detection by recursive decomposition of a manipulator workspace. In Proc. of the IEEE International Conference on Robotics and Automation, Vol. 2. (pp. 1044-1049). San Francisco, CA, 7 – 10 April 1986. IEEE. doi: 10.1109/ROBOT.1986.1087620
11. Duff T. (1992). Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry. In Proc. of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH – 92). New York: ACM, 26(2), pp. 131-138. doi: 10.1145/142920.134027
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2017.05.pp.039-044
и заполните ФОРМУ
Отправляя форму вы даете согласие на обработку персональных данных.
.
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:
10.14489/vkit.2017.05.pp.039-044
and fill out the FORM
.
|
Archive
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»