Collision Detection Algorithm Research And Application Of Three-dimensional Graphics Processing System

Three-dimensional graphic system is comprised of a mass of geometric objects and moving objects, the collision among which has to be detected in order to decide the next direction of moving objects. Typically real-time collision detection can greatly improve the immersion and reality of the system, which plays a very important role in computer graphics and visualization.This thesis initially presents several existed collision detection algorithms, analyzing some typical algorithms and their performances and the situation they suit. Building upon these results, we develop and analyze a hybrid Bounding Volume Hierarchies (BVHs) with three bounding volumes (BV), which are sphere, fixed directions hulls(FDH) and oriented bounding boxes(OBB). The present BVHs algorithms which select only one BV to build hierarchies has the conflict between BV's briefness and tightness. So the efficiency of this algorithm largely depends on the objects' figures. In the hybrid BVHs presented in this thesis, the nodes in different hierarchy select different BV based on BV's characters. We solve the problem that it is complex to build and traverse the hybrid BVHs. so the efficiency rises and the robustness is enhanced.Based on the axis-aligned bounding boxes (AABB) algorithm, we present a new method Intersection AABB(IAABB). IAABB is the intersection of the BVs of two objects. IAABB could filter out the elements which do not intersect the IAABB. So it decrease largely the number of the candidate surfaces and the candidate polygons for detection.Finally the algorithm proposed in this thesis is implemented in the Field Three-dimensional Situation System.