A Fast and Robust GJK Implementation for Collision Detection of Convex Objects

Gino van den Bergen
Eindhoven University of Technology

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

Abstract

This paper presents an implementation of the Gilbert-Johnson-Keerthi algorithm for computing the distance between convex objects, that has improved performance, robustness, and versatility over earlier implementations. The algorithm presented here is especially suitable for use in collision detection of objects modeled using various types of geometric primitives, such as boxes, cones, and spheres, and their images under affine transformation.

Author Information

Gino van den Bergen, Dept of Math & CS, Eindhoven University of Technology, PO Box 5135600 MB Eindhoven, Netherlands gino@win.tue.nl

Source Code

The GJK implementation discussed in this paper is released as part of the Software Library for Interference Detection (SOLID) version 2.0. Also, a standalone demo package, called GJK-engine, has been made available. The complete C++ source code for both packages can be downloaded from http://www.win.tue.nl/~gino/solid/.

BibTeX Entry

@article{vanDenBergen99,
  author = "Gino van den Bergen",
  title = "A Fast and Robust GJK Implementation for Collision Detection of Convex Objects",
  journal = "journal of graphics, gpu, and game tools",
  volume = "4",
  number = "2",
  pages = "7-25",
  year = "1999",
}