Assigning mountain-valley fold lines of flat-foldable origami patterns based on graph theory and mixed-integer linear programming. (15th October 2020)

• Record Type: Journal Article
• Authors: Chen, Yao; Fan, Linzi; Bai, Yongtao; Feng, Jian; Sareh, Pooya
• Is Part Of: Computers & structures. Volume 239(2020)
• Publication Date: 2020-10-15
• Subjects: Origami -- Crease pattern -- Particle swarm optimization -- Graph theory -- Folding; Structural engineering -- Data processing -- Periodicals; Electronic data processing -- Structures, Theory of -- Periodicals; 624.171
• DOI: 10.1016/j.compstruc.2020.106328
• Languages: English
• ISSNs: 0045-7949

Abstract

Highlights: Automated mountain-valley assignment of origami fold patterns is established. Graph-theoretic representation of subgraphs is combined with a cycle detection algorithm. Origami design is converted to a mixed-integer linear programming problem. The proposed approach is robust for origami patterns with degree-4 or degree-6 vertices. Various origami patterns can be obtained from independent subgraphs of given configuration. Abstract: Traditional origami design is generally based on designers' artistic intuition and skills, mathematical calculations, and experimentations, which can involve challenges for crease patterns with a large number of vertices. To develop novel origami structures for engineering applications, systematic and easy-to-implement approaches capable of generating diverse origami patterns are desired, without requiring extensive artistic skills and experience in origami mathematics. Here, we present a computational method for automatically assigning mountain-valley fold lines to given geometric configurations of origami structures. This method is based upon a geometric-graph-theoretic representation approach combined with a graph-theoretic cycle detection algorithm, taking the subgraphs of a given structure as inputs. Then, a mixed-integer linear programming (MILP) model is established to find flat-foldable origami patterns under given constraints on the local flat-foldability and degree of vertices, leading to the identification of crease lines associated with local minimum angles. Numerical examples are presented to demonstrate the performance of the proposed approach for a range of origami structures with degree-4 or -6 vertices represented by their corresponding subgraphs.