Overview of the Collision-Detection Problem
The collision problem involves both collision detection and collision response. There are moving objects in the virtual environment that may collide with each other during their motion, and the accurate detection of these collisions and the correct response have a crucial impact on the realism of the virtual environment. Among them, the hierarchical bounding box algorithm is more widely used because it is very suitable for collision detection in complex environments. The hierarchical bounding box method is further divided into the sphere-detection algorithm, the axis-aligned bounding boxes (AABB) detection algorithm, the oriented bounding box (OBB) detection algorithm, the discrete orientation polytopes (k-DOP) detection algorithm, and other methods. These algorithms have their own characteristics and are widely used in different applications (Garcia et al., 1994). A simple illustration of the above types of bounding boxes is shown in Fig. 2.
Figure 2. Four Common Types of Bounding Box in a Two-Dimensional Plane (Note. The construction method of bounding boxes in two-dimensional and three-dimensional spaces is slightly different, and the effect in the two-dimensional plane is only used as a demonstration in the figure)
The different bounding boxes require different system resources because of the different construction and detection methods (Chen et al., 2005). The cost of collision-detection algorithms based on the hierarchical representation of bounding boxes can be expressed in general terms by the following cost function:
T=Nv×Cv+Np×Cp+Nu×Cu+Cd(1)In (1), T is the total collision-detection cost equation, Nv is the number of pairs of bounding boxes involved in the overlapping trials, Cv is the cost of a pair of trials with overlapping envelopes, Np is the number of geometric basis element pairs tested, Cp is the cost of testing a pair of geometric basis elements, Nu is the number of wrappers that must be updated when an object is rotated, Cu is the cost of updating a bounding box, and Cd is the cost of updating the tree of the bounding box when the object is deformed into a shape. Table 1 compares the comprehensive performance of the bounding boxes.
Table 1. Comparison of Four Common Functions of Bounding Boxes
| Type | Difficulty of Construction | Compactness | Time Consumption |
|---|
Sphere
| 1
| 1
| 1
|
AABB
| 1
| 2
| 2
|
OBB
| 3
| 3
| 4
|
| k-DOP | 2 | 4 | 3 |
Note. The larger the number in the table, the more difficult, dense, and time-consuming it is to construct this type of bounding box.
AABB and sphere detection are less difficult to construct but less compact. Sphere detection does not need to be updated when the object is rotated or displaced, while AABB needs to recalculate the enclosed set of objects to update the new bounding box. In addition, both sphere and AABB detection need to be recalculated and updated when the object is deformed. In contrast, OBB and k-DOP are relatively difficult to construct. OBB needs to find the optimal direction before constructing the bounding box, while the direction of k-DOP is fixed in the k axes. In the case of object deformation, both OBB and k-DOP must reconstruct the bounding box, so OBB has some disadvantages for complex polygonal objects.