Suppose
. One of the most convenient geometric models to
express is a set of triangles, each of which is specified by three
points,
,
,
. This model
has been popular in computer graphics because graphics acceleration
hardware primarily uses triangle primitives. It is assumed that the
interior of the triangle is part of the model. Thus, two triangles
are considered as ``colliding'' if one pokes into the interior of
another. This model offers great flexibility because there are no
constraints on the way in which triangles must be expressed; however,
this is also one of the drawbacks. There is no coherency that can be
exploited to easily declare whether a point is ``inside'' or
``outside'' of a 3D obstacle. If there is at least some coherency,
then it is sometimes preferable to reduce redundancy in the
specification of triangle coordinates (many triangles will share the
same corners). Representations that remove this redundancy are called
a *triangle strip*, which is a sequence of triangles such that
each adjacent pair shares a common edge, and a *triangle fan*,
which is a triangle strip in which all triangles share a common vertex.
See Figure 3.6.

Steven M LaValle 2012-04-20