Fast Collision Detection Algorithm of Polyhedra Based on the Minkowski Sum
Xiaocai Zhang · Journal of Chinese Computer Systems · 2012
In order to further improve the immediacy of collision detection,a fast collision detection algorithm of polyhedra is proposed based on the Minkowski sum.The algorithm does not need to accurately measured the shortest distance between two polyhedra.Firstly,the collision detection problem is converted to inspecting whether the origin is in the Minkowski sum by structuring the Minkowski sum of two polyhedra.Secondly,the three-dimensional problem is converted to the two-dimensional problem by ray and the intersection calculation.Then,the polyhedra collision is detected by estimating whether the origin is in the planar polygon,and the real-time and reliability of collision detection are improved.To test the presented algorithm,a motion planning control system is studied with OpenGL graphics library in Visual C# environment.Experimental results indicate that its average detection efficiency is markedly superior to traditional algorithms and it reduces the storage space and time complexity effectively.