Exact 3D Path Generation via 3D Cam-Linkage Mechanisms
YINGJIE CHENG, University of Science and Technology of China, China and Singapore University of Technology and
Design, Singapore
PENG SONG, Singapore University of Technology and Design, Singapore
YUKUN LU, University of Science and Technology of China, China and Singapore University of Technology and Design,
Singapore
WEN JIE JEREMY CHEW, Singapore University of Technology and Design, Singapore
LIGANG LIU, University of Science and Technology of China, China

Fig. 1. We present a new 3D cam-linkage mechanism that can exactly generate a user-specified 3D path such as the Trefoil Knot curve shown here, driven bya single actuator (indicated by a circular arrow on the left).
Exact 3D path generation is a fundamental problem of designing a mechanism to make a point exactly move along a prescribed 3D path, driven
by a single actuator. Existing mechanisms are insufficient to address thisproblem. Planar linkages and their combinations with gears and/or platecams can only generate 2D paths while 1-DOF spatial linkages can only
generate 3D paths with rather simple shapes. In this paper, we present a
new 3D cam-linkage mechanism, consisting of two 3D cams and five links,
for exactly generating a continuous 3D path. To design a 3D cam-linkage
mechanism, we first model a 3-DOF 5-bar spatial linkage to exactly generate a prescribed 3D path and then reduce the spatial linkage’s DOFs from
3 to 1 by composing the linkage with two 3D cam-follower mechanisms.
Our computational approach optimizes the 3D cam-linkage mechanism’s
topology and geometry to minimize the mechanism’s total weight while
Authors’ addresses: Yingjie Cheng, University of Science and Technology of China,
China, and Singapore University of Technology and Design, Singapore, chengyj@mail.
ustc.edu.cn; Peng Song, Singapore University of Technology and Design, Singapore,
peng_song@sutd.edu.sg; Yukun Lu, University of Science and Technology of China,
China, and Singapore University of Technology and Design, Singapore, lyrik@mail.
ustc.edu.cn; Wen Jie Jeremy Chew, Singapore University of Technology and Design,
Singapore, jeremycwj@gmail.com; Ligang Liu, University of Science and Technology
of China, China, lgliu@ustc.edu.cn.
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
© 2022 Association for Computing Machinery.
0730-0301/2022/12-ART225 $15.00
https://doi.org/10.1145/3550454.3555431

ensuring smooth, collision-free, and singularity-free motion. We show thatour 3D cam-linkage mechanism is able to exactly generate a continuous
3D path with arbitrary shape and a finite number of C 0 points, evaluate
the mechanism’s kinematic performance with 3D printed prototypes, anddemonstrate that the mechanism can be generalized for exact 3D motion
generation.
CCS Concepts: • Computing methodologies → Shape modeling.
Additional Key Words and Phrases: cam-linkage mechanism, 3D path generation, computational design, 3D printing
ACM Reference Format:
Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang
Liu. 2022. Exact 3D Path Generation via 3D Cam-Linkage Mechanisms.
ACM Trans. Graph. 41, 6, Article 225 (December 2022), 13 pages. https://doi.org/10.1145/3550454.3555431

1

INTRODUCTION

Path generation is a fundamental problem of designing a mechanism
to make a point move along a prescribed path [Russell et al. 2014].
Although this task can be achieved by robotic arms, they require
coordinating motion of multiple actuators by using complex control
software. Instead, path generation mechanisms can perform repetitive motion precisely driven by a single actuator, in which motionof the actuated part is embedded in mechanism components. This
single-actuator-driven property brings several advantages including
low-cost, lightweight, and easy to control, making them widely usedin many applications such as machines [Roussel et al. 2018] androbotics [Mannhart et al. 2020].
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

225:2 •Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang Liu• We propose an optimization-based approach to designing a 3D
cam-linkage mechanism for exactly generating a continuous 3D
path while ensuring the mechanism’s fabricability and minimizing
its weight.

Fig. 2. Our 3D cam-linkage mechanism is a composition of (left) 3D camfollower mechanisms [Cheng et al. 2021] and (right) a spatial linkage.

Planar linkages [Bächer et al. 2015], as well as their combinations
with gears [Coros et al. 2013] and planar cams [Mundo et al. 2006]
are the most widely used mechanisms for generating a path on aplanar surface. Besides a planar surface, 3D cam-follower mechanisms enable to generate a path on a cylindrical or a sphericalsurface [Cheng et al. 2021]; see Figure 2 (left). To generate a 3D path,spatial linkages are commonly employed. However, due to the finite
number of design parameters (e.g., joint positions), spatial linkages
driven by a single actuator (i.e., 1-DOF spatial linkages) can only
generate 3D paths with rather simple shapes [Chu and Sun 2010;
Liu et al. 2020; Sun et al. 2012]; see Figure 2 (right).
In this paper, we study mechanisms that can make a point exactly
move along a prescribed 3D path, a problem known as exact 3D pathgeneration. Moreover, we want such mechanisms to be simple andlightweight such that they can be easily deployed into many existing
systems such as machines, vehicles, or robots. As mentioned above,
1-DOF spatial linkages can only generate 3D paths with simple
shapes. Extending the spatial linkage to 3-DOF enables it to exactly
generate a 3D path, yet requires three independent actuators. To
model an exact 3D path generation mechanism, our idea is to firstmodel a 3-DOF spatial linkage to exactly generate a prescribed 3D
path and then to reduce the spatial linkage’s DOFs from 3 to 1 bycomposing the linkage with 3D cam-follower mechanisms sincethese mechanisms are able to convert 1-DOF rotation to arbitrary 2DOF motion [Cheng et al. 2021]. We call our new mechanism 3D camlinkage since it is a composition of 3D cam-follower mechanisms
and a spatial linkage; see Figure 1 for an example.
Given a user-specified 3D path represented as a continuous spacecurve with a finite number of C 0 points, our problem is to modeland design a simple 3D cam-linkage mechanism that can exactly
generate the path. This problem is challenging in three aspects.
First, determining the 3D cam-linkage mechanism’s topology is
non-trivial since there are many different ways to combine 3D camfollower mechanisms with a spatial linkage. Second, the 3D camlinkage mechanism’s end-effector should be able to exactly follow
the 3D path while the whole mechanism’s motion should be smooth,collision-free, and singularity-free. Third, the 3D cam-linkage mechanism should be fabricable and as lightweight as possible.
To address the challenges, we make the following contributions:• We introduce a new 3D cam-linkage mechanism for exact 3D pathgeneration, which only consists of two 3D cams and five links.
• We enumerate all possible topologies of the 3D cam-linkage mechanism, and present a unified method to model the geometry andkinematics for the mechanism with different topologies.
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

We demonstrate that our 3D cam-linkage mechanism is able toexactly generate a continuous 3D path with arbitrary shape and afinite number of C 0 points, and verify its kinematic performancewith 3D printed prototypes. Although we focus on path generationin this paper, we show that our 3D cam-linkage mechanism can begeneralized for accomplishing more complex motion transfer tasks
such as exact rigid body guidance (i.e., exact 3D motion generation).

2

RELATED WORK

Mechanism design. The goal of mechanism design is to construct
a mechanism to transfer an input motion (typically from a motor)
to an output motion that satisfies a set of motion characteristics.
Two typical mechanism design problems are rigid body guidance
and path generation. Rigid body guidance aims to design a mechanism for guiding a rigid body through a series of specified positions and orientations. Researchers in the graphics community
have addressed this problem to design various 3D printable mechanical automata, including mechanical figures that mimic humanmotions [Ceylan et al. 2013], planar mechanical characters [Megaro
et al. 2014], kinetic wire characters [Xu et al. 2018], multi-pose mechanical objects [Nishida et al. 2019], and invertible paradoxic loop
structures [Li et al. 2020]. Rather than focusing on a rigid body,
path generation aims to design a mechanism to make a point movealong a prescribed trajectory. Several computational approaches
and tools have been developed to address the 2D path generation
problem, e.g., for designing mechanical characters [Coros et al. 2013;
Thomaszewski et al. 2014], drawing devices [Roussel et al. 2018],
and walking machines [Bharaj et al. 2015]. When the output motion
is restricted to 1-DOF translation and/or 1-DOF rotation, such as
end-effector motion of mechanical toys [Zhu et al. 2012] and windup toys [Song et al. 2017], there is no specific difference between
rigid body guidance and path generation.
2D path generation. Path generation problem can be classified
as 2D or 3D, depending on whether the prescribed path is planaror spatial. Path generation problem also can be classified as exact
or approximate, depending on whether the mechanism can exactly
generate the prescribed path or not.
The most widely used mechanism for 2D path generation is 1DOF planar linkage due to its simplicity and ease-of-fabrication.
However, due to the finite number of design parameters (e.g., joint
positions), planar linkages alone can only approximate a prescribed
path [Bächer et al. 2015; Pan et al. 2019; Thomaszewski et al. 2014],
or generate a path that exactly passes through a few prescribed 2D
points (e.g., 9 precision points for 4-bar planar linkages [Wampler
et al. 1992]). To address the exact 2D path generation problem,
planar linkages have to be combined with mechanical parts whose
shape is defined by an infinite number of parameters, in particular,
planar cams [Kay and Haws 1975; Mannhart et al. 2020; Mundo
et al. 2006; Singh 1981] or non-circular gears [Mundo et al. 2009].
Besides planar linkages, Cheng et al. [2021] proposed a 3D camfollower mechanism with a ball-move-in-groove joint for exact pathExact 3D Path Generation via 3D Cam-Linkage Mechanisms • 225:3
generation. The mechanism can exactly generate a path not only
on a planar surface, but also on a cylindrical or spherical surface,defined by the follow-support joint.
3D path generation. To generate a 3D path, the most typical way
is to use 1-DOF spatial linkages in which the links can move in the
3D space driven by a single actuator. Similar to their 2D counterparts, these spatial linkages can only approximate a prescribed 3D
path [Chu and Sun 2010; Liu et al. 2020; Sun et al. 2012], or generatea path that exactly passes through a few prescribed 3D points (e.g., 7
precision points for UR-2SS linkages [Chung 2015] and 9 precision
points for RCCC linkages [Bai et al. 2022]). Compared with these
spatial linkages, our 3D cam-linkage mechanism is able to exactly
generate a prescribed continuous 3D path with arbitrary shape anda finite number of C 0 points.
One possible way to generate 3D paths with complex shapes
is to combine spatial linkages with planar cams. Takahashi andOkuno [2018] developed an automaton that can draw user-specified
2D sketches with disconnected segments. The core component of theautomaton is a spatial cam-linkage mechanism that combines 3 RSSR
linkages with 3 planar cams to move a pen along a 3D trajectory
precomputed from the user’s 2D sketch. Although this cam-linkage
mechanism can generate a complicated 3D path, it has a complex
topology with 20 mechanical parts that are spread in the 3D space.
In contrast, our 3D cam-linkage mechanism has three advantages.
First, our mechanism has a simpler topology with 7 mechanicalparts only (i.e., 2 3D cams and 5 links). Second, our mechanism canexactly generate a continuous 3D curve which is taken as a hardconstraint (see Equation 14) in our mechanism design approach
while the design approach in [Takahashi and Okuno 2018] aims
to minimize the pointwise distance between the generated pathand the input curve. Third, our mechanism can be generalized foraccomplishing more complex motion transfer tasks such as exact
3D rigid body guidance (see Figure 15). Compared with [Takahashi
and Okuno 2018], one limitation of our mechanism is fabricability.
Due to the complex geometry of the 3D cams, our mechanism canbe fabricated only by 3D printing with support materials while theplanar cams in [Takahashi and Okuno 2018] can be fabricated byeither support-free 3D printing or laser cutting.

3

PROBLEM AND OVERVIEW

Our problem is to model and design a 3D cam-linkage mechanismthat can exactly generate a user-specified path, driven by a single
actuator. The user-specified path is represented as a continuous
space curve, either open or closed, denoted as R(u), u ∈ [0, 1]. The
input curve R(u) is not necessary to be smooth; i.e., R(u) can have afinite number of C 0 points, denoted as {R(uh )}. In case R(u) is an
open curve with two endpoints p1 and p2 , we parameterize R(u) ina way that R(0) = p1 , R(0.5) = p2 , and R(1) = p1 . Obviously, both
R(0) and R(0.5) are C 0 points in the open curve. The input curveR(u) can be prepared by users in different ways, e.g., creating 3Dparametric curves using 3D modeling tools or projecting 2D curves
onto a 3D surface; see Figure 3 for examples.
Besides exact path generation, the 3D cam-linkage mechanism
should also satisfy the following requirements related to topology,
fabrication, and kinematics:

Fig. 3. Users can specify the target path in different ways: model (a) a closedor (b) an open 3D parametric curve, or (c) project a 2D curve (e.g., a jigsaw
puzzle piece boundary) onto a 3D surface (e.g., a saddle surface). Note thatC 0 points in (a&b) are colored in pink.

(1) Simple mechanism. The mechanism should consist of as few
mechanical parts as possible.
(2) Lightweight mechanism. The size of each component part in themechanism should be as small as possible, to minimize the total
weight.
(3) Collision-free motion. There is no collision among the mechanicalparts during their motion. This also implies that each part motion
should be within the range allowed by the mechanical joints.
(4) Singularity-free motion. The mechanism’s motion should always
remain a safe distance away from singularities of the spatial
linkage.
(5) Smooth motion. The acceleration of the mechanical parts should
be as low as possible to ensure smooth motion, assuming the
input motion is a uniform rotation.
Overview of our approach. In Section 4, we study topologies of the
3D cam-linkage mechanism such that it can perform exact 3D pathgeneration with a minimal number of mechanical parts. We propose
a unified method to parameterize the geometry of the mechanism, as
well as formulate analytical equations for modeling the kinematicsof the mechanism. Taking the mechanism modeling as a foundation, Section 5 addresses the problem of designing 3D cam-linkage
mechanisms for exact 3D path generation. We formulate the design
problem as an optimization to search for an optimal topology andgeometry of a 3D cam-linkage mechanism that can satisfy our design requirements. We also propose an optimization solver methodthat can explore the large design space efficiently.

4

MODELING 3D CAM-LINKAGE MECHANISMThis section presents our approach to modeling the 3D cam-linkage
mechanism’s topology, geometry, and kinematics, respectively.

4.1

Topology Modeling

Two essential components in our 3D cam-linkage mechanisms are
spatial linkages and 3D cams. Spatial linkages are necessary since
they are the primary mechanisms for 3D path generation. The simplest spatial linkages are 4-bar and 5-bar linkages. We choose a 5-bar
spatial linkage for our mechanism, and explain why a 4-bar spatial
linkage is insufficient for our goal in the supplementary material.
To enable exact 3D path generation, our 5-bar spatial linkage shouldhave 3 DOFs. Rather than controlling the linkage’s 3 DOFs using
3 independent actuators, we propose to use 3D cams [Cheng et al.
2021] to control the linkage motion, aiming to reduce the whole
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

225:4 •Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang Liu
Table 1. Link joints used in our 3D cam-linkage mechanism and their allowed degrees of freedom sk , among which α , β , and γ are the rotation
angles while d is the translation distance. Note that dˆ is the maximum
translation distance allowed by P and C joints.

Fig. 4. An illustration of our 3D cam-linkage mechanism, which consistsof five links {L i }, five link joints { Jk }, two 3D cams {C j }, two cam joints{B j }, one end-effector point pe , and a support structure (in grey).

et al. 2016]:
mechanism’s DOFs from 3 to 1 such that it can be driven by a single
actuator; see Figure 4. Note that planar cams are unable to accomplish this task since they can only transfer 1-DOF motion to another
1-DOF motion.
Our 5-bar spatial linkage consists of five links connected by five
joints, denoted as {Li } and {Jk }, 1 ≤ i, k ≤ 5, respectively. Amongthe five links, L 5 is the fixed one, and the two links connectedwith L 5 are L 1 and L 4 . Links L 5 and L 1 are connected by joint J1
while links L 5 and L 4 are connected by joint J5 ; see Figure 4. We
consider joints J1 and J5 as active joints in the 5-bar linkage while
the other joints (i.e., J2 , J3 , J4 ) as passive joints. Since the linkage
has 3 DOFs, we assume that the active joint J1 has 2 DOFs and theactive joint J5 has 1 DOF, without loss of generality. To reduce themechanism’s DOFs from 3 to 1, we use two 3D cams, denoted as{C j }, 1 ≤ j ≤ 2, to control the motion of the two active joints,
respectively. We intentionally make the two 3D cams C 1 and C 2
co-axis such that they can be driven by a single actuator directly,
without using additional mechanical parts such as gears; see Figure 4.
More specifically, we use cam C 1 to control 2-DOF motion of joint J1
and use cam C 2 to control 1-DOF motion of joint J5 . By this, C 1 , J1 ,and L 1 as well as C 2 , J5 , and L 4 form two cam-follower mechanisms
denoted as C 1 −L 1 and C 2 −L 4 , respectively. The cam-follower joints
in C 1 − L 1 and C 2 − L 4 are denoted as B 1 and B 2 , respectively.
We call {B j }, 1 ≤ j ≤ 2, cam joints, and {Jk }, 1 ≤ k ≤ 5, link joints.
Each cam joint B j is always a ball-move-in-groove joint proposedin [Cheng et al. 2021]; see Figure 2 (left). Each link joint Jk can only
be a commonly used mechanical joint (i.e., R, P, C, U, and S joints)
to satisfy our simple mechanism requirement. Table 1 shows thegeometry, name, and allowed motion for each of these link joints.
Since the active joint J1 has 2-DOF motion while the active joint
J5 has 1-DOF motion, joint J1 can only be {C, U } while joint J5 canonly be {R, P } according to Table 1.
We have determined candidates for the two active joints J1 and J5
in the 5-bar linkage. However, there are still three passive joints (i.e.,
J2 , J3 , and J4 ) remaining in the linkage. The DOFs fk of each joint
Jk in the 5-bar linkage should satisfy the mobility formula [Uicker
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

M = 6(N − 1 − K) +

K
Õ

fk

(1)

k =1

where M = 3 is the linkage’s DOFs, N = 5 is the number of links,
and K = 5 is the number of link joints. Recall that f 1 = 2 and f 5 = 1.
Substituting the values of M, N , K, f 1 and f 5 into Equation 1, wehave:
f2 + f3 + f4 = 6(2)We enumerate all possible combinations of link joints in Table 1
that satisfy Equation 2, and find that the total number of combinations is 128; please refer to the supplementary material for details.
Each combination of the link joints (e.g., J1 J2 J3 J4 J5 =URSUR) definesa unique topology of the 3D cam-linkage mechanism. Hence, wehave 128 different topologies of the 3D cam-linkage mechanism. To
compare these topologies, we conducted an experiment and foundthat P and C joints typically result in L-shaped links and a larger
motion envelope of the linkage, which violates our requirement on
a lightweight mechanism; see Section 6 and Figure 9. Hence, weonly use mechanism topologies without P or C joints for exact 3D
path generation in this paper. There are 7 such topologies in total,i.e., URSUR, URUSR, USRUR, USURR, UUSRR, UURSR, UUUUR; see
Figure 5 for examples.

4.2

Geometry Modeling

Our 3D cam-linkage mechanism consists of five different kindsof components. Below, we describe our approach to modeling thegeometry for each kind of component:i) Link joints. Table 1 shows five different types of link joints used in
our mechanism, i.e., R, P, C, U, and S joints, as well as their geometry
and allowed degrees of freedom sk . Note that the U joint is actuallya modified S joint that removes 1-DOF rotation by inserting two
pins in the S joint. Each of the R, P, C, and U joints is associatedwith a 3D axis, denoted as vk ; see Table 1 for the meaning of vk .
The geometry of each link joint defines the allowed range of relative
motion between the two associated links. Due to the fabrication

Exact 3D Path Generation via 3D Cam-Linkage Mechanisms • 225:5
constraint, both U and S joints can support [−180◦, 180◦ ] rotation
around the spinning axis and [−45◦, 45◦ ] rotation for each of theother rotation axes. The maximum translation distance dˆ allowedby the P and C joints is defined by the length of the joint and theassociated link.
ii) Cam joints. Each cam joint is modeled as a ball-move-in-groove
joint, which allows 4-DOF motion of the follower relative to thecam (i.e., 3-DOF rotation and 1-DOF translation along the camgroove); see Figure 2 (left). The joint geometry is parameterized by
the 3D cam’s pitch curve denoted as Qj and the follower ball radiusr [Cheng et al. 2021].
iii) Links. Among the five links, L 5 is a fixed link; L 1 and L 4 aredriven by the active joints J1 and J5 respectively, called active links;
and L 2 and L 3 are driven by the passive joints J2 , J3 , and J4 , called
passive links. Each active/passive link is modeled as a bar (with acircular cross-section) that connects two neighboring link joints(e.g., L 2 connects J2 and J3 ) or two neighboring link joints as well
as a cam joint (e.g., L 1 connects J1 , J2 , and B 1 ); see Figure 4. The
shape of each link is not necessary to be always a straight bar. To
avoid collision when transferring motion, we model the centerlineof each passive link as a polyline with three line segments, among
which the middle segment is usually the longest one. The centerlineof each active link has three more line segments for connecting the
cam joint; see Figure 5 for examples.
iv) End-effector. To output 3-DOF motion, the end-effector has to be
put on the passive link L 2 or L 3 since the active links L 1 and L 4 canonly output 2-DOF and 1-DOF motion, respectively. Without lossof generality, we always put the end-effector on the passive link L 2 .
The geometry of the end-effector is modeled as a bar extended fromthe link L 2 . The point on the end-effector for generating a path iscalled the end-effector point and denoted as pe ; see Figure 4.
v) 3D cams. The 3D cam geometry is modeled as a watertightsurface that holds the cam joint following the approach in [Chenget al. 2021]. One modification that we make is to remove someunnecessary volume of the 3D cam to make it more lightweight;
compare Figures 5 and 2.
vi) Support. The support of our 3D cam-linkage mechanism is a
structure that holds the common rotation axis of the two 3D cams
as well as the fixed link L 5 . We model the support structure in
two different ways: a baseboard with three supporting pillars forvisualizing the mechanism (see Figure 1) or a box frame that encloses
the 3D cams for fabricating the mechanism (see Figure 12).

Fig. 5. Three example topologies of our 3D cam-linkage mechanism.

toward the center of joint J5 , and the y-axis points toward the center of joint J2 (and is perpendicular to x-axis) in the mechanism’s
initial configuration; see Figure 4. Variables for kinematic modelingof the mechanism are all defined in this coordinate system, unlessotherwise specified.
4.3.1 Kinematics of 5-bar Spatial Linkage. We model both forward
kinematics (FK) and inverse kinematics (IK) of the 5-bar spatial
linkage, and perform singularity analysis.
Forward kinematics. Forward kinematics of a linkage aims todetermine the linkage’s state for given actuation parameters. The
state s of a linkage is defined through its time-varying joint angles,i.e., s = [s1 (t), s2 (t), ..., sK (t)]; see Table 1 for details. Note that
we consider the translation distance d of the P and C joints as a
generalized joint angle, to simplify the terminology. The actuation
parameters of our 5-bar spatial linkage are the angles of active joints
J1 and J5 , i.e., s1 and s5 . The forward kinematics of the linkage canbe expressed as the following motion transfer function:[s2, s3, s4 ] = flinkage ([s1, s5 ])Assuming the linkage’s initial state s̄ = s(0) is known and valid,
the constraint on the state s at time t enforced by the single loop in
our 5-bar spatial linkage can be formulated as (see also Figure 6):
CL (s1, s2, s3, s4, s5 ) = 0

Kinematic ModelingIn this section, we first describe our approach to modeling thekinematics of the 5-bar spatial linkage, considering joints J1 andJ5 as active joints; see Section 4.3.1. In Section 4.3.2, we model the
kinematics of the 3D cam-linkage mechanism by considering it as acomposition of the 5-bar spatial linkage (i.e., L 1 L 2 L 3 L 4 L 5 ) and two
cam-follower mechanisms (i.e., C 1 − L 1 , C 2 − L 4 ).
We define a local coordinate system for our 3D cam-linkage mechanism, where the origin is at the center of joint J1 , the x-axis points(4)

where CL is a column vector with 12 elements. Please refer to theappendix for details about computing the constraint CL . Given the
known actuation parameters s1 and s5 , we can then solve for the unknown passive joint angles [s2, s2, s3 ] of the linkage by minimizing
a non-linear least squares problem:
min
s

4.3

(3)

CTL CL(5)

We solve the optimization problem using a gradient-based method,e.g., Levenberg-Marquardt algorithm.
Once we compute the kinematic equation flinkage (·), the endeffector point position pe (t) on link L 2 at time t can be calculatedusing:pe (t) = ML2 (t) p̄e , t ∈ [0,T ](6)
where ML2 (t) is the transformation of link L 2 at time t (see theappendix for details), ML2 (0) = I, and p̄e = pe (0). When the active
joints J1 and J5 move for a whole period T , the trajectory of the
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

225:6 •Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang Liu
4.3.2 Kinematics of Cam-Linkage Mechanism. In our 3D cam-linkage
mechanism, the two active joints angles s1 and s5 of the 5-bar linkage
is actually the output motion of the two cam-follower mechanisms
C 1 − L 1 and C 2 − L 4 , respectively. Hence, the 3D cam-linkage mechanism’s forward kinematics can be obtained by composing those of
the 5-bar linkage and the two cam-follower mechanisms.
The motion transfer equation of the two cam-follower mechanisms can be written as:

Fig. 6. Our 5-bar spatial linkage in (left) the initial state at time t = 0 and(right) the current state at time t .

end-effector point pe (t) is the path generated by the 5-bar linkage
denoted as B(t); see Figure 6 (right).
Inverse kinematics. The goal of inverse kinematics is to determine
the linkage’s state s (i.e., both passive and active joint angles) thatcan generate each point on a given path R(u), u ∈ [0, 1]. Startingfrom the known initial state s̄, we determine a unique state s(t)iteratively by formulating the following optimization problem:min ∥s(t) − s(t − ∆t)∥ss.t. CTL CL = 0,
ML2 (t) p̄e = R(u)(7)

where ∆t is a small time duration in the motion period T (∆t =T /1000 in our experiments). Note that a valid solution s can always
be found by our optimization as long as the path R(u) is in thereachable space of the linkage’s end-effector, since our 5-bar linkage
has 3 DOFs. In practice, we usually do not know whether a given
path R(u) is in the reachable space of the linkage’s end-effector ornot. To handle this case, we use a gradient-based method to solve
the dual problem instead:min ||CL || 2 + ||ML2 p̄e − R|| 2(8)sStarting from the initial state s̄, we set s(t) = s(t − ∆t), for t ∈ [0,T ],as the initial value of s(t), and then use a gradient-based method tofind the optimal value of s(t). In case that our method fails to finda solution for Equation 8, it means that the 5-bar linkage cannot
reach the point R(u).
Singularity analysis. We analyze FK singularities of the linkage
following the approach in [Gosselin and Angeles 1990]. Differentiating Equation 4 with respect to time t leads to the relationshipbetween the input and output speeds as follows:
A [Ûs2, sÛ 3, sÛ 4 ] + B [Ûs1, sÛ 5 ] = 0
Lwhere A = ∂[s∂C
is the FK Jacobian matrix. The minimal singu2 ,s3 ,s4 ]lar value σmin (A) represents the distance from the linkage state s(t)to the FK singularities.
IK
We define the IK Jacobian matrix as J = ∂[s ,s∂C
, where1 2 ,s3 ,s4 ,s5 ]CIK = [CL, (ML2 p̄e −R)] according to Equation 7. Condition number
κ(J) describes the distance from the linkage state s(t) to the IK
singularities [Merlet 2006; Yoshikawa 1985]. Based on the implicit
function theorem, κ(J) quantifies smoothness of the linkage motion.

ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

s1 = fcam1 (θ ),(9)s5 = fcam2 (θ )(10)

where θ is the rotation angle of the single actuator. We compute thetwo motion transfer functions fcam1 (·) and fcam2 (·) following theapproach in [Cheng et al. 2021]. Combing Equations 3, 9, and 10, we
obtain the motion transfer function of our 3D cam-linkage mechanism:[s1, s2, s3, s4, s5 ] = fmech (θ )(11)
where fmech (·) is a composition function of flinkage (·), fcam1 (·), andfcam2 (·).

5

DESIGNING 3D CAM-LINKAGE MECHANISMThis section presents our approach to designing 3D cam-linkage
mechanisms that satisfy the high-level requirements in Section 3.
We formulate the design problem as an optimization in Section 5.1
and then present our method to solve the optimization in Section 5.2.

5.1

Optimization Formulation

Taking a user-specified continuous space curve R(u), u ∈ [0, 1]
defined in the world space as input, we aim to design a 3D camlinkage mechanism whose end-effector point pe can generate apath that is exactly the same as the curve R(u). We assume that theposition and orientation of the mechanism in the world space havebeen specified by users, represented as a matrix Tmech .
Search space. Our search space includes both the topology andgeometry of the 3D cam-linkage mechanism. The topology search
space is the 7 topologies introduced in Section 4.1, denoted as {Gl }.
The geometry search space is the parameters that define the 3D camlinkage mechanism’s geometry in the mechanism’s local coordinate
system. We classify these parameters into two classes: kinematicrelated parameters that determine motion of the mechanism, andfabrication-related parameters that affect only fabrication but not motion of the mechanism. The kinematic-related parameters, denotedas Ψ include:(1) {xk (0)}, 1 ≤ k ≤ 5 that defines the position and orientation ofeach link joint Jk in the initial state of the mechanism at t = 0.
(2) {Qj (w)}, w ∈ [0, 1], 1 ≤ j ≤ 2 that defines the pitch curve ofeach 3D cam C j . Qj (w) is modeled as a cubic spline where Qj (0)represents the position of the cam joint B j at t = 0.
The fabrication-related parameters include geometric parameters ofeach link joint (e.g., radius of S and U joints), follower ball radius r ineach cam joint, centerline of each link, radius of each link’s circularcross-section, as well as geometric parameters of the support structure. The fabrication-related parameters are either predefined orExact 3D Path Generation via 3D Cam-Linkage Mechanisms • 225:7

Fig. 7. Our approach to solving the 3D cam-linkage mechanism design problem, assuming a fixed topology. (a) Given a user-specified 3D curve, we first (b)initialize a set of 5-bar linkage candidates {Li } and then (c) compute the inverse kinematics for each linkage Li to determine the linkage state si (t ). (d) For
each linkage candidate with valid IK, we compute the geometry Q1 and Q2 of the two 3D cams based on the two joint angles s1 (t ) and s5 (t ), respectively. (e)Our output is an optimal cam-linkage design that satisfies all the constraints and minimizes the objective function in Section 5.1.

calculated as post-processing after the kinematic-related parameters
have been determined.
To quantify a mechanism design, we have to simulate the mechanism’s forward kinematics for a whole motion period T . Hence, we
also need to determine the joint angle parameters s(t) = [s1 (t), s2 (t),s3 (t), s4 (t), s5 (t)], t ∈ [0,T ] by computing the motion transfer function in Equation 11. Without loss of generality, we assume theactuator rotates with a constant angular speed ω at any time t, i.e.,θ (t) = ωt, when simulating the mechanism’s kinematics.
Objective function. Our mechanism design problem is formulated
as minimizing the following objective function:E(Ψ) = λ 1 E smth (Ψ) + λ 2 E weig (Ψ) + λ 3 E link (Ψ)
with E smth=

E weig=max t ∈[0,T ] κ(J) ,2
ÕLen( Qj (w) ) +j=1

and E link

=

(12)

v
u
t 5
Õ

kinematics:
C(s(t))TL C(s(t))L = 0, t ∈ [0,T ](13)(2) Exact path generation. The end-effector’s trajectory B(t) should
be exactly the same as the input curve R(u):Tmech B(t) = R(u), t ∈ [0,T ], u ∈ [0, 1](14)

where the left-hand side is the actual trajectory of the endeffector point pe in the world space.
For each C 0 point R(uh ) in the input curve, the end-effector’s
speed when passing the point has to be zero. To this end, the two
active joint angles s1 and s5 that drive the 5-bar linkage shouldhave zero gradient (i.e., zero angular speed) at this moment:′

fcam1 (θh ) = s1,h , fcam1 (θh ) = 0
5
Õ′Len(Li ) ,i=1(Len(Li ) − L̄)2 ,i=1

where E smth measures the smoothness of the linkage motion, E weig
approximates the mechanism’s weight based on the length of eachpitch curve Qj (w) and the length of each link Li , E link is the standard
deviation of the five links’ lengths, L̄ is the average length of thefive links in the linkage, and λ 1 , λ 2 , and λ 3 are weights of the threeenergy terms. We set λ 1 = 5, λ 2 = 1, and λ 3 = 10 in our experiments
to balance the impact of the three energy terms.
As mentioned in Section 4.2, there are two kinds of links: {L 2, L 3, L 5 }that connect two link joints, and {L 1, L 4 } that connect two link
joints and one cam joint. Denote x̃k as the positional componentof xk (0). We approximate the length of each link Li in {L 2, L 3, L 5 }as ∥ x̃a − x̃b ∥, where x̃a and x̃b are the positions of the two joints
connected by link Li . We approximate the length of each link Li in{L 1, L 4 } as ∥ x̃a − x̃b ∥ + ∥ x̃b − Qj (0)∥.
Constraints. We formulate various constraints related to kinematics and fabrication as follows.
(1) Linkage kinematics. According to Equation 4, the 5-bar linkage
should satisfy the following constraint to ensure validity of its

fcam2 (θh ) = s5,h , fcam2 (θh ) = 0(15)

where s1,h , s5,h , and θh are the joint angle s1 , joint angle s5 , andactuator rotation angle θ when the end-effector passes the C 0
point R(uh ), respectively.
(3) Singularity-free motion. The minimal distance of the mechanism
to FK singularities during a whole motion period T should belarger than a threshold µ:
min ( σmin (A) ) ≥ µ,t ∈[0,T ](16)

where µ = 0.01 in our experiments.
(4) Collision-free motion. To ensure collision-free motion, we requirethat link joints should not be too close to one another during
any time t:Dist(x̃k (t), x̃l (t)) > τ , 1 ≤ k < l ≤ 5, t ∈ [0,T ](17)

where τ is the allowed minimal distance between any pair of thelink joints. We set τ = 6r empirically in our experiments, wherer is the radius of the follower ball in the cam joint. Thanks to
the distance constraints on the link joints, link-link collision can
be avoided by varying the links’ shape as a post-process.
We avoid collision between the linkage (i.e., passive links) andthe fixed link L 5 (i.e., support) by requiring:yx̃k (t) > τ /2, 2 ≤ k ≤ 4, t ∈ [0,T ](18)

ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

225:8 •Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang Liuywhere x̃k (t) is the y-coordinate of x̃k (t) in the mechanism’s
local coordinate system. We avoid collision between the two 3D
cams by requiring:
dist( Q1, Q2 ) > τ2:yx̃5 − (MR (θ (t)) Qj (w))y > τ /2, 1 ≤ j ≤ 2, t ∈ [0,T ], w ∈ [0, 1](20)
where MR (θ (t)) is the actuator’s rotation matrix at time t.
(5) Link joint angles. The joint angle of each link joint should bewithin a valid range:(21)

where Ωl is the set of valid joint angles defined for the joint
type l in Table 1.
(6) Smooth cam groove. The pitch curve Qj (w) should be closed andsmooth such that the resulting cam groove allows the follower
ball to move periodically and smoothly in it:
ρ j (w) > ζ r, 1 ≤ j ≤ 2, w ∈ [0, 1](22)

where ρ j (w) is the radius of curvature of Qj (w), r is the follower ball radius, and ζ is a coefficient typically set as 1.2 in our
experiments.

5.2

1: function DesignMechanism(R(u))(19)

We avoid collision between each 3D cam and the fixed link L 5
by requiring:sk (t) ∈ Ωl , 1 ≤ k ≤ 5, t ∈ [0,T ]Algorithm 1 Algorithm to solve the 3D cam-linkage mechanism
design problem, taking a user-specified curve R(u) as an input.

Optimization Solver

Our optimization problem in Section 5.1 is challenging to solve. First,
the search space is large, including mechanism topologies {Gl },linkage parameters {xk (0)}, and cam pitch curves {Qj }. Second,
there are a large number of constraints, some of which are nonconvex such as collision-free motion and range of link joint angles.
To address the above challenges, our observation is that the search
space is dominated by the cam pitch curves {Qj } while the mechanism topologies {Gl } and linkage parameters {xk (0)} have a relatively low dimension. Hence, our idea is to divide our problem
into two sub-problems by considering our 3D cam-linkage mechanism as a composition of two 3D cam-follower mechanisms anda 3-DOF 5-bar linkage; see Figure 7. The first sub-problem is tocompute the pitch curves {Qj } while fixing the mechanism topology Gl and linkage parameters {xk (0)}, which can be addressed by
optimizing the two 3D cam-follower mechanisms using the method
in [Cheng et al. 2021]. The second sub-problem is to explore different mechanism topologies Gl and linkage parameters {xk (0)}. Since
the search space is relatively small, we can enumerate all possible
mechanism topologies {Gl } and explore the linkage parameters{xk (0)} by using an evolutionary algorithm.
In detail, for each given topology Gl , we first use the Particle
Swarm Optimization (PSO) [Kennedy and Eberhart 1995] to randomly initialize N (N = 40 in our experiments) particles, where eachparticle represents the kinematic-related geometric parameters Ψiof a 3D cam-linkage mechanism Mi . In particular, we only initialize
the linkage parameters xi = {xik (0)} for each particle Ψi and the corresponding pitch curves {Qij } are computed by optimizing the two
3D cam-follower mechanisms. In detail, we first solve the inverse
kinematics problem in Equation 8 for the 3-DOF spatial linkage toobtain the joint angles si (t) = [si1 (t), si2 (t), si3 (t), si4 (t), si5 (t)], where
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

3:

G optim ← ∅for each topology Gl do▷ Initialize N particles
Ψlist ← ∅5:for i = 0; i < N ; i + + do
6:xi = {xik (0)} ← initialize linkage parameters with
topology Gl
7:
Qi1 ← ∅
8:
Qi2 ← ∅
9:Ψi ← {xi , Qi1, Qi2 }10:Ψlist .push_back( Ψi )
4:

11:
12:

Ψoptim ← ∅for itr = 0; itr < itrmax ; itr + + do

▷ Evaluate N particles
for each particle Ψi ∈ Ψlist do
14:
si (t) ← solve IK in Eq. 8 with R(u) as the input
15:
ri .push_back ( residuals of Eq. 13 and 14 )16:
Qi1 ← optimize cam-follower C 1 −L 1 to minimizeiLen(Q1 ) subject to the follower motion si1 (t), Eq. 15, 20 and 22.
17:
Qi2 ← optimize cam-follower C 2 −L 4 to minimizeiLen(Q2 ) subject to the follower motion si5 (t), Eq. 15, 20 and 22.
13:

18:
19:
20:
21:
22:

23:
24:
25:

ri .push_back (residuals of Eq. 16, 17, 18, 19, 21 )N (Ψi ) ← ∥ri ∥0
S(Ψi ) ← ∥ri ∥1
E(Ψi ) ← evaluate Ψi using Eq. 12[G optim, Ψoptim, N min, S min, Emin ] ← record thebest candidate and its three metrics▷ Move N particles
for each particle Ψi ∈ Ψlist do
Update linkage parameters xi in ΨiConstruct a mechanism Moptim using [G optim, Ψoptim ]return Moptimt ∈ [0,T ] . Since the active joint angles [si1 (t), si5 (t)] are actually theoutput motions of the two cam-follower mechanisms C 1 − L 1 andC 2 − L 4 respectively, we compute the pitch curve Qi1 (Qi2 ) of 3D cam
C 1 (C 2 ) by optimizing C 1 − L 1 (C 2 − L 4 ) independently using themethod in [Cheng et al. 2021]. By this, we obtain all the parametersΨi = {xi , Qi1, Qi2 } of the cam-linkage mechanism Mi .
To evaluate each particle Ψi , we check whether it satisfies theconstraints listed in Section 5.1, and compute the corresponding
residual ri , where rik = 0 if the k-th constraint in Section 5.1 issatisfied by the particle Ψi . For constraints related to motion, we
compute the residual by discretizing the whole motion cycle T into
60 samples. We evaluate the particle Ψi using three metrics: thenumber of unsatisfied constraints 1 N (Ψi ) = ∥ri ∥0 , the sum of
1 A constraint is considered as being satisfied if the residual is less than an epsilon 10−8 .

Exact 3D Path Generation via 3D Cam-Linkage Mechanisms • 225:9

Fig. 9. Evaluating different topologies of our 3D cam-linkage mechanismwith (a) 0, (b) 1, (c) 2, or (d) 3 P or C joint(s), highlighted with red arrows.
Fig. 8. Our 3D cam-linkage mechanism exactly generates a 3D path witha variety of shapes: (a) Bézier curve, (b) Chair, (c) Puzzle Piece, and (d)Conical Rose.

residual of the constraints S(Ψi ) = ∥ri ∥1 , and the objective function E(Ψi ) in Equation 12. We consider a particle Ψi is better thananother one Ψj if one of the following condition is satisfied:(1) N (Ψi ) < N (Ψj )(2) N (Ψi ) = N (Ψj ) > 0 & S(Ψi ) < S(Ψj )(3) N (Ψi ) = N (Ψj ) = 0 & E(Ψi ) < E(Ψj )We choose the above criteria since initially many particles do notsatisfy all the constraints in Section 5.1 and we want to identify andkeep particles that satisfy more constraints.
To move the particles in the search space, we set the learning
rate to 1 and the acceleration coefficient to 2. The inertia coefficient is linearly decreased from 0.9 to 0.4. We repeat the above
PSO algorithm for each topology in {Gl } to determine the optimal
parameters [G optim, Ψoptim ], which will be used to construct the
optimal mechanism Moptim ; see Algorithm 1 for details.

6

Evaluation of mechanism topologies. Since there are 128 valid
topologies for our 3D cam-linkage mechanism, we want to know
which topologies can lead to a more usable mechanism. Our conjecture is that 3D cam-linkage mechanisms with fewer P or C joints
would be more usable since translational motion allowed by P and C
joints makes the link with L-like shape, significantly increasing thelinkage’s motion envelope. To verify this conjecture, we conducted
an experiment to compare 3D cam-linkage mechanisms with different numbers of P or C joint(s). Taking the same curve as an input,
we run our design algorithm to generate the path while restricting
Table 2. Statistics of the results shown in this paper.

RESULTSWe implemented our tool in C++ and libigl [Jacobson et al. 2018]
on a desktop computer with a 3.7GHz CPU and 16GB memory. Figure 8 shows that our 3D cam-linkage mechanism is able to exactly
generate a wide variety of curves, including an open Bézier curvewith two C 0 points (i.e., two endpoints), a closed Chair curve with
ten C 0 points, a Puzzle Piece curve projected onto a saddle surface,and a famous parametric curve Conical Rose. Table 2 provides
statistics of all the results shown in the paper, including the mechanism topology, values of the three energy terms, and time taken to
optimize each mechanism. Please refer to the accompanying videofor demos of the mechanisms and the supplementary material forequations of the input parametric curves.
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

225:10• Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang Liu

Fig. 10. Generating a 3D path with arbitrary shape and a finite numberof C 0 points. (a) Compute a continuous and volumetric portion of a 3DOF 5-bar spatial linkage’s output motion space that is collision-free andsingularity-free; (b) transform the linkage such that its output motion space
fully covers the input curve; (c) compute the geometry of the two 3D cams;and (d) optimize the geometry of the 3D cam-linkage mechanism.

the topology to have 0, 1, 2, and 3 P or C joint(s), respectively. Figure 9(a-d) shows that the more P or C joints in the 5-bar linkage,
the larger the motion envelope of the linkage, where the motion
envelope size is in the ratio of 1 : 1.181 : 1.208 : 1.793.
Generating a 3D path with arbitrary shape. In this experiment,
we demonstrate that our 3D cam-linkage mechanism is able to exactly generate a continuous 3D curve with arbitrary shape and afinite number of C 0 points. The exactness of 3D path generationmeans that the distance between each sample point (1000 sample
points in our experiments) on the generated path and the target
path represented as a parametric curve is less than a floating point
epsilon (equals 10−8 in our experiments). Without loss of generality,
we choose a 3-DOF 5-bar spatial linkage with topology USRUR. We
choose the linkage’s geometry in a way that there is a continuousand volumetric portion Φ of the linkage’s output motion space thatis singularity-free and collision-free, where the volumetric portion iscomputed using a sampling-based approach; see Figure 10(a). Next,
we model a 3D curve R(u) with arbitrary shape by moving a particle
with random acceleration in a fixed sphere, where C 0 points are
introduced in the curve by changing the particle’s current velocity(integrated from the acceleration) to a random velocity with different
direction. We transform (i.e., translate, rotate, and scale) the 5-bar
linkage such that its motion space Φ can fully cover the curve R(u);see Figure 10(b). By this, all the design constraints related to thespatial linkage (i.e., Equations 13, 14, 16, 17, 18, 21) have been satisfied. The geometry of each 3D cam C 1 (C 2 ) can be further generated
according to the active joint angle s1 (t) (s5 (t)) calculated from thelinkage’s inverse kinematics; see Figure 10(c). According to [Chenget al. 2021], we can always find such a 3D cam that satisfies theconstraints of Equations 15, 20, and 22. To ensure the collision-free
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

Fig. 11. The mechanism volume (top) and variance of normalized link length(middle) for generating 20 3D paths with increasing shape complexity, as
well as four example input curves and corresponding mechanisms (bottom).

constraint between the two 3D cams (i.e., Equation 19), we require a
sufficient distance between the two active link joints J1 and J5 along
the x-axis when choosing the linkage’s geometry; see again Figure 4. Figure 10(c) shows the resulting 3D cam-linkage mechanism
for generating the input curve with arbitrary shape and 11 C 0 points.
We further optimize the 3D cam-linkage mechanism’s geometry
to reduce its weight and smooth its motion (i.e., Equation 12); see
Figure 10(d). Please refer to the supplementary material for moredetails about this experiment.
Generating 3D paths with varying shape complexity. We conduct aquantitative experiment to evaluate the impact of the input curve’s
shape complexity on our designed 3D cam-linkage mechanism. In
detail, we model 20 continuous, closed curves {Rk }, 1 ≤ k ≤ 20with increasing shape complexity using the particle-based method
mentioned above, where Length(Rk +1 ) = 1.1 · Length(Rk ) and Rk
has k −1 C 0 points. Taking each curve Rk as an input, we design a 3D
cam-linkage mechanism using the optimization method in Section 5.
Figure 11 shows the total volume (excluding the support structure)and the variance of normalized link length of each mechanism
when the shape complexity of the input curve is increasing. We cansee that generating a curve with more complex shape requires amechanism with a larger volume since two larger 3D cams (with alonger pitch curve) are necessary to encode the input curve withmore complex shape. In addition, generating a more complex input
curve also results in a larger variance of normalized link length.
Please refer to the supplementary material for all the 20 input curves
and corresponding mechanisms.
Fabrication. To evaluate the kinematic performance of our mechanism, we used our approach to design a 3D cam-linkage mechanismthat can generate a Tennis Ball Seam curve and fabricated it with
3D printing; see Figure 12. In detail, we 3D printed the 3D cams
and 5-bar linkage as a non-assembly, articulated model (i.e., a single

Exact 3D Path Generation via 3D Cam-Linkage Mechanisms •225:11

Fig. 14. Designing and fabricating a low-cost manipulator to perform apick-and-place task by using our 3D cam-linkage mechanism.
Fig. 12. Evaluating the kinematic performance of our mechanism. (Top) Our
designed mechanism in front, side, and top views, respectively. (Bottom)
Corresponding views of our 3D printed prototype, where the generated
path is tracked on video images and visualized in yellow.

piece) using the Ultimaker S3 printer with Tough PLA material andwater-soluble PVA support material, where the link joint tolerance
is set as 0.5 mm and the cam joint tolerance is set as 0.3 mm. The
support structure is partitioned, 3D printed as multiple parts, andthen assembled with the single articulated piece of 3D cams and5-bar linkage. We tracked the path generated by our 3D printed
mechanism using an image-based approach. Figure 12 compares ourdesign and the 3D printed prototype in front, side, and top views,
respectively. We can see that the 3D print matches the virtual designvery well, and the tracked curve is very close to the input curve inall the three views. The discrepancy between the two curves can becaused by several reasons including fabrication tolerance, material
deformation, and tracking inaccuracy, which can be reduced byusing a more precise manufacturing technique, tougher fabricationmaterial (e.g., steel), and a better curve tracking technique.
To verify that our 3D cam-linkage mechanism is able to generatea path with C 0 points, we designed a mechanism that can draw a

Fig. 13. Evaluating the kinematic performance of our mechanism for generating a planar Heart curve with two C 0 points.

planar Heart curve with two C 0 points, 3D printed it using thesame 3D printer and settings as above, and tracked the generated
path using the image-based approach. Figure 13 shows that the
curve as well as its two C 0 points generated by the 3D printed
mechanism are very close to the virtual counterpart. Moreover, the3D printed mechanism’s end-effector stops when passing each of
the two C 0 points even though the 3D cams rotate uniformly, whichis consistent with our kinematic simulation of the mechanism; see
the accompanying video for a demo. The reason that our 3D camlinkage mechanism is able to reproduce C 0 points in the prescribed
3D curve is that the two 3D cams (with a smooth groove) are able
to control the motion of the two driving links (i.e., followers) of the
5-bar linkage respectively such that both driving links have zero
speed when the end-effector is passing each C 0 point; see again
Equation 15.
We fabricated one more prototype to demonstrate that our mechanism can be used as a low-cost manipulator driven by a single
actuator to perform pick-and-place tasks repetitively; see Figure 14.
In this experiment, the task is to pick a box from the floor, manipulate the box, place it on a table, go back to pick another box, and soon and so forth. The path is designed as a closed 3D spline curvewith two approximately straight segments for the mechanism’s endeffector to pick and place the box, respectively. To avoid collision
between the end-effector and the box, we add one more energy termin our optimization to approximately control the end-effector’s orientation for 20 sampled points on the path segments when picking
and placing the box. Figure 14 compares three states between thereal manipulation process and the virtual counterpart, and we cansee that they all match each other very well.
Generalizing 3D cam-linkage for 3D motion generation. Our 3D
cam-linkage mechanism can be generalized for exact 3D motion
generation, which is a more complex motion transfer task than exact
3D path generation. To this end, we first design a 6-DOF 8-bar spatial
linkage and then reduce the linkage’s DOFs from 6 to 1 by composing
the linkage with three 3D cam-follower mechanisms. We extend
our approach in Section 5 to design the generalized mechanism,
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

225:12• Yingjie Cheng, Peng Song, Yukun Lu, Wen Jie Jeremy Chew, and Ligang Liu
3D cam-linkage mechanisms, possibly with other mechanical parts
such as non-circular gears [Xu et al. 2020], into a more powerful
yet more complex mechanism.

ACKNOWLEDGMENTS

Fig. 15. Generalizing our 3D cam-linkage mechanism for exact 3D motion
generation, which consists of three 3D cams and eight links.

where the user input is a continuous set of rigid transformations
represented as a continuous 3D path as well as a local frame for eachpoint on the path; see Figure 15 (left). We solve the design problem
by making two modifications on Algorithm 1. First, we fix instead of
searching for the topology of the generalized mechanism with eightlinks and three cams. Second, we modify the IK solver to computethe link joint angles of the 6-DOF 8-bar linkage according to theprescribed positions and orientations of the end-effector. Figure 15
shows an example mechanism for 3D object manipulation. Different
from the manipulator in Figure 14, the generalized mechanism canexactly control both the position and orientation of the object along
the whole path.

7

CONCLUSION

Exact 3D path generation is a fundamental yet challenging problem
in many fields such as mechanical engineering, manufacturing, androbotics. To address this problem, we propose and study a new 3D
cam-linkage mechanism that consists of only seven mechanicalparts in this paper. A family of computational techniques has beendeveloped to model and design the 3D cam-linkage mechanism,
where the key idea is to consider the 3D cam-linkage mechanism as
a composition of two 3D cam-follower mechanisms and a 3-DOF
5-bar linkage. Our 3D cam-linkage mechanism has been evaluated inmany aspects including its topology, kinematics, ability to generate
3D paths with varying shape complexity, and a potential applicationfor 3D object manipulation.
Limitations and Future Work. Our work has several limitations
that open up interesting directions for future work. First, we do notmodel the dynamics and friction of our 3D cam-linkage mechanism,
which will be useful for understanding how much workload theend-effector can carry in practice, e.g., in the manipulation task.
Second, we do not study the role of backlash in our 3D cam-linkage
mechanisms; for example, even though our designed mechanism
stays away from singular configurations, the physical mechanism
could still get stuck due to backlash. Third, our 3D cam-linkage
mechanism currently has a fixed topology with two 3D cams andfive links. We consider developing a general algorithm to model anddesign 3D cam-linkage mechanisms with m cams (e.g., m ∈ {2, 3})
and n links (e.g., n ∈ {5, 6, 7, 8}) for 3D path/motion generation as
an interesting future work. Lastly, our mechanism currently only
has a single end-effector, limiting the tasks that it can accomplish.
To address this limitation, one possible way is to combine multiple
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.

We thank the reviewers for their valuable comments, Ke Chen for
proofreading the paper, and Robert Ferréol for providing equationsof some input parametric curves. This work was supported by the
SUTD Start-up Research Grant (Number: SRG ISTD 2019 148), andthe National Natural Science Foundation of China (62025207).

REFERENCES
Moritz Bächer, Stelian Coros, and Bernhard Thomaszewski. 2015. LinkEdit: Interactive
Linkage Editing using Symbolic Kinematics. ACM Trans. on Graph. (SIGGRAPH) 34,
4 (2015), 99:1–99:8.
Shaoping Bai, Zhongyi Li, and Jorge Angeles. 2022. Exact Path Synthesis of RCCC
Linkages for a Maximum of Nine Prescribed Positions. Journal of Mechanisms andRobotics 14, 2 (2022), 021011:1–021011:8.
Gaurav Bharaj, Stelian Coros, Bernhard Thomaszewski, James Tompkin, Bernd Bickel,
and Hanspeter Pfister. 2015. Computational Design of Walking Automata. In Proc.
ACM SIGGRAPH/Eurographics Symp. on Computer Animation. 93–100.
Duygu Ceylan, Wilmot Li, Niloy J. Mitra, Maneesh Agrawala, and Mark Pauly. 2013.
Designing and Fabricating Mechanical Automata from Mocap Sequences. ACM
Trans. on Graph. (SIGGRAPH Asia) 32, 6 (2013), 186:1–186:11.
Yingjie Cheng, Yucheng Sun, Peng Song, and Ligang Liu. 2021. Spatial-Temporal
Motion Control via Composite Cam-follower Mechanisms. ACM Trans. on Graph.
(SIGGRAPH Asia) 40, 6 (2021), 270:1–270:15.
Jinkui Chu and Jianwei Sun. 2010. A New Approach to Dimension Synthesis of Spatial
Four-Bar Linkage Through Numerical Atlas Method. Journal of Mechanisms andRobotics 2, 4 (2010), 041004:1–041004:14.
Wen-Yeuan Chung. 2015. Synthesis of Spatial Mechanism UR-2SS for Path Generation.
Journal of Mechanisms and Robotics 7, 4 (2015), 041009:1–041009:9.
Stelian Coros, Bernhard Thomaszewski, Gioacchino Noris, Shinjiro Sueda, Moira Forberg, Robert W. Sumner, Wojciech Matusik, and Bernd Bickel. 2013. Computational
Design of Mechanical Characters. ACM Trans. on Graph. (SIGGRAPH) 32, 4 (2013),
83:1–83:12.
Clement Gosselin and Jorge Angeles. 1990. Singularity Analysis of Closed-loop Kinematic Chains. IEEE Transactions on Robotics and Automation 6, 3 (1990), 281–290.
Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A Simple C++ Geometry Processing
Library. https://libigl.github.io/.
F. J. Kay and R. E. Haws. 1975. Adjustable Mechanisms for Exact Path Generation.
Journal of Engineering for Industry 97, 2 (1975), 702–707.
James Kennedy and Russell Eberhart. 1995. Particle Swarm Optimization. In Proc. Int.
Conf. on Neural Networks. 1942–1948.
Z. Li, G. Nawratil, F. Rist, and M. Hensel. 2020. Invertible Paradoxic Loop Structures forTransformable Design. Comp. Graph. Forum (Eurographics) 39, 2 (2020), 261–275.
Wenrui Liu, Jianwei Sun, and Jinkui Chu. 2020. Synthesis of a Spatial RRSS Mechanism
for Path Generation Using the Numerical Atlas Method. Journal of Mechanical
Design 142, 1 (2020), 012303:1–012303:12.
Dominik Mannhart, Fabio Dubois, Karen Bodie, Victor Klemm, Alessandro Morra, andMarco Hutter. 2020. CAMI - Analysis, Design and Realization of a Force-Compliant
Variable Cam System. In Proc. IEEE Int. Conf. on Robotics and Automation. 850–856.
Vittorio Megaro, Bernhard Thomaszewski, Damien Gauge, Eitan Grinspun, Stelian
Coros, and Markus Gross. 2014. ChaCra: An Interactive Design System for Rapid
Character Crafting. In Proc. ACM SIGGRAPH/Eurographics Symp. on Computer Animation. 123–130.
J. P. Merlet. 2006. Jacobian, Manipulability, Condition Number, and Accuracy of Parallel
Robots. Journal of Mechanical Design 128, 1 (2006), 199–206.
D. Mundo, G. Gatti, and D.B. Dooner. 2009. Optimized Five-bar Linkages with Noncircular Gears for Exact Path Generation. Mechanism and Machine Theory 44, 4(2009), 751–760.
D. Mundo, J. Y. Liu, and H. S. Yan. 2006. Optimal Synthesis of Cam-Linkage Mechanisms
for Precise Path Generation. Journal of Mechanical Design 128, 6 (2006), 1253–1260.
G. Nishida, A. Bousseau, and D. G. Aliaga. 2019. Multi-Pose Interactive Linkage Design.
Comp. Graph. Forum (Eurographics) 38, 2 (2019), 277–289.
Zherong Pan, Min Liu, Xifeng Gao, and Dinesh Manocha. 2019. Globally Optimal Joint
Search of Topology and Trajectory for Planar Linkages. In International Symposium
on Robotics Research. 1–16.
Robin Roussel, Marie-Paule Cani, Jean-Claude Léon, and Niloy J. Mitra. 2018. Exploratory Design of Mechanical Devices with Motion Constraints. Comp. & Graph.
(Computational Fabrication) 74 (2018), 244–256.

Exact 3D Path Generation via 3D Cam-Linkage Mechanisms •Kevin Russell, Qiong Shen, and Raj S. Sodhi. 2014. Mechanism Design: Visual andProgrammable Approaches. CRC Press.
Yesh Pal Singh. 1981. Synthesis of Cam-Link Mechanisms for Exact Path Generation.
Mechanism and Machine Theory 16, 4 (1981), 447–457.
Peng Song, Xiaofei Wang, Xiao Tang, Chi-Wing Fu, Hongfei Xu, Ligang Liu, andNiloy J. Mitra. 2017. Computational Design of Wind-up Toys. ACM Trans. on Graph.
(SIGGRAPH Asia) 36, 6 (2017), 238:1–238:13.
J. W. Sun, D. Q. Mu, and J. K. Chu. 2012. Fourier Series Method for Path Generation of
RCCC Mechanism. Proc. of the Institution of Mechanical Engineers, Part C: Journal of
Mechanical Engineering Science 226, 3 (2012), 816–827.
Takuto Takahashi and Hiroshi G. Okuno. 2018. Design and Implementation of Programmable Drawing Automata based on Cam Mechanisms for Representing Spatial
Trajectory. In Proc. IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems. 450–455.
Bernhard Thomaszewski, Stelian Coros, Damien Gauge, Vittorio Megaro, Eitan Grinspun, and Markus Gross. 2014. Computational Design of Linkage-Based Characters.
ACM Trans. on Graph. (SIGGRAPH) 33, 4 (2014), 64:1–64:9.
John J. Uicker, Gordon R. Pennock, and Joseph E. Shigley. 2016. Theory of Machines
and Mechanisms (5th Edition). Oxford University Press.
C. W. Wampler, A. P. Morgan, and A. J. Sommese. 1992. Complete Solution of theNine-Point Path Synthesis Problem for Four-Bar Linkages. Journal of Mechanical
Design 114, 1 (1992), 153–159.
Hao Xu, Tianwen Fu, Peng Song, Mingjun Zhou, Chi-Wing Fu, and Niloy J. Mitra.
2020. Computational Design and Optimization of Non-Circular Gears. Comp. Graph.
Forum (Eurographics) 39, 2 (2020), 399–409.
Hongyi Xu, Espen Knoop, Stelian Coros, and Moritz Bächer. 2018. Bend-It: Design andFabrication of Kinetic Wire Characters. ACM Trans. on Graph. (SIGGRAPH Asia) 37,
6 (2018), 239:1–239:15.
Tsuneo Yoshikawa. 1985. Dynamic Manipulability of Robot Manipulators. In Proc. IEEE
Int. Conf. on Robotics and Automation. 1033–1038.
Lifeng Zhu, Weiwei Xu, John Snyder, Yang Liu, Guoping Wang, and Baining Guo. 2012.
Motion-Guided Mechanical Toy Modeling. ACM Trans. on Graph. (SIGGRAPH Asia)
31, 6 (2012), 127:1–127:10.

225:13

To calculate the matrix ML2 (t) in Equation 6, we concatenate
Equation 24 for links 1 and 2, starting from the fixed link 5:
ML2 (t) = M̃(s2 (t)) M̃(s1 (t)) ML5(27)

where ML5 represents the pose of the fixed link L 5 .

APPENDIXWe describe how we formulate the constraint CL in Equation 4 forour 5-bar spatial linkage. For each link Li , 1 ≤ i ≤ 5, we denote its
two neighboring links as Lh and L j , among which Li and Lh are connected by joint Jk while Li and L j are connected by joint Jl ; see theinset. At time t, the pose of each link Li
can be calculated based on its neighboringlink’s pose and the corresponding joint angle. For example, we calculate the link Li ’spose MLi (t) based on its neighboring link
Lh ’s pose MLh (t) and the joint angle sk (t):J

MLi (t) = MLJ i M(sk (t)) MLk MLh (t)
k

(23)

h

where M(sk (t)) is the matrix representation of the joint angle sk (t),MLh (t) represents the link Lh ’s pose with respect to its center, andJ
MLk is a constant matrix that represents a translation from thehjoint Jk ’s center to the link Lh ’s center. To simplify the notation, we
re-write Equation 23 as:MLi (t) = M̃(sk (t)) MLh (t)(24)

Jwhere M̃(sk (t)) = MLJ i M(sk (t)) MLk .
khSince our 5-bar spatial linkage is a single loop of five joints, weconcatenate Equation 24 for every joint in the loop and get:M̃(s5 (t)) M̃(s4 (t)) M̃(s3 (t)) M̃(s2 (t)) M̃(s1 (t)) = I(25)

Hence, the constraint denoted as ML can be written as:
ML = M̃(s5 (t)) M̃(s4 (t)) M̃(s3 (t)) M̃(s2 (t)) M̃(s1 (t)) − I = 0 (26)
We obtain the constraint CL by concatenating the 4 × 4 matrix ML(ignoring the last row ) into a 12 × 1 column vector.
ACM Trans. Graph., Vol. 41, No. 6, Article 225. Publication date: December 2022.