TR97-23

Efficient Algorithms for Two-Phase Collision Detection


    •  Brian Mirtich, "Efficient Algorithms for Two-Phase Collision Detection", Tech. Rep. TR97-23, Mitsubishi Electric Research Laboratories, Cambridge, MA, December 1997.
      BibTeX TR97-23 PDF
      • @techreport{MERL_TR97-23,
      • author = {Brian Mirtich},
      • title = {Efficient Algorithms for Two-Phase Collision Detection},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR97-23},
      • month = dec,
      • year = 1997,
      • url = {https://www.merl.com/publications/TR97-23/}
      • }
  • Research Area:

    Robotics

Abstract:

This article describes practical collision detection algorithms for robot motion planning. Attention is restricted to algorithms that handle rigid, polyhedral geometries. Both broad phase and narrow phase detection strategies are discussed. For the broad phase, an algorithm using axes-aligned bounding boxes and a hierarchical spatial hash table is described. For the narrow-phase, the Lin-Canny algorithm is presented. Alternatives to these algorithms are also discussed. Finally, the article describes a scheduling paradigm for managing collision checks that can further reduce computation time. Pointers to downloadable software are included.