Collision detection for 3d objects
based on Fourier-Motzkin elimination method


Download this article (5Mo) for free :

If it has been useful to you,
please consider supporting me
by purchasing the paper version :

By Pascal Baillehache
This article introduces a way to detect collision between 3D objects approximated by set of parallelepipeds and tetrahedrons in software applications. After demonstrating that this problem is equivalent to the resolution of a linear inequations system, I show how to apply the Fourier-Motzkin elimination method to solve it. Then I introduce all the necessary algorithms to implement a complete solution. Finally, illustrated results prove the validity of the algorithm, and performance measurements ensure it's appropriate to real-time applications such as video games. For example, it takes less than 0.01s to test collision between one object defined by 200 primitives and 300 other objects on a standard 3.3GHz microprocessor. In the conclusion, I also suggest ways to improve the speed of the algorithms.
The content of this webpage, the pdf article and the blurb book is Copyright 2013 Pascal Baillehache (Pascal at BayashiInJapan dot net). The algorithms introduced in the article and the book are free to use and modify.
Page seen 2448 times.