Ecient Collision Detection for
Animation and Robotics
Ming C. Lin
Department of Electrical Engineering
and Computer Science
University of California, Berkeley
Berkeley, CA,
Ecient Collision Detection for Animation and Robotics
by
Ming Chieh Lin
B.S. (University of California at Berkeley) 1988
M.S. (University of California at Berkeley) 1991
A dissertation submitted in partial satisfaction of the
requirements for the degree of
Doctor of Philosophy
in
Engineering - Electrical Engineering
and Computer Sciences
in the
GRADUATE DIVISION
of the
UNIVERSITY of CALIFORNIA at BERKELEY
Committee in charge:
Professor John F. Canny, Chair
Professor Ronald Fearing
Professor Andrew Packard
1993
Ecient Collision Detection for Animation and Robotics
Copyright c
1993
by
Ming Chieh Lin
i
Abstract
Ecient Collision Detection for Animation and Robotics
by
Ming Chieh Lin
Doctor of Philosophy in Electrical Engineering
and Computer Science
University of California at Berkeley
Professor John F. Canny, Chair
We present ecient algorithms for collision detection and contact determina-
tion between geometric models, described by linear or curved boundaries, undergoing
rigid motion. The heart of our collision detection algorithm is a simple and fast
incremental method to compute the distance between two convex polyhedra. It uti-
lizes convexity to establish some local applicability criteria for verifying the closest
features. A preprocessing procedure is used to subdivide each feature's neighboring
features to a constant size and thus guarantee expected constant running time for
each test.
The expected constant time performance is an attribute from exploiting the
geometric coherence and locality. Let n be the total number of features, the expected
run time is between O(
p
n) and O(n) depending on the shape, if no special initial-
ization is done. This technique can be used for dynamic collision detection, planning
in three-dimensional space, physical simulation, and other robotics problems.
The set of models we consider includes polyhedr