spencer@eecs.umich.edu (Spencer W. Thomas) (08/09/89)
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. -- =Spencer (spencer@eecs.umich.edu)
flynn@pixel.cps.msu.edu (Patrick J. Flynn) (08/11/89)
In article <SPENCER.89Aug8181141@spline.eecs.umich.edu> 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