

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 subobject level, followed by exact collision detection. We use a linear time twopass 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: Dualspace Expansion for Estimating Penetration Depth
Young J. Kim, Ming C. Lin, and Dinesh Manocha
DEEP, dualspace 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 frametoframe 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 interobject queries between different objects as well as intraobject queries. We describe a unified approach to compute these queries based on Nbody distance computation and use properties of the second order discrete Voronoi diagram (DVD) to perform Nbody culling. Our algorithms involve no preprocessing and also work well on models with changing topologies.
Package website...


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 AABBrefitting schema is compared with OOBBrebuild and AABBrebuild schemas with timing. And we can achieve 510 times of speed up.
Package website...


HCOLLIDE: Fast and Accurate Collision Detection for Haptic Interaction
Arthur D. Gregory, Ming C. Lin, and Stefan Gottschalk
HCOLLIDE 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 forcefeedback 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: For each cell consisting of a subset of polygons of the virtual model, we precompute an OBBtree. At runtime, 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 six operations and only 36 arithmetic operations in the worst case, not including the cost of transformation.
Frametoframe 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...


ICOLLIDE: Interactive and Exact Collision Detection for Largescaled Environments
Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, and Madhav Ponamgi
ICOLLIDE 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.
ICOLLIDE employs a similar nbody processing algorithm to VCOLLIDE. ICOLLIDE 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 ICOLLIDE 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 ICOLLIDE 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 offline, preprocessed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized subgraphs to check the corresponding geometry for proximity and prefetch geometry and auxiliary data structures. To perform interactive proximity queries, we use boundingvolume 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 realtime 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 twodimensional proximity engine. The engine utilizes hardware accelerated multipass 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 imagebased approach that balances CPU and graphics subsystems that allows the use to customize settings for their particular application.
PIVOT handles twodimensional simple closed polygons. The polygon can be nonconvex 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 penaltybased 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 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.
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 pairprocessing queries explicitly, then RAPID is probably the right system for you.
Package website...


SELFCCD: Continuous Collision Detection for Deforming Objects
Min Tang and Dinesh Manocha
SELFCCD is a fast collision detection library for deforming objects. It performs both inter and intraobject 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 threedimensional 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 LinCanny closest features algorithm to find the answer for the close pairs of objects.
The ICOLLIDE 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 ICOLLIDE.
Package website...


SWIFT++: Speedy Walking Via Improved Feature Testing for Nonconvex 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 threedimensional 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 LinCanny closest feature tracking algorithm. SWIFT++ uses the SWIFT core for the overlap test between convex pieces in the BVHs.
Package website...


VCOLLIDE: Accelerated Collision Detection for VRML
Thomas Hudson, Ming C. Lin, Jonathan D. Cohen, Stefan Gottschalk, and Dinesh Manocha
VCOLLIDE is an nbody processor built on top of the RAPID system. Once your client program tells VCOLLIDE where all the models are in world space, VCOLLIDE performs a fast sweepandprune 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.
VCOLLIDE remembers where all the models are, and you can update some or all of the model placements by telling VCOLLIDE their new placements  RAPID makes incremental changes in the potential contact information with each placement modification.
VCOLLIDE 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 VCOLLIDE 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 VCOLLIDE collision detection engine. VCOLLIDE 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.
