Paper by Erik D. Demaine
- Erik D. Demaine and Tomohiro Tachi, “Origamizer: A Practical Algorithm for Folding Any Polyhedron”, in Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia, July 4–7, 2017, 34:1–34:15.
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 ε 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
- In Japanese: 一枚の紙から折るだけでありとあらゆる立体形状を実現するアルゴリズム
- The paper is available in PDF (8160k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Origamizer (Origamizer: A Practical Algorithm for Folding Any Polyhedron)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated February 10, 2020 by