Research On The Sum Of The Minkowski Sum Of Polyhedral Models In 3D

Computational Geometry is a new and fearfully vigorous subfield in the theoretical computer science field. Minkowski sum algorithm has the great significance in theory and application as an embranchment of Computational Geometry. It plays an important role in computer graphics, robotics, Geography DB, and so on.Firstly, this paper researches the existed approach of Minkowski sum of two convex polyhedra. In order to improve the efficiency of the algorithm, this paper optimizes the algrithm of the Regular Tetrahedron Central Projection to compute exact minkowski sum of convex polyhedra, proposes the method of Regular Tetrahedron Gaussian Map to resolve this problem. At the same time, the complexity of the algorithm are analyzed and compared.Secondly, for effectual computing the Minkowski sum of non-convex polyhedra, this paper introduces a new algorithm after researched many kinds of the approaches of decomposition, which decomposes them by the method of tetrahedral decomposition or surface decomposition arrcording to the attribute of the 3D geometrical modeling. At the same time, the complexity of the algorithm is analyzed.Thirdly, for improving the efficiency of the union algorithm, this paper introduces an optimal algorithm to unite the boundary of the polyhedra Minkowski sum of the sub polyhedra used the reformative approach of the Enhanced Marching Cubes. At the same time, this paper researches the process of the algorithm of Minkowski sum of any simple polyhedra, and introduces a new algorithm to improve the efficiency and precision.Finally, our experimental results show that the algorithm of Minkowski sum of any simple polyhedra is valid and feasible. At the same time, some comparisons and analysis also are done with the traditional algorithm.