A Parallel Cutting Algorithm Of Triangular Mesh And Its Application

Triangular mesh cutting is to judge whether the triangle should retain or not in accordance with the positional relation(in,cross or disjoint)between the polygon clipping window and the triangle which is in the original triangular mesh.And it is to break the original triangular mesh into different triangular facets.Triangular mesh cutting is helpful to solve problems related to computational geometry,especially in fusion and analysis of terrain.As an important problem in computational geometry,triangular mesh cutting is attracting more and more attention.There are mainly two important problems in the current triangular mesh cutting: Firstly,for triangular mesh cutting,the general polygon clipping algorithm does not take the spatial relationship of the adjacent polygons into consideration.It will produce unstable triangular mesh,if we cut a triangle in isolation.Secondly,parallel cutting algorithm is generally used to improve time efficiency of the triangular mesh cutting.But when we allocate parallel threads,a triangle is assigned a thread or a polygon window is assigned a thread,it will lead to different results.How to allocate the thread will directly affect the accuracy of the cutting results.For these two issues,in this paper,which is on the basis of analysis and research on existing related algorithms,the existing side-by-polygon clipping algorithm has been improved and accuracy and efficiency of the cutting algorithm have been analyzed and studied:(1)Through the study of side-by-clipping algorithm(Sutherland-Hodgman algorithm),we use arbitrary convex quadrilateral clipping window to cut triangle.In order to ensure the results are still triangles,triangulate the quadrilateral generated during cutting.Call the above method cyclically to complete the cutting of the original triangular mesh and find out the disadvantages based on the cutting results.(2)On the basis of analyzing various cutting operations,we proposed an improved algorithm to avoid some redundant and unstable cutting operations.We adopt the specific partitioning strategy according to the specific circumstances to eliminate a small amount of crack and T-intersections of the 3D triangular mesh model after cutting,so that we can provide a more stable triangular mesh for the next cutting operation.The experimental results show that the algorithm guaranteed the accuracy of cutting between the arbitrary convex quadrilateral and the triangular mesh model and optimized the efficiency of the triangular mesh cutting correctness is more prominent.(3)The above improved method which is called cyclically and CPU parallel optimization acceleration are applied to the cutting between an arbitrary convex quadrilateral mesh and a triangle mesh.The results show that the algorithm has higher time efficiency.Finally,the proposed partitioning method is applied to the synthesis of highway scene for geometric integration of embankment and terrain data.Practical application results show that the partitioning method can better ensure the accuracy of the cutting results and it can speed up the cutting progress.