Research And Application Of Triangular Mesh Intersection Algorithm

In the fields of computer graphics and computer animation,triangular mesh model intersection is always an important research topic,because it greatly improves the sense of reality and immersion in the virtual reality environment.However,with the increasing number of triangles,the speed of intersection of triangular meshes will be reduced.If we want to ensure the real-time and effective,we must improve the existing classical algorithm.Through collecting and researching a large number of Chinese and foreign literature,this paper divides the intersection process into two steps:the first step is collision detection before intersection.The main current collision detection algorithms are summarized,including AABB boundingbox,bounding sphere,OBB bounding box,k-DOPs bounding box and average cell method,and their advantages and disadvantages are compared.The second step is to calculate the intersection point.Two classical algorithms for finding intersection points are introduced,which aim at calculating the intersection point between two triangles quickly and effectively.The hierarchy bounding box method can quickly eliminate a large number of unrelated triangles,but as the hierarchy increases,the complexity of the tree increases correspondingly,making the calculation speed decrease;for each node,after a simple judgment,all of the triangles can be intersected.The average cell method is based on the idea of index,and it can be accurately determined from two models of possible intersecting triangles in a part of small cells.However,because the complexity of the unprocessed models is high,and there are lots of irrelevant triangles,so the efficiency is also very low.In view of the advantages and disadvantages of the above two algorithms,this paper makes a corresponding improvement: First,we create the respective bounding boxes for the two models,and use the hierarchical bounding box to rough out the triangles that may be intersected;Then,the average cell method is used for the reserved nodes,and the triangles in the different models are limited to in a small cell.Finally,we calculate the intersection of the triangles in the small cell.By sorting and sorting the nodes,we getthe correct intersection line.The improved algorithm not only improves the speed of intersection,but also greatly reduces the memory consumption,making this method more suitable for huge model scenarios.The algorithm for finding intersection points of triangle is mainly to transform the intersection operation between triangles into intersection operations between line segments and triangles.In general,it is necessary to determine the intersection of 2 triangles at least 6 times.Every intersection detection corresponds to the edge of one triangle and the other triangle.When a large number of triangles are intersecting,a large amount of computation will take place,which leads to low computational efficiency.In view of the above shortcomings,this paper makes the following improvements: First,by judging whether the line segment is intersected with the plane of the triangle,the disjoint line segments are excluded.Then,based on the strong correlation between the linear equations,the corresponding calculation is reduced by using the common variable and the linear matrix operation.Finally,for line section and triangle coplanar case,it can be transformed into intersection operation between line segment and line segment,and the strong correlation between equations is also used to reduce computation.Finally,the above two improved algorithms are implemented and compared repeatedly.The experimental results show that the two improved algorithms are applied to the intersection calculation of triangular meshes,which will bring about the improvement of the intersection performance.