/ciol/media/agency_attachments/c0E28gS06GM3VmrXNw5G.png)
Follow UsCollision detection has been a nagging problem for the
computer scientist for a long time. Hence it has been an active research area
for years. When graphics was in its infancy, representation of objects was done
using six sided boxes. The human body could be represented using about 10 boxes
(hence the number of polygons was 10x6=60). Finding collisions between two such
objects required finding collisions between only 60x60 polygon pairs. Now, if
collision between two polygons took 10 milli seconds, the total time taken for
finding collision between two 60-polygon objects would be about 36 seconds. This
was reasonable in the past but in modern times, when the objects are represented
by millions of polygons, the computational time would be so large that it would
be practically unacceptable.
With the increase in computing power, object representation
has become very precise through the use of finer polygons. It is so fine that
the viewer often believes the simulated object to be as good as the real one.
Millions of polygons are used to model such objects. Detecting collisions
between two such objects is not a simple task. If the time taken for finding
collisions between two polygons is one micro second, then the time taken for
finding collision between two objects each with one million polygons is 1
million x 1 million micro seconds, i.e. 11.5 days!! Often a scene would have
many such objects and finding collisions among all these pairs would be a
horrendous task with the above method. So we try to discover other more
efficient approaches to find collision. One such approach is described next.
Click here to view Figure 1: AABB and OBB for a scene.
Assume a scene with many objects, as shown in Figure 1. Some
objects are very far from others and some are near. Let's ask some common sense
questions… Is there any use checking for collision between two far away
objects? Surely far away objects should be rejected quickly, but how can we
reject them from a collision test? A simple technique is to put boxes around
each of the objects covering the object completely. This box is called a
bounding box. If it aligns with the major axes, then it is called axis aligned
bounding box (AABB). The picture on the left in Figure 1, has AABB fitted around
the objects. Instead of checking for collisions with the objects, we first check
for overlap between two bounding boxes. If the two bounding boxes do not
overlap, then there is no chance of a collision between the two objects inside
them. Hence a lot of computation can be saved. So the next question is,
"How do we put the bounding boxes around the object?" One simple way
is to put horizontal and vertical parallelepipeds around the objects. This does
the job but often objects are not always tightly covered. Long and inclined
objects cannot be covered tightly by this method. As shown in the left picture
of Figure 1, the bounding boxes of such inclined objects are overlapping even
though the two inclined objects are far away. We solve this problem by orienting
or rotating the bounding boxes to align to the major axes of the object and then
fit the bounding box around the object tightly. This type of box is called
oriented bounding box (OBB), see the picture on the right in Figure 1.
With OBB comparisons, only the actually colliding or very
close objects will be left for collision test after the non-overlapping OBBs are
rejected. However, we may not yet be able to say whether the two objects are
really colliding or not and the naive method described in the beginning for
finding out the answer are yet very costly. The trick that we do is to split the
OBBs even further. The OBBs are split by dividing the object into two halves and
then again fitting an OBB for each of the halves. This is done for both the
objects (and OBBs). Now we compare the four pairs of OBBs for possible overlaps.
If any of the four pairs still overlap, again split and compare. This process is
continued till there is no overlap or the OBB cannot be split any further. If
there is no overlap among the OBBs at this level, then there is no collision
between the objects. If the OBB at this level cannot be split, go for exact
collision detection computation (a time consuming task, but only very few
polygons are now involved so overall time is very less). As the number of
polygons which undergo exact computation is either one or two, the collision
result can be decided in very quick time. Figure 2 shows one such example where
using the OBBs, the exact location of the collision can be quickly detected.
Click here to view Figure 2: Spheres with OBBs at third level: Colliding
polygons shown in redÂ
One of the fastest collision detection algorithms from Tata Elxsi!
The design and development center of Tata Elxsi’s Visual Computing Group,
which works in the area of advanced 3D graphics, has developed a reusable
component for collision detection. This is efficient in both performance and
memory usage. We compare our work with RAPID (Rapid Prototype for Interference
Detection), a freeware developed by the University of North Carolina where
research on collision detection is being done. The following performance report
(Figure 3) shows the time taken by TELCD (Tata Elxsi Ltd. Collision Detection)
and the RAPID for the same input data. The blue and green lines are of TELCD and
the red and brown lines are of RAPID. As the number of polygons increase, you
will see that the time taken by TELCD is far less compared with the RAPID
algorithm.
Click here to view Figure 3: Performance comparison between
TELCD and RAPID
Where do we need collision detection?
Assume there is a computer-simulated house with many chairs, tables and other
objects, and the user is free to move and arrange the furniture as he/she likes.
The user picks a chair and moves it to a table and if the chair penetrates the
table and the computer also allows it, it would be unrealistic and of very
little practical use. What is missing here is something that can detect the
collision between the two objects and prevent the unrealistic penetration.
Mathematically or graphically, wrongly moving the chair inside the table is
feasible but something must prevent it from penetrating it into another object.
The mechanism that can do this is collision detection, which can be used to
prevent objects from penetrating into other objects. Before any movement of an
object, this mechanism checks for collision with all the objects and if a
collision is found the object is restricted from moving.
Applications of collision detection
Collision detection is a crucial problem in robotics, computer animation,
interior decoration, molecular modeling, game development, tele-operations and
computer simulated environments. In these applications, an object's motion is
constrained by its collision with other objects in the scene and by other
dynamic constraints. In robotics, a robot's motion and path are constrained by
collisions with the other objects on the scene. Quite a few of the special
effects in computer or video games are all a result of collisions. Tele-surgery
is another advanced application of collision detection in surgery. If the expert
surgeon is in one country and the patient is in another country, the surgeon
operates on a virtual patient and a robot will operate on the real patient by
imitating the surgeon. Here, very precise and real-time collision detection is a
must. Similarly, for nuclear operations where humans cannot enter, a robot would
use collision detection to grasp and do operations. In computer-simulated
virtual reality environments, collision detection between objects and the human
is required to give force feedback/haptic feedback in order to make the virtual
world feel as good as the real for the human.
Click here to view Figure 4: Two rhinos: colliding polygons shown in red
color
Click here to view Figure 5: Collision sequence with leg movement
Future
Due to the non-availability of fast and precise collision detection algorithms
earlier, applications were built with simple or no collision detection
algorithms. With the availability of fast, real-time collision detection
algorithms, more and more applications will be developed with real-time 3D
graphics. So look forward to a bright animated future!!
The authors belong to the Visual Computing Group, Design and Development
Center of Tata Elxsi Ltd., Bangalore.