Origami, Linkages, & Polyhedra:: Folding Algorithms

Origami, Linkages,
& Polyhedra:
Folding with Algorithms
Erik Demaine, MIT
New Book
• www.gfalop.org
• Appearing
this month
• Cambridge
University
Press
• ~600 pages
Geometric Folding
Linkages Paper Polyhedra

(1D) (2D) (3D)
Folding is Everywhere:
Linkages
[CanadArm]
Mechanics Robotics
[Leclercq,
Akkouche,
Galin
2001] HIV protease
Graphics Biology
5m →
100m
Paper
[You &
[Hercules Beetle, opus 424, Robert Lang] Kuriba-
yashi
2003]
[Lang & LLNL

2002]
Origami Deployable structures
[BRL Inc]
Airbags
Polyhedra
[Daniela Rus et al.]

[Lundström Design]
Sheet-metal Reconfigurable robotics,

manufacturing self-assembly, nanomanufacturing
Geometric Folding

(1D) (2D) (3D)
Linkages
Watt 1764
Peaucellier 1864
Basic Questions about Linkages
Given a linkage…
• Rigidity:
▪ Does the linkage move at all?
• Universality:
▪ Into what configurations can it fold?
• Motion planning:
▪ How do we get there?
Rigidity
• What linkages can move at all?

• Rigid frameworks: buildings, bridges, etc.
[Chubynsky, Hespenheide, Jacobs, Kuhn, Lei,

[Big Dig in Boston] Menor, Rader, Thorpe, Whiteley, Zavodszky 2003]
Rigidity
• What linkages can move at all?

▪ Known: Characterization in 2D [Laman 1970]
▪ Unsolved: Most problems in 3D
Rigid Rigid
Rigid Flexible
Universality
• Can a linkage move universally between

any two configurations?
AIM Inc
Horn Machine Tools CanadArm
Hydraulic tube Robotic arm

Wire bending bending folding
Universality
• Can a chain linkage move universally

between any two configurations?
▪ Yes in 2D
[Connelly, Demaine, Rote — FOCS 2000]
▪ No in 3D
[Cantarella & Johnston 1998]
▪ Yes in 4D
[Cocan & O’Rourke 2002]
Universality: Unfolding 2D Chains
[Cantarella, Demaine, Iben, O’Brien — SoCG 2004]
spiral
spider
tentacle
Motion Planning
[Iben, O’Brien, Demaine — SIGGRAPH 2004, SoCG 2006]
• Find short motion from A to B (if possible)

• Universality results give new insight into
cases of interest, e.g., polygon morphing
→?→
→?→
Challenge in 3D
• 3D chains can be locked:

[Cantarella & Johnston 1998]
• Unsolved: Which 3D chains are locked?

• Known: Motion planning of 3D chains
is computationally intractable
[Alt, Knauer, Rote, Whitesides 2004]
Proteins
• DNA encodes
proteins in
genetic code
• Proteins are
“fundamental
building blocks
of life”
Protein
Folding
Importance of Protein Folding
• Geometry of a protein folding is an

important aspect of its behavior
• Prediction of protein folding, and
synthesis of proteins with desired
foldings, are central problems in
computational biology
▪ Drug design
▪ Preventing diseases (e.g., Alzheimer’s,
mad-cow disease, cystic fibrosis,
some forms of cancer)
Mechanics of Protein Folding
• Protein backbone is roughly a 3D chain

with fixed-angle constraints
… …
• Natural question:
▪ 3D chains are hard to fold
▪ How does nature fold
proteins so easily?
• Why do proteins fold easily?

• Possible answer:
▪ Ribosome constructs
proteins, enforcing
geometric constraints
[Nissen, Hansen,
Ban, Moore, Steitz
— Science 2000]
• Why do proteins fold easily?

• Possible answer: z
▪ Ribosome constructs α
proteins, enforcing
geometric constraints Cα
• Cone model: [Demaine, y
Langerman, O’Rourke 2006]

x
▪ All producible states Bα
can reach each other
▪ Flattenable q0
▪ Helical canonical state ribosome

Geometric Folding

(1D) (2D) (3D)
Origami
• Perhaps as old as paper itself (105 AD)

• Revolution in complex
origami design over
past ~25 years
Satoshi Kamiya Joel Cooper

Photos from
Origamido:
Mask by Eric Joisel Masterworks of
Paper Folding
Bat by
Michael LaFosse
Black
Forest
Cuckoo
Clock by
Robert Lang
Pangolin by Eric Joisel
Roosevelt Elk, Models & photos
opus 358 by Robert Lang
Mt Diablo Tarantula, opus 481
Dancers,
opp. 457 & 458 Hermit Crab
Tree Frog, opus 280 Koi, opus 425

2006 Design Challenge
Jason Ku
Photos by Brian Chan
Andrea Hawksley
Brian Chan
Giang Dinh Robert Lang

Origami Mathematics & Algorithms
• Explosion in technical origami thanks

in part to growing mathematical and
computational understanding of origami
Gargoyle
Jason Ku
• Theorem: Any 2D or 3D shape

can be folded from a square of paper
[Demaine, Demaine, Mitchell 1999]
• Algorithm to fold optimal origami “base”

with desired stick-figure projection
[Lang 1996–2006; Lang & Demaine 2006]
Folded States vs. Folding Motions
• Folded
Every folded
state state
= origami
can model
be made by a
• folding
Folding motion:
motion =No
how“locked origami”
you got there
[Demaine, Devadoss, Mitchell, O’Rourke 2004]
?
crease pattern folding motion folded state
Paper Thickness
[Galivan 2001]
• Analysis of paper “loss”

from repeatedly
folding in half
• ¾-mile long paper
folds in half 12 times!
Fold-and-Cut Problem
• Fold a sheet of paper flat

• Make one complete straight cut
• Unfold the pieces
• What shapes can result?
?
Fold-and-Cut Result
• Any collection of straight cuts can be
made by folding flat & one straight cut
[Demaine, Demaine, Lubiw 1998]
[Bern, Demaine, Eppstein, Hayes 1999]
5m →
100m
Deployable Structures
• Existing design ad hoc

• Unsolved: techniques &
algorithms to design
[Lang & LLNL

2002]
[You & Kuribayashi 2003]

Origami Flashers [Jeremy Shafer]
Origami Flashers [Jeremy Shafer]
Self-Folding Origami:
Pleated Hyperbolic Paraboloid
Circular Variation from Bauhaus
Circular Variations [Demaine & Demaine]
Simulating Paper Folding
[Demaine, Demaine, Fizel, Ochsendorf 2006]
• Particle-spring simulation of forces in paper:

elasticity and crease “failure”
Geometric Folding

(1D) (2D) (3D)
Unfolding Polyhedra
• Given 3D polyhedron
• Cut surface & unfold
• No overlap
• Goals:
▪ Minimum cutting
(⇒ minimum gluing)
▪ Efficient layout [Lundström Design]
Theory of
Unfolding Polyhedra
• Focus on one-piece unfoldings
• Convex polyhedra (no “dents”)
▪ Known: Always have a
one-piece unfolding
[Sharir & Schorr 1986;
Aronov & O’Rourke 1991]
▪ Unsolved: By cutting
only along edges?
[Dürer 1525]
Theory of
Unfolding Polyhedra
• Focus on one-piece unfoldings
• Nonconvex polyhedra
▪ Unsolved: Always have a
one-piece unfolding?
▪ Known: Not possible
just by edge cuts
[Bern, Demaine,
Eppstein, Kuo,
Mantler, Snoeyink 2003]
Folding Polygons into Polyhedra
• Given polygon of paper

• Fold arbitrarily
• Glue boundary together
• What convex polyhedra
can be made?
Folding Polygons into Polyhedra
• Efficient algorithms to find all

gluings into convex polyhedra
[Demaine, Demaine, Lubiw, O’Rourke 2002]
▪ Unsolved: Efficient algorithms
to find actual polyhedra formed
Reconfigurable Robotics
• Crux of many
reconfigurable
robots is the
attach/detach
[Daniela Rus et al.]
mechanism
• Hinged polyhedra
suggest that
components can
remain connected
[O’Rourke]
Self-Assembly &
Nanomanufacturing
• Millimeter-scale
“self-working” 2D
hinged polygons
[Mao, Thalladi, Wolfe,
Whitesides, Whitesides 2002]
Self-Assembly &
Nanomanufacturing
• Generalization to
arbitrary desired
3D shapes via
hinged polyhedra
(currently at macro level)
[Demaine, Griffith,
Jacobson 2007]
DNA Folding
• Synthetic DNA to
fold into desired
polygon [Rothemund
— Nature 2006]
~100nm

Origami, Linkages, & Polyhedra:: Folding Algorithms

Uploaded by

Copyright:

Available Formats

Origami, Linkages, & Polyhedra:: Folding Algorithms

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Origami, Linkages, & Polyhedra:: Folding Algorithms

Uploaded by

Copyright:

Available Formats

What are some applications of geometric folding?

What are some applications of geometric folding?

What are some open problems in rigidity of linkages?

What are some open problems in rigidity of linkages?

Origami, Linkages,

Linkages Paper Polyhedra

[Lang & LLNL

Origami Deployable structures

[Daniela Rus et al.]

Sheet-metal Reconfigurable robotics,

Linkages Paper Polyhedra

• What linkages can move at all?

[Chubynsky, Hespenheide, Jacobs, Kuhn, Lei,

• What linkages can move at all?

• Can a linkage move universally between

Horn Machine Tools CanadArm

Hydraulic tube Robotic arm

• Can a chain linkage move universally

• Find short motion from A to B (if possible)

• 3D chains can be locked:

• Unsolved: Which 3D chains are locked?

• Geometry of a protein folding is an

• Protein backbone is roughly a 3D chain

• Why do proteins fold easily?

• Why do proteins fold easily?

• Cone model: [Demaine, y

Langerman, O’Rourke 2006]

▪ Helical canonical state ribosome

Linkages Paper Polyhedra

• Perhaps as old as paper itself (105 AD)

Satoshi Kamiya Joel Cooper

Mt Diablo Tarantula, opus 481

Tree Frog, opus 280 Koi, opus 425

Giang Dinh Robert Lang

• Explosion in technical origami thanks

• Theorem: Any 2D or 3D shape

• Algorithm to fold optimal origami “base”

• Analysis of paper “loss”

• Fold a sheet of paper flat

• What shapes can result?

• Existing design ad hoc

[Lang & LLNL

[You & Kuribayashi 2003]

• Particle-spring simulation of forces in paper:

Linkages Paper Polyhedra

• Given polygon of paper

• Efficient algorithms to find all

You might also like