License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.34
URN: urn:nbn:de:0030-drops-72315
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7231/
Go to the corresponding LIPIcs Volume Portal

Demaine, Erik D. ; Tachi, Tomohiro

Origamizer: A Practical Algorithm for Folding Any Polyhedron

pdf-format:
LIPIcs-SoCG-2017-34.pdf (8 MB)

Abstract

It was established at SoCG'99 that every polyhedral complex can be folded from a sufficiently large square of paper, but the known algorithms are extremely impractical, wasting most of the material and making folds through many layers of paper. At a deeper level, these foldings get the topology wrong, introducing many gaps (boundaries) in the surface, which results in flimsy foldings in practice. We develop a new algorithm designed specifically for the practical folding of real paper into complicated polyhedral models. We prove that the algorithm correctly folds any oriented polyhedral manifold, plus an arbitrarily small amount of additional structure on one side of the surface (so for closed manifolds, inside the model). This algorithm is the first to attain the watertight property: for a specified cutting of the manifold into a topological disk with boundary, the folding maps the boundary of the paper to within epsilon of the specified boundary of the surface (in Fréchet distance). Our foldings also have the geometric feature that every convex face is folded seamlessly, i.e., as one unfolded convex polygon of the piece of paper. This work provides the theoretical underpinnings for Origamizer, freely available software written by the second author, which has enabled practical folding of many complex polyhedral models such as the Stanford bunny.

BibTeX - Entry

@InProceedings{demaine_et_al:LIPIcs:2017:7231,
  author =	{Erik D. Demaine and Tomohiro Tachi},
  title =	{{Origamizer: A Practical Algorithm for Folding Any Polyhedron}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7231},
  URN =		{urn:nbn:de:0030-drops-72315},
  doi =		{10.4230/LIPIcs.SoCG.2017.34},
  annote =	{Keywords: origami, folding, polyhedra, Voronoi diagram, computational geometry}
}

Keywords: origami, folding, polyhedra, Voronoi diagram, computational geometry
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI