Assigning mountain-valley fold lines of flat-foldable origami patterns based on graph theory and mixed-integer linear programming. (15th October 2020) - Chen, Yao; Fan, Linzi; Bai, Yongtao; Feng, Jian; Sareh, Pooya
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.