## Velocity Aligned Discrete Oriented Polytopes

*Dan Coming, and Oliver G. Staadt*

## 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 _{1}* and

*s*with velocity

_{2}

*v**=*

_{1}

*v**are shown in 2D with AABB and VADOP bounding volumes, respectively. The AABB uses standard axes*

_{2}

*a**and*

_{1}

*a**, whereas the VADOP selects axes*

_{5}

*a**and*

_{2}

*a**based on*

_{3}

*v**. Axes set*

_{2}*S*{

*a**...*

_{1}

*a**} is one possible set of axes available for the VADOP. Values*

_{8}*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

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]

## Links

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.

## Contact

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