Collision detection algorithms of bounding cylinders with terrain model

Е.V. Strashnov, M.A. Torgashev


This paper considers the task of collision detection for bounding cylinders surrounding the geometry of virtual objects with a terrain. To solve this task, an approach is proposed in which the cylinder is defined analytically, and the terrain is represented as a regular rectangular polygonal mesh. As part of the proposed approach, algorithms have been developed in which the intersection is determined depending on the relative position of the cylinder and the plane of the polygonal mesh element (rectangle or triangle). These algorithms consist of several stages and allow to detect both the fact of the intersection and calculate the necessary contact information about intersection. The proposed solutions are based on fast geometric tests, which are actively used in computer graphics, and that allows to effectively implement algorithms on both CPU and GPU.

The developed algorithms for collision detection of bounding cylinders with terrain were implemented in the form of software modules. Approbation of these modules in the created software package of the virtual environment showed the adequacy and effectiveness of the proposed solutions in this paper.

Full Text:

PDF (Russian)


C. Eicson, Real-time collision detection. San Francisco: Morgan Kaufmann Publishers, 2005.

Bounding volume. Available:

J. Huynh, "Separating axis theorem for oriented bounding boxes," 2009,


D. Gregorius, "The separating axis test," In GDC, 2013.

L. Olvang, "Real-time collision detection with implicit objects," Department of Information Technology, Uppsala University, Sweden, 2010.

A. V. Sannikov, "Numerical simulation of rigid, deformable and stiff bodies," Ph.D. dissertation, Moscow, 2015.

G. van den Bergen, and D. Gregorius, Game physics pearls, AK Peters/CRC Press, 2010.

J.A. Newth, "Minkowski portal refinement and speculative contacts in Box2D," Master’s Projects, 2013.

D. Gregorius, "Implementing quickhull," Game Developers Conference (Valve Software) in San Francisco, 2014.

F.J. Melero, A. Aguilera, and F.R. Feito, "Fast collision detection between high resolution polygonal models," Computers & Graphics, 2019, pp. 97-106.

N. Backman, "Collision detection of triangle meshes using GPU," Master’s thesis, Umea University, 2010.

A. Moravanszky, and P. Terdiman, "Fast Contact Reduction for Dynamics Simulation," In Game Programming Gems 4, Charles River Media, 2004, pp. 253–263.

P. Terdiman, "Contact generation for meshes", Available:

E.-A. Karabassi, G. Papaioannou, T. Theoharis, and A. Boehm, "Intersection test for collision detection in particle systems," Journal of Graphic Tools, 1999, pp. 25-37.

M. G. Coutinho, Dynamic simulation of multibody systems. Springer, 2001

E.V. Strashnov, and L.A. Finagin, "Collision detection of bounding spheres with terrain," Proceedings of NIISI RAS, Vol. 9, No. 5, 2019, pp. 111-118.

E.V. Strashnov, and D.V. Omelchenko, "Collision detection of bounding cylinders with spheres and a plane," Proceedings of NIISI RAS, Vol. 8, No. 2, 2018, pp. 92-97.

M. Cyrus, and J. Beck. "Generalized two- and three-dimensional clipping," Computers & Graphics, 1978, pp. 23–28.

E.V. Strashnov, and M.V. Mikhaylyuk, "Methods for robotic manipulator force control in virtual environment systems," International Journal of Open Information Technologies, Vol. 7, No. 9, 2019, pp. 39-45.

P. Yu. Timokhin, M.V. Mikhaylyuk, and A.V. Maltsev, "Real-time construction on the GPU of adaptive terrestrial relief model based on the spheroid," International Journal of Open Information Technologies, Vol. 7, No. 10, 2019, pp. 22-35.


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162