Collision detection has been a fundamental problem in computer animation, physically-based modeling, geometric modeling, and robotics. In these applications, interactions between moving objects are modeled by dynamic constraints and contact analysis. The motions of the objects are constrained by various interactions, including collisions.
A virtual environment, like a walkthrough, creates a computer-generated world, filled with virtual objects. Such an environment should give the user a feeling of presence, which includes making the images of both the user and the surrounding objects feel solid. For example, the objects should not pass through each other, and things should move as expected when pushed, pulled or grasped. Such actions require accurate collision detection, if they are to achieve any degree of realism. However, there may be hundreds, even thousands of objects in the virtual world, so a naive algorithm could take a long time just to check for possible collisions as the user moves. This is not acceptable for virtual environments, where the issues of interactivity impose fundamental constraints on the system. A fast and interactive collision detection algorithm is a fundamental component of a complex virtual environment.
Physically-based modeling simulations depend highly on the physical interaction between objects in a scene. Complex physics engines require fast, accurate, and robust proximity queries to maintain a realistic simulation at interactive rates. We couple our proximity query research with physically-based modeling to ensure that our packages provide the capabilities of today's physics engines.
These systems have been applied to large-scaled interactive environments and simulations. None of the algorithms make any assumption on the motions of the objects; that is, their motions are not assumed to be expressible as a closed-form function of time. In many applications, this is important because it can be difficult to predict a user's motion in a virtual environment or completely express the dynamic constraints for an object in a complex simulation. We have been working on issues related to collision detection between massive models composed of millions of primitives. Our H-COLLIDE collision detection system for haptic interaction has been used in an interactive multi-resolution modeling and three-dimensional painting system, called InTouch. The PIVOT system, has been used in rigid- and deformable-body simulations, providing intersecting points, penetration depth, and separation distance in a penalty-based dynamics simulator. For a brief description of all our packages click here.
Other Recent Projects in Collision Detection and Proximity Queries
Efficient Local Planning Using Connection Collision Query Min Tang, Young J. Kim, and Dinesh Manocha We introduce a proximity query, connection collision query (CCQ), and use it for efficient and exact local planning in sampling-based motion planners. Given two collision-free configurations, CCQ checks whether these configurations can be connected by a given continuous path that either lies completely in the free space or penetrates any obstacle by a given threshold. Our approach is general, robust, and can handle different continuous path formulations. We have integrated the CCQ algorithm with sampling-based motion planners and can perform reliable local planning queries with little performance degradation, as compared to prior methods. Moreover, the CCQ-based exact local planner is about an order of magnitude faster than prior exact local planning algorithms. Project website...
Multi-core Collision Detection Between Deformable Models Using Front-based Decomposition Min Tang and Dinesh Manocha We present a parallel algorithm for fast continuous collision detection (CCD) between deformable models using multi-core processors. We use a hierarchical representation to accelerate these queries and present an incremental algorithm that exploits temporal coherence between successive frames. Our formulation distributes the computation among multiple cores by using fine-grained front-based decomposition. We also present efficient techniques to reduce the number of elementary tests and analyze the scalability of our approach. We have implemented the parallel algorithm on eight-core and sixteen-core PCs, and observe up to 7x and 13x speedups respectively, on complex benchmarks. Project website...
Highly Parallel Collision Avoidance for Multi-agent Simulation Stephen J. Guy, Ming C. Lin, and Dinesh Manocha We present the ClearPath collision avoidance algorithm between multiple agents for real-time simulations. ClearPath extends the velocity obstacle (VO) from robotics and formulates the conditions for collision-free navigation as a quadratic optimization problem. We use a discrete optimization method to efficiently compute the motion of each agent and parallelize the algorithm by exploiting data and thread-level parallelism. ClearPath can robustly handle dense scenarios with hundreds of thousands of heterogeneous agents in a few milliseconds. Project website...
Fast Collision Detection for Deformable Models Using Representative-triangles Sean Curtis and Dinesh Manocha We present a new approach to accelerate collision detection for deformable models. Our formulation applies to all triangulated models and significantly reduces the number of elementary tests between features of the mesh, i.e., vertices, edges and faces. We introduce the notion of representative-triangles, standard geometric triangles augmented with mesh feature information and use this representation to achieve better collision query performance. The resulting approach can be combined with bounding volume hierarchies and works well for both inter-object and self-collision detection. We demonstrate the benefit of representative-triangles on continuous collision detection for cloth simulation and _N_-body collision scenarios. We observe up to a one-order of magnitude reduction in feature-pair tests and up to a 5x improvement in query time. Project website...
A Fast and Practical Algorithm for Generalized Penetration Depth Computation Liangjun Zhang, Young J. Kim, and Dinesh Manocha We present an efficient algorithm to compute the generalized penetration depth between rigid models. Given two overlapping objects, our algorithm attempts to compute the minimal translational and rotational motion that separates the two objects. We formulate the generalized penetration depth computation based on model-dependent distance metrics using displacement vectors. As a result, our formulation is independent of the choice of inertial and body-fixed reference frames, as well as specific representation of the configuration space. Furthermore, we show that the optimum answer lies on the boundary of the contact space and pose the computation as a constrained optimization problem. We use global approaches to find an initial guess and present efficient techniques to compute a local approximation of the contact space for iterative refinement. Project website...
Interactive Continuous Collision Detection Between Deformable Models Using Connectivity-based Culling Min Tang, Sean Curtis, Sung-Eui Yoon, and Dinesh Manocha We present an interactive algorithm for continuous collision detection between deformable models. We introduce two techniques to improve the culling efficiency and reduce the number of potentially colliding triangle candidate pairs. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh from self-collision tests. Second, we exploit the mesh connectivity and introduce the concept of orphan sets to eliminate almost all redundant elementary tests between adjacent triangles. In particular, we can reduce the number of elementary tests by many orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, _N_-body simulations and breaking objects. Project website...
Interactive Collision Detection Between Deformable Models Using Chromatic Decomposition Naga K. Govindaraju, Ilknur Kabul, Russell Gayle, Ming C. Lin, and Dinesh Manocha We present an algorithm for accurately detecting all contacts, including self-collisions, between deformable models. We precompute a chromatic decomposition of a mesh into non-adjacent primitives using graph coloring algorithms. The chromatic decomposition enables us to check for collisions between non-adjacent primitives using a linear-time culling algorithm. As a result, we achieve higher culling efficiency and significantly reduce the number of false positives. We use our algorithm to check for collisions among complex deformable models consisting of tens of thousands of triangles for cloth modeling and medical simulation. Project website...
Efficient Inter- and Intra-object Collision Culling Using Graphics Hardware Naga K. Govindaraju, Ming C. Lin, and Dinesh Manocha We present a fast collision culling algorithm, QUICK-CULLIDE, for performing inter- and intra-object collision detection among complex models using graphics hardware. Our algorithm is based on CULLIDE and performs visibility queries on the GPUs to eliminate a subset of geometric primitives that are not in close proximity. We present an extension to CULLIDE to perform intra-object or self-collisions between complex models. Furthermore, we use a novel visibility-based classification scheme to compute potentially-colliding and collision-free subsets of objects and primitives that considerably improves the culling performance. Project website...
Fast and Reliable Collision Culling Using Graphics Processors Naga K. Govindaraju, Ming C. Lin, and Dinesh Manocha We present a reliable culling algorithm, R-CULLIDE, that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs to eliminate a subset of primitives that are not in close proximity. To overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. Our algorithm can perform reliable GPU-based collision queries at interactive rates on all types of models, including non-manifold geometry, deformable models, and breaking objects. Project website...
Fast Collision Detection Between Massive Models Using Dynamic Simplification Sung-Eui Yoon, Brian Salomon, Ming C. Lin, and Dinesh Manocha We present an approach for collision detection between large models composed of tens of millions of polygons. Each model is represented as a clustered hierarchy of progressive meshes (CHPM). CHPM is a dual hierarchy of the original model; it serves both as a multi-resolution representation of the original model, as well as a bounding volume hierarchy. We use the cluster hierarchy of a CHPM to perform coarse-grained selective refinement and the progressive meshes for fine-grained local refinement. We present a novel conservative error metric to perform collision queries based on the multi-resolution representation. We use this error metric to perform dynamic simplification for collision detection. Our approach is conservative in that it may overestimate the set of colliding triangles, but never misses collisions. Furthermore, we are able to generate these hierarchies and perform collision queries using out-of-core techniques on all triangulated models. Project website...
Fast Continuous Collision Detection for Articulated Models Stephane Redon, Young J. Kim, Ming C. Lin, and Dinesh Manocha We present an algorithm to perform continuous collision detection for articulated models. Given two discrete configurations of the links of an articulated model, we use an arbitrary in-between motion to interpolate its motion between two successive time steps and check the resulting trajectory for collisions. Our approach uses a three-stage pipeline: dynamic bounding-volume hierarchy (D-BVH) culling based on interval arithmetic; culling refinement using the swept volume of line swept sphere (LSS) and graphics hardware accelerated queries; exact contact computation using OBB-trees and continuous collision detection between triangular primitives. The overall algorithm computes the time of collision, contact locations and prevents any interpenetration between the articulated model with the environment. Project website...
Interactive and Continuous Collision Detection for Avatars in Virtual Environments Stephane Redon, Young J. Kim, Ming C. Lin, and Dinesh Manocha We present an algorithm for continuous collision detection between a moving avatar and its surrounding virtual environment. We model the avatar as an articulated body using line-skeletons with constant o sets and the virtual environment as a collection of polygonized objects. Given the position and orientation of the avatar at discrete time steps, we use an arbitrary in-between motion to interpolate the path for each link between discrete instances. We bound the swept-space of each link using a swept volume (SV) and compute a bounding volume hierarchy to cull away links that are not in close proximity to the objects in the virtual environment. We generate the SVs of the remaining links and use them to check for possible interferences and estimate the time of collision between the surface of the SV and the objects in the virtual environment. Furthermore, we use graphics hardware to perform the collision queries on the dynamically generated swept surfaces. Our overall algorithm requires no pre-computation and is applicable to general articulated bodies. Project website...
Fast Update of OBB-trees for Collision Detection Between Articulated Bodies Harald Schmidl and Ming C. Lin Our work presents a new, faster oriented bounding box (OBB) algorithm which is especially helpful and beneficial for building box hierarchies for articulated, human-like figures. One of the largest critiques of using OBBs is that they can be very slow to update. Our main contribution lies in the fast update of the box hierarchy when the joints in the articulation hierarchy are updated. Our method provides a comparable fit to other methods of calculating loose fitting OBBs but with considerably faster speed. Project website...
Dual Hierarchies for Multi-resolution Collision Detection Miguel A. Otaduy and Ming C. Lin We present contact levels of detail (CLOD), a framework for multi-resolution collision detection. Given a polyhedral model, our algorithm automatically builds a dual hierarchy, both a multi-resolution representation of the original model and its bounding volume hierarchy for accelerating collision queries. We have proposed various error metrics, including object-space errors, velocity dependent gap, screen-space errors and their combinations. At runtime, our algorithm uses these error metrics to select the appropriate levels of detail independently at each potential contact location. Compared to the existing exact collision detection algorithms, we observe significant performance improvement using CLODs on some benchmarks, with little degradation in the visual rendering of simulations. Project website...
Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical Refinement Young J. Kim, Miguel A. Otaduy, Ming C. Lin, and Dinesh Manocha We present an algorithm to compute penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translation distance to separate them using a combination of object-space and image-space techniques. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest-point query using rasterization hardware and refines the estimated PD by object-space walking. It uses bounding volume hierarchies, model simplification, object-space, and image-space culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. Project website...
Fast Penetration Depth Estimation for Elastic Bodies Using Deformed Distance Fields Susan M. Fisher and Ming C. Lin We present a penetration depth estimation algorithm between deformable polyhedral objects. We assume the continuum of non-rigid models are discretized using standard techniques, such as finite element or finite difference methods. As the objects deform, the distance fields are deformed accordingly to estimate penetration depth, allowing enforcement of non-penetration constraints be- tween two colliding elastic bodies. This approach can automatically handle self-penetration and inter-penetration in a uniform manner. Project website...
Current Members Sean Curtis Past Members Jonathan D. Cohen Stephen A. Ehmann Susan M. Fisher Russell Gayle Stefan Gottschalk Naga K. Govindaraju Arthur D. Gregory Stephen J. Guy Kenneth E. Hoff III Thomas Hudson Ilknur Kabul Young J. Kim Eric Larsen Miguel A. Otaduy Amol Pattekar Madhav K. Ponamgi Stephane Redon Brian Salomon Harald Schmidl Avneesh Sud Min Tang Gokul Varadhan Nolan Walker Andy Wilson Sung-Eui Yoon Andrew Zaferakis Liangjun Zhang
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.
