Salam to all,
Well, today I would like to discuss more on technical. Something related to my upcoming research in Computer Visualization using 3D Models of Rigid Bodies.
For those who does not understand what the different between rigid bodies and deformable bodies. Rigid stand for fixed shaped model, where the object does not change even though there is a force been applied. It can only change its direction and velocity (under certain circumstances) . But for deformable body, it stands for an object than be changed under any force such as clothing, hair, or any kind of shapes that can be altered.
In order to detect collision between two or more polyhedra in virtual environment, several stuff needs to be considered. *Polyhedral means any 3D object that has a shape made of points that is connection to each other. It has several entities such as vertices, edges, and faces.
The stuff that we are going to consider it about contact points between these two polyhedra, the complexity of the polyhedra, the velocity of the polyhedra, and the behavior of the polyhedra (whether it is rigid or deformable).
Several researches has been done in order to come out with numerous solution of detecting two or more polyhedra but all of them seems to tackle on specific application. it is not based on general solution. Even though the introduction of Bounding-Volume (BV) helps to improve the speed of the intersection algorithm, but it still suffers from the accuracy of the colliding objects.
Back to the collision detection method, there are two types of it. One if Discrete Collision Detection (DCD) and the other one is Continuous Collision Detection (CCD). DCD is always faster than CCD method but their accuracy is lesser than the CCD method.
CCD requires no backtracking (Backtracking is some sorts of re-tracing back the path of colliding objects if the DCD failed to detect collision within time steps) like the DCD. Sometime, it is hard to notify and to calculate the path of colliding objects when the object tunneling through the thin wall. As the DCD may reports back that there is no collision.
Tunneling is an effect of object passing through the second object without DCD algorithm even notice. Even though DCD might be able to notice it, it requires backtracking method to computer back between the interval before collision and after collision until the point that DCD algorithm has completed their search for collision.
Compared to the DCD algorithm, CCD can easily be defined as a collision that is based on the path of the object towards the other object. It has many different type of algorithms used in CCD algorithm but all of them is much slower than DCD algorithm but has a big advantage of very accurate collision detection method. It also complex to implement compared to the DCD algorithm.
Currently from year 2008 until recent 2011, Graphics Processing Unit (GPU) has been used extensively to speed up the process of CCD algorithm by the factor almost 100x than previous CCD method. However, DCD algorithm also benefits from the GPU hardware as the algorithm for DCD also improved at least twice as CCD method. But, as long as the Frame Per Second (FPS) for CCD method is above 30 fps (where human eye can see as a smooth object motion), then it can be considered as a successful algorithm for simulation, animation and visualization.
GPU used parallel processing by exploring the use of the core inside GPU hardware. Higher numbers of cores means that higher numbers of calculation can be done in parallel.
Currently, there are two common library that can be used to programming in GPU. OpenCL and CUDA. OpenCL is the newest technology that enable the user or programmer to use any kind of GPU hardware named it ATI RADEON or NVIDIA. While CUDA is from NVIDIA.
So, the technology to speed up the process of CCD is already in the market and what we can do is to simulate the CCD algorithm into parallel by using OpenCL + GPU card (Cheapest GPU card can be bought for only RM150).
asyrani.com 