Virtual reality technology is closely related to many disciplines, which is widely used in simulation teaching, medical surgery, urban planning, industrial simulation and other fields [1]. In various virtual reality applications, objects in the virtual system often collide with each other due to the interaction between users and objects in the virtual environment. In order to maintain the authenticity of the virtual environment, the system needs to timely judge the occurrence of collisions and make corresponding operations, otherwise it will violate the authenticity of the real world and the user’s experience [2]. Collision detection in virtual reality technology is a hot research direction is also one of the most important problems. Collision detection is to determine whether two or more objects in the same space have contact or intersection [3]. If a collision occurs, the collision response will be triggered and the virtual reality system will be guided to the next operation. Collision detection algorithms can be roughly divided into two categories: time domain and space domain [4]. Bounding box is a kind of detection algorithm based on spatial domain. It has the advantages of high detection efficiency and simple detection process [5].
For the complex model to be tested, the thought of bounding box is to surround the model to be tested with simple bounding box whose volume is slightly larger than the model to be tested and whose geometric features are regular [6]. When collision detection is done on two objects, the first detection is to check whether the bounding box intersects. If not, the two objects do not intersect. On the contrary, it is necessary to further accurately detect the two objects. This method can quickly exclude disjoint objects and reduce unnecessary calculation.
Many scholars have studied and explored the bounding box algorithm. The results show that the choice of bounding box algorithm is one of the key factors affecting the result of collision detection. The more compact the virtual model under test is wrapped by a bounding box, the simpler the set features are, indicating that its wrapping effect is better. But at the same time in bounding box algorithm, its simplicity and compactness are usually contradictory [7]. So the researchers came up with a different algorithm. Palmer and Grimsdale et al. [8] proposed a collision detection algorithm based on spherical bounding boxes. Smith et al. [9] proposed an intersection detection algorithm based on AABB axial bounding box. Both the bounding sphere and the AABB bounding box are simple in construction, but poor in tightness. Therefore, Gottschalk et al. [10] proposed the construction of OBB bounding boxes based on the theory of Smith’s AABB bounding boxes. Klosowski et al. [11] also proposed a collision detection algorithm using
Bounding sphere is defined as the smallest volume sphere that can encase the model to be tested [12]. It is a kind of bounding body with good simplicity and flexible structure. To determine the bounding sphere, it first need to determine the center of the bounding sphere, which is composed of the mean value of the vertex coordinates of all elements in the model to be measured. Then determine the radius of the sphere, which is the distance between the center of the ball and the points specified by the three maximum coordinates. The three-dimensional structure of the bounding sphere is shown in Figure 1.
The radius of the sphere can be expressed as the distance between the farthest vertex and the center of the sphere, and the center of the longest axis is the center surrounding the sphere. The bounding sphere is expressed as formula (1):
The principle of intersecting detection between bounding spheres is as follows: judging from the relationship between the sum of the center distance and radius between two spheres, if A and B represent two bounding spheres, the intersection of A and B is only necessary and sufficient if |
For update operations, only rotation and translation are needed to satisfy any operation in space. The update operation of the bounding sphere is that no matter the object rotates or moves along any axis or any point, the bounding sphere always wraps the model under test. Therefore, for a translation operation, it just need to do the same transformation of the center of the sphere according to the translation vector, while for a rotation, it don’t need to do any update operation, and the position of the center of the sphere doesn’t change no matter how rotate it. When compared to other bounding boxes, the advantage of the bounding sphere is obvious. It requires the least amount of computation compared to other bounding boxes.
By reason of the foregoing, although the calculation of the bounding sphere is small, its tightness is also poor. There are too many redundant calculations for most objects with uneven spatial distribution such as irregular geometric models or elongated objects. Because of its structural characteristics, it is suitable for the movement environment where the detection accuracy is not high. Therefore, when selecting the bounding box, the bounding box that is closer to the model to be tested should be selected, and the best scheme should be selected after comprehensive consideration of the advantages and disadvantages.
An Axis-Aligned Bounding Box(AABB) is defined as the smallest hexahedron that wraps the model under test in the same direction as the coordinate axis, so only six scalars are needed to describe an AABB [13]. It was the first bounding box to be used. Determining an AABB requires calculating the maximum and minimum values of the
In the construction of AABB, all bounding boxes have the same direction along the axial direction of the local coordinate system of the model. AABB is expressed as formula (2):
The principle of intersection detection between AABB is as follows: if the vertex of the model intersects all the projected intervals on the three coordinate axes, collision may occur between the detection models. If A and B represent two AABB, where
Both translation and rotation have an impact on the AABB update operation, which is not complicated due to the simplicity of AABB. In the case of translation operation, there is no need to rebuild AABB, but only need to change the vertex coordinates of AABB according to the direction vector and displacement of target model translation. In the case of rotation operation, the coordinates of the rotated vertices need to be calculated by rotation Angle and then re-projected to the
Oriented Bounding Box(OBB) is defined as the smallest cuboid that wraps the model to be tested and is in an arbitrary direction relative to the coordinate axis[14]. The most important feature of OBB is its arbitrary orientation, which makes it possible to surround the model as closely as possible according to the shape characteristics of the surrounded model, but also makes its intersection test complicated. OBB approximates the model more closely than bounding sphere and AABB, which can significantly reduce the number of bounding volumes, thus avoiding the intersection detection of a large number of bounding volumes. The difficulty is to determine the direction to minimize the volume of OBB according to the three-dimensional structure of the model to be tested. The three-dimensional structure of the OBB is shown in Figure 5.
Because of the flexible orientation of the OBB and its ability to wrap the model under test more tightly, it is difficult to create and update the bounding box for collision detection. The OBB region can be expressed as formula (3):
The principle of OBB’s intersecting detection is complicated, and it uses the Separating Axis Theorem (SAT) test. If you can find A straight line so that the bounding box A is exactly on one side of the line and the bounding box B is exactly on the other side, then the two bounding boxes do not overlap. This line is the separation line and must be perpendicular to the separation axis. The two-dimensional schematic diagram of the testing principle is shown in Figure 6. If A and B represent two OBB bounding volumes, then A and B intersect only if |
OBB’s update operations for rotation and translation are less computationally intensive. When the model is translated or rotated, the OBB needs to be updated. A new OBB can be obtained by carrying out the same displacement or rotation on all direction vectors of the model.
OBB is used in a narrow range of scenarios, only between rigid bodies. For soft body, OBB is not applicable. When the object is deformed, the update and reconstruction of OBB hierarchy tree is cumbersome and the calculation is very large, so the real-time detection conditions cannot be guaranteed. There is no good solution to the problem of updating the OBB hierarchy tree, and the cost of rebuilding the bounding box hierarchy tree is too high, so OBB is not suitable for collision detection between soft bodies.
The discrete oriented polytope (
The common
The biggest drawback of
This paper simulates the above three bounding box algorithms. The experiment uses VS2107 compilation environment and VTK visualization library. The 3D point cloud data is the rabbit point cloud data of Stanford in the format of pcd file. Entering point cloud data into it can get the bounding sphere, the bounding box of AABB and OBB that wraps the whole point cloud data. The simulation results are shown in Figure 7.
Comparison of various bounding box algorithms is shown in Table I.
COMPARISON OF VARIOUS BOUNDING BOX ALGORITHMS
Bounding box type | Simplicity | Tightness | Collision Detection Difficulty | Update the Difficulty | Application Scenarios |
---|---|---|---|---|---|
|
simpler | worst | easiest | easiest | All |
|
simplest | worse | easier | more difficult | Both rigid body and soft body are applicable |
|
most complex | better | most difficult | easier | All |
|
more complex | best | more difficult | most difficult | All |
Through the analysis of the table, it is found that the bounding sphere is relatively simple compared with other bounding boxes in terms of construction difficulty, collision detection difficulty and update calculation difficulty, and it has a wide range of applications, including rigid body and soft body. The only drawback is that it has the worst tightness surrounding the model. In the scene where the detection accuracy is not high, the bounding sphere algorithm can be given priority. AABB is relatively simple in terms of construction difficulty and collision detection difficulty, and has the same disadvantage as the bounding sphere, which has a relatively weak enveloping tightness. It is also relatively difficult to update the calculation. In particular, AABB is not suitable for models with narrow and long shapes and direction deviating from the coordinate axis. OBB has strong bounding compactness and less updating calculation, but its disadvantage is that compared with other bounding boxes, it is more difficult to construct and collision detection, and its application scope is smaller. The tightness of
Bounding box algorithm is a very important algorithm idea in ray tracing and collision detection. This paper introduces some classical bounding box algorithms and analyzes their advantages and disadvantages as well as their application scenarios and scope. It can be seen from this article that there is no one kind of bounding box is the best choice, but according to different scenes to select the most appropriate bounding box. The bounding sphere is simple but with poor accuracy; AABB is simple but complicated to calculate; OBB has good accuracy and simple update but complicated to construct;