Fast and Simple Geometric Proximity Queries Using Graphics Hardware

Kenneth E. Hoff III
Andrew Zaferakis
Ming Lin
Dinesh Manocha

PIVOT:Proximity Information from VOronoi Techniques
Abstract: We present a new approach for computing generalized proximity information of arbitrary 2D objects using graphics hardware.  Using multi-pass rendering techniques and accelerated distance computation we present a unified approach for performing a variety of proximity queries between objects.  These not only included detecting collisions, but also computing intersections, separation distance, penetration depth, and contact points and normals.  We use a hybrid geometry- and image-based apprach, that balances computation between CPU and graphics subsystems.  Geometric object-space techniques coarsely localize potential intersection regions or closest features between two objects, and image-space techniques compute the low-level proximity information in these localized regions.  Most of the proximity information is derived froma distance field computed using graphics hardware.  We demonstrate the performance in collision response computation for rigid and deformable body dynamics simulations.  Our approach provides proximity information at interactive rates for a variety of simulation strategies including backtracking and penalty-based collision responses.

Features: Our method supports the following proximity queries defined in the paper: collision detection, intersection checking, separation distance, penetration depth, contact points and normals.  The main features of our approach include:  generality, simplicity, efficiency, no precomputation, robustness, bounded error approximation, and portability.

           (click images for larger version)
Fast and Simple 2D Geometric Proximity Queries Using Graphics Hardware
(Acrobat) Kenneth E. Hoff III, Andrew Zaferakis, Ming Lin, and Dinesh Manocha. Appeared in Proc. of ACM Symposium on Interactive 3D Graphics, 2001.

Fast 3D Geometric Proximity Queries between Rigid and Deformable Models Using Graphics Hardware Acceleration
(Acrobat) Kenneth E. Hoff III, Andrew Zaferakis, Ming Lin, and Dinesh Manocha. UNC-CS Technical Report, 2002.

2D Voronoi Demo
Tutorial (mpeg, 5.8 Mb)

The tutorial for our collision detection method, this demonstrates the steps in determining the proximity information for two objects.

2D Rigid Body Dynamics and Collisions
Map Demo (mpeg, 0.8 Mb)
Map Demo Zoomed (mpeg, 1.0 Mb)

The continents in this demonstration are modeled as rigid bodies.  Notice the high complexity of the colliding coastlines.

3D Rigid Body Dynamics using 2D Collisions
Bumpercar Sim (mpeg, 2.3 Mb)
Linked 3's (mpeg, 1.7 Mb)
Gears (mpeg, 2.9 Mb)

This demostration shows how some 3D scenes can be simplified to a 2D collision detection problem.  Here we demostrate various convex rigid body scenes moving and interacting realistically.

3D Deformable Body Dynamics using 2D Collisions
No Collision Response (mpeg, 1.3 Mb)
Collision Response 1 (mpeg, 2.2 Mb)
Collision Response 2 (mpeg, 2.7 Mb)
Separation Force (mpeg, 0.5 Mb)

This demonstration shows two deformable jello disks colliding and responding based on their penetration.  The models are deforming, showing how our method is dynamic and does not rely on any precomputation.

Army Research Office
Department of Energy ASCI Program
National Science Foundation
Office of Naval Research
Collision Detection
UNC Collide Group

Hardware Accelerated Voronoi Computation
Fast Computation of GVD using Graphics Hardware

UNC Geometry Group

PIVOT2D is now available for downloading, please visit our download page.
Copyright 2000. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

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.
last updated: 5.9.01