Objective

2

Collision detection is a key technique applied in virtual reality

especially in virtual assembly. A collision detection algorithm based on an object space uses three-dimensional geometric features of the object for expansion and calculation. This phenomenon is evaluated by two methods

namely

a space division method and a bounding box method. The collision detection algorithm based on the bounding box method has attracted considerable attention and is widely used globally. The testing between the bounding boxes increases the possibility of collision detection errors. This condition can be explained by the use of an algorithm based on the axis-aligned bounding box (AABB) hierarchy binary tree that has many testing nodes but lowers detection efficiency in several cases. The space division method divides the entire virtual space into a sequence of equally sized cells and only detects objects in the same cell. The space division method is suitable for consistently distributed and sparse objects. The cells are divided into small sizes for cases with many objects and irregular distribution. The intersection tests between the collections of cells reduce the collision detection speed and require considerable storage space. To solve the problems of traditional collision detection algorithms

this study proposes a collision detection algorithm based on AABB bounding box and space division.

Method

2

The proposed algorithm utilizes a step-by-step detection method. In the pre-detection phase of the algorithm

a bounding box is generated for each object in the scene. This method determines the intersection area of the two bounding boxes based on the AABB algorithm. Subsequently

the method divides the areas of intersections to conduct cross-tests on each planned area. The algorithm combines the direction and movement trend of the model to create a space division. The intersection of space-time related parts is evaluated based on the corresponding correlation of collision detection. In this algorithm

the spatial correlation of the object is used to reduce the detection range

which improves the efficiency of the algorithm. The transfer of bounding box into triangle surfaces and points is used to reduce detection errors. The algorithm refines the interference detection between the triangle plane and points. This process directly restores the collision detection between various models. In addition

the algorithm uses a rapid detection method to determine whether a set of points passes through a triangle or not. The detection method conducted in two steps obviously improves the efficiency of the collision detection algorithm.

Result

2

In the experiment

five typical experimental environments are established to compare the AABB hierarchical bounding box binary tree algorithm

$$k$$

-Dops(discrete orientation polytopes) bounding box algorithm

and BPS(Binary Space Partitioning Tree) spatial segmentation tree algorithm. Two kettle models with a large number of triangular faces are used as the experimental model. The model has planes

surfaces

and rings

which can verify the advantages and disadvantages of the algorithm. The five experimental environments are built to evaluate the geometric collision accuracy

collision detection time loss in the translation degree of freedom and rotation degree of freedom

and the impact of the number of triangle faces on collision detection of the algorithm. In terms of geometric collision accuracy

six locations are randomly selected in performing collision detection. At the same position

the algorithm is used to perform collision detection by using three traditional algorithms. The space difference between the three algorithms and the proposed algorithm is recorded. The distance between the proposed algorithm and AABB algorithm and the distance between the algorithm and

$$k$$

-Dops algorithm exceed the threshold of 0.02 in most cases. Visible visual gaps are observed when the distance exceeds 0.02. This finding proves that the algorithm remarkably improves the collision geometry accuracy. In terms of collision time consumption and collision detection

difficulty

the proposed algorithm reduces the detection time by more than 50% in contrast to the AABB algorithm and BSP algorithm for the translation degree of freedom. Moreover

the proposed algorithm reduces the detection time by more than 50% in contrast to the

$$k$$

-Dops algorithm and AABB algorithm in the rotation degree of freedom. The experimental results show that the proposed algorithm attains superior performance in the calculation of collision detection for complex models. In terms of the influence of triangle number on the algorithm's collision detection time consumption

two groups of experiments are conducted in this study. We use a coordinate positioning method to ensure that each collision detection position is the same and the required time for each collision detection in the current position is obtained. In the first set of experiments

a teapot model with 530 faces is set as the dynamic model

and a model with different number of faces is set as the static model. In the second group of experiments

a teapot model with a face number of 530 is set as the static model

and a model with different number of faces is set as the dynamic model. The experiment result shows that the computational time cost of the proposed algorithm is less than those of the AABB algorithm and the BSP algorithm when collision detection occurs at the same location. The proposed algorithm shows high stability when the triangle number of the motion model is large. The algorithm reduces the detection scope to reduce the cost and improves the detection efficiency of the algorithm and the geometric accuracy of collision detection.

Conclusion

2

This study proposes a collision detection algorithm that combines the bounding box and space division methods. The proposed algorithm utilizes the advantages of the bounding box method

such as easy update

speed

compactness

and simple cross-section testing

to rapidly exclude the disjoint objects and determine the areas that may intersect. At the same time

the probability of model collision in the same partition space is increased using the space division method. The space division method reduces the collision detection time and invariably improves the collision detection accuracy. The proposed algorithm is suitable in virtual assembly technology field

which can increase its accuracy and can satisfy the real-time interaction of the users.