Collision Detection/Proximity Query Packages

DEEP

DEEP, Dual-space Expansion for Estimating Penetration Depth, is an incremental algorithm to estimate the penetration depth between convex polytopes along with the associated penetration direction. Here, penetration depth (PD) is defined as the minimum translation distance to make the interiors of two polytopes disjoint.

DEEP finds a "locally optimal solution" by walking on the surface of the Minkowski sums. Furthermore, DEEP is designed to fully utilize the frame-to-frame motion coherence in the environment.

More about DEEP

SWIFT++ provides proxmity queries such as intersection detection, tolerance verification, exact and approximate distance computation, and contact determination of general three-dimensional polyhedral objects undergoing rigid motion.

SWIFT++ operates by first computing a surface decomposition of the input models. The pieces are then grouped hierarchically using convex hulls. A pair of bounding volume hierarchies (BVHs) are tested using an improved Lin-Canny closest feature tracking algorithm. SWIFT++ uses the SWIFT core for the overlap test between convex pieces in the BVHs.

More about SWIFT++

PIVOT, Proximity Information from VOronoi Techniques, is currently a 2D proximity engine. The engine utilizes hardware accelerated multi-pass rendering techniques and distance computation to perform a variety of proximity queries between objects.

The supported queries include detecting collisions, computing intersections, separation distances, penetration depth, and contact points with normals. We use a hybrid geometry- and image-based approach that balances CPU and graphics subsystems that allows the use to customize settings for their particular application.

PIVOT handles 2D simple closed polygons. The polygon can be non-convex however, saving the application the problem of decomposing objects into triangles. PIVOT has performed very well in applications that require detailed information about the proximity even when objects are penetrating, such as penalty-based simulators.

PIVOT2D has been released to the public.

More about PIVOT

SWIFT provides proxmity queries such as intersection detection, exact and approximate distance computation, and contact determination of three-dimensional objects undergoing rigid motion. The allowed objects are convex polyhedra or composite objects constructed from convex pieces.

SWIFT uses a sweep and prune test to remove uninteresting pairs from further consideration and then uses an improved Lin-Canny closest features algorithm to find the answer for the "close" pairs of objects.

The I-COLLIDE package provides a subset of the functionality provided by SWIFT. In addition, SWIFT is much faster and more robust, so it should be used instead of I-COLLIDE.

More about SWIFT

H-Collide is a framework for fast and accurate collision detection for haptic interaction. It consists of a number of algorithms and a system specialized for computing contact(s) between the probe of the force-feedback device and objects in the virtual environment. To meet the stringent performance requirements for haptic interaction, we use an approach that specializes many earlier algorithms for this application. Our framework utilizes:

• Spatial Decomposition: It decomposes the workspace into uniform grids or cells, implemented as a hash table to efficiently deal with large storage requirements. At runtime, the algorithm can quickly find the cell containing the path swept out by the probe.

• Bounding Volume Hierarchy based on OBBTrees: An OBBTree is a bounding volume hieachy and each node of the hieachy corresponds to a tight-fitting oriented bounding box (OBB). For each cell consisting of a subset of polygons of the virtual model, we pre-compute an OBBTree. At run-time, most of the computation time is spent in finding collisions between an OBBTree and the path swept out by the tip of the probe between two successive time steps. To optimize this query, we have developed a very fast specialized overlap test between a line segment and an OBB, that takes as few as 6 operations and only 36 arithmetic operations in the worst case, not including the cost of transformation.

• Frame-to-Frame Coherence: Typically, there is little movement in the probe position between successive steps. The algorithm utilizes this coherence by caching the contact information from the previous step to perform incremental computations.

More about H-COLLIDE

PQP

As compared to RAPID, PQP also provides support for distance computation and tolerance verification queries (in addition to collision detection). Its API is similar to that of RAPID. It is applicable to general polygonal models and needs no topological information. Given two models, PQP supports a number of diffeent queries. It makes use of swept sphere volumes as the choice of BV for distance queries. Futhermore, it allows the client progam the flexibility of using more than one bounding volume for a given query. More details are available.

More about PQP

V-COLLIDE is an "Nbody" processor built on top of the RAPID system. Once your client program tells V-COLLIDE where all the models are in world space, V-COLLIDE performs a fast sweep-and-pune operation to decide which pairs of models are potentially in contact, and then for each potential contact pair it uses RAPID to determine true contact status. V-COLLIDE remembers where all the models are, and you can update some or all of the model placements by telling V-COLLIDE their new placements - RAPID makes incremental changes in the potential contact information with each placement modification.

V-COLLIDE also works with polygon soups, and reports only contact status (but not distance).

If you have many complex objects, many of which can bump into many of the other objects, then V-COLLIDE is probably the right choice.

In addition to updating the models' positions, the client program can also add or delete models from the collection being managed by the V-COLLIDE collision detection engine.

V-COLLIDE also supports multiple independent collision detection engines.

More about V-COLLIDE

Of the packages, RAPID is the smallest and easiest to use. It works with "polygon soups", which ae just polygonal models which do not require any paticular topological structure, such as forming a mesh or even a closed object. RAPID will accept a cloud of disconnected triangles as a model. RAPID does require that the models be composed of triangles (as opposed to quadrilaterals, for instance).

Given two models and their placement within a world coodinate system, RAPID returns a list of the triangle contact pairs - where each contact pair is a triangle taken from each model. If the list it returns is an empty list, then the models do not touch.

To process a pair of models, the client program must explicitly call a collision procedure, passing those two models and their placements. Hence, RAPID does not perform "Nbody" processing - which is the determination of which pairs of a collection of models are in contact. RAPID only processes a specific pair of models upon an explicit command from the client program.

So, if you have a small or moderate number of complex polygonal models on which you (as author of the client program) are willing to make pair-pocessing queries explicitly, RAPID is probably the right system for you.

More about RAPID

I-COLLIDE only works for models which are convex polyhedra. But it exploits the special characteristics of convex polytopes to very quickly determine contact status. It also exploits temporal coherence, so that collision query times are extremely fast when the models are moved only a relatively small amount between frames.

I-COLLIDE employs a similar "Nbody" processing algorithm as does V-COLLIDE. I-COLLIDE maintains the placements of all the models, and updates the potential contact pair list as the models placements' are modified. So, objects may be added and deleted from the managed set wheve the client wishes.

One of I-COLLIDE's great strengths is that it retuns the distance between interesting pairs of objects (you get to decide beforehand what pairs are considered interesting).

The SWIFT package provides the same functionality as I-COLLIDE and more. It is also faster and much more robust and should be used instead.

More about I-COLLIDE

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the "regions of interest" within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off-line, pre-processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub-graphs to check the corresponding geometry for proximity and pre-fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding-volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real-time on such a model.

More about IMMPACT