Designing and Fabricating Mechanical Automata from Mocap Sequences1

Duygu Ceylan1
Wilmot Li2
Niloy J. Mitra3
Maneesh Agrawala4
Mark Pauly1
2
3
4
EPFL
Adobe Research
University College London
University of California Berkeley

Figure 1: We present a method for generating the design of a mechanical automaton (bottom row) that approximates an input motion
sequence (top row). Our algorithm automatically determines the configuration, dimensions, and layout of all mechanical components.

Abstract

1

Introduction

Mechanical figures that mimic human motions continue to entertain us and capture our imagination. Creating such automata requires expertise in motion planning, knowledge of mechanism design, and familiarity with fabrication constraints. Thus, automaton
design remains restricted to only a handful of experts. We propose an automatic algorithm that takes a motion sequence of a humanoid character and generates the design for a mechanical figurethat approximates the input motion when driven with a single input
crank. Our approach has two stages. The motion approximation
stage computes a motion that approximates the input sequence as
closely as possible while remaining compatible with the geometricand motion constraints of the mechanical parts in our design. Then,in the layout stage, we solve for the sizing parameters and spatiallayout of all the elements, while respecting all fabrication and assembly constraints. We apply our algorithm on a range of input
motions taken from motion capture databases. We also fabricate
two of our designs to demonstrate the viability of our approach.

Mechanical automata are machines that use a combination of interconnected mechanical parts such as cranks, gears, and pulleys toconvert a driving force into a specific target motion. Since antiquity, mechanists have created a wide variety of such machines formany different purposes (e.g., clocks, music boxes, fountains). Automata designed to look like human figures performing every-day
actions like walking, waving, etc. are especially popular. Famous
historical examples include Leonardo Da Vinci’s life-sized armorclad “robot” from 1495 that could sit, stand and move its arms, aswell as the“Draughstman-Writer” of Henri Maillardet from the late
18th century, which was the primary inspiration for the automaton in Brian Selznick’s book, The Invention of Hugo Cabret. Today, wind-up toys in the form of characters are the most common
types of mechanical figures. Our longstanding fascination with humanoid automata likely stems from their ability to produce surprisingly complex, lifelike motions from simple input forces throughpurely mechanical means (see Figure 2).

CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Physically based modeling I.3.7[Computer Graphics]: Three-Dimensional Graphics and Realism—
Animation

Despite their widespread appeal, the design of automata is currently
restricted to a very small group of experts. Consider the challenges
involved in creating a mechanical figure that performs a specific target motion. First, a designer must choose a set of mechanical partsand decide how to connect the parts together to approximate the

Keywords: mechanical assembly, humanoid motion, computational design, fabrication constraints, automaton
Links:

DL

PDF

W EB

V IDEO

DATA

C ODE

Figure 2: Examples of mechanical automata: Da Vinci’s mechanical knight; Maillardet’s writer; an aviation chronograph.

prescribed motion. Creating this initial design typically requires
extensive knowledge of different part types and how part interactions transfer movement through the assembly. Next, the designermust determine the appropriate part parameters (e.g., gear radius,
crank length) to best match the target motion. This step may require simplifying the target motion so that it falls within the rangeof achievable motions for the set of parts. The final step is to arrange the parts spatially to create a valid physical realization of theautomaton. Few people have the necessary skills and expertise toperform all of these design tasks.
In this work, we present an automated approach for generating mechanical figures that approximate a given target motion. The input is an animation sequence for an articulated 3D humanoid figure (e.g., from a motion-capture database) that specifies the target
motion. Since automata typically perform repetitive actions, we assume that the input motions are roughly periodic (e.g., a walk cycle,
an arm waving back and forth). We also assume that the motion ofindividual limbs are nearly planar. While these restrictions limit the
space of motions that our approach can handle, we show that there
are many human movements that meet these assumptions. For example, in most walking motions, the arms and legs move primarily
in planes that are parallel to the saggital plane of the body. Givensuch a target motion, our system designs a mechanical automaton
in which the moving limbs are treated as a set of rigid links connected by revolute joints and driven by gears, pulleys, and four-bar
linkages (see Figures 1 and 6).
Our method has two main stages. First, in the motion approximation stage, we convert the input sequence into a mechanically realizable motion based on the constraints imposed by the types ofjoints (revolute) and parts (gears, pulleys and four-bar linkages) in
our designs. More specifically, we convert the motion of each limb
in the input figure to a set of oscillating bone rotations that canbe reproduced by a kinematic chain of rigid links in our automaton design. Then, in the layout stage, we solve for the parameters(e.g., tooth counts, link lengths) and spatial layout of the mechanical parts to produce the desired motion of each link. We formulate
a constrained optimization that tries to match both the target motion and the bone proportions of the input figure, while satisfying
various physical and fabrication constraints.
Our system generates designs with the following characteristics:
Simple components. Our designs use only a few different types ofcomponents (rigid links, spur gears, bevel gears, pulleys, and fourbar linkages, see Figure 6) that are easy to fabricate or obtain. The
use of four-bar linkages allows us to generate oscillating motions
with continuous acceleration rather than abrupt changes in direction, which can put significant stress on the components. In ourphysical examples, we fabricate the links, spur gears and four-bar
linkages with a laser cutter and obtain pre-made bevel gears andpulley components from a craft store.
Single input crank. Our mechanical figures are designed to be
driven with a single input crank that rotates at a constant angularspeed. The automaton converts the crank rotation to oscillatory
movements that are propagated to the appropriate links in the figure.
This propagation can generate oscillations with different phases andfrequencies for different body parts, which greatly expands the expressive range of our designs. For example, in running motions, theoscillations of the upper and lower arms are typically out-of-phase.
Freestanding. Our system generates freestanding automata where
the mechanisms that produce motion are attached directly to thelinks of the figure. In contrast, tethered automata often place mechanisms in a box below the figure and create motion by physicallyconnecting moving parts in the box to the limbs above (e.g., [Zhuet al. 2012]). Freestanding designs enable a wider range of mo-tion because limbs are not connected to an external structure (e.g.,arms tethered from below cannot cross each other in arbitrary ways
because their connectors may collide).
We have evaluated our framework using a variety of motion capture
sequences from the CMU motion database [Carnegie Mellon University 2003]. We generated physically-realizable mechanical designs for several different motions and validated each of them in a
kinematic simulator. In addition, we physically manufactured, assembled, and tested two of our designs (see Figure 1 and 7 and the
supplementary video).

2

Related Work

Mechanism design. Mechanism design is traditionally divided into
two phases. Creating a conceptual design involves identifying thetypes of mechanical parts that are capable of realizing desired motions. Previous work attempts to automate this task by decomposing
specific functional goals into smaller subgoals and matching them
to a database of common building block mechanisms ([Chiou andSridhar 1999; Roy et al. 2001; Han and Lee 2006] and references
therein). Since our work focuses on one specific type of motion
conversion (i.e., converting the rotation from an input crank to rotations of bones), we do not require an explicit conceptual designphase. As mentioned earlier, our designs use a small set of predefined parts, which simplifies the fabrication process.
The second phase of mechanism design is dimensional synthesis,
which determines the configuration parameters and spatial layoutof the identified parts. A common approach is to identify the relevant spatial constraints between parts and then satisfy these constraints to compute part positions and orientations [Anantha et al.
1996; Kim et al. 2000]. Recent methods encode the mating andalignment relations between different parts of an assembly usinga graph of geometric constraints [Peng et al. 2006; Haller et al.
2009]. We adopt a similar constraint-based approach to synthesize
our mechanical designs. However, the complex, articulated humanmotions that we aim to reproduce impose a unique set of constraints
on both the configuration parameters and spatial layout of our gears.
In particular, our dimensional synthesis algorithm must generate asystem of gears, pulleys and four-bar linkages that produce hierarchical bone rotations that match a given target motion.
In recent work, Zhu et al. [2012] present a system for producing mechanical assemblies that approximate user-specified input motions.
Two key differences distinguish their problem setting from ours.
First, they produce tethered assemblies where characters or objects(represented as rigid feature components) are driven from below
by mechanisms hidden inside a box. We generate freestanding articulated automata, which imposes very different requirements on
our dimensional synthesis algorithm. Furthermore, Zhu et al. focus
on target motions that are different from ours. Their tethered designs drive each rigid feature component with one or two mechanical parts, which allows the component to perform a simple rotation,translation or certain combinations of two rotations/translations
along orthogonal planes or axes. In contrast, our mechanisms reproduce articulated human motions with moving kinematic chainsof rigid links, each of which can undergo complex motions basedon the combined motions of its ancestor links in the skeleton.
In concurrent work, Coros et al. [2013] present an interactive system for designing animated mechanical characters. Their method
supports complex target motions that are specified by sketching planar motion curves. For each kinematic chain of the given articulatedcharacter, a single actuation point is selected, and the motion is
propagated to the rest of the chain by rigid connections provided aspart of the input. In contrast, we present a method to realize the motion of each bone in a kinematic chain as oscillations with possibly

Layer 1:

li-1

li-1

Ri-1

moving pivots

Layer 2:

Di

Ai

Bi

Layer 3:Ri-1

Ci
fixed pivots

connectorDi

moving pivots

Di

Ai

Bi

li

revolute joint

Ri-1

axles

Layer 5:

Pi

Qi

Ri

li

(c) Driving li

fixed pivots

Qi

Pi

li

Ri-1

Ri
Pi

Di+1

(a) Oscillation module: stacking orderCiconnectorCirevolute joint
Layer 4:

Bi
Ai

Qi

Di+1
(b) Oscillation module: exploded view(d) Driving Di+1

Ri
Di+1

Figure 3: Oscillation module. In our design, we drive the rigid links of the automaton with oscillation modules that consist of gears, pulleys,
and four-bar linkages (a–b). These components are stacked onto axles that are connected to each link. We show the stacking order of theparts (a) starting from the bottom layer (Layer 1), as well as an exploded view (b) of the module that shows the axles and rigid connectors.
The module converts an input rotation to an oscillating motion (b) and also propagates a uni-directional rotation to the next module (c).
different phases and frequencies. Our approach is fully automaticconsisting of a motion approximation stage to convert the input sequence into a mechanically realizable motion and a layout stage tooptimize for the placement and parameters of the elements of thedesigned automaton.
Shape analysis. Researchers have investigated how to retarget input poses/motions using articulated motions by determining joint
locations and types. For example, Xu et al. [2009] analyze input
models based on local slippage analysis to assign appropriate joint
types and support joint aware deformations. In the context of mapping human motion to humanoid robots, Pollard et al. [2002; 2003]
impose joint angle and velocity limits to a captured human motion
to match the less flexible skeleton of a robot. Mitra et al. [2010]
analyze static 3D meshes of mechanical assemblies to understandtheir part interactions and resulting inter-part motion possibilities.
Recently, Bacher et al. [2012] augment skinned meshes with 3D
printable joints that do not require any assembly. Users can thenpose these models into different configurations. In contrast, we startfrom an articulated 3D figure and focus on automatically generating a mechanical automaton that recreates an input motion sequencewhen driven by a single input crank.
Fabricatable models. The advent of accessible 3D fabrication
techniques has led to recent work on various fabrication-awaremodeling techniques, including optimizing geometry towards creating functionally valid furniture [Umetani et al. 2012]; improving stability and robustness of printed models with thin structures [Stava et al. 2012]; creating complex assemblies of planar intersecting pieces [Schwartzburg and Pauly 2013]; creatingassembly-free printable articulated models [Calı̀ et al. 2012]; anddecomposing large models into smaller parts that can be printed
and assembled [Luo et al. 2012]. These methods generate static
models, while our goal is to create moving mechanical figures thatrecreate a target motion.

3

Generating mechanical designs

The input to our system is an animation sequence of an articulated
3D human figure. Since automata typically perform repetitive actions, we assume the input is a periodic motion where parts of the
figure oscillate. From this animation, our system automatically produces a humanoid automaton design that uses a combination of

rigid links, pulleys, gears and four-bar linkages to approximate theinput motion. The first stage in our method is motion approximation, where we convert the input animation to a simpler motion thatcan be realized mechanically. In particular, we decompose the motion of the entire figure into the motions of kinematic chains (armsand legs) that can be approximated by planar oscillations of individual bones (see Section 3.2). Then, in the layout stage, we generate
a physically valid layout of the mechanical components that realizes the simplified target motion and respects the proportions of thebones in the input figure. We first solve for the layout of each individual kinematic chain (Section 3.3). Then we generate additional
gears and support structures to compose all the chains into a unified
design that is driven by a single input motor (Section 3.4).

3.1

Mechanical automaton design

Before describing the details of our motion approximation and layout optimization, we first introduce the basic mechanical design that
we use to generate a moving automaton.
Our design represents the bones of the
input figure with rigid links. Sincemany human motions are characterized primarily by the movement of
the limbs, we connect the arm andleg links with revolute joints to create points of articulation at the shoulders, elbows, hips and knees of the automaton. We orient these joints suchthat the motion of all the links within
a limb lies in a single plane that is parallel to the saggital, coronal or transverse plane of the figure (see the inset
figure).

saggitalcoronaltransverse

revolute joint
head-shoulderstorso-hipsleft armright arm
left legright leg

While constraining limb motions to these orthogonal planes limits the range of movements that our mechanisms can achieve, thisdesign makes it possible to transfer the rotation of a single input
motor to the motion plane of each limb using standard bevel gears,
which convert rotation across orthogonal planes. Furthermore, as
our results show, there are many human movements in which the
motion of the limbs is mostly parallel to one of these planes (e.g.,

hi
bi

αi

Di

Ai

of the output crank Ci at time t as:

ci

θi(0)


φi (t) = arctan

φi(0)

gi

Si (t)Ti (t)

+ arccos

Ui (t) − Vi (t)Wi (t)

(1)

Si (t) = 2bi ci cos(θi (t)) − 2gi ci
Ti (t) = 2bi ci sin(θi (t))
Ui (t) = 2bi gi (cos(θi (0))−cos (θi (t)))(a) Motion parametersli-1

φi-1(t) - φi-1(0)

tαi

Di

Ai

-tαi + (φi-1(t) - φi-1(0))(b) Dependency on parent link

Figure 4: Motion parameters. The output oscillation of a module
is defined by a set of motion parameters (a). When we connect
modules into a chain, the motion of one module depends on the
motion of its parent link (b).

Vi (t) = 2ci (gi cos(φi (0))−bi cos(θi (0)−φi (0)))
q
Wi (t) = 2ci gi2 +b2i −2bi gi cos(θi (0)),

where θi (t) denotes the rotation of the input crank Bi at time t.
If Di is rotated by an angular speed of α̇i , both Ai and Bi will
have an angular speed of −α̇i . Thus, we can conclude that θi (t) =θi (0) − tα̇i .
When we connect a chain of oscillation modules together, we mustaccount for the fact that the input crank rotation θi (t) for each module depends on the motion of the parent link li−1 . Since the axle of
Ai is connected to li−1 , Ai rolls around Di as li−1 rotates, which
affects the total rotation of Ai (see Figure 4b). Specifically, if we
apply the rotation speed α̇i to Di , then the angular speed of Ai is
a combination of this input rotation and the rotation of li−1 . As aresult, the definition for θi (t) in a chain of modules becomesθi (t) = θi (0) − tα̇i + (φi−1 (t) − φi−1 (0)),

walking, jumping jacks). Since we focus primarily on the motionof the limbs, we combine the head, shoulder, torso and hips to forma single rigid component.
To make the links move, we introduce an oscillation modulethat uses gears, a pulley, and a four-bar linkage to convert unidirectional rotation into an oscillating motion (see Figure 3a–b andFigure 6). The input to a module Mi is gear Di . Applying a unidirectional rotation to Di causes Ai to rotate, which drives the input
crank Bi of a four-bar linkage. The linkage converts this input rotation into an oscillating rotation of its output crank Ci . The axles ofDi , Ai and the fixed pivot of Ci are all attached to link li−1 while
the moving pivot of Ci is connected rigidly to link li . Thus, theoscillation of Ci causes li to oscillate as well (Figure 3c). Rotating Di also drives pulley wheel Pi , which is attached rigidly to thesame axle as Di . The pulley belt Qi transfers the rotation of Pi topulley wheel Ri . To prevent slipping between Pi , Qi and Ri , weuse pulley wheels and belts that have interlocking teeth. Connecting Ri rigidly to the same axle as the input gear Di+1 of the next
module Mi+1 propagates the motion to the next link in the chain(see Figure 3d). Thus, we can move an entire limb of the automaton by attaching a chain of oscillation modules to the rigid links anddriving the root module M1 (which must be attached to a stationary link of the figure) with a uni-directional rotation. Note that themodule that drives the last link in the chain does not have pulleyparts because no further rotation propagation is required. To simplify the motion and layout parameters described below, we restrict
Di and Ai to be the same size.
Motion parameters

There are several parameters that define the mechanical motion of achain of oscillation modules. The motion of a single module is defined by the rotation speed α̇i of the input gear Di , the bar lengths
bi , ci , gi in the four-bar linkage, and the initial angles θi (0) andφi (0) of the input and output cranks in the linkage (see Figure 4a).
Note that the length hi of the bar connecting the ends of the two
cranks Bi and Ci is fully determined by the other linkage parameters. Following [McCarthy 2000], we can express the angle φi (t)(2)

where (φi−1 (t) − φi−1 (0)) denotes the total rotation of Ci−1 (andthus the attached link li−1 ) with respect to its initial angle at time t.
Since the root module M1 that drives the first link l1 in the chain is
attached to the main support structure of the automaton rather thana moving link, we define φ0 (t) to be 0 for all t.
Our design imposes a few contraints on the motion parameter values. To ensure that the input crank Bi of the linkage can rotate fully
when driven by Di , we constrain the relative lengths of the linkagebars as follows [McCarthy 2000]:
gi + bi − hi − ci(hi − ci )2 − (gi − bi )2<0<0

Further, since the argument of the arccos function in Equation 1
must be in the range −1 to 1, we enforce the following constraint:
2gi (bi cos(θi (0)) − ci cos(φi (0))) +2bi ci cos(θi (0) − φi (0)) − b2i − c2i − gi2 ≤ 0
The equations above define the space of all possible motions for achain of rigid links using our design. Section 3.2 describes how
we use these relationships to compute motion parameters that best
approximate an input animation sequence.
Layout parameters

While the motion parameters partially specify the configuration of
the oscillation module components, we must specify several additional parameters to fully define the layout of the module. The
parameters bi , ci , gi determine the lengths of the linkage bars, butsince scaling the entire linkage uniformly does not change its motion, we treat the overall scale ωi as a free layout parameter. The
other layout parameters include the radii of the gears and pulleywheels (rDi , rAi , rPi , rRi ) as well as the pulley belt length sQi
and link length sli . As mentioned earlier, we restrict Di and Ai tobe the same size, so we set rAi = rDi and eliminate rAi as a free parameter. Given a fixed tooth size, the tooth count of the gears, pulleywheels and pulley belt determines the radius/length of those components. Thus, our layout optimization expresses rDi , rPi , rRi , sQi
in terms of integer tooth counts kDi , kPi , kRi , kQi .

Φi

Bone
Approxt(a) Initialize motion approximation based on Fourier decomposition

Φi

3.2

Motion approximation

Given a mocap sequence as input we simplify the animation by
projecting the motion of the bones within each limb onto a plane.
We then run an optimization to find the motion parameters that yield
the best approximation of the planar motion that can be generated
with a chain of oscillation modules.
Planar approximationt(b) Optimize four-bar linkage parameters: bi, ci, gi, θi, φiΦit(c) Optimize input angular speed αi and pulley ratios pk

For each kinematic chain, we start by tracing the path Xi ={xi (1), xi (2), ..., xi (n)} of the endpoint of the ith bone at eachframe of the input animation sequence with respect to its parent
joint where n is the total number of frames. We then compute theleast-squares plane of the traced path and project each point onto
this plane to obtain a planar path Yi = {yi (1), yi (2), ..., yi (n)}.
Finally, for every frame j, we convert the motion of each bone to arotation Φi (j) around the normal of the fitted plane ascos(Φi (j)) = cos(Φi (j − 1)) +Figure 5: Motion approximation graphs.

Not all assignments of layout parameters result in physically valid
layouts. There are three relevant constraints:
1. To prevent Ai from colliding with the axle of the next link
li+1 , we must ensure that rAi < ωi gi .
2. Similarly, to avoid collisions between the pulley wheel Ri ofthe module Mi and the axle of the gear Ai+1 of the next module Mi+1 , the relation rRi < 2rAi+1 must hold.
3. The length of each link must match the size of the components
placed on the link, so that sli = 2rAi+1 + ωi+1 gi+1 . The
link length also influences the pulley belt length sQi . However, since belts with a small amount of slack do not preventthe pulley from functioning, we represent this relationship as
an energy term in our layout optimization rather than a hardconstraint (see Section 3.3).

where cos(Φi (1)) denotes the initial orientation of the bone withrespect to its parent and cos(Φi (0)) = 0. Converting the rotationof a single input crank to motion in different planes requires theuse of bevel gears. Since standard bevel gears only allow changing
the rotation axis across orthogonal planes, we snap the plane of
motion for each limb to the saggital, coronal or transverse plane of
the figure.
Motion parameter optimization

Given the planar bone rotation angles Φi (j) for each chain, our goal
is to compute motion parameters that approximate the mocap bone
motion with the corresponding rigid links in the automaton. Since
each link li is driven by the output crank Ci , we aim to produce amechanical motion where changes in the crank angle φi (t) matchchanges in the bone angles Φi (j). Thus we define the following
energy term for each chain:EΦi =There are also a few constraints that reflect limitations of our fabrication process.
1. We manufacture gears Di and Ai with a laser cutter, which
limits the minimum and maximum sizes (i.e., tooth counts)of these components. In our designs, we constrain the toothcount to be between 14 and 80.
2. Similarly, we constrain the lengths of the linkage bars basedon the minimum bar length (8mm) that we can cut.
3. Finally, since it is difficult to create robust pulley wheels andbelts with a laser cutter, we use stock pre-made pulley parts
that are only available in a discrete set of wheel and belt sizes.
To encode this constraint in our layout parameterization, we
introduce a set of binary indicator variables {u1 , u2 , ..., uN }to select between the N available part sizes {v1 , v2 , ..., vN },P
and we represent the size of each pulley part as N
i=1 ui vi
PN
with the constraint i=1 ui = 1.
This set of layout parameters and constraints fully specifies thephysical layout of a limb mechanism in our design. Section 3.3
describes how we solve for a layout that matches a set of target
motion parameters.

yi (j − 1)yi (j)·,
kyi (j)k kyi (j − 1)k

XX
i

j

∆Φi (j) − ∆φi (j)
sin
2

2
(3)

where i indexes the bones, j indexes the frames of the animation
sequence, ∆Φi (j) = Φi (j + 1)−Φi (j) denotes the change in thebone angle between frames j and j +1 and ∆φi (j) = φi (j +1) −φi (j) denotes the corresponding change in angle of the output crankCi .
As explained in Section 3.1, φi (t) depends on the four-bar linkage
parameters bi , ci , gi , θi (0), φi (0), and the input angular speed ofeach module α̇i . We minimize EΦi by optimizing these parameters. Instead of directly optimizing for α̇i , we represent α̇i in termsof the pulley ratios for all the preceding modules in the chain. In
particular, for all but the root
Q module M1 , the input angular speedof Mi is defined as α̇i = i−1
k=0 pk where pk = kPk /kRk is thepulley ratio of module Mk . Based on this relationship, we optimize
for the linkage parameters, the angular speed α˙1 of the root module,
and the pulley ratios pi of each remaining module in the chain.
We apply a two-step optimization procedure to minimize EΦi . In
the first step, given α˙1 and pi , we solve for the linkage parameters bi , ci , gi , θi (0), φi (0) of each module. In the second step, we
use the computed linkage parameters to update α˙1 and pi acrossall the bones in the chain. In both of these steps, we minimize thenon-linear error function given in Equation 3 with respect to theconstraints involving the linkage parameters described in the previous section. We use the SQP method implemented in the MATLAB
Optimization Toolbox to solve these optimization problems, which
typically converges in 5-10 iterations.
The non-linearity of the objective function defined in Equation 3
mandates a good initialization of the optimization variables to obtain a valid minimum. Since we are considering periodic motions,
we employ a frequency-space analysis for this purpose. More precisely, we initialize the motion parameters using a Fourier decomposition on the rotation angles of each bone in the chain. The motion of each bone is then approximated using the Fourier componentof highest magnitude as

3.3

Layout: kinematic chains

Given a simplified motion, the next step is to compute layout parameters for the oscillation modules of each kinematic chain thatmatch both the target motion parameters and relative bone lengthsof the input figure as closely as possible. As described in Section 3.1, the layout is defined by continuous parameters (ωi , sli ),discrete parameters (kDi , kPi , kRi , kQi ), and the binary indicatorvariables for the pulley part sizes. Thus, we use mixed-integer programming to search over the space of possible solutions.
Energy function(4)

Our energy function encodes several desired properties for the layout of each kinematic chain.

where µ represents the magnitude, f represents the frequency, and ρ
represents the phase of the Fourier component. This cosine function
represents the change in rotation of the output crank of the four-bar
linkage as the input crank completes one full rotation cycle in n/fframes. Assuming a fixed initial orientation θi (0) of the input of thelinkage, each sampled value of j corresponds to a desired pair of input and output crank rotation angles (θi (0)+2πj(f /n), Φ(j)). We
sample 3 such angle pairs which uniquely specifies a set of linkage bar lengths that interpolate the sample points [Freudenstein2010]. We initialize α˙1 as 2π(f1 /n) where f1 is the frequency of
the Fourier component approximating the rotation of the first bonein the chain. We assume the initial values for the pulley size ratios
are pi = (2π(fi /n))/(2π(fi−1 /n)).

Propagated rotation. At the end of the motion parameter optimization step, we have computed a desired angular speed α˙1 driving theroot module M1 of each chain and the ratios of the pulley wheel
radii, pi , that specify how the input rotation should be propagatedto the remaining modules in the chain. Several layout parameters
determine the actual values of α˙1 and pi in the final automaton. In
our designs, the input crank of the automaton drives an input gear
whose rotation is propagated to the driving gear D1 of each root
module M1 . Thus, the angular speed driving M1 can be expressedas α˙1 = αI kI /kD1 where αI is the constant angular speed of theautomaton input crank, kI is the tooth count of the input gear, andkD1 is the tooth count of D1 . The pulley ratios pi can simply be
expressed as kPi /kRi (i.e., the ratios of the corresponding pulleywheel tooth counts).

Φ(j) = µ ∗ cos(2πf (j/n) + ρ),

To prevent having too short or too long bars upon scaling of the
four-bar linkage, we add an additional energy term to penalize large
ratios between the bar lengths. Specifically, we define the following
relations between the bar lengths:
κi =bi gi cos(θi (0))−gi ci cos(φi (0))+bi ci cos(θi (0)−φi (0))(bi ci )λi = gi /biµi = gi /ci

and add the energy term below to the first step of the optimization:
i
Ebar
=


κi −

1
κi

2

2

2
1
1
+(λi −1)2+−1 +(µi−1)2+
−1
λi
µi

Finally, in order to reduce drift in the motion of the links over time,
we introduce a periodicity constraint in the second step of the optimization. Specifically, assuming the provided motion sequence
contains one cycle of the desired motion, the period of the overallmotion is n frames. Each oscillation module should return backto its initial state at the end of the motion cycle. Thus, the periodicity of each bone in the chain is an integer divisor of n, andthe input crank of the corresponding four bar linkage should be rotated by an integer multiple of 2π, 2πmi during the given motion
cycle. In addition to the propagated input rotation parameters, we
also solve for these discrete multipliers mi . However, since bothEΦ and the constraints defined in Section 3.1 are non-linear, wetreat mi as a continuous variable and adopt a branch and boundstrategy to round them to integer values. Specifically, starting at
the root module, at each iteration we round mi to bmi c and dmi eand choose the value resulting in smaller optimization error. We
observed that duplicating the input motion several times (10 in our
experiments) and running the motion approximation to this longer
cycle improves the approximation results while still satisfying theperiodicity constraints.

Based on these expressions, we add the following energy term topenalize deviations from the desired angular speed and pulley ratios:((α˙I kI /kD1 − α˙1 )2 if i = 1
Eroti =
(5)
(kPi /kRi − pi )2
if i > 1
Pulley belt length. In our oscillation module design, the wheelsof each pulley, Pi and Ri , are attached to the axles at either endof link li−1 (see Figure 3b). Thus, we can express the tooth count(i.e., length) of the pulley belt kQi in terms of the tooth counts ofthe pulley wheels, kPi and kRi , and the length sli−1 of link li−1 :kQi zp = zp (kPi + kRi )/2 + 2sli−1 ,(6)where zp is a constant defining the distance between two consecutive teeth of the pulley wheels or belt.
The pulley wheels P1 and R1 that drive the second link l2 of eachchain are part of the root module M1 . Since M1 is attached to themain support structure of the automaton rather than a link in the
chain, the tooth count kQ1 of the pulley belt Q1 is not constrainedby the length of a link. Instead, kQ1 depends on the tooth counts ofthe pulley wheels, P1 and Q1 , the input gear D1 , and the distanceω1 g1 between the fixed pivots of B1 and C1 :kQ1 zp = zp (kP1 + kR1 )/2 + 2(zp kD1 + ω1 g1 )(7)

In practice, a small amount of slack in the pulley belt does not prevent the mechanism from functioning properly. Therefore, insteadof treating the above equalities as hard constraints, we define anenergy term to penalize the difference between the belt length kQi
chosen from the discrete set of available options and the ideal belt
length defined by the layout of the mechanism:kP +kR(kQi zp −zp i 2 i +2(mp kDi−1 +ωi−1 gi−1 )−)2
Epuli =
(kQ zp − zp (kP + kR )/2 + 2sl
− )2
i

i

i

i−2

if i = 1
if i > 1

four-bar linkage

pulleysoscillation module

bevel gears

Figure 6: The basic components of our automata. From left to right: Four-bar linkages transfer a rotational motion into an oscillatingone. Belts and pulleys are used to propagate the input rotation along the kinematic chain. An oscillation module joins these components
to represent one bone of the figure. Bevel gears change the orientation of the input rotation. Our optimization solves for the configuration,
dimensions, and placement of all these components to best approximate a given input motion sequence.
where we set  = 1 to allow for the slack. Note that the pulleypart sizes referenced in this formulation are represented by the corresponding binary indicator variables as described in Section 3.1.
Link lengths. Each link in the chain should be long enough toaccommodate the parts attached to itself. However, in order to preserve the shape of the input figure, the length sli of each link should
also match as closely as possible the corresponding relative bonelength sbi . The dimensions of the bones are defined up to a scaleusing a free scale variable ξ. Thus, the desired length of each rigid
link is sli = ξsbi . To penalize the deviations from the original bonelengths, we add the following term to our energy function for eachlink:
Esli = (sli − ξsbi )2
We further desire symmetric bone pairs (e.g., left and right upper
leg bones) to have similar lengths. For each such symmetric bone
pair, we penalize the differences between the corresponding link
lengths as,
Esij = (sli − slj )2 .
Combined energy function. We combine all the energy terms foreach link li in each serial chain cj to obtain the final energy function:

E=

X X

wroti Eroti +wpuli Epuli +wsli Esli +cj li ∈cjX

wsij Esij ,i,j∈S

where S denotes symmetric bone tuples and wroti , wpuli , wsli ,and wsij are the weights for each energy term. In our examples, we
set wroti and wpuli to 5 and set wsli and wsij to 1.
Mixed-integer progamming

Given the energy function E and all the linear hard constraints
described above, we formulate the optimization as a mixed integer programming problem and solve it using a branch-and-boundtechnique. More specifically, we use the constrained mixed-integer
solver CoMISo [Bommes et al. 2012] that provides a wrapper to the
Gurobi solver [Gurobi Optimization 2012]. During the optimization process, the solver treats the discrete unknowns as continuous
variables and generates a solution where these variables have fractional values. The solver then constructs a search tree where eachbranch represents the result of constraining a discrete variable toeither the floor or ceiling of its fractional value from the continuous solution. In our experiments, this optimization process takes
around 100 seconds to find a feasible solution for a problem with360 binary, 10 integer, and 10 continuous variables. The result of
the optimization is a set of layout parameters that fully define thesize of the mechanical parts in each oscillation module.

(a) parallel-planelayout(b) multi-planelayoutFigure 8: The input crank rotation is propagated to the root moduleof each chain using pulleys. For multi-plane layouts, we also use
bevel gears (right).

3.4

Layout: unified design

The final step in our pipeline composes all the kinematic chains intoa unified design that can be driven by a single input crank. This
process involves choosing the orientation and position of the crankand then generating mechanisms that propagate the crank rotation
to the root module of each moving chain in the automaton. In ourdesigns, we attach the input crank to the torso link of the figure anduse pulleys and bevel gears (if necessary) to propagate the rotation.
We arrange these pulleys and bevel gears on the stationary torso,
head and (in some cases) shoulder links based on the orientationsof the motion planes for the moving limbs.
Parallel-plane layout: If the motion planes of the moving limbs
are all parallel to either the saggital or coronal planes of the figure,
we orient the input crank, torso and head links parallel to the motion plane (see Figure 8(a)). Recall from Section 3.1 that the root
module of each chain must be placed on one of the stationary links.
We position the root modules of the arms on the head link, and weput the root modules of the legs on the torso link. Finally, we use
pulleys to connect the input crank to the driving gear of each root
module. If the limbs move parallel to the saggital plane, we position the pulleys on the left and right sides of the torso/head links,
and for coronal plane motion, we put the pulleys on the front andback sides of the torso/head links.
Multi-plane layout: If the motion planes of the moving limbs are
all parallel to the transverse plane, or if the motion planes are not
all parallel to each other, we incorporate bevel gears into our unified
design (see Figure 8(b)). If all of the non-tranvserse motion planes
are parallel to the coronal plane, then we orient the input crank,
torso and head links parallel to the coronal plane as well. Otherwise, we orient these components parallel to the saggital plane. We
orient the root module of each chain so that its rotation plane is parallel to the rotation plane of the input crank. As in case 1, we place
the root modules for the arms and legs on the head and torso links,

Figure 7: Physical prototype of dancing motion sequence. (Please refer to the supplementary video.)
respectively. For chains whose motion plane is orthogonal to therotation plane of the input crank, we use bevel gears to convert therotation of the root module output crank C1 and pulley wheel R1 tothe appropriate motion plane.
Special case: Where the motion plane of an arm is parallel to thecoronal or transverse plane (as in the dancing example in Figure 9)
we use the shoulder link as an additional support structure to accommodate the root module of the arm. We orient the shoulder tobe parallel to the motion plane of the arm, and if the input crankrotates in a different plane, we add a bevel gear configuration toconvert the input crank rotation to the appropriate motion plane.

4forward kinematics to qualitatively validate how faithfully the sequences recreate the input motion. Specifically, we build a mechanism graph G = (V, E), where each node vi ∈ V represents apart (e.g., a gear or a pulley) and each edge eij ∈ E connecting thevertices vi and vj represents the relation between the corresponding parts. In our setup, the typical relations include the coaxial orparallel-axis properties of the gears, and the motion chains comprising of pulleys and four-bar linkages. At every frame of the motion
sequence, we assume that the input crank rotates clockwise with aconstant speed. We propagate this rotation along the edges of themechanism graph to compute the position and orientation of eachcomponent in the mechanism. Note that by construction, the graphs
are free of any loops.

Evaluation
We fabricated automata for two of the designed sequences, one for each of the major types of layout configurations:
the walking sequence (see Figure 1), which does not require any
bevel gears; and the dancing sequence (see Figure 7), which involves motion in two different planes. We used off-the-shelf pieces
for the bevel gears, pulleys, and pins. The linkages and gears werelaser cut based on the dimensions as prescribed by our optimization. The most time consuming part was assembling the pieces,which was done manually. However, given that our design consists of similar modular components (i.e., the oscillation modules)
the assembly process was relatively straightforward (albeit somewhat tedious). Finally, we used a single speed motor to drive theautomata. Figure 1 and 7 and the supplementary video show ourfabricated automata in motion. Note how subsequent joints oscillate at different phases and with different periods.
Fabrication.

In order to evaluate how well our planar motion simplification algorithm approximates various human motions, we analyzed a large number of mocap sequences from existing databases.
Data sets.

We first trace the path Xi = {xi (1), xi (2), ..., xi (n)} of the endpoint of the ith bone of a kinematic chain cj at each frame of
the input motion. We compute the common least squares plane
Pj (n, d) of all such paths for cj . We then measure the fitting
error asP
the deviationfrom a planar motion over n frames asP
Ej :=bi ∈cjn (n · xi (n) + d). In order to account for differences in the lengths of the paths traced by each bone, we normalize theby the total length of the paths, measured as
P errorPmj :=bi ∈cjn kxi (n + 1) − xi (n)k. The final planar fitting score of the motion is then computed over all the chains as
Mp := minj mj /(Ej + ) with  = 0.01 used as a regularizer.
Essentially, Mp measures how well a non-trivial motion can be approximated using a set of planes, one for each chain.
We tested our algorithm on a total of 80 mocap sequences fromthe CMU motion database. We found the following motion types(about 40% of the database) to be well suited for our algorithm:
walking, running, jogging, exercising, waving, drinking as they
consistently get high scores (Mp > 10). We call them good motion
types. On the other hand, sequences like swimming, swordplay,fishing (Mp < 2) contain large out-of-plane motions, and hence ouralgorithm cannot replicate them faithfully. In Figure 9, we present
representative realizations for some of the good motion types (seealso the accompanying video).
Our system produces a mechanical automaton design for a given input motion. We simulate the mechanism using
Simulation.

Figure 9 shows the mechanical automata generated byour system for several motion sequences. For each motion type,several snapshots of the original animation and the corresponding
simulation frames are provided. Our system generates automata
consisting of a chain of oscillation modules driven by a single actuator. While the use of standard planar mechanical components
simplifies the fabrication and assembly processes, there are aspectsof certain motions that our method fails at reproducing accurately(see the accompanying video).
Results.

In all of our example automata the torso of the figure has been usedas the main support structure. In the dancing example, the shoulders
have been used as an additional support structure since the arms
move parallel to the transverse plane of the figure. As describedin Section 3.4, to propagate the rotation of the driver gear to eachkinematic chain, pulleys are used to fill up the space between the

EXERCISING

f=97

f=156

f=197

f=248

JUMPING JACK

f=20

f=135

f=155

f=275

f=10

f=25

f=125

f=155

BALLERINA

f=15

Figure 9: Example automata generated by our system. For each example, snapshots of the original motion sequence in different time frames(denoted by the numbers) and the corresponding simulation result of the automata are given. The bevel gear configuration used in theballerina sequence is shown in orange.

Limitations.

Our algorithm has several limitations:(i) Since our automata are based on predominantly planar linkages, our initial planar projection step for each kinematic chain cansignificantly distort certain types of mocap sequences (e.g., swimming). Further, in order to simplify the fabrication/assembly processes, we generate automata driven by a single actuator that use
standard planar mechanical components and standard bevel gears.
These decisions impose additional constraints in the motion approximation step of our method. Better approximations can possibly be obtained by adding other types of mechanical elements(e.g. non-circular pulleys) at the cost of increased complexity ofthe optimization and the resulting automata.
(a) captured motion(b) generated automaton

Figure 10: Commercial motion sensing input devices such as theMicrosoft Kinect enable direct capturing of input motions to oursystem. A snapshot of the captured motion sequence (a) and thegenerated automaton (b) is shown.

(ii) We assume periodic motions as input to allow driving the automaton indefinitely with a constant-speed input rotation. While
we did not observe noticeable drift for extended operation of ourassemblies, machining imprecisions or mechanical wear could potentially cause temporal deviations that over time reduce the accuracy of the motion approximation. At a certain point, the automaton
might have to be partially disassembled to re-align the parts to theoriginal configuration.

driver gear and the root of the chain along the support structure.
While bevel gears enable mechanisms with arbitrary orientation of
motion planes for different kinematic chains, such gears can be difficult to manufacture depending on the fabrication method. For example, it is not possible to create bevel gears with a standard laser
cutter. In motion sequences where different kinematic chains movein nearly-parallel planes, the use of bevel gears can be avoided
by mapping the input sequences to motions restricted to parallel
planes. In the walking, exercising, and jumping jack examples, weshow that plausible motion approximations can be generated despite this restriction. However, in the dancing automata, the use ofbevel gears is necessary since the arms move in an orthogonal planeto the legs.
In our examples, we have primarily used motions selected fromthe existing motion databases as input. However, recent advancesin commercial motion sensing input devices such as the Microsoft
Kinect enable easy tracking of the human skeleton and thus provide
an interface to directly capture input motions. We demonstrate theflexibility of our input requirements with the kendo sequence (seeFigure 10 and the supplementary video). To produce this result,
we used the Kinect to record a performance, extracted the humanskeleton with the commercial tool ipi Soft [2013], and then used theskeleton motion as input to our system.
Although our system has a fully automatic mode,
the user can also control the final design in various ways.
User control.

(i) Depending on the target fabrication method, the user can provide
additional constraints. Based on the specification of our laser cutter,
we used minimum and maximum gear tooth counts of 14 and 80(given a 1mm tooth size). These constraints have a direct effecton the realization of the desired motion, specifically for links that
require a large change in input angular speed.
(ii) Our system restricts the motion planes of the limbs to be parallelto the saggital, coronal or transverse plane of the figure. The user
can also manually specify the motion plane orientations. We use
the automatically generated motion planes in our results.
(iii) Finally, the user can set a threshold for the minimum angularrange for the motion of the bones (0.35 radians in our results). We
set bones oscillating with an angular range less than this thresholdto be fixed, thus reducing the complexity of the generated mechanisms.

5

Conclusion

In this paper, we have presented an algorithm to automatically realize a mechanical automaton starting from an input mocap sequence.
Our work includes three main contributions. We introduce an oscillation module design that can generate kinematic chain motions
with links that oscillate at different phases and frequencies. We
also describe a motion approximation algorithm that converts an
input sequence to a mechanically realizable motion. Finally, we
present an automated method for determining the parameters andspatial layout of mechanical parts that takes into account physicaland fabrication constraints. Our results demonstrate that our proposed approach can generate mechanical automata that reproduce
non-trivial human motions with multiple moving limbs.
We see several interesting avenues for future work:
Perception of human motion: In the motion approximation partof our method, we use an objective function based on the rotation
angles of each joint. Our intuition is that the changes in joint angles
have a significant effect on how we perceive a motion since they are
visually well exposed in the static body posture. Developing better
perceptual metrics for comparing human motions is an interesting
avenue for future work.
Joint optimization of motion and layout parameters: Our current
method optimizes for the motion parameters of the mechanism first,
and then solves for the layout of the parts. It is possible that a joint(or perhaps iterative) optimization of these parameters could produce better motion approximations in the final automaton designs.
Self-standing automaton: It would be interesting to consider thedesign of self-standing mechanical figures that remain balanced
while they move. Generating such automata would require amethod that accounts for both the stability of the design as wellas the target motion. One challenge here is that the placement of
mechanical components (e.g., gears, linkages) affects the weight
distribution and thus the stability of the automaton.
Integrated designs: It might be possible to fabricate automata withembedded movable parts that do not require assembly. If the goal
is to place all of the mechanisms within the volume of the figure,this would likely require very compact arrangements of mechanicalparts.
Extension to other mechanism types: The basic building block ofour design is a planar four-bar mechanism, which is a very common
type of linkage. Our motion approximation and parameter optimization algorithms can be useful in designing a variety of linkagebased mechanisms (e.g., windshield wipers, vehicle suspensions,moving parts in industrial machinery, path tracing mechanisms,etc.). Furthermore, by specifying different constraints between thelengths of the linkage bars, our method can be adapted to handle
other types of linkages, such as slider-crank and folding linkages.

Acknowledgements
We thank the anonymous reviewers and Nobuyuki Umetani for theirvaluable comments. We thank Minh Dang for performing the kendo
sequence and Zohreh Sasanian for helping with the assembly of
the physical prototypes. We are grateful to the ENAC Output Center at EPFL for providing us with the laser cutting facilities andTina J. Smith for the video voice over. This research has received
funding from the European Research Council under the European
Union’s Seventh Framework Programme (FP/2007-2013) / ERC
Grant Agreement 257453, ERC Starting Grant COSYM, a Marie
Curie CIG, an Adobe Research grant, and a UCL impact award.

K IM , J., K IM , K., C HOI , K., AND L EE , J. 2000. Solving 3d
geometric constraints for assembly modelling. The International
Journal of Advanced Manufacturing Technology 16, 843–849.
L UO , L., BARAN , I., RUSINKIEWICZ , S., AND M ATUSIK , W.
2012. Chopper: partitioning models into 3d-printable parts.
ACM TOG (SIGGRAPH Asia) 31, 6, 129:1–129:9.
M C C ARTHY, J. 2000. Geometric Design of Linkages. Interdisciplinary Applied Mathematics Series. Springer Verlag.
M ITRA , N. J., YANG , Y.-L., YAN , D.-M., L I , W., AND
AGRAWALA , M. 2010. Illustrating how mechanical assemblies
work. Proc. ACM SIGGRAPH 29, 3.
P ENG , X., L EE , K., AND C HEN , L. 2006. A geometric constraint
solver for 3-d assembly modeling. The International Journal ofAdvanced Manufacturing Technology 28, 561–570.
P OLLARD , N., H ODGINS , J. K., R ILEY, M., AND ATKESON , C.
2002. Adapting human motion for the control of a humanoid
robot. In IEEE ICRA.

References

ROY, U., P RAMANIK , N., S UDARSAN , R., S RIRAM , R., AND
LYONS , K. 2001. Function-to-form mapping: model, representation and applications in design synthesis. Computer-Aided
Design 33, 10, 699 – 719.

A NANTHA , R., K RAMER , G. A., AND C RAWFORD , R. H.
1996. Assembly modelling by geometric constraint satisfaction.
Computer-Aided Design 28, 9, 707 – 722.

S AFONOVA , A., P OLLARD , N., AND H ODGINS , J. K. 2003. Optimizing human motion for the control of a humanoid robot. In
Intl. Symp. on Adaptive Motion of Animals and Machines.

B ÄCHER , M., B ICKEL , B., JAMES , D. L., AND P FISTER , H.
2012. Fabricating articulated characters from skinned meshes.
Proc. ACM SIGGRAPH 31, 4, 47:1–47:9.

S CHWARTZBURG , Y., AND PAULY, M. 2013. Fabrication-aware
Design with Intersecting Planar Pieces. Computer Graphics Forum 32, 2, 317–326.

B OMMES , D., Z IMMER , H., AND KOBBELT, L. 2012. Practical mixed-integer optimization for geometry processing. In Intl.
Conf. of Curves and Surfaces, 193–206.
C AL Ì , J., C ALIAN , D. A., A MATI , C., K LEINBERGER , R.,S TEED , A., K AUTZ , J., AND W EYRICH , T. 2012. 3d-printing
of non-assembly, articulated models. ACM TOG (SIGGRAPH
Asia) 31, 6, 130:1–130:8.

S TAVA , O., VANEK , J., B ENES , B., C ARR , N., AND M ĚCH , R.
2012. Stress relief: improving structural strength of 3d printableobjects. Proc. ACM SIGGRAPH 31, 4, 48:1–48:11.
U METANI , N., I GARASHI , T., AND M ITRA , N. J. 2012. Guided
exploration of physically valid shapes for furniture design. Proc.
ACM SIGGRAPH 31, 4, 86:1–86:11.

C ARNEGIE M ELLON U NIVERSITY, 2003. Cmu graphics lab motion capture database.

X U , W., WANG , J., Y IN , K., Z HOU , K., VAN DE PANNE , M.,
C HEN , F., AND G UO , B. 2009. Joint-aware manipulation of
deformable models. ACM TOG (SIGGRAPH Asia) 28, 3, 35:1–
35:9.

C HIOU , S.-J., AND S RIDHAR , K. 1999. Automated conceptual
design of mechanisms. Mechanism and Machine Theory 34, 3,
467 – 495.

Z HU , L., X U , W., S NYDER , J., L IU , Y., WANG , G., AND G UO ,B. 2012. Motion-guided mechanical toy modeling. ACM TOG(SIGGRAPH Asia) 31, 6, 127:1–127:10.

C OROS , S., T HOMASZEWSKI , B., N ORIS , G., S UEDA , S., F OR BERG , M., S UMNER , R. W., M ATUSIK , W., AND B ICKEL , B.
2013. Computational design of mechanical characters. Proc.
ACM SIGGRAPH 32, 4 (July), 83:1–83:12.
F REUDENSTEIN , F. 2010. Approximate synthesis of four-bar linkages. Resonance 15, 8, 740–767.
G UROBI O PTIMIZATION , I., 2012. Gurobi optimizer reference
manual.
H ALLER , K., J OHN , A. L.-S., S ITHARAM , M., S TREINU , I.,
AND W HITE , N. 2009. Body-and-cad geometric constraint systems. In Proc. Symp. on Applied Computing, ACM, 1127–1131.
H AN , Y.-H., AND L EE , K. 2006. A case-based framework forreuse of previous design concepts in conceptual synthesis ofmechanisms. Computers in Industry 57, 4, 305 – 318.
I P I S OFT LLC., 2013. ipi soft - markerless mocap.