VGIS-COLLIDE: an effective collision detection algorithm for multiple objects in virtual geographic information system

Collision detection is an important component in simulation applications which are based on virtual geographic information system (VGIS). In this paper, an effective collision detection algorithm for multiple objects in VGIS, VGIS-COLLIDE, is presented. The algorithm firstly integrates existing quadtree, which is the global hierarchical structure of VGIS, with axis-aligned bounding box of object to perform the broad-phase of collision detection. After that, exact collision detection between two objects which have passed the broad-phase of collision detection is performed. The algorithm makes no assumption about input primitives or object's motion and is directly applicable to all triangulated models. It can be applicable to both rigid and deformable objects without preprocessing. The performance of the algorithm has been demonstrated in several environments consisting of a high number of objects with hundreds of thousands of triangles.