Some of the features of SWIFT are explained more in detail here. The
spirit of this page is to give a what and a why.
It is designed to more or less describe what is possible with the system and
give some motivation or reason for it.
For a detailed description of how to use the system, refer to the
user manual.
We are always looking for ways to improve SWIFT.
If you have any ideas of things we could add to the system that we have not
mentioned here or in the Future Versions section,
please let us know. To use non-convex polyhedral models, check out
SWIFT++.
the objects must be either convex or be a set of convex pieces (in a future version, this may be relaxed to allow arbitrary non-convex polyhedra)
The basis of the SWIFT system is to use a Lin-Canny type of algorithm to minimize the distance between two convex models. No bounding volume hierarchy is constructed to test for intersection directly. Bounding volume hierarchies are used at a higher level but in a different sense than in some packages like RAPID for example.
Thus, a requirement for the models that are processed by the SWIFT system is that they be convex or composed of convex pieces. Every closed object can be decomposed into a set of convex pieces but the SWIFT system does not do that for the application. The application is responsible for this decomposition if it is so desired. Each convex piece is treated like an object. Currently, there is no grouping of convex pieces within an object. The system will not test pairs of pieces that are part of the same object.
detecting whether two objects intersect (penetrate)
Some applications simply require knowledge of the presence of intersection in the scene. Likely, they will reject any configuration that is intersecting. Other applications require knowledge of all the pairs of intersecting objects in the scene so that they can compute a reaction for these objects.
There are two possible ways that SWIFT allows for intersection detection/testing. The first is to report TRUE or FALSE for the whole scene. The second reports a list of all the intersecting objects in the scene.
Currently, there is no measure of penetration depth given by SWIFT. It simply returns the pairs that are penetrating or a negative distance if distance is being computed. In the future, it is likely that we will provide some additional computation routines that can determine penetration depth given two objects that are known to be penetrating.
computing the minimum distance with an error bound between a pair of objects
SWIFT allows the computation of the distance between two objects to be performed approximately. This is most useful if hierarchies are used. If no hierarchy is used, then the approximate distance computation is the same as the exact distance computation. The approximate distance has a one-sided error since it is derived from bounding volume deviations. The application provides an error tolerance and a distance tolerance. The error tolerance is used to refine the approximate distance to the necessary precision. The distance tolerance is used to reject all pairs whose distance is greater than the tolerance. A minimum possible distance and an error bound are returned. The exact distance lies in the range [distance, distance+error] where the distance is less than the distance tolerance and the error is less than the error tolerance.
SWIFT allows the approximate distance to be computed between any pair of objects if their bounding boxes are overlapping (if this is enabled). The boxes may be enlarged to handle any tolerance the application wishes. Negative distances represent intersections. The negative distance, however, is not a measure of penetration. In addition, there is the option of stopping the entire scene test if intersection is found or of continuing and reporting all intersections as well (as negative distances).
computing the minimum distance between a pair of objects
SWIFT allows the exact distance to be computed between any pair of objects if their bounding boxes are overlapping (if this is enabled). The boxes may be enlarged to handle any tolerance the application wishes. The exact distance is only reported if it meets a given tolerance. Negative distances represent intersections. The negative distance, however, is not a measure of penetration. In addition, there is the option of stopping if intersection is found or of continuing and reporting all intersections as well (as negative distances).
computing the closest features (vertex,edge,face) on a pair of objects
Many times, an application is only interested in knowing when two objects come sufficiently close to warrant a response computation and what the features are that are closest. There are various contact items that may (optionally) be computed. They are: distance, nearest points, nearest feature ids, and contact normals.
SWIFT allows for contact determination queries which yield the pair of nearest features on all pairs or only on pairs of objects that are closer than some tolerance. Only certain combinations of vertex, edge, and face are possible: v-v, v-e, v-f, e-e. Only a single (arbitrary) pair of nearest features is returned to the application. There may very well be more than one pair of nearest features. Like the distance computations, computation can be stopped if there is an intersection detected, or the computation can continue and report all intersections as well as applicable nearest features.
query is significantly faster than other packages (I-Collide, V-Clip, Enhanced GJK)
Here are shown low level comparisons of the speed of V-Clip vs. SWIFT. Note that SWIFT performs significantly better on all tests than V-Clip.
We stress that these times are for distance minimization only. No bounding box, hierarchy, or caching scheme was built upon the low level algorithm. There are absolutely NO optimizations that are object specific. We measured the time taken to compute the distance between two randomly tessellated ellipsoids of 2000 triangles each, rotating around each other at various angular velocities per frame. We ran three tests, one for each type of object pair (fat, plate, long). We feel that this is a suitable benchmark for the low level behavior of these packages. More details on the exact test procedure are given in the technical report.
We did not compare I-Collide here because the paper that accompanies the V-Clip distribution put V-Clip equal or faster than I-Collide on all the benchmarks that were used. Likewise we did not compare against the enhanced GJK algorithm. All timings were taken on a single 300 MHz MIPS R12000.
Even though the comparisons here talk only of low level walking, it is also true that at a higher level, SWIFT out-performs other packages as well due to inclusion of hierarchical and non-coherence features (see the technical report).
as robust as or more robust than other packages
V-Clip is a robust system and has no error tolerances. SWIFT also contains no tolerances. Valid answers can be given for all but the most pathological cases (due to floating point computation).
In addition, we ran the test from the V-Clip paper named Algorithm 10. It is designed to probe an algorithm's robustness in degenerate situations. SWIFT passed this test.
a simplified bounding hierarchy around each object, which can either be provided by the application or created automatically, accelerates proximity queries
SWIFT allows each convex object or piece, to be (optionally) surrounded by a hierarchy of simpler bounding shells. These shells are useful to accelerate the walking around the object. They also possess a measure of deviation from the actual object so that queries may in fact be answered without descending the entire hierarchy for an object.
A feature unique to SWIFT is that the application may provide its own simplification hierarchy. SWIFT will automatically take care of the hierarchy's bounding properties and the deviation computation. Alternatively, SWIFT can build its own simplification hierarchy in two different ways. There is the modified Dobkin-Kirkpatrick method and the QSlim method. Each is described in detail in the technical report. A comparison of various acceleration methods is also given there.
efficient querying even if coherence is not present
Some applications exhibit high coherence but some do not. For those that do not, there may exist cases when coherence is very low. SWIFT can be configured to use a fast lookup scheme to provide a good initial starting point to the distance minimization routine. The additional cost of this lookup when coherence is high is small.
bounding boxes are placed around each object to prune unnecessary computation through a sweep and prune sorting algorithm
The sweep and prune algorithm that is used in I-Collide is also used in SWIFT. When there are more than two or three objects, it is useful to use since it helps to "cull" away large amounts of computation.
bounding boxes types can be chosen automatically
For an object's bounding box, there are essentially two choices. A cube which bounds the object at any orientation or a dynamic bounding box that is updated at each frame may be used. SWIFT is able to make an intelligent choice when an object is added to a scene about which bounding box type to use (if the application so desires).
objects that are declared static (fixed or not moving) are automatically optimized for and any pair may be activated or deactivated
Pairs may be activated or deactivated. SWIFT supports objects which can be declared static. Pairs that comprise two static objects are always deactivated. The application still has control over the other (non-static) pairs. Pairs of objects that will never interact should be deactivated.
objects may be added to a scene through arrays or through files of various formats and may be copied and deleted
To import object geometry into SWIFT is simple. It can be done in either of two main ways. Arrays describing vertex positions and connectivity can be passed to the object creation routines. Alternatively, filenames can be given which reference files that contain the geometry information. SWIFT file formats are supported (see user manual). The arrays and files do not have to contain triangle specifications. SWIFT can automatically triangulate models when they are imported.
Objects can be efficiently deleted and copied at runtime, allowing for dynamic scene management.
objects that are made of the same geometry can share that geometry
If multiple objects are described in the same way geometrically, it is wasteful to replicate the description. Since all the transformations are rigid, it is possible to share the geometry. SWIFT supports this type of sharing across objects. This does not work for differing transformations of pieces within an object however.
Author: Stephen Ehmann
Maintained by: ehmann@cs.unc.edu
Copyright 2000
Last Modification: Aug 15, 2001