Velocity Aligned Discrete Oriented Polytopes

Dan Coming, and Oliver G. Staadt



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)

Diagram AABB versus VADOP
Objects s1 and s2 with velocity v1 = v2 are shown in 2D with AABB and VADOP bounding volumes, respectively. The AABB uses standard axes a1 and a5, whereas the VADOP selects axes a2 and a3 based on v2. Axes set S{a1...a8} is one possible set of axes available for the VADOP. Values xj{min,max} are the projections of the objects onto axes aj.

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.


Coming, D. and Staadt, O. "Velocity-Aligned Discrete Oriented Polytopes for Dynamic Collision Detection". IEEE Transactions on Visualization and Computer Graphics (2007), to appear.

Coming, D. and Staadt, O. "Velocity-Aligned Discrete Oriented Polytopes for Dynamic Collision Detection", Technical Report No. CSE-2005-25, Sep. 2004, Department of Computer Science, UC Davis [PDF]


VADOPs are well-adapted for use with the "Sweep and Prune" method in the I-COLLIDE system.
We rely on spherical coverings for optimal axis sets for VADOPs.


Daniel Coming coming@cs.ucdavis.edu
Oliver Staadt staadt@cs.ucdavis.edu