An algorithm has been created that generates instructions for folding origami of any shape

In 1999, Erik Demaine, then an 18-year-old graduate student at Waterloo University in Canada, described an algorithm that could determine how to fold a sheet of paper into any conceivable three-dimensional shape. This was a significant milestone in the field of computational origami, but the algorithm could not create folding schemes that could really be put into practice.

Essentially, the algorithm took as a basis a very long strip of paper and folded it into the desired shape. The resulting structures, as a rule, had many seam lines, where the layers of paper tape were superimposed on each other, forming folds, due to which the resulting structures were not very strong.

In 1999, Demane proved that any polyhedron can be folded, but the way this can be achieved is not the most effective. The proposed method works if the original sheet of paper is long and narrow. But if you need to work, for example, with a square sheet, then the algorithm will still first fold the paper to a thin strip, wasting all the material in vain.

Now professor of electrical engineering and computer science at the Massachusetts Institute of TechnologyEric Demain and his colleague Tomohiro Tachi from the University of Tokyo are ready to announce the completion of a quest that began in 1999: in July 2017, they will present an algorithm for creating origami at a symposium on computational geometry that guarantees the smallest possible number of stitches. Demain and Tachi are also working on implementing the algorithm in the new version of Origamizer, a free software for generating origami drawings. The first version was released by Tachi in 2008.

The researchers algorithm develops bend patterns to create any polyhedron, that is, a three-dimensional surface consisting of many planes. Computer graphics software models three-dimensional objects as polyhedrons, consisting of many tiny triangles.



Strictly speaking, the guarantee that folding the sheet will include a minimum number of seams means that it preserves the “borders” of the original sheet of paper. Suppose you have a round sheet of paper and want to fold a cup from it. By leaving a smaller circle in the center of this sheet, you can join the sides.

In this case, the cup boundary — its rim — is the same as the boundary of the extended circle — its outer edge. Demane’s previous algorithm did the same: the bowl he proposed was made up of a thin strip of paper wrapped in a reel, and probably could not hold water.

The mathematical property that distinguishes between both methods, scientists call "water resistance." So the new algorithm saves the border of the original sheet of paper on the border of the surface that the user is trying to make. A closed surface, such as a sphere, has no border, so origami will require a seam where these borders meet. We cannot get a completely enclosed surface, but we can choose where to draw the border.


Folding the surface according to the previous Demane algorithm (left) and "waterproof" (right). The border of the sheet is indicated by a thick line.

At the first stage, the algorithm projects the faces of the desired shape onto a flat surface. But at the time when the faces will be in contact, when the folding is completed, they can be quite far apart from each other on a flat surface. The user adds all the additional materials and combines the edges of the figure. Folding additional material can be a very complex process. Folds combining several sides may include tens or even hundreds of individual folds.


Orgamizer scheme for folding a rabbit

The development of a method for automatically calculating origami instructions included several different ideas, but the central one that could be called approximately corresponding to the Voronoi diagram. To understand this concept, the authors propose to imagine a plain covered with grass. A series of lights turn on on it at the same time, and they all propagate in all directions at the same speed.

The Voronoi diagram, named after the 19th century Russian scientist Georgy Voronoi, describes both the place where the lights are installed and the borders with which the adjacent lights meet. In the Demane and Thachi algorithm, the borders of the Voronoi diagram determine the places where the paper is folded.

The work of scientists has received very favorable reviews from other experts in this field. Robert Lang, one of the pioneers of computational origami and a member of the American Mathematical Society, who in 2001 abandoned a successful career in optical technology to become a full-fledged origami, noted that this is very impressive material.

Lang believes that scientists have successfully completed a long journey towards creating a computational method for efficiently bending a sheet of paper of any given shape, which began 20 years ago. Along the way, some researchers were able to demonstrate several solutions to the problem that could not be called universal. Algorithms were developed for folding paper of any shape that were not very effective, as well as an algorithm for folding tree forms, but not surfaces. In his opinion, the algorithm of Demein and Tochi is rather complicated, but this is connected to a greater extent with the fact that it is also comprehensive.

doi:10.4230 / LIPIcs.SoCG.2017.34