WIMI Hologram Academy: Collision Detection Algorithm Based on Virtual Reality Technology

By AIT News Desk On Jul 8, 2022

WIMI Hologram Academy, working in partnership with the Holographic Science Innovation Center, has written a new technical article describing their exploration of collision detection algorithm based on virtual reality technology. This article follows below:

Collision detection is an important technical difficulty and computing resource consumption point in the fields of graphics, simulation, artificial intelligence, virtual reality, and animation. The industry has conducted more in-depth research on collision detection algorithms. Scientists from WIMI Hologram Academy of WIMI Hologram Cloud Inc., discussed overall classification and corresponding applicable scenarios for collision detection algorithms. This paper analyzes the common graph-based real-time collision detection algorithm from the perspective of virtual reality technology applications and compares the advantages and disadvantages of the hierarchical surround box method and spatial segmentation method. Finally, the problems existing in the algorithm research and the future development direction are summarized.

Collision detection is used to determine whether a pair or more models occupy the same region at the same time within a particular 3-D region. It is one of the unavoidable problems in the fields of virtual reality, animation, computer simulation, and so on. In virtual reality research, role and obstacles, role and role, collision detection between obstacles and obstacles is the basis of motion planning and collision effect, the model must be able to truthfully respond to collision detection results, namely make the collision effect, otherwise, the model will produce penetration phenomenon, affect the authenticity of the virtual scene.

In general, there are three main purposes of collision detection: to detect whether collisions occur between models; to determine the location where collisions occur or are about to occur and to query the distance between models dynamically. This paper expounds on the overall classification of collision detection algorithms, focusing on the graph-based real-time collision detection algorithm most commonly used in virtual reality technology.

Classification of the collision detection algorithm

From the computer graphics proposed, the researchers have done a lot of meaningful work in the field of collision detection, proposed a series of mature detection algorithms, and developed the corresponding software tools. According to the different application fields, the collision detection requirements are also different, so many types of collision detection algorithms are proposed. In general, the algorithm can be divided into two categories. One is the static interference detection algorithm, which is mainly used to detect whether the interference occurs between the models in the stationary state, such as the interference inspection in the assembly process of mechanical parts. Such algorithms require little real-time performance but require very high accuracy. The second is the dynamic collision detection algorithm. It mainly detects whether the model in virtual reality scenes changes with time and whether it collides with other models in a given space, such as the collision between a bullet and the ground, the collision between a car and a tree, etc. Dynamic collision detection algorithm can be divided into discrete collision detection algorithm and continuous collision detection algorithm.

In essence, every discrete time point of the discrete collision detection algorithm is implemented by a method similar to the static interference detection algorithm, but it focuses on the algorithm’s efficiency. If there are a large number of independent models in the space, it will cause a great resource burden on the computer itself. Because this algorithm is calculated based on discrete data, this algorithm itself also has some problems, such as the puncture phenomenon and omission in the detection. However, because the real-time detection process is the basic requirement of virtual reality technology applications, so the discrete collision detection algorithm is still the focus and hotspot of collision detection algorithm research. Moreover, the deficiency of discrete detection algorithms can be reduced to some extent by the adaptive step technique.

To overcome the shortcomings of the discrete collision detection algorithm, the continuous collision detection algorithm models the motion process of the model constructs a continuous motion path, and then judges the collision situation between the models based on the path. Through the use of the user interface or the dynamic simulator, we determine the motion interpolation between several locations, reducing the complex motion process of the model to a series of simple rigid motions. However, such algorithms generally involve four-dimensional space-time problems or accurate modeling of structure space, which are usually slow to compute, and need further research needs to be applied for the implementation of collision detection in large-scale scenarios.

At present, most good real-time collision detection algorithms belong to discrete collision detection algorithms. These algorithms can be roughly divided into two categories: graph-based and image-based algorithms. The former evaluates the 3-D structure of the model, while the latter evaluates the image and depth information of the model. On the graph-based collision detection algorithms, the researchers have done a lot of work to build mature algorithms such as the hierarchical surround box algorithm and the spatial segmentation algorithm. The advantage of an image-based algorithm is that it can share the pressure of the CPU through graphics hardware, especially with the rapid development of graphics hardware technology in recent years, graphics hardware has a programmable function, which makes the image-based collision detection algorithm enter a new stage of development.

In terms of virtual reality systems, according to the different system design objectives, generally can be divided into two categories, one is oriented to product performance simulation verification, from the extreme use conditions of products, found under the bad conditions, error operation conditions product design defects, to improve the design scheme, provide a reference for product design; The other type is industry-oriented training, which is mainly used to train front-line personnel. Due to the different use scenarios, the two algorithms require great differences in the collision detection algorithm. The former requires the high precision of collision detection, while the latter emphasizes the real-time nature of the system. This paper mainly analyzes the graph-based discrete collision detection algorithm with more real-time performance.

Analysis of the real-time collision detection algorithm

The real-time collision detection algorithm is divided into the hierarchical surround box method and the spatial segmentation method. Both classes of algorithms use hierarchical models, and the goal is to reduce the number of geometric models that require intersection testing to improve the real-time performance of the algorithm. Due to its large storage capacity and poor flexibility, it is usually suitable for collision detection with relatively uniform model distribution in the environment, and it is more widely used for collision detection in complex environments.

Layer surround box method

The hierarchical surround-box method is widely used in collision detection algorithms, and it has been deeply studied in many fields of computer graphics. Its basic idea is to use a slightly larger volume and simple geometric characteristics of the box to approximate describe complex geometric objects, and then through the construction of tree hierarchy approximate the object geometric model, until almost completely obtain the geometric characteristics of the object, in the model collision detection, first to surround box, because the box of the intersection of the model is simple, so can quickly exclude many disjoint models, if the intersection only further intersection test, accelerate the algorithm.

Elastic Now Collaborates With AWS to Leverage Generative AI Capabilities

Nov 25, 2024

Arcee AI Signs Strategic Collaboration Agreement with AWS to Accelerate the Deployment of Smaller, Specialized Language Models

Nov 25, 2024

aiOla Unveils the First One-Step AI Model That Masks Sensitive Information to Preserve Privacy

Nov 25, 2024

Prev Next 1 of 40,461

Assuming that models A and B want to conduct collision detection, they first establish their enclosure box tree in the enclosure box tree, where the root node is the enclosure box of each model, and the leaf node is the basic geometric element of the model. The middle node is the enclosure box corresponding to each level. The core of the hierarchical surround-box collision detection algorithm is to effectively traverse the two trees to determine whether some parts of object A collide with some parts of object B at the current position. The core of the hierarchical box method is how to construct a box tree and rapid collision detection. At present, the more typical types of enclosure boxes include surround ball, axial enclosure box AABB, directional surround box OBB, and discrete direction polyhedral k-DOPs.

A surround ball is a class of enclosure boxes with good simplicity and poor tightness, and a surround ball of a given object is defined as the minimum sphere containing the object. To calculate the surrounding ball of a given object, first calculate the mean x, y, and z coordinates of all the vertices in the basic elements of the object set of the object to determine the center of the ball, and then the radius r is calculated from the distance between the center of the ball and the three coordinates of the maximum values. The intersection test between encircling balls is also relatively simple. For two encircling balls (c1, r1) and (c2, r2), if the ball center distance is less than the sum of the radius, the two encircling balls intersect, otherwise, they do not intersect.

Axial surround box AABB is the first class of surround boxes, the most widely used in collision detection studies, and the AABB of a model is defined as a minimum positive hexahedron containing the object with edges parallel to the coordinate axis. For a given object, its AABB requires only six scalar descriptions, namely, the x-coordinates of the vertices of the base set elements, the y-coordinates, and the maximum and minimum z-coordinates of the constituent model. The test of overlap between AABB is simple, where the two AABBs overlap if and only if their projection intervals across the three axes overlap.

The OBB hierarchy surround box is a class of surround boxes with good tightness and complex intersection testing. The OBB of a given object is defined as an arbitrarily minimal positive hexahedron that contains the object and has orientations concerning the coordinate axis. The biggest feature of OBB is the arbitrariness of the direction, which allows it to surround the objects as closely as possible according to the shape characteristics of the surrounded object, but also makes its intersection test complicated. The intersection test between OBB is based on the separation axis theory. If the projection of two OBB’s does not overlap on an axis, this axis is called the separation axis. If a pair of OBB has a separation axis, it can be judged that the two OBB’s do not intersect, otherwise, they intersect.

Because the tightness of AABB and the surrounding ball is relatively poor, and the overlap test and node modification of OBB is relatively expensive, the discrete direction polyhedral k-DOPs algorithm proposes a compromise scheme.K-DOPs are convex polyhedra, whose faces are determined by some parallel planes, and whose outer normal direction is selected from the k fixed directions in the space, using these planes to wrap the model. By adopting the fixed-direction in the space as the normal vector of the surrounding plain, the k-DOPs are also called the fixed-direction convex hull FDH. When k= 6, the normal direction of the six faces of the 6-DOPs is determined by the positive and negative direction of the three axes and is converted into AABB surround boxes. When k is large enough, the k-DOPs develop into convex packets of the model. The larger the value of k is, the closer the enclosure box is to the surrounded model. Therefore, the choice of k values depends on the different needs of collision detection, balancing between the simplicity of collision detection and the tightness of the wrapping model.

2.2 Spatial segmentation method

In the spatial segmentation method, the entire virtual space is divided into regular cells, to divide the model in the scene into smaller groups, and only the geometric objects that occupy the same cell or adjacent cells. In general, the spatial segmentation method needs to determine the spatial units occupied by each model at each collision detection. If there are many unmovable models in the scene, you can advance the spatial cells and determine the spatial units occupied by each model. When there is a model motion, it only needs to recalculate the space occupied by the motion model.

The method of spatial segmentation technology, which divides the space of inclusive models into independent subspaces, restricts all tests to the overlapping local regions of the two models and ranks them by the minimum and maximum values in all subspaces within the overlapping regions, thus further reducing the time of detection.

The spatial segmentation method is suitable for scenes with a relatively uniform model distribution. Space segmentation is independent of objects when using uniform grid segmentation, which makes it particularly suitable for deformed body objects. Deformed objects can deform in motion, and the enclosure box method needs to rebuild or update the enclosure tree, reconstructing the entire data structure; the key problem of uniform space segmentation is to determine the proper cell size. The appropriate selection of cell size can calculate the algorithm to maintain a certain accuracy without too much cost.

Compared with the surround box method, the spatial segmentation method has some advantages in computational efficiency, but when the models in the scene are dense and evenly distributed, the cells need to be further divided, the cross-test and storage between cells need large space, and the computational efficiency decreases sharply. It is greatly limited by being sensitive to the storage volume.

Conclusion

The development of graph-based collision detection algorithms is very mature, forming many typical algorithms, such as the hierarchical surround box method and spatial segmentation method, but the algorithm itself is greatly affected by the complexity of the scene. On the premise of ensuring the high accuracy of the algorithm, further improving the real-time performance of the algorithm has always been the goal of researchers. So the research of the algorithm should optimize the advantages of graphics hardware (GPU) and parallel computing method. Accelerated computing based on graphics hardware is currently ushering in a new era. A group of researchers is conducting this research, in the field of collision detection. The load balance problem between CPU and GPU needs further study to improve the algorithm efficiency. Due to its advantages, especially with the rapid development of graphics hardware, this algorithm has broad research prospects and research value.

In conclusion, there are still many aspects of collision detection technology that need to be further explored and studied, including collisions between complex models, and spatial consistency between frameworks. Therefore, researchers need to constantly study carefully, broaden their thinking, and design more efficient algorithms, to meet the requirements of real-time collision detection between a large number of complex models in virtual scenes.

Founded in August 2020, WIMI Hologram Academy is dedicated to holographic AI vision exploration and researches basic science and innovative technologies, driven by human vision. The Holographic Science Innovation Center, in partnership with WIMI Hologram Academy, is committed to exploring the unknown technology of holographic AI vision, attracting, gathering, and integrating relevant global resources and superior forces, promoting comprehensive innovation with scientific and technological innovation as the core, and carrying out basic science and innovative technology research.

[To share your insights with us, please write to sghosh@martechseries.com]