Abstract

We propose Kinetic Sweep and Prune (KSP), 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.

Collision detection is a common and often critical requirement 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 providing realistic environments, accurate simulations, and both appropriate and robust user interactions. The level of accuracy in collision detection directly affects each of the aforementioned properties. While some situations involve relatively few objects, it is common to find scenarios with hundreds or more objects. Scenarios requiring many-body collision detection include: large or complex environments, collaborative environments, and complex or large-scale physical simulations.

KSP operates on a continuum of time, processing collisions, updates, and other events without any need for regular polling frequencies, usually called “frames”. Since collisions are usually irregularly distributed in time, this allows KSP to be both robust and efficient, avoiding both the penalties of missing collisions due to polling frequency as well as the high costs of polling for collisions too frequently.

Our method works independent of the underlying description of objects, which could be made up of triangles, point sets, or parameterized functions, for example. KSP requires an axis-projected bounding volume (BV) such as Axis-Aligned Bounding-Box (AABB) or Discrete Oriented Polytope (k-DOP), along with the motion of the BV for a time interval. This makes up a kinetic BV (moving BV as opposed to swept BV), which bounds the object for the interval. At any point in time, the objects' BV's and/or motions can be updated.

Further, KSP is independent of the motion of underlying objects, dependent only on the possibly simplified motion of the kinetic BV provided. Rotations and even deformations can be accounted for in the motion of the kinetic BV. It is also necessary that some methods for testing object interactions are defined. KSP works best with intersection methods that account for motion and time (i.e. dynamic intersection tests). When paired with dynamic intersection tests, KSP is guaranteed to not miss collisions.

For complex models, we use Oriented Bounding-Box Trees (OBBTrees) to reduce the number of intersection tests necessary. We have tested KSP with over 4000 rings composed of 64 triangles each, with results at interactive rates. Additionally, we have achieved similar results with 100 models composed of over 6000 triangles each.

Publications

Links

Contact