Efficient Collision Detection of Complex Deformable Models using AABB Trees

Gino van den Bergen
Eindhoven University of Technology

This paper appears in issue Volume 2, Number 4.
Purchase this issue from the akpeters.com web site.

Abstract

We present a scheme for exact collision detection between complex models undergoing rigid motion and deformation. The scheme relies on a hierarchical model representation using axis-aligned bounding boxes (AABBs). Recent work has shown that AABB trees are slower than oriented bounding box (OBB) trees for performing overlap tests. In this paper, we describe a way to speed up overlap tests between AABBs, such that for collision detection of rigid models, the difference in performance between the two representations is greatly reduced. Furthermore, we show how to update an AABB tree quickly as a model is deformed. We thus find AABB trees to be the method of choice for collision detection of complex models undergoing deformation. In fact, because they are not much slower to test, are faster to build, and use less storage than OBB trees, AABB trees might be a reasonable choice for rigid models as well.

Author Information

Gino van den Bergen, Eindhoven Univ of Tech/Dept of Math & CS, PO Box 5135600 MB Eindhoven, Netherlands gino@acm.org

Source Code

An implementation of the data structure presented in this paper is released as part of the Software Library for Interference Detection (SOLID) version 2.0. The complete C++ source code and documentation for SOLID 2.0 is available at http://www.win.tue.nl/cs/tt/gino/solid/.

BibTeX Entry

@article{vanDenBergen97,
  author = "Gino van den Bergen",
  title = "Efficient Collision Detection of Complex Deformable Models using AABB Trees",
  journal = "journal of graphics, gpu, and game tools",
  volume = "2",
  number = "4",
  pages = "1-14",
  year = "1997",
}