Computational Origami - Lecture Notes

Computational Origami Computational Origami is a rapidly growing area of computational geometry with many applications in computer science and engineering. One of the big open problems is to devise a computer program and to design a machine that could fold a sheet of material into any origami object. The computational complexity of such program is tremendous. But applications are equally tremendously important: airbag design, machine folding, protein folding, and a variety of others. In this activity we well examine some basic aspects of this problem and try to determine if a crease pattern drawn in a sheet of paper can be folded flat. Crease Patterns If we fold an origami figure, the creases along which folds have take place form a pattern of segments in the square sheet called the crease pattern of the figure. The crease pattern of an origami figure is like the blueprint of a house. However, it may be quite difficult to realize the origami figure from the crease pattern: the order in which the folds take place is important; often intermediate creases are formed which are not part of the crease pattern. A basic example that illustrates this is the pajarita, a traditional origami model from Spain. The diagram on the right is the crease pattern for the pajarita. You will notice that your paper has more creases than are drawn here. Those are the intermediate creases, used to construct landmarks for subsequent creases, but not part of the creases in the final model. Creases in the pattern come in two flavors: mountain creases (drawn as − · · · − · · · −) and valley creases (drawn as − − − − −−). For the purpose of this activity, we need not distinguish them. The pajarita is one example of a flat origami model or 2D origami model: it can be pressed flat between the pages of a book without crushing it (ignoring the thickness of the paper). Not all origami model are flat. For example, the body of your car is not a flat origami model; it can be pressed flat between two metal plates, as they do in scrap metal plant, but that alters considerably its appearance. 1 Another traditional model is the flapping bird shown below. Our first project today is to understand some basic facts about the computational geometry of origami. For example, you can draw a pattern of segments and ask the question: is this the crease pattern of a flat origami model? ¶ 1. • Draw the crease pattern for your flapping bird model. For that, carefully unfold your model and draw with a pen the creases that are actually part of the finished design, ignoring all other creases that played an intermediate role. • Then color the faces of your crease pattern with as few colors as possible in such a way that no two adjacent faces (that is, no two faces that share a whole edge) have the same color. What is the fewest number of colors that you can use? • What will the coloring look like when you refold your model? ¶ 2. The coloring activity should already give you a hint as to a necessary condition for a pattern to be the crease pattern of a flat origami model. State your conjecture. 2 Realizing crease patterns In this part of the activity we examine in more detail single vertex folds of flat models. Here we take into account whether the creases are mountains or valleys. The general problem is to determine which patterns are possible at a vertex of a flat model. Here is one example: Boat ¶ 3. Take a square piece of paper and make a single vertex crease pattern that folds flat. Place the vertex near the center of the square, draw some crease lines coming out of it, and then add more as needed to make the whole thing fold flat. The purpose of this problem is to formulate as many conjectures as you can about how such folds work. 3 Folding flat crease patterns The previous problem concerned what happen at a single vertex of a crease pattern. The crease pattern of a flat origami figure will have many vertices, and it is expected that there would be some interaction between them. Elvis’ Hairpiece (after Peter Budai) ¶ 4. Given a pattern on a square sheet of paper, we try to answer the question: is it possible to make a mountain-valley assignment to the segments so that the resulting pattern is in fact the crease pattern of a flat origami model? Here are two examples. Your task is to find out what they can fold into. You may not add more crease lines, but you have the choice of declaring which creases are valleys and which are mountains. Twist Pattern T. Hull Pattern Literature [1] Thomas Hull, Project Origami, A.K.Peters Ltd., 2006. [2] Erik Demaine and Joseph O’Rouke, Geometric Folding Algorithms, Cambridge University Press, 2007. 4