Review of Bounding Box Algorithm Based on 3D Point Cloud

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.

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): (1) R = { ( x , y , z ) | ( x − O x ) 2 + ( y − O x ) 2 + ( z − O x ) 2 < r 2 }

O_x, O_y, O_z represent the x, y, z coordinates of the spherical center O, and r is the radius.

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 |d| < (r ₁ + r ₂) is true. This is shown in Figure 2.

Figure 2.

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 x, y, and z coordinates of the vertices of each element in the set of basic geometric elements that make up the object. The three-dimensional structure of the AABB is shown in Figure 3.

Figure 3.

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): (2) R = { ( x , y , z ) | x min ⁡ ≤ x ≤ x max ⁡ , y min ⁡ ≤ y ≤ y max ⁡ , z min ⁡ ≤ z ≤ z max ⁡ }

x_min, y_min, z_min, x_max, y_max, z_max represents the minimum and maximum values of the projection of the model on the x, y, and z axes.

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 l_A and l_B are the projections of A and B bounding boxes on the X-axis respectively, x_A and x_B are A respectively, and the projections of O_A and O_B on the X-axis of the middle points of B bounding boxes. If |d| < (l_A + l_B ), then it means that the projection of the bounding box A and B on the X-axis overlaps, otherwise, the projection of the bounding box on the X-axis does not overlap. In the three-dimensional space, the intersection test of AABB bounding box needs at most 6 comparison operations. This is shown in Figure 4.

Figure 4.

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 x, y and z axes to get the maximum and minimum values, and then rebuild AABB. Similarly, AABB can be used in a wide range of scenarios, including rigid body and soft body.

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.

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): (3) R = { O + a r 1 v 1 + b r 2 v 2 + c r 3 v 3 | a , b , c ∈ ( − 1 , 1 ) }

O represents the center of OBB. r₁, r₂, r₃ represent the radii of x, y, z coordinate axes respectively. v₁, v₂, v₃ are used to calculate the direction of OBB respectively, which is a vector mutually orthogonal to the direction of coordinate axes.

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 |T · L|≤l_A + l_B is true. T represents the displacement vector between A and B, and L is the unit vector parallel to the separation axis.

Figure 6.

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 (k-DOP) is defined as a convex polyhedron that wraps the model to be tested and the normal vectors of all faces come from a fixed set of orientation (k vectors) [15]. K-DOP can surround the model to be tested more closely than other bounding volumes. The more directional axes it has, the closer it is to the model to be tested. Therefore, its construction difficulty and phase test are more complex. In fact, the AABB bounding box mentioned above is a special case of 6-DOP. When k value is infinite, the k-DOP bounding box is actually the convex hull of the model, so the tightness of the k-DOP bounding box is the best among these kinds of bounding boxes.

The common k-DOP generally includes 8-DOP, 14-DOP, 18-DOP and 24-DOP. Since each k-DOP of the same category uses the same and fixed directional axis, the test process of intersection between them is similar to that of AABB. The test process can be simply described as finding whether there are separate projection intervals between two k-DOP on k/2 directional axes in turn. If there is a separate projection interval, the two k-DOP are separated from each other, and vice versa, the two k-DOP bounding boxes intersect.

The biggest drawback of k-DOP is that even if objects in space rarely collide, it is necessary to perform an update rotation operation on the bounding box to redetermine the maximum and minimum values on the axis. K-DOP update operation is that when the model rotates, k-DOP update computation is relatively large. In this case, we cannot simply update k-DOP by the same rotation, but recalculate k-DOP after rotation. However, the cost of recalculating a k-DOP vertex is high, so the idea of linear programming is adopted for optimization. For soft body, k-DOP needs to update the deformed leaf node first, and then update the parent node according to the bottom-up method, so k-DOP is suitable for both rigid body and soft body environment.