Assigning mountain-valley fold lines of flat-foldable origami patterns based on graph theory and mixed-integer linear programming

摘要

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. (C) 2020 Elsevier Ltd. All rights reserved.