Background of the research
Collision detection is very important for many applications in computer graphics, simulations, visualization and virtual reality (VR). Collision detection is the essential purpose in simulating real-world events with computer graphics and also important in games.
For this report, I read the paper "Simple and Rapid Collision Detection using Multiple Viewing Volumes".
The typical input for a collision detection algorithm is a number of geometric objects moving within a certain environment. We need not only to determine the contacts that occur between pairs of objects accurately, we also need to do that detection at real-time rates. This is obvious in computer games in which speed is the most required and the most important. Some applications may require hundreds to thousands of collision detections per second.
In the past years, the CPU (Central Processing Unit) was used for computing the collision detection algorithms and the CPU was the only option for programmers. But the advanced technologies and researches in graphic hardware devices introduced very powerful graphic hardware for programmers. Today's graphic processors are not just co-processor for main CPU. They are even more powerful and efficient than main CPU in processing graphic related functions and commands and they are now called GPU (Graphic Processing Unit). Moreover, the advanced data transferring technologies for graphic data such as AGP (Accelerated Graphic Port) and PCI-Express also support the power of these GPUs. Programmers can used these GPU to speed up the collision detection processes and to improve the processing performance. These powerful and advanced graphic processors are now widely used in computationally intensive tasks for graphic processing programs and game programs.
There are many various algorithms for collision detection based on many facts such as bounding volumes hierarchies, geometry reasoning, formulations, space partitions, parse methods and optimization techniques.
In this paper, the detection algorithm for collision detection between a model with convex geometry and an arbitrary geometry model was presented.
The presenters used bounding volumes for convex geometry input model as a main entity in this approach. The convex geometry model is more simple and easy to compute bounding volumes than arbitrary geometry model. They used bounding box to create "viewing volumes" for one model and then detect collision with another model based on these viewing volumes. I think the process is more similar than other collision detection techniques.
First, we need to define the bounding box for a model before we define bounding volumes. In determining bounding box for a given polygonal model, we have many things to consider. We can define bounding rectangle or bounding sphere for a given model. Although mathematics of the bounding circle (for 2D) and bounding sphere (for 3D) are simple and straightforward, the bounding circle/sphere may have problems for some arbitrary models. If an object is in general rectangular geometry, approximating this object with bounding circle/sphere would cause a lot of errors. We should use bounding box for such models.
Creating a bounding rectangle for a given model needs to find the edges for that bounding rectangle. We have to find the minimum (x,y) and maximum (x,y) (for 2D) among all the vertices of that model. Even constructing of bounding rectangle for a rectangular model, there may be some error regions. The following figure shows that error regions.
Bounding volumes are used for a particular mesh in 3D space. Two common examples of the bounding volumes used are spheres and boxes. Other examples are cylinders, ellipsoids, lozenges, and capsules.
To speed up visibility test and collision test we can use bounding volumes. We can easily say that the mesh is not visible if its bounding box or bounding sphere is not visible. Because a mesh is composed of many triangles, we can reduce the processing cost greatly by first testing with its bounding volumes. Bounding volumes can be used to speed up in collision detection of two or more meshes. Since the objects are made up of triangles if we want to detect collision between these objects, we need to make test for all the triangles in those two objects. This approach would require many intersection tests one for each triangle of each object in the scene.
A more efficient approach is to compute bounding box of each mesh and do intersection test for these bounding boxes. If the bounding boxes do not intersect with each other, we can easily say that the two meshes not collide with each other. We need to do more precise tests only to objects whose bounding boxes are hit. Bounding volumes are useful because they approximate the volume of a mesh and can therefore be used to speed up calculations related to the volume of space that a mesh occupies.
The proposed algorithm
The algorithm in this paper uses graphic hardware to make collision detection between two objects. By using graphic hardware to detect collision, the performance will be better than using CPU. We can use graphic hardware based queries using OpenGL proposed by HP such as GL_HP_occlusion_query and proposed by Nvidia such as GL_NV_occulusion_query.
If A is a convex geometry object and B is a arbitrary shaped and we need to make collision detection between these two objects, there is a chance that some part of B can be seen from inside A if A and B are intersect each other.
First, bounding box of A is built and then six viewing volumes are defined based on six faces of bounding box of object A and camera position which is internal point of A. The six faces of bounding box of object A are used as far clipping planes. We can make collision detection between object A and B easily by querying the rendering results based on six viewing volumes and also compare the depths. Consequently, the six viewing volumes of A are very important to the correctness of collision detection results.
In this algorithm, first we need to define viewing volumes and their parameters of rectangular geometry object A. Then we will render object A and B using graphic hardware. We can use occlusion queries to the graphic hardware for our collision detection between A and B.
The viewing volumes are constructed using bounding box. Therefore, the size of the bounding box will influence on the size of viewing volumes and consequently, it will also influence on the performance and efficiency of the collision detection process. Each viewing volume of A is corresponding to a face of the bounding box of A. The camera position within A (typically the center of A) is used as a common camera position for all six viewing volumes. In this paper, the perspective projection is used.
After rendering and defining the viewing volumes of A, there are two ways to render B and detect the collision between A and B.
The first way is we can choose and render the faces of object B that are appeared in the particular view volume of A and then make detection of collision for only those faces. This can reduce the processing cost because we can only render and process for those faces that can be seen from viewing volumes of A.
Another approach is that we can first construct bounding volume hierarchy (BVH) of B. Then we make rendering the root bounding volume of B in all the viewing volumes of A using graphic pipelines. If we find that the root bounding volume of B does not appear in any one of viewing volumes of A, we can easily say that A and B do not intersect or interfere each other. If the root bounding volume interferes with one of the viewing volumes of A, we should do recursive checks to the two children bounding volumes of that root bounding volume until the leaf nodes of the bounding volume hierarchy are reached. This process can also accelerate the collision detection process.
Results of the algorithm
In the real implementation of the algorithm, we can use graphic hardware based collision detection for occlusion query. For the real-time image rendering and occlusion query, I think we should use high-performance graphic hardware such as Nvidia Geforce FX and later or ATI Radeon or later series.
In this paper, three scenarios were tested with different number of triangles for each object models. The proposed algorithm is better when there are more triangles in objects and large-scale virtual environment. Moreover, the propose algorithm wants to use the graphic hardware in detection of collision between objects. Therefore, it can take advantages of further developed graphic hardware to speed up more.
Strengths and limitations
The proposed algorithm and technique uses graphic hardware to render and detect collision between two objects. Because of the dedicated graphic hardware, this technique can be far faster than methods that use main CPU. The algorithm does not need to read back the frame-buffer by CPU which may be major bottleneck in current graphic buses and therefore it can significantly improve overall performance.
The drawback is that one of the objects in making collision detection must be convex geometry model. But the writers of this paper argued that the arbitrary shaped objects can be decomposing into convex components before entering into the algorithim.