Research On Computing Union Of Sub-Minkowski Sum Of Non-Convex Polyhedral

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. Therefor, how to calculate the path of obstacle avoidance quickly and accurately has been an important research subject of the home and foreign scholars.Main works as follow.Firstly, this paper researches the existed approach of Distance Field of polyhedron. In order to receive smaller set of triangulars and improve the efficiency of the algorithm, this paper proposes a new algorithm for computing Distance Field that based on sphere search with radius increasing uniform. At the same time, the paper makes a comparative analysis of existed algorithms.Secondly, boundary extraction is an important step of computing Minkowski sum of non-convex polyhedral. So, to improve extraction efficiency of boundary of finial Minkowski sum, the paper proposes an improved algorithm to extract boundary that based on sign determination and function value of common vertex after studying the extraction methods. At the same time, the complexity of the algorithm is analyzed.Thirdly, the paper gives the overall idea of computing the Minkowski sum of arbitrary non-convex polyhedron. After computing Minkowski sum of sub-polyhedron, the paper uses improved Distance Field algorithm to get the Distance Field of the polyhedron of sub-Minkowski sum; then does max/min operation on Distance Field to unite polyhedrons of sub-Minkowski sum; at last, uses the Enhanced Marching Cubes to extraction the boundary of finial Minkowski sum.Finally, the paper validates the above algorithm and gives the results. The paper also does some comparison and analysis with the existing algorithm.