Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!uwvax!tank!eecae!cps3xx!flynn From: flynn@pixel.cps.msu.edu (Patrick J. Flynn) Newsgroups: comp.graphics Subject: Re: 3-D triangulation? Message-ID: <4129@cps3xx.UUCP> Date: 11 Aug 89 11:52:38 GMT References: Sender: usenet@cps3xx.UUCP Organization: Pattern Rec. & Image Processing Lab, CS, Michigan State U. Lines: 40 In article spencer@eecs.umich.edu (Spencer W. Thomas) writes: >Can someone point me to a 3-D "triangulation" algorithm? What we need >is something equivalent to the 2-D Delauney triangulation. I.e., we >want to create a set of tetrahedra that fill the space within the >convex hull of a set of randomly distributed 3-D points. > >I found reference to 3-D Voronoi diagrams in Preparata and Shamos, but >not even an algorithm (although there seems to be reference to work >that may contain an algorithm). And, in any case, it's not obvious >how to go from the Voronoi diagram to a triangulation. > >Reference to an accessible publication would be sufficient. In 3D vision, work has been done by J.D. Boissonnat and colleagues at INRIA. Boissonnat, ``Representation of Objects by Triangulating Points in 3D Space,'' Proc. 6ICPR, 830-832, 1982. Boissonnat, ``Representing 2D and 3D Shapes with the Delaunay triangulation,'' Proc. 7ICPR, 745-748, 1984. O'Rourke also did some early work. O'Rourke, ``Polyhedra of minimal area as 3D object models,'' Proc. 7th IJCAI, 664-666, 1981. Also see De Floriani, ``Surface representations based on triangular grids,'' The Visual Computer, v.3, 27-50, 1987. (Pub. by Springer-Verlag) Choi et al., ``Triangulation of Scattered Data in 3D Space,'' Comp. Aided Des. v. 20, n. 5, 239-248, 1988. (Pub. by Butterworths) Avis and ElGindy, ``Triangulating Point Sets in Space,'' Disc. Comput. Geom., v.2, 99-111, 1987. (Pub. by Springer-Verlag) ------------------------------------------------------------------------------ Patrick Flynn, CS, Mich. State Univ. -- flynn@cps.msu.edu -- uunet!frith!flynn " " -- Marcel Marceau