Abstract

We propose an acceleration scheme for many-body dynamic collision detection at interactive rates. We use a tight bounding volume representation that offers fast update rates and that is particularly suitable for applications with fast-moving objects. The axes selection that determines the shape of our bounding volumes is based on spherical coverings. We demonstrate that we can detect robustly collisions that are missed by pseudo-dynamic collision detection schemes, without significant performance penalties.

In many applications with dynamic objects it is necessary to determine whether these objects intersect. This is the task of collision detection, a common requirement for virtual reality, augmented reality, animation, and video games, and a critical requisite for computer aided design, robotics, and physics-based simulations. In addition to determining exactly when and where two objects will intersect, subsequent collision response can be carried out to simulate, e.g., elastic collision. The aforementioned applications rely on accurate collision detection to provide realistic responses to user's actions and movements of objects in the scene, avoid collisions, or gather information about interactions.

In order to guarantee that collisions are not missed, we must consider time. For interactive applications, we limit collision detection to the time interval between consecutive frames. Dynamic collision detection requires solving parameterized equations involving both the position of an object and the velocity of the object to determine the first time of intersection of the objects. The benefits of this are twofold: the exact time and location of collision is known, and detecting all collisions is guaranteed.

We present Velocity-Aligned Discrete Oriented Polytopes (VADOP), bounding volumes based on k-DOPs. VADOPs offer faster update times than k-DOPs and are especially well-adapted for dynamic collision detection, as well as high object velocities, an uncommon trait in collision detection. VADOPs are also more well-behaved than AABBs or k-DOPs in the "sweep and prune" method from I-COLLIDE.

We define a VADOP as a bounding volume whose description consists of a number of axes, along with a pair of discrete values for each axis. Each pair of values bounds a discrete interval along the axis, representing the bounded object's maximum and minimum projection onto the axis. In this respect, the VADOP is similar to an AABB or k-DOP. The difference is in the selection of axes. Whereas the axes used for AABBs or k-DOPs are the same for all objects, the axes used for an object's VADOP are selected from a common pool of axes. Specifically, the axes selected for a VADOP are the axes in the pool which are orthogonal to the corresponding object's velocity vector. Due to this selection of axes, the bounding volume tends to be long, narrow, and velocity-aligned. (See figure below)

Objects s₁ and s₂ with velocity v₁ = v₂ are shown in 2D with AABB and VADOP bounding volumes, respectively. The AABB uses standard axes a₁ and a₅, whereas the VADOP selects axes a₂ and a₃ based on v₂. Axes set S{a₁...a₈} is one possible set of axes available for the VADOP. Values x_j^{min,max} are the projections of the objects onto axes a_j.

Using VADOPs, we are able to efficiently detect collisions among high-velocity objects that pseudo-dynamic collision detection schemes fail to detect. We are also able to demonstrate real-time performance of dynamic collision detection for high-velocity objects. In fact, we have achieved real-time frame-rates with up to 10,000 separate and independently-moving objects in a dense scene. With our framework, VADOPs are able to efficiently use any number of axes k from 1 to 78,000, the current limits set forth by spherical coverings.

Publications

Links

Contact