# Message Boards

Answer
(Unmark)

GROUPS:

21

# [BOOK] An introduction to computational origami

Posted 1 year ago

An introduction to computational origami Tetsuo Ida (University of Tsukuba) with contribution of Hidekazu Takahashi (HIKONE HIGASHI High School) May 6, 2021
1 . AbstractThis post is on Monograph “An Introduction to Computational Origami,” Springer, September 2020. In the monograph, we discuss the basis of the computational origami from a symbolic and algebraic point of view. We use many origami illustrations to help the reader to appreciate the essence of this discipline. We design and produce those illustrations utilizing a software system called the E-origami system (abbreviated to Eos). We developed Eos as a tool to enjoy and understand computational origami. Thus, familiarizing ourselves with Eos is an excellent step to study this discipline deeply. Eos is written in Mathematica and is runnable where Mathematica runs. This post also serves as a guide to install and use Eos.
2 . Summary of the monograph The monograph is for students and researchers who love origami and are interested in the computational, geometric, and artistic aspects of origami. Computational origami is the field of study on origami with extensive use of mathematics and computer science. We treat origami as a subject of art, a science and technology of shapes. We developed a software system called Eos (E - origami system) to reason about origami computationally. Eos is written in Wolfram Language and is available as a package of Mathematica. In computational origami, we can apply computing power to enhance the speed and scale of the construction and verification and ensure rigor, abstraction, and generality, which are the claimedproperties of the main ingredients of the discipline of computational origami. We hope this monograph is used as a textbook in a course on special topics in applied computing for college students in computer science and applied mathematics or an interdisciplinary master course. We also hope that it is read as a research monograph by researchers interested in origami, geometry, and the applications of algebraic computation. As a monograph in the series of textbooks in symbolic computation, we proceed as follows . We collect some of our research results, glued together with the works of the pioneers in this field, and make the collection into a short coherent story of computational origami . We assume some maturity level of logic, algebraic, and symbolic manipulation. However, the examples are primarily from high school mathematics. We start with elementary geometry, whose power is equivalent to a two-dimensional Euclidean geometry with the tool of a straightedge and a compass, and then formalize a simple origami geometry. The origami geometry is equipped with seven rules of paper folding . Algebraic treatise of origami geometry realizes the precise construction of lines and points involved in paper folding. It further enables us to tackle the automated theorem proving in origami geometry. Finally, abstract origami allows us to formalize origami construction; and more sophisticated folds that the readers may find in origami recipe books.
2. Rules of the game Origami means “folding paper.” We find it more convenient to use the word “origami” to refer to a sheet of paper that we want to fold, an act of paper folding, and a sub-discipline of the science of shapes. Only in the first case, we treat the word as a countable noun. As Euclidean geometry employs a straightedge and a compass as a tool of construction of points and curves, origami uses a tool. However, the tool is not a concrete device like a compass; it is a set of rules of paper folding by hand. We define seven rules O1, O2, ..., O7. They are called Huzita-Justin rules. The rules are simple; to superpose (1) a point and a point, (2) point(s) and line(s), and (3) lines. The superposition entails a new line. We assume that we may mark the points of the intersection of the new fold-line and the existing lines. As case (2) allows us an infinite number of fold-lines, we need specific combinations of superpositions to make the finite (including 0) number of fold-lines. In other words, the rules make the operation possess the decidability property.
Example 1 - Angle trisection Without elaborating the above introduction further, we immediately jump to an example of construction using Eos. We describe the construction and verification of trisection of an arbitrary angle. The programming language in which we reason about origami on Eos is Orikoto. To execute the commands in Orikoto and construct an origami, we need to install Eos described in Section 5. But we hope that the following explanation alone is enjoyable without it. To invoke Eos, we load the Eos package as follows : (Please see section 5 “Installation of Eos” for instructions on how to download and install the package) <<"EosHeader.m" After loading the Eos package, we are in the context of Orikoto`. Orikoto is a small language whose syntax is the same as Wolfram Language. We can now use Orikoto commands. Usually, the first command that we enter is EosSession, which initializes Eos run-time environment. The argument of EosSession is a string that names the session we begin. This name will appear in the subsequent steps of the command executions.
Construction In[]:= EosSession["Angle trisector"]; We then create a new origami of 10 by 10 square. In[]:= NewOrigami[10] Angle trisector: Step 1 Out[]= We construct a new point E at an arbitrary position on the origami. For the construction, we have to give a concrete location, e.g., (7,10) in this example. Any point on the origami will do. In[]:= NewPoint["E"{7,10}] Angle trisector: Step 1 Out[]= The following command is one of the fold rules, O1. It asks Eos to fold the origami along the line that extends the segment AE. At the fundamental level of origami geometry, the fold line is determined uniquely by two superpositions, i.e., point A and point A, and point E and point E. However, we can forget about the logical meaning as long as we use Orikoto and think the fold in terms of manipulations of origami. The named parameter Handle is necessary in this case since we have to tell Eos the direction we want to fold, i.e., the righthand side of the directed segment (vector) AE or the lefthand. The default fold is so-called “valley fold.” We should note that the command line below terminates by an exclamation mark ‘!’. The exclamation mark is a postfix operator of Unfold. The following line consists of two commands of folding by rule O1 and unfolding the resulting origami to restore to the previous shape. The net effect is to obtain the crease EA. Eos shows the graphics image immediately below the command after executing it, together with the step number. In[]:= HO["AE",Handle"D"]! Angle trisector: Step 3 Out[]= We will trisect the angle ∠EAB. To do so, we need three lines AB, HI, and FG. The three lines are parallel, and Line HI is equidistant from AB and FG. Since we already have AB, we next construct line FG. We apply rule O2, i.e., to superpose two distinct lines. We do this with two points, A and D. We obtain line FG. Line FG is the perpendicular bisector of the segment AD. Note that in the command arguments we specify Mark-> {“AD”,”BC”}. This added parameter asks Eos to mark the intersections of the fold-line with segments AD and BC. The names of the intersections are not specified in the command. Hence, the system automatically assigns names F and G to the intersections with AD and BC. In[]:= HO["A","D",Mark{"AD","BC"}]! Angle trisector: Step 5 Out[]= Similarly, we obtain line HI . In[]:= HO["A","F",Mark{"AD","BC"}]! Angle trisector: Step 7 Out[]= The next step is the most important in the construction. In this step, we enter a command of rule O6 Namely; we fold the origami in such a way as to bring point F to line AE and point A to line HI. The command calls for two superpositions. We see that three fold-lines satisfy this requirement. Therefore, this command with four arguments cannot determine a requested folding. It only shows three possible cases. In[]:= HO["F","AE","A","HI"] Angle trisector: Step 7 Out[]= ,, We select the third one in the above cases and obtain the origami shown below. In[]:= HO["F","AE","A","HI",FoldLine3] Angle trisector: Step 8 Out[]= We almost finish the construction of the two trisectors. The line that passes through the left-bottom corner of the original origami and point A is one trisector, and the other is the line that passes through the left-bottom corner and point H. The rest of the commands help us to view the obtained trisectors. The meaning of the commands is self-explanatory. In[]:= ProjectPoint[{"A","H"}]! Angle trisector: Step 9 Out[]= In[]:= HO["AJ",Handle"B"]! Angle trisector: Step 11 Out[]= In[]:= HO["AK",Handle"B"]! Angle trisector: Step 13 Out[]= The graphics output below more clearly shows the trisectors. They are the lines that extend the segments AK and AJ. In[]:= GraphicsOrigami[More{Thick,Red,GraphicsLine[{"A","K","A","J"}]}] Angle trisector: Step 13 At this point, we apply synthetic reasoning of geometry and prove the correctness of the construction. We can perform the algebraic theorem proving using Groebner basis computation. Only the following is required to verify the correctness of the construction program for any point E. For the proof, we use GroebnerBasis function built into Mathematica. Orikoto incorporates WildBerger’s rational trigonometry (Divine Proportions: Rational trigonometry to universal geometry, 2005). Function Spread[X,Y, Z] in the Goal function below represents 2 Sin
Proof In[]:= Goal[Spread["E","A","K"]==Spread["K","A","J"]∧Spread["K","A","J"]==Spread["J","A","B"]]; In[]:= map={"A"{0,0},"B"{1,0},"C"{1,1},"D"{0,1},"E"{u1,u2}}; In[]:= Prove["Angle trisection by Abe's method: case 1 ",Mapping{"A"{0,0},"B"{1,0},"C"{1,1},"D"{0,1},"E"{u1,u2}},GroebnerBasis{MonomialOrderDegreeReverseLexicographic,CoefficientDomainRationalFunctions},TacticsSplit] ::gbstart ::gbsuccess ::gbstart ::gbsuccess Proof is successful. Angle trisector: Step 13 Out[]= {Success,2.01206`, Angle trisection by Abe's method: case 1 .nb We end the current session by EndSession[]; In[]:= EndSession[]; It is impossible to construct a trisector of an arbitrarily given angle with a straightedge and compass. It had been a long-standing problem to construct one.
3. Examples viewed by Manipulate function
Regular heptagon This example is an origami construction of a regular heptagon. We know that only with a straightedge and compass can we not construct a regular heptagon. You will notice that we use fold rule O6 at Steps 7 and 8. The polygon connecting points G, N, P, Q, T, S, R, and G by the straight lines is a desired heptagon. We do not show the verification of the construction below. A straightforward method is to prove that the seven inner triangles sharing center O are congruent each ether. We can prove it as in the angle trisection. In the manipulator output below, increment the range counter one-by-one manually. We only show the steps from Step 1: NewOrigami[] to Step 21, where we can see the seven constructed points. At Step 1, we only see NewOrigami[ ] since we are about to construct a new origami. At Step 2, we see the initial sheet of origami. Looking at this image, we reason what to perform on it. In this example, we bring point A to D. This is an operation of rule O2. The fold-line realized by rule O2 is the perpendicular-bisector of segment AD. It intersects with other existing segments (including the sides). Let E be the intersection with side AD and F be the intersection with BC. We type the command HO[ .....]! as shown on the right side of the manipulation panel. We can follow the subsequent steps as we click the icon “+“ until Step 21. On the panel of Step 21, two differently colored curves; red polygon and green circle. We draw them directly by the use of Mathematica graphics functions. In Orikoto, we provide a few commands that interface with the Mathematica graphics functions. We could have drawn the former curves by repeated applications of rule O1 and the unfold operations. As far as our geometric reasoning is concerned, these are extra steps, and we omitted them. We obtained seven vertices G, R, S, T, Q, P, and N of the heptagon. The circle is the circumscribed circle of the regular heptagon. We note that a regular polygon has a circumscribed circle. The center of the circle is the center of the regular polygon as well. This manipulator output shows the transformation of the origami and tells us precisely a recipe for making a regular heptagon without using a natural language. To understand fully the recipe of the regular heptagon, press the stop button and increment the step-counter one by one. In the panel, we look at the origami on the left and define and execute the command based on the named points that you see to the left. Then in the next panel, we will view the origami, to which we apply a new command or a function of Wolfram Language, and so on. In[]:= cmd=TraditionalForm/@HO"A","D",Mark
In[]:= orig=,,,,,,,,,,,,,,,,,,,,,,; In[]:= Manipulate[Row[{orig〚i〛,cmd〚i〛}],{i,1,20,1},SaveDefinitionsTrue] Out[]=
Petals of sakura This example shows that from Eos, we can access the full functionality of Mathematica. We use Spline functions to draw a curve on the origami and cut the origami along the curve. When you unfold the remaining origami, you may find an expectedly beautiful shape of origami. In the following case, we make petals of sakura (cherry). In[]:= CmdList=TraditionalForm/@NewPoint"O"{5,5},"E"10,5+5Tan 3π 20 3π 20 In[]:= image=,,,,,,,,,,,,,; In[]:= Manipulate[Row[{image〚i〛,TraditionalForm[CmdList〚i〛]}],{i,1,14,1},SaveDefinitionsTrue] Out[]=
4. Towards 3D origami and variations
Origami piano The following example illustrates the semi-3D origami with texture mapping. Nowadays, we can buy at shops of stationery goods a set of origami sheets with beautiful patterns such as shown below. The purpose of this example is to show that Eos incorporates the capability of using this kind of pattern on the surface of the face of an origami. A 2D origami would not be rendered an exciting illustration with a textured sheet of origami. We use semi-3D modeling of origami here. We perform twice “squash fold” as well. Therefore, this origami construction is beyond Huzita-Justin’s. Since we focus on the two features of the construction of this example, we assume that we have the necessary points already generated. Our assumption is satisfied by the command NewPoin[...] in the Orikoto program.
Preparation In[]:= Get["EosHeader.m"] Eos3.34 (May 2,2021) running under Mathematica 12.2.0 for Mac OS X x86 (64-bit) (February 2, 2021) In[]:= OT= , , , , , , , , , , , ; In[]:= textureY=Graphics[{Yellow,Rectangle[{0,0},{4,4}]}]; In[]:= SetView["3D"]; SetOptions[ShowOrigami,Lighting"Neutral",FrameFalse,Texture{textureY,OT〚9〛}];
Construction In[]:= Off[TsubushiOri::separate]; In[]:= MarkOn[]; In[]:= EosSession["Piano"]; In[]:= NewOrigami[4] Piano: Step 1 Out[]= We create the necessary points at specific positions on the origami. In[]:= NewPoints[{"G"{3,2},"H"{4,1},"I"{3,0},"J"{1,2},"K"{0,1},"L"{1,0},"M"{1,1},"N"{3,1},"N2"{3,1.5},"M2"{1,1.5}}] Piano: Step 1 Out[]= We perform a valley fold along line EF by angle π. To this effect, we use HO to bring D onto A. The markpoints E and F are created automatically. In[]:= HO["D","A"] Piano: Step 2 Out[]= Now we perform the squash folds on the right and left sides of the origami. The parameter {2,3} is a pair of face Ids (that we can find by adding an optional named parameter). In[]:= SquashFold[{2,3},{"GH","GI"},π] Piano: Step 3 Out[]= We perform the second squash fold on the left side. In[]:= SquashFold[{4,12},{"JK","JL"},π] Piano: Step 4 Out[]= In[]:= ValleyFold["MN",π] Piano: Step 5 Out[]= The following valley fold makes a half-plane perpendicular to the base pane z=0. So at this point, we depart from the traditional 2D geometry. In[]:= ValleyFold["N2M2",π/2] Piano: Step 6 Out[]= In[]:= ValleyFold["NM",π/2] Piano: Step 7 Out[]= In[]:= ValleyFold["N2G",π/2] Piano: Step 8 Out[]= The construction completes with the execution of the next valley fold. However, we will refine the final “product” by adding more attributes by the command GraphicsOrigami[]. In[]:= ValleyFold["M2J",π/2] Piano: Step 9 Out[]= We remove the marked points and change the viewpoint by manipulating the graphics output by hand. And we make the size of the image larger. In[]:= GraphicsOrigami[MarkPoints{},ImageSize250] Piano: Step 9 Out[]=
Jumping Frog In this sub-section, we show the origami of a jumping frog. The frog consists of a stack of layers of faces. These layers act as a kind of a spring. The frog will jump forward if we press the lower bottom side (if we made it out of an actual sheet of paper). We find it easier to specify the required fold-lines in a logical formula to make this shape precisely. Furthermore, we use one of the classical folds, “InsideReverse fold,” to make layers of faces. The left image below is the top-view (slightly tilted), and the right one is the 3D view with graphics visualization of connected faces by a hinge-like surface. You may change the viewpoint of the figure below, as they are the outputs of the Mathematica Graphics3D function. Thus, you can analyze the inner structure of the origami artworks manually.
5. Installation of Eos
System requirements Eos consists of Mathematica packages. The current version of Eos is 3.4 (experimental). The version of Mathematica we are using now is 12.2.0. The version Eos 3.3.2 that is uploaded to the Eos project homepage was tested by Mathematica 12.1. We are testing Eos3.4 and the experimental version will be uploaded in the Eos project homepage to coincide the upload of this post. Eos runs under the operating systems(Windows10, macOS, and Unix, where Mathematica 12.2.0 is installed. We do not guarantee that Eos works correctly for versions earlier than Mathematica 11, although most of Eos’ functionality remains valid on Mathematica 11. We recommend a computer equipped with at least 4 MB main memory for a reasonably speedy interaction with Eos.
Installation Steps The installation of Eos requires no special knowledge about Eos and Mathematica, but only general knowledge about the structure of the Mathematica system and its applications. You need to know where your “init.m” file should be placed and set up “$Path” through which Eos accesses its internal data structures. The installation is semi-automated. It consists of the following two steps.
Download You have to download the Eos package. The newest one is Eos 3.4 (experimental), which runs on Mathematica 12.2.0. We will explain the installation of Eos3.4, but the procedure is the same as the one for earlier ones. To download Eos 3.4, you have to be an Eos website blog member. To become a member, visit the Eos Project website: Eos Project website: Eos Project website First, register yourself. The website is realized by WordPress 5.7.1 (free, open-source software distributed under license GPLv2). You need to provide your account name and your email address. The account name is typically your name (space in the middle is allowed) or a nickname. If the same name has been taken already, you have to create a unique new name. When the registration is successful, you will receive an Eos Project email telling you how to retrieve your password. The password is strictly yours, and there is no way that anyone including the site managers read or recover it. However, we recommend that you change the initial password. To change the password, please refer to the WordPress documents. Using the password, try to log in to the Eos Project website. Successful login implies that you become a member whose status is a "mono-reader. " We use your account name and email address only for the communication between you and Eos website. Once you have logged in to the Eos Project website, you will see the website’s front page in more detail. There, you can find the main menu bar. You reach the supplement page by clicking the menu tab “Supplement.” Under the supplement tab, you see two articles: one for Mathematica 12.1 or earlier and the other for Mathematica 12.2. This section of the post comes from the supplementary article for Mathematica 12.2. You will find Eos 3.4 by the menu tab "Eos software." Open Eos3.4 page.
Directory structure Download the zipped archive of Eos3.4. The zipped file name of the latest version is Eos-3-4.zip. Unzip the file to your desired folder. In the archive, we use the folder whose path is ~/Dropbox. This path marks the root directory of the Eos system. In macOS, for example, it is /Users/xxx/Dropbox/, if your user name is xxx. Note that the user name xxx is your macOS user name and has nothing to do with the name of your account of Eos website membership. Folder Eosvnum is created in the Dropbox folder, where “vnum” in Eosvnum is a version number of form “3.3” , “3-3-2”, “3-4” etc., depending on the zipped file you downloaded. If your folder is Eos3-4, rename it to Eos3.4. In the Eos3.4 folder, you will find files Installer.nb and init.m. Open init.m by Mathematica or by a text editor, and rewrite the path according to your directory structure. Namely, if you prefer a different root folder, e.g. EosSystem, to Dropbox, rewrite the line FileNameJoin[{$HomeDirectory,"Dropbox","Eos3.4"}] to FileNameJoin[{$HomeDirectory,"EosSystem","Eos3.4"}] and save init.m. Then, open, by Mathematica, Installer.nb, and rewrite Dropbox to EosSystem, likewise. {$HomeDirectory,"Dropbox","Eos3.4","init.m"}]; to {$HomeDirectory,"EosSystem","Eos3.4","init.m"}]; Execute Installer.nb (Cmd-a + shift enter). Click Yes when you are asked whether you allow the installer to proceed. The installer will put the init.m in user’s Mathematica/Kernel, replacing the existing init.m if it exists. If the existing init.m is important for your other applications, save it elsewhere before you evaluate Installer.nb. In the case of macOS, the installer prints, Succesfullyinstalled /Users/xxx/Library/Mathematica/Kernel/init.m where xxx is the user name. Exit the Mathematica. You can evaluate the Installer.nb, whenever you changed the init.m. In other words, you can modify init.m to allow your other applications to work together with Eos, you should edit the init.m and install it again by the installer.
Testing In the webpage following the menu tabs Origami Works -> Test Examples, you will find test examples. Download the files. Open and evaluate each file. Except for yacht.nb, each file has more than one section; Header, Construction, and Verification. The header section contains initialization cells that automatically load the Eos system when you execute the first command in Construction. Therefore, you may start from Section Construction.
6. More about Eos Environment
Computing mode
Exact vs. Inexact. We distinguish two modes of computation on numbers in the sense of Mathematica. This distinction amounts to say that we use NSolve when the computation mode is inexact and Solve when the computation is exact. For the proof, we use the exact computation. Exact[ ] sets the computation to be exact. Inexact[] switches the computation to be inexact.
Interactive vs. non-interactive Command InteractiveFold[True] sets Eos in the interactive mode. Sometimes Eos needs more input from the origamist (user) to proceed. Then Eos displays an input-prompt box to receive the origamist’s choice or instruction. Command InteractiveFold[False] sets Eos in the non-interactive mode. In this mode, the origamist provides data as the argument of the requesting command.
On interactive construction We write an Orikoto program interactively with a computer. This process is comparable to human origamists making it with a sheet of paper. Starting from an initial origami, we design a shape of the origami and fold the origami step by step. We have a few options in each step: method of folding, unfolding, and other manipulations of the origami, such as handling the geometric objects on the origami (e.g., marking points). Any slight change at some step may induce a situation that we restart the construction from the beginning. The mode of computation using a Notebook is particularly suited to the origami construction since restarting from the start or at some step will not pose a problem during the origami construction if you group the input cells properly. Furthermore, for each execution of a command, you can see the origami shape so that you ensure your interactive construction process and leave the record of construction as an Orikoto program. The Orikoto program is the origami recipe.
Graphics layer For visualization of origami by Mathematica, Eos employs a data structure for origami suited not only for symbolic and algebraic computing but for the graphics processing by Mathematica. Roughly speaking, the data structure of origami has layers of faces. A small adjustable gap separates each layer. Command GraphicsOrigami has the functionality to make the visualized origami more refined. For example, we can specify the gap by the use of the named parameter Gap -> desired-value. For details, read Chapter 7 of the monograph.
Initial origami By default, the initial origami is a square of one, and the left bottom vertex is point A(0, 0). We may change the size of the origami by supplying the value of the size as the argument of NewOrigami[ ]. In[]:= NewOrigami[5/2] new session: Step 1 Out[]= We created an initial origami by a square of size 5/2 by 5/2. Note that the size of the graphics output does not change on your computer screen, but the locations of each point are certainly varied. See the result of the following command execution. In[]:= {ToPointValue["C"],ToPointValue["A"]} new session: Step 1 Out[]= {Point[2.5,2.5,0.,C],Point[0.,0.,0.,A]} You may define the shape of the initial origami to be rectangular. |