A presentation as a part of CS698R - Robot Motion Planning, a Semester
Course.
Instructor: Dr. Amitabh Mukherjee.
Author: Digvijay Singh Lamba
Collision detection is a fundamental problem in computer animation, computer graphics, physically based modeling, and robotics. For applications and simulations in these domains to be convincing, they should not only render realistic images but should also precisely model object interactions such as pushing, striking, or deforming other objects. Detecting collisions, computing distances, and determining exact contact manifolds are of fundamental importance to the ability to model these interactions accurately. Researchers have written extensively about the issues concerning collision detection and distance computation, but actually building a general-purpose, robust, and efficient system for complex scenes and deformable objects remains an outstanding research challenge.
The collision detection (CD) problem takes as input a geometric model of a
scene or environment (e.g., a large collection of complex CAD models), together with a set of one or more
moving (``flying'') objects, possibly articulated, and asks that we determine all instants in time at which
there exists a nonempty intersection between some pair of flying objects, or between a flying object and
an environment model.
Usually, we are given some information about how the flying objects are moving,
at least at the current instant in time; however, the motions may change rapidly, depending on the
evolution of a simulation (e.g., modeling some physics of the system), or due to input devices under
control of the user. In some applications, it is important to make computations based on the geometry of the
region of intersection between pairs of colliding objects.
Pair processing vs. nbody processing
If the problem involves only a pair of models, we call it ``pair processing.''
If we have many different parts, we call it ``Nbody processing,'' in reference
to the classic problem in celestial mechanics (many bodies moving under mutual gravitational influence).
Motions: static vs. dynamic
Queries are often executed repeatedly on the same models in the same
environment, as the objects rotate and translate (or possibly subject to
nonrigid transformations ) at successive time steps. In these
dynamic environments, the geometric relationship may only differ slightly
from that of the previous step, if the motion between steps is relatively
small. Algorithms that can capitalize on this property are said to be
exploit temporal coherence.
In order to exploit temporal coherence, some algorithms require bounds the
motion of the objects (e.g. objects' velocities or accelerations). Other algorithms, such as the ones based on interval arithmetic, need a
closed form expression of the motion as a function of time.
Some algorithms demand no information on the motion, but need only
the placements of the objects at successive time steps.
Sometimes the problem involves objects which are not in motion. For
example, given a model of an entire power plant, design engineers may be
interested in performing static interference checks among components of
the entire plant for tolerance verification and access clearance.
Rigid bodies vs. deformable models
When the component of time is introduced, there is also the possibility that the models deform over time. Assuming that the deformations
between time steps are small, some algorithms may be able to exploit
temporal coherence in this case as well.
The problem is encountered in computer aided design and machining (CAD/CAM), robotics and automation, manufacturing, computer graphics, animation and computer simulated environments. Collision detection enables simulation based design, tolerance verification, engineering analysis, assembly and disassembly, motion planning, animated figure articulation, walkthrough, etc. All these tasks involve contact analysis and spatial reasoning among static or moving objects. In many of these application areas, collision detection is considered a major computational bottleneck. Collision detection is an essential component of robot motion planning and control, where it helps to steer the robot away from its surrounding obstacles. In virtual prototyping, it is used to refine designs without productions of physical prototypes in the initial design stage. Collision detection can also be a significant aid in simulation for engineering analysis. Experiments which are impractical to conduct can be simulated, such as support design for tunnels. Another example is automobile crash test and ergonomics analysis which can be done systematically at much lower cost and more controlled conditions.
Polygonal objects are the most commonly used models in computer graphics and modeling. They have a simple representation. They are versatile. Hardware accelerated rendering of polygon is widely available. The most general class of polygonal model is the ``polygon soup,'' which is a collection of polygons that are not geometrically connected and has no topology information available. If the polygons form a closed manifold, then the model has a well defined inside and outside -- it is a proper solid. Some geometric algorithms rely on this structure. If the object defined by the closed manifold is convex, then this additional structure can be exploited in collision detection algorithms.
Constructive Solid Geometry or CSG forms objects from primitives such as blocks, spheres, cylinders, cones, and tori, by combining them with set theoretic operations such as union, intersection, and set difference. One strength of the CSG representation is that it enables an intuitive design process of building shapes by means of cutting (intersection and set difference) and joining (union) simple shapes to form more complex ones. It also makes finding a collision witness easier. The difficulty with CSG is that certain operations, such as rounding an edge or filleting a join, are difficult to describe with CSG operations. Furthermore, an accurate boundary or surface representation, useful for rendering or interference computations, can be hard to compute from CSG representations
Implicit surfaces are defined using implicit functions. They are defined
with mappings from space to the real numbers, f : R 3 7 -> R, and the
implicit surfaces are the loci of points where f(x; y; z) = 0. Such a function
defines unambiguously what is inside the model; f(x,y,z)<0 and what
is outside, f(x; y; z) > 0. Consequently, implicit surfaces are generically
closed manifolds, a desirable property.
If the function is polynomial in x, y, and z, then it is called algebraic, which includes the algebraic surfaces,
higher order functions and convolution surfaces. Implicits are also often used as
the primitives in CSG systems.
A special case of algebraic surfaces are the quadrics, which are the
second degree polynomials in x, y, and z. These can represent slabs, cones,
spheres, and cylinders in a unified framework. They are widely used in
a number of applications and a number of specialized algorithms have
been developed for intersection computations between quadrics
Parametric surfaces are mappings from some subset of the plane to space. Unlike implicit surfaces, parametric surfaces are not generally closed manifolds. Hence, unlike CSG and implicit surfaces, they do
not represent a complete solid model, but rather a description of surface
boundary.
Parametric surfaces are easier to polygonalize and render as compared
to the implicits, and a special class called the NonUniform Rational BSpline (NURBS) has gained in popularity in CAD. NURBS
have some very nice properties which make them easier to operate on.
They can also be represented using B'ezier patches. It is worth noting
that rational parametric surfaces (like NURBS and B'ezier patches) are a
proper subset of algebraic surfaces.
The input models are composed of many hundreds of thousands of polygons.
2. Unstructured Representation:The input models are represented as collections of polygons with no topology information. Such models are also known as `polygonsoups’ and their boundaries may have cracks, T-joints, or may have non-manifold geometry. No robust techniques are known for cleaning such models.
3. Close Proximity:In the actual applications, the models can come in close proximity of each other and can have multiple contacts.
4. Accurate Contact Determination:The applications need to know accurate contacts between the models (up to the resolution of the models and machine precision).
In general, given two spline surfaces, there is no good and quick solution to the problem of whether they intersect or have a common geometric contact. The simplest solution is based on using subdivision and checking the control polytopes or convex bounding boxes for collision.
Since CSG objects are defined using set operations, the intersection problem is conceptually trivial. To test if two object are touching, simply take their set intersection. If the result is the null set, then the objects are disjoint, otherwise they collide . However, this requires efficient ways to compute whether an intersection yields the empty set or not. This is sometimes called the ``Null Object Detector'', or NOD. One possible solution involves computing a boundary representation of the resulting solid. However, efficient, accurate and robust computation of the boundary remains a hard problem for CSG models described using curved primitives.
Interval arithmetic may be employed to evaluate implicit functions over boxlike regions of space to determine whether the regions lie entirely
inside, entirely outside, or potentially laying across the boundary of the
implicit surfaces. This is the familiar point classification scheme extended
to regions obtained from adaptive subdivision of space. This technique
is intrinsically approximate. It may not be able to determine the contact
status of disjoint models which are almost touching.
This method is adaptive subdivision over the space in which the models
are embedded, and the precision of the results is limited to the fineness of
the subdivision. Allowing for the finite precision of the method, it is an
extremely robust and concise formulation of the problem, as well as easy
to implement. It is also an expensive method which will not perform real
time collision detection on large models with current computing hardware.
There are four techniques for finding the intersection of two parametric surfaces: subdivision methods, lattice methods, tracing methods, and analytic methods. Many practitioners actually use some combination of these.
1. Subdivision methods for parametric surfaces All subdivision methods for parametric surfaces work by recursively subdividing the domain of the two surface patches in tandem, and examining the spatial relationship between patch subsections. Depending on various criterion, the subsections are further subdivided and recursively examined, or the given recursion branch is terminated. In all cases, whether it is the intersection curve or the distance function, the solution is known only to finite precision, according to how finely the domain has been subdivided and how it maps into space.
2. Lattice methods
The intersection curve of two surfaces in space has a preimage curve on
the domains of both patches. Lattice methods attempt to locate specific
points of these preimages by selecting many isoparametric curves (where
a u or vparameter is held constant) which crisscross the surface like a
latticework. Selecting a value for u on one of the patches reduces
the dimensionality of the search space to one -- the only free variable is v
on that patch.
So, we can express the points of surface intersection as the zeroes of a
function of v. An analysis of the degree of the polynomial and the derivatives
allow us to perform root trapping techniques to robustly find where
the intersection preimage meets the isoparametric curve. The difficulty
with this method is that the intersection curve can be a very small closed
loop which is missed by the isoparametric curves -- this most often occurs
when the surfaces are grazing or barely penetrating. In some cases, lattice
methods or subdivision methods are used to find starting points for use
by the tracing methods.
3. Tracing methods The tracing method begins with a given point known to be on the intersection curve. Then the intersection curve is traced in sufficiently small steps until the edge of the patch is found, or until the curve returns to itself to close a loop. While it is easy to check for meetings with a patch boundary, it is difficult to know when the tracing point has returned to its starting position, as it requires the use of some arbitrarily chosen tolerance. Frequently this is posed as an initial value differential equations problem or solving a system of algebraic equations. At the intersection point on the surfaces, the intersection curve must be mutually orthogonal to the normals of the surfaces. Consequently, the vector field which the tracing point must follow is given by the cross product of the normals.
4. Analytic methods
Analytic methods usually involve implicitizing one of the parametric surfaces -- obtaining an implicit representation of the model. The parametric surface is a mapping from (u; v)space to (x; y; z)space, and
the implicit surface is a mapping from (x; y; z)space to the real numbers.
By substituting the parametric functions fx(u; v); fy(u; v); fz(u; v) for
the x; y; z of the implicit function, we obtain a scalar function in u and v.
The locus of roots of this scalar function map out curves in the (u; v) plane
which are the preimages of the intersection curve. Based on its representation as an algebraic plane curve, efficient
algorithms have been proposed by a number of researchers.
We can use implicit functions to represent shape and the property of the ``insideoutside'' functions for collision detection. Besides its restriction to implicits, the algorithm has a drawback in terms of robustness as it only uses point samples. Efficient algorithms for curved models composed of either spline surfaces and algebraic surfaces undergoing rigid motion, using extension of algorithms for polyhedra, hierarchical representation and equation solving techniques. These algorithms work well on mostly low degree primitives.
1. Bounding Volumes: The simplest algorithms for collision detection in polygonal models are based on using bounding volumes and spatial decomposition techniques in a hierarchical manner. Typical examples of bounding volumes include axis-aligned boxes (of which cubes are a special case) and spheres, and they are chosen for to the simplicity of finding collision between two such volumes.
2. Hierarchical Structures: These include cone trees, k-d trees and octrees, sphere trees, Rtrees and their variants, trees based on S-bounds etc.
3. Spatial Representations: Other spatial representations are based on BSP’s and
its extensions to multi-space partitions, spatial representations
based on space-time bounds or four-dimensional
testing and many more.
All of these hierarchical methods do very well in performing rejection tests,
whenever two objects are far apart. However, when the
two objects are in close proximity and can have multiple
contacts, these algorithms either use subdivision techniques
or check very large number of bounding volume pairs for
potential contacts. In such cases, their performance slows
down considerably and they become a major bottleneck in
the simulation.
4. Computational Geometry: In computational geometry, many theoretically efficient algorithms have been proposed for polyhedral objects. Most of them are either restricted to static environments, convex objects, or only polyhedral objects undergoing rigid motion. However, their practical utility is not clear as many of them have not been implemented in practice.
5. Linear Programming: Other approaches are based on linear programming and computing closest pairs for convex polytopes and based on line-stabbing and convex differences for general polyhedral models.
6. Spacial and Temporal Coherence: Algorithms utilizing spatial and temporal coherence have been shown to be effective for large environments represented as union of convex polytopes. However, these algorithms and systems are restrictive in terms of application to general polygonal models with unstructured representations. Thus all the above have inherent weaknesses when used in problems with characteristics typical to the Robot Motion Planning applications.
Hierarchical Bounding Volumes HBV's have been extensively used to speed up several collision detection and other interference computations. In terms of application to large models, two main issues arise: how can we compute a tight-fitting HBV enclosing a model and how quickly can we test two such boxes for overlap? For polygonal models, specifically for those with the given characteristics HBV's tend to perform extremely well.
Spheres as bounding volumes have a very simple implementation. We will not discuss them further here.
Axis-aligned bounding boxes, or AABBs, are the easiest ones. For a vintage Asteroids-spaceship, they might look like this:
The sides of an AABB are always aligned to the main coordinate axes (X, Y and Z). The box never rotates, even when your object does. This property makes it extremely easy to detect collisions between two AABBs. Formally: if two boxes, A and B, are at positions Pa and Pb respectively, then let T = Pa - Pb. Furthermore, if each box has a width, height and depth (W, H, D), then the boxes collide if
| |Tx| <= (Wa + Wb) and | |
| |Ty| <= (Ha + Hb) and | |
| |Tz| <= (Da + Db); where |x| = Abs(x) |
It's that easy, and more importantly, it's that fast! If you want to find out if the player is colliding with other entities, simply check the AABBs. If either of the three tests fails, the axis in question is called the separating axis. Remember this for later.
An AABB test is easy and fast, but it's not always very accurate. If you want a slightly more precise solution, you can use oriented bounding boxes, or OBBs. OBBs look like this:
If you rotate an object, the box rotates with it. An OBB can be represented by six planes, or by storing local coordinate axes for it. If you use local axes, you can store position and size just like you would do for an AABB. OBBs are slightly harder to work with, because you can't just do a separating axis test on X, Y and Z. You could still do a separating axis test, using the local coordinate axes, but there's another, easier way out as we will see.
Cost comparison of various kinds of bounding boxes:
Given two large models and their
hierarchical representation, the total cost function for
interference
detection can be formulated as the following cost
equation:
T = Nv Cv + Np Cp; where
T: total cost
function for interference detection,
Nv: number of
bounding volume pair overlap tests
Cv: cost of testing
a pair of bounding volumes for overlap,
Np: is the number
primitive pairs tested for interference,
Cp: cost of testing
a pair of primitives for interference.
Given this cost function, various hierarchical data structures are
characterized by Choice of Bounding Volume:
The choice is governed by two conflicting constraints:
1. It should fit the original model as tightly as possible
(to lower Nv and Np).
2. Testing two such volumes for overlap should be as fast
as possible (to lower Cv).
Simple primitives like spheres and AABBs do very well with respect to the second constraint. But they cannot fit some primitives like long-thin oriented polygons tightly. On the other hand, minimal ellipsoids and OBBs provide tight fits, but checking for overlap between them is relatively expensive.
Furthermore, given two models, the total cost of interference detection varies considerably with relative placement of the models. In particular, when two models are far apart, hierarchical representations based on spheres and AABBs work well in practice. However, when two models are in close proximity with multiple number of closest features, the number of pair-wise bounding volume tests, Nv increases, sometimes also leading to an increase in the number pair-wise primitive contact tests, Np. For a given model, Nv and Np for OBBTrees tend to be smaller as compared to those of trees using spheres or AABBs as bounding volumes. At the same time, the best known earlier algorithms for finding contact status of two OBBs were almost two orders of magnitude slower than checking two spheres or two AABBs for overlap.
The algorithm contains a large number of mathematical calculations and figures. Download this pdf file and study it for details of the algorithms.
paper with the algo for Collision Detection using OBB's
Dynamic collision detection is of two types.
1. For collision detection between objects with constant linear velocity and no angular velocity click here.
2. For collision detection between objects with constant linear velocity and constant angular velocity click here.
For more information and detailed algorithm on Proximity queries including:
1. Collision Detection using proximity queries.
2. Distance calculation using proximity queries.
1. ICOLLIDE collision detection system
http://www.cs.unc.edu/~geom/I_COLLIDE.html
ICOLLIDE is an interactive and exact collision detection library for environments composed of many convex polyhedra or union of convex pieces, based on the expected constant time, incremental distance computation algorithm and algorithms to check for collision between multiple moving objects.
2. RAPID interference detection system
http://www.cs.unc.edu/~geom/OBB/OBBT.html.
RAPID is a robust and accurate polygon interference detection library for pairs of unstructured polygonal models. It is applicable to polygon soups -- models which contain no adjacency information and obey no topological constraints. It is most suitable for close proximity configurations between highly tesselated smooth surfaces.
3. VCOLLIDE collision detection system
http://www.cs.unc.edu/~geom/V_COLLIDE
VCOLLIDE is a collision detection library for large dynamic environments, and unites the nbody processing algorithm of ICOLLIDE and the pair processing algorithm of RAPID. It is designed to operate on large numbers of static or moving polygonal objects to allow dynamic addition or deletion of objects between timesteps.
4. Distance computation between convex polytopes
http://www.comlab.ox.ac.uk/oucl/users/stephen.cameron/distances.html
This package is an enhanced and dynamic version of the distance routine of Gilbert, Johnson and Keerthi (GJK), which allows the tracking of the distance between a pair of convex polyhedra. It requires a list of all the edges in each convex polyhedra for best performance. Its performance is comparable to LinCanny convex polytope overlap test.
5. SOLID interference detection system
http://www.win.tue.nl/cs/tt/gino/solid/
SOLID is a library for interference detection of multiple threedimensional polygonal objects (including polygon soups) undergoing rigid motion. Its performance and applicability is comparable to that of VCOLLIDE.
6. VClip collision detection system
http://www.merl.com/people/mirtich/vclip.html
The Voronoi Clip, or VClip, algorithm is a lowlevel collision detection algorithm for polyhedral objects -- an improvement of the closestfeature tracking algorithm. It operates on a pair of convex polyhedra, or nonconvex hierarchies of them. In addition to distance computation, it can also report penetration points and estimated penetration distance between overlapping models.