Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!ucbvax!ucsd!pacbell.com!pacbell!barn!everexn!roger
From: roger@everexn.com (Roger House)
Newsgroups: comp.graphics
Subject: Re: 3D convex hull algorithms
Message-ID: <1990Sep17.193645.4486@everexn.com>
Date: 17 Sep 90 19:36:45 GMT
References: <16029@thorin.cs.unc.edu>
Organization: Everex Systems, Inc.
Lines: 19

In <16029@thorin.cs.unc.edu> bergman@alanine.cs.unc.edu (Larry Bergman) writes:

>I'm looking for references/implementations
>of 3D convex hull algorithms.  I'm familiar
>with 2D algorithms, but not 3D.  I'll 
>appreciate any pointers.

Introduction to Computational Geometry, Preparata and Shamos, Springer-Verlag,
NY, 1985 describes a 3d hull algorithm.  A real-world implementation of the
algorithm in Preparata and Shamos is described by Day, A.M., "The Implementa-
tion of an Algorithm to Find the Convex Hull of a Set of Three-Dimensional
Points", ACM Transactions on Graphics, vol. 9, no. 1 (Jan. 1990), 105-132.

The latter paper is very interesting in that it shows that "[A]s is often the
case with geometric algorithms, the original publication tends to give a
rather concise strategic outline that emphasizes the complexity analysis but
glosses over implementation issues."

						Roger House