Collision Detection and Proximity Query Packages

CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware

Naga K. Govindaraju, Stephane Redon, Ming C. Lin, and Dinesh Manocha

We present a novel approach for collision detection between multiple deformable and breakable objects in a large environment using graphics hardware. Our algorithm takes into account low bandwidth to and from the graphics cards and computes a potentially colliding set (PCS) using visibility queries. It involves no precomputation and proceeds in multiple stages: PCS computation at an object level and PCS computation at sub-object level, followed by exact collision detection. We use a linear time two-pass rendering algorithm to compute each PCS efficiently. The overall approach makes no assumption about the input primitives or the object's motion and is directly applicable to all triangulated models.

Package website...


DEEP: Dual-space Expansion for Estimating Penetration Depth

Young J. Kim, Ming C. Lin, and Dinesh Manocha

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.

Package website...


DVD: Fast Proximity Computation Among Deformable Models Using Discrete Voronoi Diagrams

Avneesh Sud, Naga K. Govindaraju, Russell Gayle, Ilknur Kabul, and Dinesh Manocha

We present algorithms to perform collision and distance queries among multiple deformable models in dynamic environments. These include inter-object queries between different objects as well as intra-object queries. We describe a unified approach to compute these queries based on N-body distance computation and use properties of the second order discrete Voronoi diagram (DVD) to perform N-body culling. Our algorithms involve no preprocessing and also work well on models with changing topologies.

Package website...


DEFORMCD: Collision Detection for Deforming Objects

Min Tang and Dinesh Manocha

DEFORMCD is a fast collision detection library designed to accelerate calculation for deforming objects. For deforming objects, whose vertices are vibrating, a AABB refitting solution is used for collision detection. The efficiency of the AABB-refitting schema is compared with OOBB-rebuild and AABB-rebuild schemas with timing. And we can achieve 5-10 times of speed up.

Package website...


H-COLLIDE: Fast and Accurate Collision Detection for Haptic Interaction

Arthur D. Gregory, Ming C. Lin, and Stefan Gottschalk

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 contacts 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 OBB-trees: For each cell consisting of a subset of polygons of the virtual model, we pre-compute an OBB-tree. At runtime, most of the computation time is spent in finding collisions between an OBB-tree 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 six 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.

Package website...


I-COLLIDE: Interactive and Exact Collision Detection for Large-scaled Environments

Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, and Madhav Ponamgi

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 n-body processing algorithm to 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 whenever the client wishes.

One of the great strengths of I-COLLIDE is that it returns 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.

Package website...


IMMPACT: Partitioning and Handling Massive Models for Interactive Collision Detection

Andy Wilson, Eric Larsen, Ming C. Lin, and Dinesh Manocha

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.

Package website...


PIVOT: Proximity Information from Voronoi Techniques

Kenneth E. Hoff III, Andrew Zaferakis, Ming C. Lin, and Dinesh Manocha

PIVOT, proximity information from Voronoi techniques, is currently a two-dimensional 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 two-dimensional 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.

Package website...


PQP: Fast Proximity Queries with Swept Sphere Volumes

Eric Larsen, Stefan Gottschalk, Ming C. Lin, and Dinesh Manocha

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 different queries. It makes use of swept sphere volumes as the choice of BV for distance queries. Furthermore, it allows the client program the flexibility of using more than one bounding volume for a given query. More details are available.

Package website...


RAPID: Robust and Accurate Polygon Interference Detection

Stefan Gottschalk, Ming C. Lin, and Dinesh Manocha

Of the packages, RAPID is the smallest and easiest to use. It works with polygon soups, which are just polygonal models which do not require any particular 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 coordinate 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 n-body 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.

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-processing queries explicitly, then RAPID is probably the right system for you.

Package website...


SELF-CCD: Continuous Collision Detection for Deforming Objects

Min Tang and Dinesh Manocha

SELF-CCD is a fast collision detection library for deforming objects. It performs both inter- and intra-object collisions. Moreover, it performs continuous collision detection between the discrete instances.

Package website...


SWIFT: Speedy Walking Via Improved Feature Testing

Stephen A. Ehmann and Ming C. Lin

SWIFT provides proximity 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.

Package website...


SWIFT++: Speedy Walking Via Improved Feature Testing for Non-convex Objects

Stephen A. Ehmann and Ming C. Lin

SWIFT++ provides proximity 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.

Package website...


V-COLLIDE: Accelerated Collision Detection for VRML

Thomas Hudson, Ming C. Lin, Jonathan D. Cohen, Stefan Gottschalk, and Dinesh Manocha

V-COLLIDE is an n-body 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-prune 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.

Package website...


This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.