Graphics Reference
In-Depth Information
many objects there are, their relative sizes and positions, if and how they move, if
they are allowed to interpenetrate, and whether they are rigid or flexible.
4.
Performance
. Real-time collision detection systems operate under strict time and
size restrictions. With time and space always being a trade-off, several features are
usually balanced to meet stated performance requirements.
5.
Robustness
. Not all applications require the same level of physical simulation. For
example, stacking of bricks on top of each other requires much more sophistication
from a collision detection system than does having a basketball bouncing on a
basketball court. The ball bouncing slightly too early or at a somewhat larger
angle will go unnoticed, but even the slightest errors in computing contact points
of stacked bricks is likely to result in their slowly starting to interpenetrate or slide
off each other.
6.
Ease of implementation and use
. Most projects are on a time frame. Scheduling
features of a collision detection system means nothing if the system cannot
be completed and put in use on time. Decisions regarding implementational
simplicity therefore play a large role in what approach is taken.
These issues are covered in further detail in the remainder of the chapter.
2.2
Application Domain Representation
To select appropriate collision detection algorithms, it is important to consider the
types of geometrical representations that will be used for the scene and its objects. This
section talks briefly about various object representations, how simplified geometry
can be used instead of modeling geometry, and how application-specific knowledge
can allow specialized solutions to be used over more generic solutions.
2.2.1
Object Representations
Most current hardware uses triangles as the fundamental rendering primitive.
Consequently, a
polygonal representation
is a natural choice for scenes and scene
objects, as well as for their corresponding collision geometry. The most generic polyg-
onal representation is the
polygon soup
: an unordered collection of polygons with no
connectivity information specifying how one polygon relates to another. With no
inherent constraints, the polygon soup is an attractive representation for artists and
level designers. Algorithms operating on polygon soups apply to any collection of
polygons but tend to be less efficient and less robust than those relying on additional
information. For example, a polygon soup contains no information regarding the
“inside”of an object, so there is no easy way of finding out if an object has somehow
