The Theory Study Of Minkowski Sum Algorithm Based On Direct Mapping Mechanism

Collision detection technology is widely used in robotics, computer virtual simulation,and so on, and plays a very important role. With the rapid development of computertechnology, automatic control and multimedia technology, no matter the precisionrequirement for the robotic operation, or the visual effects requirement in the field ofvirtual simulation, have a higher demand, the traditional collision detection algorithms aredifficult to meet the needs. Therefore, the study of fast and accurate collision detectionalgorithm is an urgent problem to be solved. Minkowski sum, as a branch of computationgeometry, can determine the collision space of two polyhedron by accurately numericalcalculation, which can accurately detect whether two polyhedron is collision. Minkowskisum has become an effective method to collision detection. However, the computation ofMinkowski sum is much difficult, which limits its application as a technical bottleneck. So,the algorithm of Minkowski sum for convex polyhedron is researched in-deepth.First of all, the direct mapping method of convex polyhedron based on rhombohedronare proposed, and then a new Minkowski sum calculation method for convex polyhedronis given based on above direct mapping method. Through the analysis to the principles ofMinkowski sum surface, four kinds of contribution elements relationship who forms thesurface of Minkowski sum are given. In order to find these contribution elements, directmapping method is given. With this method, the elements including faces, edges andvertices of convex polyhedron are directly mapped to two regular triangles, and then tofind two convex polyhedron’s contribution elements in two triangle mapping planes. Inthis way, the Minkowski sum of two convex polyhedron will be got.Secondly, aimed at the contribution elements relationship of the above four categoriesand triangle mapping plane, the traversal algorithm for overlay of triangle plane divisionsis given. Elements information of direct mapping is preserved by defined data structure inthe algorithm, which is expressed by red-black tree in order to realize search, intersectionand other operations quickly. with Planar sweep algorithm，the pairs of elements whoforms the face of Minkowski sum can be got. Thirdly, in view of the above pairs of elements, Minkowski sum algorithm for convexpolygon is put forward based on translation mapping. The algorithm can quickly constructMinkowski sum of two convex polygons through translate convex polygon’s edges.Because the pair of faces formed the face of Minkowski sum is parallel inthree-dimensional space, the algorithm is improved and a new Minkowski sum algorithmfor parallel convex polygon in three-dimensional is proposed. Thus, the overallMinkowski sum algorithm based on the direct mapping mechanism is realized completely.Finally, the proposed algorithm’s experiment is given, and compared the performancebetween the proposed algorithm and others to demonstrate the effectiveness of theproposed algorithm. Besides, based on Minkowski sum，collision detection algorithm isgiven，and the simulation experiment is also given to verify the practicability of theMinkowski sum method.