Straight skeletons of three-dimensional polyhedra

ABSTRACT

In this video we present an algorithm for computing the straight skeleton of a polyhedron in three dimensions.

REFERENCES

• 1: O. Aichholzer, F. Aurenhammer, D. Alberts, and B. Gartner,A novel type of skeleton for polygons, J. of Universal Computer Science, 1 (1995), 752--761.
• 2: Gill Barequet , David Eppstein , Michael T. Goodrich , Amir Vaxman, Straight Skeletons of Three-Dimensional Polyhedra, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_13]
• 3: Gill Barequet , Michael T. Goodrich , Aya Levi-Steiner , Dvir Steiner, Contour interpolation by straight skeletons, Graphical Models, v.66 n.4, p.245-260, July 2004 [doi>10.1016/j.gmod.2004.05.001]
• 4: E. Bittar, N. Tsingos, and M.-P. Gascuel, Automatic reconstruction of unstructured 3D data: Combining a medialaxis and implicit surfaces, Computer Graphics Forum,14 (1995), 457--468.
• 5: H. Blum, A transformation for extracting new descriptors of shape,in: Models for the Perception of Speech and Visual Form(W. Wathen-Dunn, ed.), MIT Press,362--380, 1967.
• 6: Siu-Wing Cheng , Antoine Vigneron, Motorcycle graphs and straight skeletons, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.156-165, January 06-08, 2002, San Francisco, California
• 7: E.D. Demaine, M.L. Demaine, J.F. Lindy, and D.L. Souvaine,Hinged dissection of polypolyhedra, Proc. 9th Workshop on Algorithms and Data Structures, Waterloo, Ontario, Canada,phLNCS, 3608,Springer-Verlag, 205--217, 2005.
• 8: Erik D. Demaine , Martin L. Demaine , Anna Lubiw, Folding and Cutting Paper, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.104-118, December 09-12, 1998
• 9: D. Eppstein and J. Erickson,Raising roofs, crashing cycles, and playing pool: Applications of adata structure for finding pairwise interactions,phDiscrete & Comp. Geometry,22 (1999), 569--592.
• 10: M. Held, On computing Voronoi diagrams of convex polyhedra by means of wavefront propagation, Proc. 6th Canadian Conf. on Computational Geometry,Saskatoon, Saskatchewan, Canada,128--133, 1994.
• 11: M.A. Price, C.G. Armstrong, and M.A. Sabin, Hexahedral mesh generation by medial surface subdivision: Part I. Solids with convex edges, Int. J. for Numerical Methods in Engineering,38 (1995), 3335--3359.
• 12: Mirela Tanase , Remco C. Veltkamp, Polygon decomposition based on the straight line skeleton, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777802]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Theory

Keywords:
medial axis, straight skeleton