Kinetic Sweep and Prune for Collision Detection.pdf

Workshop On Virtual Reality Interaction and Physical Simulation (2005) F. Ganovelli and C. Mendoza (Editors) Kinetic Sweep and Prune for Collision Detection Daniel S. Coming and Oliver G. Staadt Institute for Data Analysis and Visualization Department of Computer Science University of California, Davis Abstract We propose an acceleration scheme for real-time many-body dynamic collision detection. We kinetize the sweep and prune method for many-body collision pruning, extending its application to dynamic collision detection via kinetic data structures. In doing so, we modify the method from sample-rate driven to event-driven, with no more events than the original method processed, also removing the per-frame overhead, allowing our method to scale well in terms of frame-rates. Unlike many schemes for many-body collision pruning, ours performs well in both sparse and dense environments, with few or many collisions. Categories and Subject Descriptors (according to ACM CCS): I.3.6 [Computer Graphics]: Methodology and Techniques—Graphics data structures and data types; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism—Virtual reality General Terms: Algorithms, Performance, Reliability Additional Key Words and Phrases: dynamic collision detection and kinetic data structures 1. Introduction Collision detection is a common and often critical require- ment for virtual and augmented reality, haptics, and physical simulations. The work of collision detection is to determine if/when objects intersect, or interact, which is useful in pro- viding realistic environments, accurate simulations, and both appropriate and robust user interactions. The level of accu- racy in collision detection directly affects each of the afore- mentioned properties. While some situations involve rela- tively few objects, it is common to find scenarios with hun- dreds or more objects. Scenarios requiring many-body colli- sion detection include: large or complex environments, col- laborat