Up: Directory of Computational Geometry Software



Collision detection library for moving convex polyhedra. Uses properties of convexity and coherence between simulation time steps to get fast and accurate results. Has been used in a number of applications. For more information, links to technical papers, and pointers to the code, look at the Web page.

By Jon Cohen, Ming C. Lin, Dinesh Manocha, and M.K. Ponamgi at U. North Carolina, and Brian Mirtich and John Canny at U.C. Berkeley.

Canny-Lin collision detection

The original C implementation of the Canny-Lin collision detection algorithm by
Brian Mirtich is available from Berkeley.


One-shot collision detection for sets of triangles in 3D. Fast and small. The OBB algorithm, described in a recent Siggraph paper, uses a hierarchy of arbitrarily oriented bounding boxes.

By S. Gottschalk, Ming Lin, and Dinesh Manocha, at UNC.
Info, C++ source code and paper available from the
Web page.

Also check out the collision detection program for convex polytopes by Rabbitz in Graphics Gems IV.

Constraint solver

A very classy geometric constraint solver, embedded in a mechanical design tool, which you can look at on the Web. Lots of theoretical and practical information on constraint solving.

By Chris Hoffman, Willaim Bouma, Xiangping Chen, Ioannis Fudos, and Pamela J. Vermeer, at Purdue.

Euslisp is a robotics testbed written in LISP.

Robot localization

Software to enter a polygonal map and solve the Robot Localization Problem, which is to decide where a robot is located based on the visibility polygon it can `see' as it moves around, is available by email. In C++ and LEDA.

See the Web site describing the project for more details.
By Hartmut Noltemeier, Oliver Karch and others at the University of Wuerzburg.

Up: Directory of Computational Geometry Software

[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu