Graphics Reference
In-Depth Information
specialization is relevant is particle collisions. Rather than sending particles one by
one through the normal collision system, they are better handled and submitted
for collision as groups of particles, where the groups may form and reform based
on context. Particles may even be excluded from collision, in cases where the lack of
collision is not noticeable.
Another example is the use of separate algorithms for detecting collision between
an object and other objects and between the object and the scene. Object-object
collisions might even be further specialized so that a player character and fast-moving
projectiles are handled differently from other objects. For example, a case where all
objects always collide against the player character is better handled as a hard-coded
test rather than inserting the player character into the general collision system.
Consider also the simulation of large worlds. For small worlds, collision data can
be held in memory at all times. For the large, seamless world, however, collision data
must be loaded and unloaded as the world is traversed. In the latter case, having
objects separate from the world structure is again an attractive choice, so the objects
are not affected by changes to the world structure. A possible drawback of having
separate structures for holding, say, objects and world, is that querying now entails
traversing two data structures as opposed to just one.
2.3
Types of Queries
The most straightforward collision query is the
interference detection
or
intersection
testing
problem: answering the Boolean question of whether two (static) objects,
A
and
B
, are overlapping at their given positions and orientations. Boolean intersec-
tion queries are both fast and easy to implement and are therefore commonly used.
However, sometimes a Boolean result is not enough and the parts intersecting must
be found. The problem of
intersection finding
is a more difficult one, involving finding
one or more points of contact.
For some applications, finding any one point in common between the objects
might be sufficient. In others, such as in rigid-body simulations, the set of contact-
ing points (the
contact manifold
) may need to be determined. Robustly computing
the contact manifold is a difficult problem. Overall,
approximate queries
— where the
answers are only required to be accurate up to a given tolerance — are much easier to
deal with than
exact queries
. Approximate queries are commonplace in games. Addi-
tionally, in games, collision queries are generally required to report specific collision
properties assigned to the objects and their boundaries. For example, such properties
may include slipperiness of a road surface or climbability of a wall surface.
If objects penetrate, some applications require finding the
penetration depth
. The
penetration depth is usually defined in terms of the
minimum translational distance
: the
length of the shortest movement vector that would separate the objects. Computing
this movement vector is a difficult problem, in general. The
separation distance
between
two disjoint objects
A
and
B
is defined as the minimum of the distances between points
