|
|
|
|
Collision Detection and Proximity Queries
|
Efficient Local Planning Using Connection Collision QueryMin 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. |
|
Multi-core Collision Detection Between Deformable Models Using Front-based DecompositionMin 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. |
|
Highly Parallel Collision Avoidance for Multi-agent SimulationStephen 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. |
|
Fast Collision Detection for Deformable Models Using Representative-trianglesSean 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. |
|
A Fast and Practical Algorithm for Generalized Penetration Depth ComputationLiangjun 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. |
|
Interactive Continuous Collision Detection Between Deformable Models Using Connectivity-based CullingMin 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. |
|
Interactive Collision Detection Between Deformable Models Using Chromatic DecompositionNaga 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. |
|
Efficient Inter- and Intra-object Collision Culling Using Graphics HardwareNaga 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. |
|
Fast and Reliable Collision Culling Using Graphics ProcessorsNaga 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. |
|
Fast Collision Detection Between Massive Models Using Dynamic SimplificationSung-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. |
|
Fast Continuous Collision Detection for Articulated ModelsStephane 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. |
|
Interactive and Continuous Collision Detection for Avatars in Virtual EnvironmentsStephane 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. |
|
Fast Update of OBB-trees for Collision Detection Between Articulated BodiesHarald 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. |
|
Dual Hierarchies for Multi-resolution Collision DetectionMiguel 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. |
|
Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical RefinementYoung 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. |
|
Fast Penetration Depth Estimation for Elastic Bodies Using Deformed Distance FieldsSusan 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. |
|
Principal InvestigatorsResearch Sponsors |
Current MembersPast Members
|
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.
