Research On Computing Minkowski Sum Of Non-Convex Polyhedral In Thress Demension

Computational Geometry is an important embranchment of computer theoretical science. The subject has already made a tremendous development and produced a series of theoretical results. Minkowski sum algorithm has the great significance in theory and application as an embranchment of Computational Geometry. It plays an important role in robotics, dynamic simulation, computer graphics, and so on, especially in the field of robotics, it is an important tool for computing collision-free path. Therefore, how to calculate the path of obstacle avoidance quickly and accurately has been an important research subject of the home and foreign scholars.Firstly, this paper researches the existed approach of Minkowski sum of two convex polyhedral. In order to reduce the amount of computing overlay of two planar subdivisions and improve the efficiency of the algorithm, this paper proposes a new algorithm for computing exact Minkowksi sum that based on Regular Tetrahedron Map and Point Projection. Through this method, it can reduce the problem in 3D to 2D.Secondly, convex decomposition is an important step of computing Minkowski sum of two non-convex polyhedral. So, for effectively computing the Minkowski sum of non-convex polyhedral, the papers uses the methods of set theory and graph theory and propose a new algorithm to decompose non-convex polyhedron that based on Successful Loop after studying the convex decomposition algorithms. At the same time, the complexity of the algorithm is analyzed.Thirdly, the paper gives the algorithm of computing the Minkowski sum of non-convex polyhedral. It uses Successful Loop to decompose non-convex polyhedral into convex pieces, then computes their pair wise Minkowski sum that based on Regular Tetrahedron Map and Point Projection, last, uses the reformative approach of the Enhanced Marching Cubes to unite the boundary of polyhedral Minkowski sum of the sub polyhedral.Finally, we validate the above algorithm and give the results. We also do some comparison and analysis with the existing algorithm.