Computational Design of Mechanical Characters

Stelian Coros*1 Bernhard Thomaszewski*1 Gioacchino Noris1 Shinjiro Sueda2 Moira Forberg2
Robert W. Sumner1 Wojciech Matusik3 Bernd Bickel1
1 2 3
Disney Research Zurich Disney Research Boston MIT CSAIL

Figure 1: The interactive design system we introduce allows non-expert users to create complex, animated mechanical characters.

Abstract 1 Introduction

We present an interactive design system that allows non-expert

users to create animated mechanical characters. Given an articu- Character animation allows artists to bring fictional characters to
lated character as input, the user iteratively creates an animation life as virtual actors in animated movies, video games, and live-
by sketching motion curves indicating how different parts of the action films. Well-established software packages assist artists in
character should move. For each motion curve, our framework cre- realizing their creative vision, making almost any digital charac-
ates an optimized mechanism that reproduces it as closely as pos- ter and movement possible. In the physical world, animatronic
sible. The resulting mechanisms are attached to the character and figures play an equivalent role in theme parks and as special ef-
then connected to each other using gear trains, which are created fects in movies and television. While these sophisticated robots are
in a semi-automated fashion. The mechanical assemblies generated far from becoming household items, toys that exhibit mechanical
with our system can be driven with a single input driver, such as a movement are extremely popular as consumer products. However,
hand-operated crank or an electric motor, and they can be fabricated unlike virtual characters, creating complex and detailed movement
using rapid prototyping devices. We demonstrate the versatility of for mechanical characters, whose motion is determined by physi-
our approach by designing a wide range of mechanical characters, cal assemblies of gears and linkages, remains an elusive and chal-
several of which we manufactured using 3D printing. While our lenging task. Although mechanical characters have been part of
pipeline is designed for characters driven by planar mechanisms, the toy industry since the nineteenth century [Peppe 2002], design
significant parts of it extend directly to non-planar mechanisms, al- technology for these characters has changed little and is limited to
lowing us to create characters with compelling 3D motions. expert designers and engineers. Even for them, the design process
is largely trial and error, with many iterations needed to produce
an acceptable result. Since iteration times increase greatly as the
CR Categories: I.3.6 [Computer Graphics]: Methodology and complexity of the design space increases, mechanical characters are
Techniques—Interaction Techniques; I.3.5 [Computer Graphics]: limited in scope and complexity, which in turn limits the range of
Computational Geometry and Object Modeling—Physically based possible movement and the creative freedom of the designers.
modeling
We present a computational design system that allows non-expert
Keywords: mechanical characters, animation, fabrication, inter- users to design and fabricate complex animated mechanical char-
active design acters (Fig. 1). Our system automates tedious and difficult steps in
the design process, and the resulting mechanical characters can be
Links: DL PDF fabricated using rapid manufacturing methods such as 3D printing.
Interactivity is a core design principle of our system, allowing users
to quickly explore many different mechanical design options, as the
motion of the characters is iteratively created.

In order to make the computational design problem tractable, we

limit the scope of this work to characters that perform cyclic mo-
tions and that do not need to sense or respond to the external envi-
ronment. However, within these restrictions, we wish to support a
wide range of complex, user-defined motions. In order to accom-
plish this goal, we begin with a library of parameterized mechanical
assembly types. Our system first pre-computes a sparse sampling of
their parameter spaces, resulting in a representative set of motions
for each type of mechanical assembly. After this precomputation
step has been completed, our interactive design pipeline proceeds
*The first two authors contributed equally to this work. as follows (see Fig. 2 for a visual summary):
Figure 2: Overview of our interactive design system: a) an input character and a gear box are provided; b) the desired motion of the
character is specified by sketching motion curves; c) optimized driving mechanisms are generated by our framework; d) gear trains are
created to connect all the driving mechanisms to one actuator; e) support structure is generated; f) the mechanical character is 3D-printed.

1. Given an articulated character as an input, the user selects a set the system recursively decomposes it into simpler sub-functions
of actuation points on the character and sketches associated until a match is found in the database. Similarly, Subramanian
motion curves. and Wang [1995] define valid configuration spaces for building
blocks and use an iterative deepening search to generate mechanism
2. For each input curve, the precomputed database is queried topologies and geometries that satisfy given motion constraints. Al-
to find an assembly that matches the motion specified by the ternatively, genetic algorithms or other stochastic search methods
user. This gives us both the type of mechanical assembly that can be applied [Cabrera et al. 2002]. Recently, Zhu et al. [2012]
is best suited for each motion curve, and a good initial set of suggested selecting a mechanism from a parameterized set accord-
parameter values (Sec. 4). ing to a priori knowledge of its motion. The selected mechanism is
3. Appropriate driving mechanisms are instantiated, connected then refined by optimizing over both discrete and continuous vari-
to the character, and their parameter values are further opti- ables using simulated annealing. While this approach can effec-
mized using a gradient-based formulation (Sec. 4.2). tively handle, e.g., linear, ellipsoidal or circular motions, creating
mechanical characters exhibiting complex motions requires a more
4. Once all driving mechanisms are set up, the gears that actuate general formulation. In our work, we use a sampling-based ap-
them are connected to each other through a gear train in a proach to generate a sparse but representative set of motions that
semi-automatic fashion (Sec. 6.1). different types of mechanisms can generate. This allows us to de-
termine which of the available mechanism types are well-suited to
5. For planar characters, our system then repositions the me- create a desired motion, and we use a gradient-based method in
chanical components to ensure that no collisions occur during order to further optimize the mechanisms generated by our frame-
operation (Sec. 6.2). work.
6. Finally, support structures are generated to hold the compo-
nents of the assembly in place (Sec. 6.3). The complete char- Motion and Interaction Analysis. There exists a variety of
acter model and the mechanical assembly driving it are then methods for analyzing the geometry of mechanisms in order to ex-
ready for fabrication (Sec. 6.4). tract the kinematic constraints that define their motions. For in-
stance, Mitra et al. [2010] present a semi-automatic technique for
2 Related Work depicting the operation of mechanical assemblies. Their method
determines the causal relationship between different parts of an
Mechanical Assemblies have tremendously changed our way assembly based solely on geometry. Such processes are also in-
of life since the industrial revolution — for a comprehensive in- vestigated for reverse engineering of scanned devices [Demarsin
troduction into mechanisms and mechanical devices we refer the et al. 2007]. Recent work also explores the creation of a print-
interested reader to the textbook of Sclater and Chironis [2001]. able articulated model from input geometry by analyzing a skinned
The potential to use specialized software for analysis and design mesh [Bächer et al. 2012] or offering an intuitive user interface
of mechanisms has been recognized since the early days of com- to control the placement and range of motion of joints [Calı̀ et al.
puters [Freudenstein 1954]. Consequently, a variety of approaches 2012]. While the resulting characters can be posed, these methods
for representing mechanical structures have been presented. Some do not address the challenge of animating them. In principle, how-
modeling systems, for instance, implement function-oriented and ever, the characters designed using these methods could be used as
shape-oriented approaches, where objects, assemblies and posi- input for our framework.
tional relationships are represented as nodes in a graph structure,
and an explicit or procedural representation is used for shape prim-
Design Systems and Personalized Fabrication are quickly
itives [Wesley et al. 1980; Gui and Mäntylä 1994]. Similar tech-
gaining interest in the computer graphics community. Interac-
niques are used to implement basic functionality for commercially
tive systems enable non-expert users to design, for example, their
available CAD/CAM tools. Despite the significant benefits pre-
own plush toys [Mori and Igarashi 2007] or furniture [Lau et al.
sented by such tools, creating complex mechanisms, such as those
2011; Umetani et al. 2012]. Rapid prototyping devices allow for
needed to animate mechanical characters, currently requires expert
the fabrication of physical objects with desired properties based
designers.
on custom microgemetry [Weyrich et al. 2009], reflectance func-
tions [Malzbender et al. 2012], subsurface scattering [Hasan et al.
Kinematic Synthesis. Several existing methods aim at automat- 2010; Dong et al. 2010] and deformation behavior [Bickel et al.
ing the design of devices that transform a specified input motion 2010]. Ensuring that printed objects are structurally stable, Stava
into a specified output motion. Chiou and Sridhar [1999], for et al. [2012] proposed to relieve stress by automatically detecting
instance, use symbolic matrices representing a library of mecha- and correcting problematic parts of the models. In our work, we
nism as basic building blocks. Starting with an intended function, focus on the problem of designing mechanical assemblies. Inspired
Figure 3: The driving mechanisms we use as building blocks can generate a continuous space of widely different motions. To generate
optimized assemblies that best match an input motion, we first perform a coarse exploration of the space of possible motions for each
mechanism, followed by a continuous parameter optimization.

by recent work in sketch-based interfaces [Eitz et al. 2012] and de- Pin Connections are used to model hinge joints between pairs
sign galleries [Marks et al. 1997], we present an interactive design of components i and j. The constraints output by this type of con-
system that allows non-expert users to intuitively create complex, nection take the form Cc = {(x(xi )i − x(xj )j )T (v(vi )i −
animated mechanical characters. v(vj )j )T }T . The parameters xi , xj , vi and vj define the position
and rotation axis of the pin joint. Note that while the Pin Con-
nections output six constraints, they only remove five degrees of
3 Assembly simulation freedom from the system: the two connected components can still
rotate freely with respect to each other about the axis v(vi )i (or
The recent method proposed by Zhu et al. [2012] simulates me- equivalently v(vj )j ). Attaching two pin connections between the
chanical assemblies in a two-stage process. First, the configuration same pair of components results in them being welded to each other.
of the driving assembly is computed using forward kinematics: by
assuming a tree-based representation of the mechanism [Mitra et al.
2010], the configuration of a component fully determines the con- Point On Line Connections ensure that a pin on component i
figuration of all other components that are connected to it. Second, always lies on a line defined on component j. This type of con-
the motion of the toys is computed using inverse kinematics. In nection outputs constraints Cc = v(vj )j × (x(xi )i − x(xj )j ),
contrast, we employ a constraint-based simulation of mechanical where xi represents the local coordinates of the pin on component
assemblies. This allows us to reconstruct the motion of the charac- i, and the vector vj and point xj define the line that the pin should
ter and the driving assemblies in a unified manner, and it enables us lie on. Using two point on line connections between the same pair
to simulate a much broader range of mechanisms, such as assem- of components allows us to model prismatic joints. As for the Pin
blies with kinematic loops, which cannot be simulated using the Connections, we can create three additional scalar constraints to en-
forward kinematics approach employed by [Zhu et al. 2012]. As sure that the two components can only rotate with respect to each
discussed shortly, this approach also allows us to efficiently com- other about one axis.
pute gradients needed to optimize individual sub-assemblies.

Phase Connections are typically used to connect gears to each

3.1 Components and Connections
other, and they directly constrain the phase of the affected compo-
nents. In its most general form, the scalar constraint output by these
The mechanical assemblies we simulate consist of rigid compo- connections has the form: Cc = αi − f (αj ). The function f de-
nents that are connected to each other. The world-coordinates x of a pends on the types of gears that are connected. For spur and bevel
point x expressed in the local coordinates of component i are given gears, f (α) = −r ∗ α, where r is the ratio of the number of teeth of
by x(x)i = Ti + Rγi Rβi Rαi x. Similarly, the world-coordinates the two gears. For non-circular gears, f is slightly more involved,
v of a vector v expressed in the local coordinates of component i as described in Sec. 4.3. As a special case of the phase connection,
are v(v)i = Rγi Rβi Rαi v. The 6-dimensional state of the compo- we allow gears to be directly connected to a virtual actuator, which
nent is defined as si = {TTi , γi , βi , αi }T , where Ti ∈ R3 denotes we call the Input Driver.
the global position of the component, γi , βi , αi are the Euler an-
gles parameterizing the component’s orientation and Rγi , Rβi and
Rαi are the corresponding rotation matrices. The rotation axes nγ Fixed State Connections affect individual components and out-
and nβ are initially set to the x and y-axes respectively. To avoid puts six constraints: Cc = s−sd , where s is the state of the affected
numerical problems due to the gimbal lock, they (together with the component, and sd is the desired state. The phase variable can be
corresponding rotational degrees of freedom γ and β) can be re- optionally omitted from the list of constraints, allowing components
computed by decomposing the component’s net orientation when- to rotate freely about one axis. These connections are used to sim-
ever it approaches a singularity. The axis of rotation for Rαi is set ulate support structures such as walls or shafts, and to allow users
to the component’s local z-axis, and we refer to the rotation angle to temporarily freeze parts of the characters.
α as the phase of the component.

The components of an assembly are linked to each other through 3.2 Simulation
different types of connections. Each connection c outputs a set of
scalar constraints Cc . We have implemented four types of connec-
tions that, when combined, allow us to simulate a wide variety of To run a simulation step, we first advance the phase of the Input
mechanical assemblies: Driver forward in time. We then solve the following optimization
problem in order to compute component state values that satisfy all
the constraints:

1
min CT C, (1)
s 2

where C is a vector collecting the scalar constraints output by

all the connections in the assembly. We use a standard Newton-
Raphson method to solve Eq. (1), assuming that the phase of the
Input Driver fully determines the configuration of the entire assem-
bly. The mechanical assemblies that we simulate, however, can be
under or over constrained, if the user employs too few or too many
driving mechanisms. Our framework detects these problems (if the
system is over-constrained, Eq. (1) has a non-zero minimum; if it
is under-constrained, the hessian of 21 CT C is singular) and allows
the user to edit the assembly as required.

4 Mechanism Design
Our interactive design system allows users to sketch a set of curves
that specify the motion of different parts of the input character.
For each of the input curves, our system outputs optimized driv-
ing mechanisms that are attached to the character and control its
motion. Two problems need to be addressed in order to achieve Figure 4: We assume as input a library of parameterized driving
this. First, out of a library of input driving mechanism types, our mechanisms such as the ones illustrated here. These building blocks
system must choose an appropriate one. Second, the parameters of are instantiated by our framework, optimized and attached to the
the selected mechanism must be optimized in order to best match input character, driving its motion. The locations of the attachment
the motion specified through the input animation curves. points are highlighted.

For simple motion trajectories specified by circular, elliptical or

straight-line curves, the map to an appropriate driving mechanism The input motion curves provided to our system directly specify the
can be manually specified [Zhu et al. 2012]. However, as the com- trajectories that the attachment point of a driving mechanism should
plexity of the driving mechanisms increases, the space of possible trace out. To determine which type of mechanism is capable of
output motions grows significantly (see, e.g., Fig. 3), and this ap- best matching an input curve, it is therefore sufficient to search the
proach very quickly becomes impractical. Furthermore, in order to precomputed database using the curve similarity metric described
accommodate arbitrary, black-box mechanisms, we do not assume in Sec. 5. Once a mechanism is selected from the database, it is
that there exist analytic expressions describing the relationship be- first scaled, rotated and translated using the transformation that best
tween a given set of parameters and the motion they lead do. The aligns the curve traced out by its attachment point to the input curve
methods we describe in this section allow us to address the chal- (see Sec. 5). If a designated gear box is provided as input, then
lenges of working with complex driving mechanisms. we must ensure that the bounding box of the chosen mechanism
fits inside. If this is not the case, we discard the mechanism and
Overview Our system takes as input a library of parameterized proceed to the next best match.
mechanism types as illustrated in Fig. 4. Each of these mechanisms As the database we pre-compute represents only a sparse sampling
contains at least one driving gear that is either connected directly of the parameter space for each assembly type, the selected mech-
to the Input Driver or to other gears. Once instantiated, the assem- anisms need to be further optimized, as described in Sec. 4.2. We
blies are attached to the character, typically through pin connec- note that the driving mechanisms obtained by querying the database
tions. While the locations of the pin joints on the input character are typically provide a good starting point for the continuous opti-
generally user-specified, the attachment points on the driving mech- mization method we use. This significantly improves convergence
anisms are parameterized. For each type of driving mechanism, the rates and reduces the likelihood of encountering bad local-minima,
locations of the pin and point-on-line connections between the indi- which is a very real possibility given the highly non-linear relation-
vidual components as well as the positions of the support shafts are ship between assembly parameters and the resulting motions.
also parameterized. As an example, the mechanism types shown in
Fig. 4 have between 6 and 12 parameters.
4.1 Parameter Space Exploration
To address the challenge of determining which assembly type is
best suited for a desired animation, we begin by performing a coarse We approximate the space of motions that a given type of mecha-
exploration of their parameter spaces through sampling (Sec. 4.1). nism can generate by sampling its parameter domain. Our goal in
This pre-processing step results in a database that stores a repre- this context is to obtain a good coverage of the space of possible
sentative set of possible motions for each class of mechanism, as motion curves with a sparse set of samples. The latter point is im-
illustrated in Fig. 3. Rather than recording the motion trajectories portant since it determines the response time for curve retrieval dur-
of the individual gears and linkages comprising the mechanisms, ing interactive design. In order to generate a sparse set of samples
however, the database represents a map between specific points in that cover a large variety of motion curves, we use a Poisson-disk
an assembly’s parameter space and the motion curves traced out sampling scheme in metric space. This amounts to requiring that
by the mechanism’s attachment point, since these trajectories fully for any pair of parameter-space samples, the distance between the
define the motion of the input character. two corresponding curves must not be lower than a given thresh-
 the more involved metric described in Sec. 5. Because the curve
traced out by the marker point is already aligned with the input
curve, and their shapes are relatively similar, we have found this to
be sufficient. For any phase t, the gradient of the matching objective
∂Ft
∂p
is given by:

∂Ft ∂x ∂x ∂st T
=( + ) (x(p, st ) − x̂t ), (3)
∂p ∂p ∂st ∂p

where all the partial derivatives are evaluated at (p, st ). In the

∂x
equation above, ∂p represents the change in the marker’s position
when the state of the sub-assembly remains unaltered. For instance,
Figure 5: The trajectory (gray polyline) traced out by a marker changing the location of the attachment point in the linkage struc-
point (red dot) to approximate a target curve (red polyline). A ture shown in Fig 5 (left) does not affect the evolution of the state of
marker point can either be located on the driving mechanism (left) the sub-assembly, but results in a different curve being traced out.
or on a part of the character that is driven by a mechanism (right). The term ∂s∂x
t
is evaluated analytically, and the remaining term, ∂s∂p
t
,
represents the change in the state of the assembly as its parameters
change. This term cannot be evaluated analytically because the sub-
old. Unfortunately, fast Poisson-disk sampling methods [Bridson assemblies we optimize can be arbitrarily complex, and in general
2007] cannot be applied in our setting: while it easy to satisfy the there is no closed-form solution describing their motion. Finite dif-
minimum distance criterion in parameter space, this is not the case ferences can be used to estimate the derivatives, but this requires Eq.
in metric space since the mapping between the parameters of the (1) to be solved O(|p|) times to a high degree of accuracy, which
mechanism and its generated motion curve is non-trivial. is too computationally demanding for interactive applications. In-
stead, we exploit the implicit relationship between the parameters
We therefore generate the samples using a simple recursive process. of the sub-assembly and the state configuration that results in all
For each accepted sample, we generate a number of new samples by constraints being satisfied, i.e., C(p, st (p)) = 0. According to the
uniformly probing the parameter space around the current sample’s Implicit Function Theorem,
location. For each generated sample, we compute the correspond-
ing curve, and using the distance metric described in Sec. 5, we
∂st ∂C −1 ∂C
check whether it is too close to any of the existing samples in the =− . (4)
database. If this is the case, we reject the sample, otherwise it is ∂p ∂st ∂p
added to the database. We note that it is possible that some regions
in the parameter space lead to infeasible configurations. As a re- We estimate ∂C ∂p
using finite differences. This requires us to in-
sult, although our sampling strategy is very effective for exploring stantiate sub-assemblies with different parameters p e and compute
connected regions of a mechanism’s parameter space, we have no the value of the constraints C(e p, st (p)). We note that this does
guarantees that it exhaustively explores the entire space of feasible not require Eq. (1) to be minimized, and its computational cost
parameters. ∂C
is therefore negligible. The matrix ∂s t
is computed analytically.
As noted in Sec. 3, our mechanical assemblies can have more
4.2 Continuous parameter optimization constraints than degrees-of-freedom. Since the additional con-
∂C
straints are redundant however, the matrix ∂s t
still has full col-
After selecting an appropriate driving mechanism from the umn rank, and in such cases, we instead use the pseudo-inverse
database, its parameters need to be further fine-tuned, and we use ∂C + ∂C T ∂C −1 ∂C T
= ( ∂s ) ∂st .
a continuous optimization method for this purpose. We assume ∂st t ∂st

that a marker point specified on the character should follow a user- We minimize Eq. (2) by evaluating the matching objective and its
provided curve as closely as possible. The marker can either coin- gradient at a discrete number of points (i.e., t values). To improve
cide with the attachment point of the driving mechanism, or it can convergence rates we use the BFGS quasi-Newton method to esti-
be located at an arbitrary point on the character, as illustrated in mate the approximate Hessian ∂p ∂ ∂F
[Nocedal and Wright 2006].
∂p
Fig. 5. To optimize the resulting motion, we minimize the follow-
ing objective as a function of the mechanisms’s parameters p: 4.3 Timing control via non-circular gears
Z 1
1 Controlling the timing of motions is an integral part of character
F = (x(p, st ) − x̂t )T (x(p, st ) − x̂t )dt, (2) animation. We therefore also allow users to explicitly control the
2 t=0
timing of the characters’ motions. This is accomplished through
where t is the phase of the Input Driver, such that when t = 1 a full the use of non-circular gears, which are always used in pairs: a
cycle of the animation has been completed. x(p, st ) and x̂t denote constant angular velocity input signal applied to the first gear gets
the position of the marker point and its target position at phase t. transformed to variable angular velocity for the second gear. The
The state of the assembly at phase t, st , is computed by minimizing phase-dependent ratio of angular velocities of the two gears de-
Eq. 1 after instantiating the mechanism with the current set of pa- pends on the shape of their profiles, and in particular, on the ra-
rameters p. As the parameters of the mechanisms directly affect the tio of the gears’ radii at the point where they mesh. Asking users
connections between the different components, for the remainder of to directly provide the phase-dependent ratio of angular velocities,
this section we write the system constraints as an explicit function however, is not intuitive, as the integral of this ratio needs to re-
of the parameters and the state variables i.e. C(p, st ). main constant (otherwise one gear rotates more than the other over
a full cycle). Instead, we allow users to define the relative phase
Note that in Eq. (2), we use a point-based metric to measure the profile between the two gears, as illustrated in Fig 6 (left). This is
similarity between the input and output motion curves, rather than accomplished by allowing the user to set samples (α1i , α2i ) that
 Let ci and cj denote closed, planar polygonal curves and let fi
and fj denote their corresponding feature vectors. We define the
distance metric as
p
d(ci , cj ) = ||fi − fj ||A = (fi − fj )T A(fi − fj ) ,

In order for d to be a proper metric, i.e., satisfying positivity and the

triangle-inequality, the matrix A has to be positive semi-definite.
For simplicity, we consider only diagonal A such that this condition
Figure 6: Non-circular gears control the timing of the motion. reduces to Aii ≥ 0.

5.1 Curve Features

specify the phase of the second gear as a function of the phase of
the first gear. Two additional sample points, (0, 0) and (1, 1) are We do not want the metric to be sensitive to absolute position,
automatically added to ensure that a full revolution of the first gear size, and orientation of the curve in world-space since we can
corresponds to a full revolution of the second gear. These sample always translate, scale, and rotate the entire sub-assembly as re-
points define the function f (α) used by the Phase Connection, as quired. However, we must capture these quantities relative to the
described in Sec. 3. In particular, we compute f (α) using Radial sub-assembly, since design constraints such as the location of the
Basis Function interpolation, such that f (α1i ) = α2i , ∀i with the gear box dictate how the sub-assembly has to be positioned, scaled
additional constraints f 0 (0) = f 0 (1), f 00 (0) = f 00 (1). These con- and oriented relative to an input sketch of the user.
straints ensure that the ratio of angular velocities varies smoothly.
The interpolation uses thin plate splines as basis functions, and a Before computing the actual features of a curve, we perform
low degree polynomial to accommodate the additional constraints. a number of pre-processing and normalization steps. We start
by re-sampling the curve using constant length strides along
its original segments. Timing information is discarded at
The phase profile function f (α) is used to simulate the mechanical this point, since we can explicitly control the velocity pro-
assemblies, and also to generate the geometry of the non-circular file as a post process using non-circular gears (see Sec. 4.3).
gears. Let r1 (α) and r2 (f (α)) represent the non-constant radii that In order to normalize the curve with
define the pitch surfaces of the two non-circular gears. Since the respect to global transformations, we
two gears are assumed not to move relative to each other, r1 (α) + translate it such that the anchor
r2 (f (α)) = a, where a is the distance between the two gears. In xanchor of its generating mechanism
∂f
addition, the relative angular velocity ∂α (α) of the two gears is lies at the origin. Next, we compute
given by the ratio of the radii at the meshing point r1 (α)/r2 (f (α)). the two unit-length principal direc-
These two equations are sufficient to compute the radii of the two tions vmax and vmin of its points us-
gears for any α, and therefore their pitch surfaces. The teeth of the ing principal component analysis. Fi-
gears are added procedurally, orthogonal to the pitch surfaces. nally, we extract the lengths lmax and
lmin of the curve along the principal
directions and normalize its scale by
5 Curve Metric multiplying by 1/lmax .
We compute all features of the curve in this normalized setting.
The driving mechanisms described in Sec. 4 trace out planar, closed
Let ci,j denote the np vertices of ci and define edges vectors and
curves that we represent by polygons. In order to find the driv-
directors as ej = ci,j − ci,j−1 , respectively tj = ej /||ej ||.
ing mechanism from our library that can best approximate a user-
With the first three features, we capturePthe geometric character-
provided input curve, we must measure the distance, or similarity, np
between such curves. As an obvious candidate, the Hausdorff dis-
istics of the curve: its length (fi,1 = j ||ej ||), area (fi,2 =
1
P n p
tance is simple to compute, but it does not consider the course of 2 j ci,j × ci,j−1 ), and ellipticity (fi,3 = lmin /lmax ). We fur-
the curve, which can lead to unexpected similarities. A metric that thermore extract the position of the curve relative to its generating
is frequently used in the context of handwriting recognition is the mechanism as fi,4 = ||d||, where d = xanchor − xcom is the vec-
Fréchet distance, which is also referred to as dog-walking metric tor between the anchor of the driving mechanism and the center of
[Alt and Godau 1995]: it is the length of the shortest leash nec- mass of the curve. The relative orientation of the curve is stored as
essary to connect a dogwalker and its dog as they progress along fi,5 = arcsin(||d/||d|| × vmax ||). Finally, we use the number of
the two curves, possibly at different rates but without backtracking. intersections between non-neighbor segments as feature fi,6 .
While the discrete Fréchet distance [Eiter and Mannila 1994] can
While the above features capture the geometric characteristics of a
be computed in (sub-)quadratic time with respect to the number of
given curve in an integral sense, we would also like to distinguish
points in the polygons, our experiments showed that the resulting
curves based on local variations. To this end, we use two additional
matching quality is not always satisfying (see Sec. 7.1).
indicators that are computed for pairs of curves: the L2 norm of the
vertex-wise difference in position and curvature. Since we cannot
It is generally unlikely that a single parameter metric is able to re- assume that the starting points of the two curves are in correspon-
flect the similarity as perceived by the user across a broad range dence, we use the minimum distance values obtained by offsetting
of curves. On the other hand, manually selecting coefficients the starting index of one of the curves and define
for multi-parameter metrics is very difficult. We therefore take
a different, more user-centered approach: we start by converting 1 X
curves into feature vectors that capture salient characteristics such d2pos (ci , cj ) = min ||ci,k − cj,k+l ||2 (5)
np l
as length, curvature, area and so forth. We then formulate our met- k
ric as a bilinear form on differences in feature vectors and optimize
X
d2angle (ci , cj ) = min (κi,k − κj,k+l )2 , (6)
its coefficients using user-generated data. l
k
 2t
j−1 ×t j
where κi,k = 1+t j ·tj−1
is the discrete curvature at vertex k (see the mechanisms have to be connected to an input driver using inter-
[Bergou et al. 2010]). We evaluate these indicators whenever the mediate gears (Sec. 6.1), the assembly needs to be edited to ensure
distance between two curves has to be determined and add their there are no collisions between the various moving parts (Sec. 6.2),
square roots as additional entries to (fi − fj ). Note that, unlike and a support structure that holds all components in place has to be
the other features, (5) and (6) require the curves to have the same designed (Sec. 6.3).
number of vertices. If this is not the case, we upsample the coarser
one.
6.1 Gear Optimization
5.2 Metric Training
Each of the driving mechanisms of the assembly has to be con-
It is not obvious how to choose the coefficients of the feature-based nected to an input driver, which can be a gear connected to a ser-
curve metric in order to best reflect a desired notion of similarity. vomotor, a handle operated by the user, or a wheel in contact with
We therefore automatically compute the coefficients that best ex- the ground. Each type of driving mechanism has one or more driv-
plain a given set of interactively generated training data. The train- ing gears. The location and angular velocity of these driving gears
ing data consists of a set S of pairs of similar curves as well as a set are fixed during the mechanism design step, but other parameters
D of dissimilar curves. Using the formulation of Xing et al. [2002] such as their radii can vary. For simplicity, we assume that the driv-
as a basis, we compute the coefficients by solving the following ing gears as well as the input driver have the same axis of rotation,
constrained optimization problem which essentially reduces the problem to 2.5 dimensions. When
this assumption does not hold, we split the path between driving
2 gears and input drivers with bevel gears. Given this input data, we
P P
minA (i,j)∈S ||fi − fj ||A + kreg Ai (7)
seek to find a set of intermediate gears that connect pairs of existing
s.t. ||fk − fl ||A ≥ γ, ∀(k, l) ∈ D and Ai ≥ 0 (8) gears, as selected by the user. This problem consists of two parts:
first, we have to determine the gear layout, i.e., the number of gears
The objective term (7) asks for small coefficients Ai (kreg is a and how they connect to each other. Second, we must compute the
small regularizing scalar) that minimize the distance between simi- parameters of the gears that satisfy a set of constraints (meshing of
lar curves. The inequality constraints (8) require dissimilar pairs to connected gears, desired angular velocities, no intersections), while
have a distance greater than a given threshold value γ, which for all minimizing an objective function that measures the quality of the
our experiments is set to 1. resulting gear train.
The choice of training data determines the coefficients and thus the
behavior of the metric. Since it is difficult for the user to select
good data without getting feedback on its quality, we use an iter- Gear Layout Generation Automatically computing a gear layout
ative training scheme. During an initial stage, we ask the user to subject to given optimality conditions (e.g., minimum number of
select a few (e.g., five) similar and dissimilar pairs from sets of gears or shafts) is difficult due the combinatorial nature of the prob-
nine randomly generated curves. We then compute a first guess for lem. Each time such a layout is generated, it has to be tested using
the coefficients from this training data by solving the optimization continuous optimization and it is unclear how to exchange feedback
problem (7-8) using sequential quadratic programming (SQP). In between these disconnected parts. Fortunately, it is a rather simple
the second stage of the training process, we randomly generate pairs matter for the user to create the gear layout interactively: we let the
of curves and categorize them into four similarity classes (’similar’, user select pairs of gears that should be connected to each other.
’probably similar’, ’probably different’ and ’different’) according Depending on the relative location of the gears (in one plane, on
to their current distance. The pairs are then presented to the user the same axis or neither), we generate parallel and sequential gear-
three at a time with a color-coding indicating their similarity class. to-gear connections (Fig. 7). Gears on the same axis are connected
Apart from providing feedback on the current behavior of the met- in parallel, gears in the same plane are connected with an auto-
ric, we also allow the user to flag any of the pairs as ’similar’ or matically determined number of in-between gears depending on the
’different’, which leads to pairs being added to the list of objective signs of the angular velocities, the distance between them and their
terms, respectively constraints. The metric coefficients are then re- radii. The third case is treated with both a parallel and a sequen-
computed using the updated lists. In addition to adding new pairs, tial connection. These connections are then transformed to a set of
we also ask the user to reconfirm or dismiss pairs from the lists that constraints and objectives for the continuous optimization scheme.
belong to the two uncertain categories. The result of the optimization is added to the mechanical assem-
bly, and the parameters of all the gears that were involved in the
The system’s response to user input is virtually instantaneous as optimization process are treated as hard constraints for subsequent
solving the SQP takes only a few milliseconds even with more than steps. See also the accompanying video for a visual demonstration
a hundred pairs of curves in the lists. In our experiments, we noticed of this process. Although this way of iteratively connecting pairs of
that the training scheme converges quite fast: after 30-40 iterations, gears can be more restrictive than connecting all the existing gears
the metric typically produces stable results that are consistent with at once, our experiments show that it is a very intuitive process that
the perceived similarity of the user. We provide an analysis of the leads to fast results.
matching quality for our metric in Sec. 7.1.

6 Character Finishing
Once the driving mechanisms that generate the desired motion of
the character are designed, three more steps have to be performed
before the character can be manufactured: the mechanisms have to
be connected to an input driver using intermediate gears (Sec. 6.1),
the assembly needs to be edited to ensure there are no collisions be- Figure 7: Types of connections generated during interactive gear
tween the various moving parts (Sec. 6.2), and a support structure layout: sequential (yellow), parallel (red), and combined (green).
that holds all components in place has to be designed (Sec. 6.3).
Gear Parameter Optimization The gear layout step provides us
with a number of ng interconnected gears, each of which we assign
five degrees of freedom pi = (x, y, z, r, ω)T , where x, y and z
are the gear’s coordinates, r is its radius, and ω its angular velocity. A  
Without loss of generality, we assume that the z-axis is normal to
the surface of the gears. We convert the connections between the
B  
gears into a set of equality constraints Ci and inequality constraints
Ii , as well as a number of ng objective terms Fi .
A sequential connection between two gears gi and gj is defined by
three constraints that ensure the gears mesh properly:
A   B  
depth
Cseq (pi , pj ) = zi − zj
ω
Cseq (pi , pj ) = ri ωi + rj ωj
C  
mesh
p
Cseq (pi , pj ) = (xj − xi )2 + (yj − yi )2 − (ri + rj ) .

The first constraint requires the gears to lie in the same plane (one Figure 8: Left: component placement in different planes to remove
could also take into account the thickness of the gears by formulat- collisions. Right: types of collisions that can occur between com-
ing corresponding inequality constraints instead). The second con- ponents.
straint requires that the relative angular velocities of the two gears
is correct, whereas the third one ensures that the distance between
them is equal to the sum of their radii. We model parallel gear con-
nections with four constraints, is very challenging, and it would require a close integration with
the mechanism design phase. While conceptually clean, this ap-
y
Cpar (pi , pj ) = yi − yj , x
Cpar (pi , pj ) = xi − xj proach would prevent us from treating sub-assemblies in isolation,
ω thus rendering the optimization process significantly more com-
Cpar (pi , pj ) = ωi − ωj plex. For assemblies where all the components move along parallel
depth
Ipar (pi , pj ) = zj − zi − h planes, and many of our results fall in this category, we can how-
ever address the intersection problem automatically by offsetting
each component along the direction normal to this motion plane.
The first two ensure that the gears are aligned correctly, the third
one asks that they have the same angular velocity, since both gears Overview We aim to place each component in a different plane,
are welded to the same support shaft, and the last constraint requires such that as the animation is playing, the assembly remains
that the gears should not be closer than the average gear thickness collision-free. We discretize the 3D space occupied by the assembly
h. In addition to these connections, we create non-intersection con- into layers that are parallel to the plane along which the components
straints for all pairs of gears that are not connected. To this end, are moving (Fig. 8, left), and we assign each component a layer (or
we convert the distance constraint from above to inequality form plane) index. We start the process by checking for collisions be-
and add a small negative safety threshold in order to prevent gears tween each pair of components (gears, linkages, and body parts of
from being too close to each other. We switch these constraints on the character) that were assigned the same layer index. Note that we
whenever two gears are closer than the gear thickness in the z di- do not need to deal with gear-gear collisions, since we apply non-
rection. Finally, we introduce inequality constraints in order to en- intersection constraints to all pairs of gears in the gear parameter
force a minimum admissible gear radius as well as unary equality optimization stage of the pipeline (Sec. 6.1). We perform standard
constraints that fix the parameters of gears that have been optimized collision checks between the triangle meshes of the components,
by previous user operations. after projecting them onto the motion plane. The two basic types
Given these constraints, we compute optimal gear parameters p by of collisions that may occur are shown in Fig. 8 (right): on the
solving the constraint optimization problem top, components A and B are detected as colliding; on the bot-
tom, component C is detected as colliding with a pin that connects
ng
X components A and B. For the first example, components A and B
p = arg min ((r̃i − ritarget )2 + kreg ||p̃i − p̄i ||2 ) (9) cannot be assigned to the same layer, while for the second exam-
p̃
i ple, component C cannot lie in a layer between those assigned to A
s.t. Ci (p̃) = 0 and Ii (p̃) ≥ 0 , and B. We solve the layer assignment problem using boolean op-
timization, a variant of discrete constrained optimization, with the
where ritarget denotes a user-provided (or otherwise automatically non-intersection conditions as constraints.
inferred) desired radius for gear i, kreg is a small regularizer coeffi-
cient, and p̄ represents the set of initial parameters. Since some of Algorithm With n components and m layers, there are mn pos-
the constraints are nonlinear, we solve (9) using a standard sequen- sible layer assignments, since each component can be placed in any
tial quadratic programming solver. of the layers. Even for relatively small problems, brute force ap-
proaches are intractable. One option for solving this problem is
6.2 Collision-free Layering for Planar Motions with integer programming, which can work quite well especially
if the problem is linear. Some of our constraints, however, are
Up to this point, no measures were taken to prevent different mov- non-linear. The non-linearity is due to the second type of con-
ing parts of the assembly from intersecting with each other. Our straint shown in Fig. 8, which states that a variable cannot lie be-
framework allows users to intuitively edit the assembly by indepen- tween two other variables, a disjunctive constraint expressed as
dently moving the driving mechanisms if intersections are detected. (C < A) ∨ (B < C). We therefore pose this as a constraint satis-
However, it would be desirable to also provide an automatic solu- faction problem (CSP) for which there are efficient, robust solvers
tion to this problem. For general three-dimensional motions, this for the scale of problems that we are interested in.
The CSP formulation assumes that we already know the number video, and they are summarized in Table 1. Before presenting our
of discrete layers m. Since this number is typically not known a results, we first validate some important design choices and discuss
priori, we seek to find the minimum number of layers such that all alternative approaches.
components can be laid out without collisions. We start by setting
m = 4 and increment until we obtain feasible solutions. Usually, 7.1 Validation
there are multiple solutions once a feasible m is found. By re-
peatedly running the constraint solver, we obtain a set of feasible Metric Comparison In order to compare the matching quality
solutions, and select the one that minimizes the total length of the of our metric to alternative measures, we created a set of hand-
pins connecting the components of the assembly. We then estimate drawn curves and retrieved the closest one for each of them from
the thickness of each layer as the maximum thickness of the com- a database containing 1000 randomly generated samples each for
ponents assigned to it and offset each component to the center of a four- and a five-bar linkage. Fig. 9 shows the best matching
the layer it was assigned to. curves (in red) for three different metrics: our feature-based metric
The worst-case running time for the CSP solver is exponential. with optimized coefficients (first row), the discrete Fréchet distance
However, even for our largest examples, which consists of close [Eiter and Mannila 1994] (second row) and our feature-based met-
to 100 components and more than 10 layers, an off-the-shelf CSP ric with all coefficients set to 1.0. While the two alternatives found
solver (Walksat [Selman et al. 1993]) using default parameters was reasonable curves in many cases, some of the matches (e.g., row
able to generate 1000 random solutions in less than 30 seconds. 2, column 2 or row 3, column 4) are clearly off. Although rank-
For comparison, a naive random search was unable to find a single ing the perceived similarity is difficult, our optimized metric yields
solution within a reasonable amount of time (several hours). well-matching curves in all cases.

6.3 Support Structure Driving Mechanisms Generation and Optimization We use

four main types of driving mechanisms, as illustrated in Fig. 4. The
At this point in the design process, the components of the assembly two mechanisms on the left columns are driven by two gears each.
are interconnected and non-intersecting, but they are still floating Altering the relative angular velocity of the two gears also affects
in space. As a last step, a support structure is designed to ensure the output motions. To ensure that the period of the output mo-
that the support shafts needed by the various components in the tion is the same as for the input driver, we create four variations of
assembly are held in place. In many cases, the support structure is each of these assemblies, where the ratio of the angular velocities
subject to aesthetic considerations and is thus best designed by the of the two gears are fixed to −2, −1, 1 and 2 respectively. The two
user. Whenever this is not the case, we use a simple algorithm to mechanism types on the right are much simpler, and it is therefore
assist the user in the design of the support. not required to perform the parameter exploration for them. Rather,
when needed, we proceed straight to the continuous optimization
We start by computing a bounding box that contains all components stage. Consequently, our motion database is built using 8 distinct
of the assembly except for the character. We voxelize this volume mechanism types. For every type of mechanism we store up to 3000
on a regular grid and flag as occupied all voxels that lie inside the representative motions. The parameter space exploration took be-
volume swept by the individual components during a full cycle of tween 0.5 and 2.5 hours until no further samples could be found.
animation. The result of this process is a set of non-occupied vox- Even with a simple linear search, the database retrieval time is neg-
els that define regions where supporting shafts can be inserted and ligible. Using the approach discussed in Sec. 4.2 to compute gradi-
grounded without interfering with the other moving objects. This ents is 20 to 30 times faster than using finite differences, depending
information is then presented to the user, who can select planar on the number of parameters of the assembly. As a result, the con-
slices from the non-occupied voxel grid in order to instantiate sup- tinuous optimization process is interactive, especially when using
port walls. Once such a wall is created, we automatically connect the initial parameter values obtained by querying the database.
to it all the support shafts that can reach it without passing through
occupied voxels of the grid. During this process, we provide feed-
7.2 Summary of Results
back to the user regarding which shafts still require support. Once
all shafts are connected, the assembly is ready for manufacturing.
Designing the motions and the corresponding driving mechanisms
for the mechanical characters presented in this paper took less than
6.4 Fabrication half an hour on average. The characters that were 3D printed in
one piece (Cyber Tiger, Clocky, DrillR) were ready for fabrication
We use rapid manufacturing technology to create physical proto- within one day, with most of the additional time being spent on
types of our mechanical characters. Many examples exhibit a lay- generating the support structures. 3D Printing took up to 42 hours,
ered structure that allows easy decomposition of the mechanical and removing the support material up to two hours. The characters
components. In such cases, it is most efficient in terms of material that were created component-by-component (Pushing Man, EMA,
cost and fabrication time to fabricate all components individually Bernie), required some additional manual work to prepare for man-
and assemble the character afterwards. Another advantage of this ufacturing and to assemble, but printing times were significantly
layer-wise fabrication is that it lends itself to less expensive man- lower.
ufacturing devices such as laser cutters or services such as Shape-
ways. Characters with internal driving mechanisms can be quite The simplest of our examples is Pushing Man (Fig. 10), a character
cumbersome to assemble, which is why we manufacture these ex- inspired by the Sisyphus automata model [Johnson 2010]. Its mo-
amples in one piece using a 3D printer. tion is generated by three driving mechanisms, one for each leg and
one for the chest. Despite the simplicity of the design and the rela-
tively small number of driving mechanisms, the resulting motion is
7 Discussion and Results fluid and compelling.
To demonstrate the versatility of our framework, we designed ten Our design interface makes it easy for non-expert users to create
animated mechanical characters, many of which we also manufac- mechanical characters of higher complexity. For instance, the EMA
tured. These results are presented in detail in the accompanying characters show an example of different animations being created
Figure 9: Comparing the quality of curve matching for different metrics on a set of examples curves (black). Top row: feature-based metric
with optimized coefficients, middle row: discrete Fréchet distance, bottom row: feature-based metric with all coefficients set to 1.0.

for the same character. Our interface supports this style of motion
design by providing the user with intuitive ways to select driving
mechanisms that trace out desired motion curves and to adjust the
velocity profile along these curves. The latter is essential for creat-
ing the characteristic motion of EMA gallop, which our framework
implements using non-circular gears that directly control the timing
of the foot-falls.
Even when the individual driving mechanisms are restricted to pla-
nar trajectories, users can create compelling 3D motions by com-
bining components that operate in different planes. An example of
this can be seen in the side-to-side tail and body sway of the TRex
character shown in Fig. 11. Moreover, if the types of driving mech-
anisms available in the input library are capable of generating non-
planar motions, they can also be used within our framework. How-
ever, to fully exploit the pipeline we present, two changes would be
required: the curve distance metric (Sec. 5) should be extended to
operate on 3D curves, and the automatic method we use to ensure
that components do not collide with each other (Sec. 6.2) should Figure 10: PushingMan.
be revised to handle arbitrary 3D motions. The rest of our pipeline
does not need to be altered, and we used non-planar driving mech-
anisms to create the Scorpio character (Fig. 15). For this example
we optimized the dimensions of the leg concurrently with the other
parameters of the driving mechanism in order to obtain a desired,
non-planar trajectory. This mechanism has 23 parameters in to-
tal, but optimizing it took only about 2 minutes. We instantiated
the optimized leg six times and created a walking animation us-
ing physics-based simulation on the resulting mechanical assembly
(see accompanying video).
Many of our characters such as EMA, Pushing Man and TRex have
external gear boxes that are located below the characters. However,
our framework also allows the user to design mechanical assemblies
in which the gear boxes are internal to the character, as evidenced
by the Froggy and Clocky (Fig. 14, right) examples. Integrating
the gear box within the character allowed us to design free-roaming
examples such as Bernie (Fig. 12) and DrillR (Fig. 1, right).

8 Limitations and Future work

We have presented an interactive design system that allows non-
expert users to create animated mechanical characters. Our aim was Figure 11: TRex: By combining planar mechanisms that operate in
to automate this design process as much as possible, while giving different planes, we can create compelling 3D character motions.
users sufficient artistic freedom. As evidenced by the wide range of
characters that we designed, our method achieves this goal. Nev-
ertheless, many exciting avenues for future work remain. First, the
quality of the motions we generate directly depends on the types of
 Model #Driving Mechanisms #Components #Connections
Pushing Man 3 24 37
EMA Walk 5 59 74
EMA Gallop 6 93 122
Bernie 4 40 60
CyberTooth 5 54 73
Drill-R 3 32 45
Clocky 5 32 48
Froggy 4 43 47
T-Rex 5 60 67
Scorpio 8 111 117

Table 1: Statistics for the presented examples.

Figure 12: Bernie. A DC motor and a battery pack were added
to the body to make the character walk on its own (with strings
attached for support).

Figure 15: Scorpio character, showing 3D motion. Left: Leg and

driving mechanism in isolation. Right: Simulated character walk-
ing.

mechanisms that are available for use. Although we were able to

generate a range of compelling examples, the types of mechanisms
in our library ultimately limit the space of possible motions. In the
future, we plan to investigate methods that automatically extract
these building blocks from existing mechanical assemblies.

We plan to also incorporate structural analysis when designing me-

chanical characters in order to ensure that the resulting assemblies
are lightweight, yet robust. To physically manufacture the charac-
ters that are shown in this paper, we used an empirical process to
determine, for instance, the radius of the support shafts or the thick-
Figure 13: EMA Walk and EMA Gallop. For the galloping motion ness of the linkages, such that they deformed as little as possible as
we use non-circular gears to control the timing of the foot-falls. the animation was played out. We believe that this process could
be automated. In addition, for this work, we employed non-circular
gears to explicitly control the timing of the animations. In the fu-
ture we plan to also use them to reduce torque fluctuations when
driving the assemblies [Yao and Yan 2003]. Relatedly, we would
like to incorporate additional optimization objectives that minimize
the net force required to drive the assemblies.

Our system detects and reports failures at various stages in the de-
sign pipeline, for example, if the assembly is over or under con-
strained, or if there are collisions between the components of a non-
planar assembly as the animation is playing. The user is currently
expected to manually edit the assembly in order to fix these prob-
lems. An interesting direction for future work is to address such
problems automatically, or to provide helpful hints to guide the user
in addressing them in an optimal manner.

One of the most basic limitations of our research is the restriction

to cyclic motions, which leads to another interesting area for fu-
ture work. By employing physical systems that can switch between
multiple mechanism sets or different drivers, we believe we can
Figure 14: Froggy and Clocky. generate motions that do not simply repeat every cycle. Finally,
although our mechanical characters operate without environmental
awareness, our research brings us one step closer to the rapid design
and manufacturing of customized robots that sense and interact with J OHNSON , D., 2010. Sisyphus testing shoes.
their environments in order to carry out complex tasks. http://www.youtube.com/watch?v=Rh-4zSbmhFU (Accessed
on April 8, 2013).
Acknowledgments L AU , M., O HGAWARA , A., M ITANI , J., AND I GARASHI , T. 2011.
Converting 3D furniture models to fabricatable parts and connec-
We thank the anonymous reviewers for their helpful comments and tors. In Proc. of ACM SIGGRAPH ’11.
Maurizio Nitti for modeling many of the characters we used for this
work. M ALZBENDER , T., S AMADANI , R., S CHER , S., C RUME , A.,
D UNN , D., AND DAVIS , J. 2012. Printing reflectance functions.
ACM Trans. Graph. 31, 3 (June), 20:1–20:11.
References
M ARKS , J., A NDALMAN , B., B EARDSLEY, P. A., F REEMAN , W.,
A LT, H., AND G ODAU , M. 1995. Computing the fréchet distance G IBSON , S., H ODGINS , J. K., K ANG , T., M IRTICH , B., P FIS -
between two polygonal curves. International Journal of Compu- TER , H., RUML , W., RYALL , K., S EIMS , J., AND S HIEBER ,
tational Geometry & Applications 5, 01 & 02, 75–91. S. 1997. Design galleries: A general approach to setting pa-
rameters for computer graphics and animation. In Proc. of ACM
B ÄCHER , M., B ICKEL , B., JAMES , D. L., AND P FISTER , H. SIGGRAPH ’97, 389–400.
2012. Fabricating articulated characters from skinned meshes.
In Proc. of ACM SIGGRAPH ’12. M ITRA , N. J., YANG , Y.-L., YAN , D.-M., L I , W., AND
AGRAWALA , M. 2010. Illustrating how mechanical assemblies
B ERGOU , M., AUDOLY, B., VOUGA , E., WARDETZKY, M., AND work. In Proc. of ACM SIGGRAPH ’10.
G RINSPUN , E. 2010. Discrete viscous threads. In Proc. of ACM
SIGGRAPH ’10. M ORI , Y., AND I GARASHI , T. 2007. Plushie: An interactive design
system for plush toys. In Proc. of ACM SIGGRAPH ’07.
B ICKEL , B., B ÄCHER , M., OTADUY, M. A., L EE , H. R., P FIS -
TER , H., G ROSS , M., AND M ATUSIK , W. 2010. Design and N OCEDAL , J., AND W RIGHT, S. J. 2006. Numerical Optimization.
fabrication of materials with desired deformation behavior. In Springer.
Proc. of ACM SIGGRAPH ’10. P EPPE , R. 2002. Automata and Mechanical Toys. Crowood Press.
B RIDSON , R. 2007. Fast poisson disk sampling in arbitrary dimen- S CLATER , N., AND C HIRONIS , N. 2001. Mechanisms and me-
sions. In Proc. of ACM SIGGRAPH ’07. chanical devices sourcebook. McGraw-Hill.
C ABRERA , J., S IMON , A., AND P RADO , M. 2002. Optimal syn- S ELMAN , B., K AUTZ , H., C OHEN , B., ET AL . 1993. Local search
thesis of mechanisms with genetic algorithms. Mechanism and strategies for satisfiability testing. Cliques, coloring, and satis-
machine theory 37, 10, 1165–1177. fiability: Second DIMACS implementation challenge 26, 521–
C AL Ì , J., C ALIAN , D., A MATI , C., K LEINBERGER , R., S TEED , 532.
A., K AUTZ , J., AND W EYRICH , T. 2012. 3D-printing of non- S TAVA , O., VANEK , J., B ENES , B., C ARR , N., AND M ĚCH , R.
assembly, articulated models. In Proc. of ACM SIGGRAPH Asia 2012. Stress relief: improving structural strength of 3d printable
’12. objects. In Proc. of ACM SIGGRAPH ’12.
C HIOU , S., AND S RIDHAR , K. 1999. Automated conceptual de- S UBRAMANIAN , D., AND WANG , C. 1995. Kinematic synthesis
sign of mechanisms. Mechanism and Machine Theory 34, 3, with configuration spaces. Research in Engineering Design 7, 3,
467–495. 193–213.
D EMARSIN , K., VANDERSTRAETEN , D., VOLODINE , T., AND U METANI , N., I GARASHI , T., AND M ITRA , N. J. 2012. Guided
ROOSE , D. 2007. Detection of closed sharp edges in point exploration of physically valid shapes for furniture design. In
clouds using normal estimation and graph theory. Computer- Proc. of ACM SIGGRAPH ’12.
Aided Design 39, 4, 276–283.
W ESLEY, M., L OZANO -P EREZ , T., L IEBERMAN , L., L AVIN , M.,
D ONG , Y., WANG , J., P ELLACINI , F., T ONG , X., AND G UO , B. AND G ROSSMAN , D. 1980. A geometric modeling system for
2010. Fabricating spatially-varying subsurface scattering. In automated mechanical assembly. IBM Journal of Research and
Proc. of ACM SIGGRAPH ’10. Development 24, 1, 64–74.
E ITER , T., AND M ANNILA , H. 1994. Computing discrete fréchet W EYRICH , T., P EERS , P., M ATUSIK , W., AND RUSINKIEWICZ ,
distance. Tech. Rep. CD-TR 94/64, Christian Doppler Labor für S. 2009. Fabricating microgeometry for custom surface re-
Expertensyteme, TU Wien. flectance. In Proc. of ACM SIGGRAPH ’09.
E ITZ , M., R ICHTER , R., B OUBEKEUR , T., H ILDEBRAND , K., X ING , E., N G , A., J ORDAN , M., AND RUSSELL , S. 2002. Dis-
AND A LEXA , M. 2012. Sketch-based shape retrieval. In Proc. tance metric learning, with application to clustering with side-
of ACM SIGGRAPH ’12. information. Advances in neural information processing systems
15, 505–512.
F REUDENSTEIN , F. 1954. Design of Four-link Mechanisms. Ph.
D. Thesis, Columbia University, USA. YAO , Y., AND YAN , H. 2003. A new method for torque balancing
of planar linkages using non-circular gears. Proceedings of the
G UI , J., AND M ÄNTYL Ä , M. 1994. Functional understanding of Institution of Mechanical Engineers, Part C: Journal of Mechan-
assembly modelling. Computer-Aided Design 26, 6, 435–451. ical Engineering Science 217, 5, 495–503.
H ASAN , M., F UCHS , M., M ATUSIK , W., P FISTER , H., AND Z HU , L., X U , W., S NYDER , J., L IU , Y., WANG , G., AND G UO ,
RUSINKIEWICZ , S. 2010. Physical reproduction of materi- B. 2012. Motion-guided mechanical toy modeling. In Proc. of
als with specified subsurface scattering. In Proc. of ACM SIG- ACM SIGGRAPH Asia ’12.
GRAPH ’10.