Research And Implementation Of Intersection Method For Triangular Mesh Models

This thesis mainly focuses on intersection between triangular mesh models. The efficiency of an intersection algorithm mainly depends on the stage of excluding triangular meshes, collision detection is very important in this stage, and its fundamental task is to detect whether there are contacts or penetrations among multiple objects, then we can exclude lots of non-intersecting triangular meshes before model intersection. At present the collision detection technology is getting mature, there have been many research achievements on solving the problem of collision detection. But with the rapid development of computer graphics, the complexity of triangular mesh models increases, and it makes the number of triangular meshes that intersection algorithm needs to deal with increases in multiples. In order to meet people's higher requirements to the real time interactivity and realistic simulation of virtual objects, we must search for a more efficient collision detection algorithm.On the basis of the intensive survey and comprehensive analyses of various approaches to collision detection, we sum up the mainly collision detection algorithms'advantages and disadvantages. The paper mainly studies space division technology, AABB bounding boxes method and OBB bounding boxes method, in order to speed up the process of collision detection, we also explore the possibility how to combine and improve these algorithms.Space division method needs to decide every triangular mesh occupies which space cube, although it can determine the intersection between two models, the efficiency is not high, especially when the model is complicated. OBB bounding boxes method can exclude lots of disjoint triangular meshes rapidly, but this is an iterative process, from this aspect we also can improve the algorithm's efficiency. Focuses on several problems about two algorithms, this paper proposes an improved method which builds the bounding box just for one model and divides it, then decides which space cube that model's every triangle mesh occupies, this process can exclude a part of triangular meshes. In the next step, we exclude triangular meshes further by OBB bounding boxes, and finally obtain intersection of remaining triangular meshes. The performance of the improved algorithm has a statistically significant increase.Comparatively speaking, AABB bounding boxes are simple, although its poor tightness may lead to many needless bounding boxes intersection test, its operation is very simple. Making full use of AABB and OBB bounding boxes'advantage, this paper proposes a new intersection algorithm. We determine the intersecting part of two bounding boxes called common box, then exclude the triangular meshes outside the common box. We won't stop this elimination operation until the number of model's remaining triangular meshes down to a certain threshold. After the stage of elimination, the triangular meshes that need to be calculated are very few. Then we do a further elimination by use of OBB bounding boxes, at last get the intersecting lines of the remaining triangular meshes.We realize the two improved algorithms using VC++ and OpenGL, experiments show that these two improved algorithms can increase the efficiency of computing triangular mesh models'intersections.