SWIFT - Relation to Other Packages

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 Based Packages

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.

• SWIFT is an improved LC implementation
  • Provides sweep and prune bounding box support
  • Employs outer bounding hierarchies to speedup walking
  • Performance can be made independent of motion coherence
  • Allows objects composed of convex pieces
  • Allows only for rigid motion
  • Very robust
  • Can add objects through arrays or files

• V-Clip is an improved LC implementation
  • Does not provide sweep and prune bounding box support
  • Allows objects composed of convex pieces
  • Allows only for rigid motion
  • Requires QHULL only if using convex decompositions
  • Very robust
  • Can add objects through arrays or files

• I-Collide is the original LC implementation
  • Provides sweep and prune bounding box support
  • Allows only for rigid motion
  • Not very robust
  • Can only add objects through files

Polygon Soup Based Packages

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.

• SWIFT++ is an implementation using convex hull bounding volumes and is used for intersection detection, tolerance verification, exact and approximate minimum distance computation, and disjoint contact determination

• RAPID is an implementation using OBB bounding volumes and is used for intersection detection

• PQP is an implementation using SSV bounding volumes and is used for intersection detection, tolerance verification, and exact and approximate minimum distance computation

• QuickCD is an implementation using k-DOP bounding volumes and is used for intersection detection

• V-Collide uses RAPID along with AABB sweep and prune and is used for intersection detection

Author: Stephen Ehmann

Maintained by: ehmann@cs.unc.edu

Copyright 2000

Last Modification: Aug 15, 2001