Computation Method Modeling And Analysis Of Minkowski Sum Based On Geometries’ Algebraic Structure

Intelligent manufacturing,a hot topic at home and abroad,has become the core content and major development trend of manufacturing industry in the future.The precision and efficiency of collision-interference detection are important indexes to measure the level of intelligent manufacturing.It is one of the key technologies to promote the development of the industry.Minkowski sum,a branch of computational geometry,is an important tool for studying the accurate relative position relationship between two geometries.However,the existing Minkowski sum algorithms’ complexities are always high which limit its application scope.In order to improve the Minkowski sum construction efficiency and enhance its application value,this paper constructs the algebraic structure of geometric models in view of their topology structures,and does researches on the Minkowski sum computation method modeling and analysis.First of all,the algebraic structures of polyhedron and polygon are proposed based on their topology structures,which express them in an algebraic method.Meanwhile,the pole region construction of each vertex of the geometric models is investigated based on their algebraic structures.Secondly,the computation method model of the Minkowski sum of two convex polyhedral is studied.It includes two main parts: a more direct solving model to obtain the translation facets of the Minkowski sum boundary and a more rapid repairing model to mend the holes among the translation facets.Its validity,stability and higher efficiency are verified from the theoretical analysis aspect and the experimental analysis aspect.Thirdly,the computation method models of the Minkowski sum of a ring-shaped concave polyhedron and a convex polyhedron and two concave polygons are discussed based on the convolution thought.The first model includes two steps: to construct the simplified convolution based on their algebraic structures and to extract the exact Minkowski sum boundary from the convolution through trimming the inner informations by the plane-sweeping method which simplify a 3d messy facets intersecting problem into a 2d ordered lines intersecting problem.The second model can be divided into three steps: to compute the simplified convolution based on their algebraic structures;to classify the convolution edges into inner ones and boundary ones,and judge the adjacent sequence of the boundary ones;to extract the exact Minkowski sum boundary from the boundary ones by computing the intersection of the adjacent classes.The validity and stability of proposed models are verified through theoretical analysis and experiments.Finally,in order to verify the practicality of the above computation method model,its application aiming at the virtual assembly process of a special kind of mechanical parts is studied.Firstly,the Minkowski sum construction peoperties of the assembly parts are discovered in view of the models’ characteristics;secondly,the Minkowski sum based mechanical virtual assembly detection algorithm is proposed in the light of the peoperties;Finally,the model’s practicality and the algorithm’s effectiveness are verfied through theoretical analysis and simulation experiments.