We highlight two key such results, from SoCG'96 and SoCG'99 respectively. Several results tackle this problem for various notions of " best " and " anything ". 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems 1 Introduction The ultimate challenge in computational origami design is to devise an algorithm that tells you the best way to fold anything you want.
#Universal windows grid patterns software
This work provides the theoretical underpinnings for Origamizer, freely available software written by the second author, which has enabled practical folding of many complex polyhedral models such as the Stanford bunny. Our foldings also have the geometric feature that every convex face is folded seamlessly, i.e., as one unfolded convex polygon of the piece of paper. This algorithm is the first to attain the watertight property: for a specified cutting of the manifold into a topological disk with boundary, the folding maps the boundary of the paper to within ε of the specified boundary of the surface (in Fréchet distance).
#Universal windows grid patterns plus
We prove that the algorithm correctly folds any oriented polyhedral manifold, plus an arbitrarily small amount of additional structure on one side of the surface (so for closed manifolds, inside the model). We develop a new algorithm designed specifically for the practical folding of real paper into complicated polyhedral models. At a deeper level, these foldings get the topology wrong, introducing many gaps (boundaries) in the surface, which results in flimsy foldings in practice. It was established at SoCG'99 that every polyhedral complex can be folded from a sufficiently large square of paper, but the known algorithms are extremely impractical, wasting most of the material and making folds through many layers of paper. Both length and turns consume area when folding a strip, so we build on past approximation algorithms for these two objectives from 2D milling. To achieve these results, we develop new approximation algorithms for milling the surface of a grid polyhedron, which simultaneously give a 2-approximation in tour length and an 8/3-approximation in the number of turns. We also show how our strip foldings can be executed by a rigid motion without collisions (albeit assuming zero thickness), which is not possible in general with 2D sheet folding. These geometric results offer a new way to build programmable matter that is substantially more efficient than what is possible with a square N×N sheet of material, which can fold into all polycubes only of surface area O(N) and may stack Θ(N2) layers at one point.
The folding is efficient: for target surfaces topologically equivalent to a sphere, the strip needs to have only twice the target surface area, and the folding stacks at most two layers of material anywhere. We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid-for example, the surface of any polycube.
0 kommentar(er)
