SWIFT can be compared to various other packages in terms of functionality
provided. Packages that we consider are those that are publicly available.
A word about the spectrum of polyhedral proximity query algorithms is in order.
On one end is a set of algorithms that take advantage of convex models to
speed up proximity queries. These algorithms give a lot of useful proximity
information but are restricted to convex models.
At the other end of the spectrum are algorithms that can deal with arbitrary
collections of triangles. These algorithms can deal with any type of polyhedral
collection but are more restricted in the queries that they can answer.
Convex packages rely on objects being convex or composed of convex pieces. There are two main classes of algorithms that are used for convex polyhedral proximity query. One is the Voronoi region based Lin-Canny (LC) algorithm and its derivatives. Another one is the simplex-based Gilbert-Johnson-Keerthi (GJK) algorithm and its derivatives. V-Clip, an LC improvement and modification, was shown to be faster than the enhanced GJK algorithm. SWIFT is shown to be faster than V-Clip. Until the advent of V-Clip, GJK was the most robust. Now, SWIFT and V-Clip are more robust. Taking advantage of multiresolution representations in conjunction with LC, the H-Walk system, developed at Stanford, uses V-Clip as a subroutine along with an inner Dobkin-Kirkpatrick hierarchy (DKH) to "walk" more quickly to the minimum of the distance function. The SWIFT system uses an outer hierarchy of simpler bounding volumes to accelerate the walking. Below is a brief description of each publicly available package that provides exact distance and contact determination.
Polygon soup packages operate on lists of triangles. They typically create a hierarchy of bounding volumes whose leaf nodes are the triangles themselves. The hierarchies are composed of spheres, AABB's (Axis-Aligned Bounding Boxes), OBB's (Oriented Bounding Boxes), SSV's (Sphere-Swept Volumes), or k-DOP's (k-Discrete Oriented Polytopes). Since SWIFT is not in the same top-level category as these packages, the details of these packages are not given. More can be learned about them at their respective sites.
Author: Stephen Ehmann
Maintained by: email@example.com
Last Modification: Aug 15, 2001