QuickCD Collision Detection Library

[James Klosowski]

QuickCD  Version 1.00
---------------------

We are pleased to announce the release of QuickCD, an efficient
collision detection package for large polygonal environments.

QuickCD has been implemented in C and tested upon a variety of UNIX
platforms (SGI, Sun, Linux PC).  It accepts as input general polygonal
models (often called ``polygon soup''), and can easily handle cracks,
self-intersections, and other deficiencies of the input data.

Our method is based upon building bounding-volume hierarchies to
approximate the input models.  Our choice of bounding volume is to use
a ``discrete orientation polytope'', or what we have come to call a
``k-dop'', which is a convex polytope whose facets are determined by
halfspaces whose outward normals come from a small fixed set of k
orientations.

Due to our choice of bounding volume, the construction of the
hierarchies and the collision detection algorithm are straight-forward
and very efficient, both in terms of memory requirements and speed.
Another nice feature of our library is that we are able to exploit
temporal coherence as objects move from one step to the next.

QuickCD has been around for a while, although, until now, only with
limited distribution.  It was first announced at SIGGRAPH'96
(Vis. Proc., p. 151), where it was compared with the state-of-the-art
RAPID system, based on OBB-trees (SIGGRAPH'96).  A more complete
description of the data structures and algorithms used within the
QuickCD library is given in its journal publication: ``Efficient
Collision Detection using Bounding Volume Hierarchies of k-DOPs'',
which can be found in IEEE Transactions on Visualization and Computer
Graphics, vol. 4, no. 1, pp. 21--36, Jan--March 1998.  See also the
PhD thesis of J. Klosowski for further details.

In comparisons with other publicly available collision detection
libraries, QuickCD has performed very favorably.

The QuickCD library has been developed at the Computational Geometry
Lab at the State University of New York at Stony Brook.  It has been
written by:

Jim Klosowski         (jklosow at ams.sunysb.edu)
Martin Held           (held at ams.sunysb.edu)
Joseph S.B. Mitchell  (jsbm at ams.sunysb.edu)


For further information and instructions on how to obtain the source
code and example data sets, please visit the QuickCD web page:

http://www.ams.sunysb.edu/~jklosow/quickcd/QuickCD.html

Please direct comments and questions concerning QuickCD (including
being added to the mailing list) to quickcd at ams.sunysb.edu


Thank you.

Jim Klosowski

-------------------------------------------------------------------------
James T. Klosowski                       Tel   : 516-632-8366
Department of Applied Mathematics        Fax   : 516-632-8490
SUNY Stony Brook                         WWW   : www.ams.sunysb.edu/~jklosow
Stony Brook, NY 11794-3600               Email : jklosow at ams.sunysb.edu
-------------------------------------------------------------------------


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.