Beady: Interactive Beadwork Design and Construction
Yuki Igarashi∗
University of Tsukuba

Takeo Igarashi†
The University of Tokyo / JST ERATO

Jun Mitani‡
University of Tsukuba / JST ERATO

Figure 1: System overview. (a) The user creates a design model either by modeling from scratch or converting an existing polygonal model.
(b) The system runs a simulation to predict the resulting shape. (c) The beadwork model visualizes the expected result. (d) The systemcomputes the wire path. (e) The system provides a step-by-step construction guide. (f) The user manually constructs the physical beadwork.

Abstract

1 Introduction

We introduce the interactive system “Beady” to assist the designand construction of customized 3D beadwork. The user first createsa polygonal mesh model called the design model that represents theoverall structure of the beadwork. Each edge of the mesh model
corresponds to a bead in the beadwork. We provide two methods tocreate the design model. One is interactive modeling from scratch.
The user defines the mesh topology with gestural interaction andthe system continuously adjusts edge lengths by considering thephysical constraints among neighboring beads. The other is automatic conversion that takes an existing polygonal model as input
and generates a near-hexagonal mesh model with a near-uniform
edge length as output. The system then converts the design model
into a beadwork model with the appropriate wiring. Computationof an appropriate wiring path requires careful consideration, and we
present an algorithm based on face stripification of the mesh. The
system also provides a visual step-by-step guide to assist the manual beadwork construction process. We show several beadwork designs constructed by the authors and by test users using the system.

Beadwork is the art of connecting beads together by wires. Whilecommon beadwork is two-dimensional (2D), three-dimensional(3D) beadwork [Maki 2004; Freese 2007] is also popular in oriental regions such as Japan and China. However, the design andconstruction of 3D beadwork is very difficult. The final shape isdefined by the complicated three-dimensional interaction between
beads and wires, thus making the beadwork very difficult to design manually. One also needs to specify an appropriate wire path
to hold the beads together and to manually insert the wire into thebeads one by one, following the path to construct the beadwork.
Careful observation of existing beadwork structures shows several
geometrically interesting problems, which make beadwork design
a technical challenge.

CR Categories: I.3.6 [Computer Graphics]: Methodology andTechniques—Interaction Techniques; I.3.5 [Computer Graphics]:
Computational Geometry and Object Modeling—Geometric Algorithms;
Keywords: polygonal meshes, user interface, simplification, face
strip, construction guide, wire path planning, beadwork
Links:DL

PDF∗ e-mail: yukim@acm.org† e-mail: takeo@acm.org‡ e-mail: mitani@cs.tsukuba.ac.jp

Figure 2: Example beadworks created from existing 3D models. These are CG shapes rendered using commercial software (efrontier Shade8).
This paper presents an interactive computational system to assist
the design and construction of original beadwork. Figure 1 shows
the overall process. The user first creates a polygonal mesh model,
called a design model, which represents the overall structure of the
beadwork (Figure 1(a)). A bead of the beadwork is represented asan edge (not a vertex) of the design model. The system then converts the design model into a beadwork model by placing beads
on the edges with the appropriate wiring (Figure 1(c)). The user
specifies the color and shape of individual beads in the beadwork
model by using a painting interface. Finally, the user manuallyconstructs the physical beadwork by following the step-by-step instruction generated by the system (Figures 1(e) and (f)).

We provide two methods to create the design model. First, the system provides a specialized modeling interface for the design of asimple polygonal mesh model with near-uniform edge length. The
user first builds an approximate shape by combining predefinedprimitives. Next, the user modifies the shape by applying a basic mesh editing operation such as face extrusion, edge insertion,edge split, edge deletion, or vertex merger. We provide a modelessgestural interaction for applying these operations to support rapid
exploration. The system also allows the user to add auxiliary parts(bead chains) to the model.
Second, the system provides an automatic method that converts anexisting triangular mesh model to a design model. The system first
applies mesh reduction to the model until the number of edges (i.e.,
number of beads) is equal to the user-defined target number. The
system then makes a dual of the triangular mesh, yielding a polygonal mesh with all vertices with valence three and mostly hexagonal
faces. Figure 2 shows examples of beadworks created from popularmesh models.
Conversion of the design model into a beadwork model consists of
two main steps. The first step is geometry computation. The systemgenerates another polygonal mesh model, called a structure model,
by adding local wire connections between neighboring beads of thedesign model (Figure 1(b)). The system runs a physical simulation to compute the geometry of the resulting beadwork model byconsidering the physical interaction among beads and wires. This
simulation runs during interactive modeling and updates the shapeof the design model after each editing operation. The second stepis wire path planning (Figure 1(d)). The wire path should be appropriately defined to efficiently connect the beads. We show that avalid wire path is given as an Eulerian cycle on a graph derived fromthe structure model. However, a single wire path often makes the
manual construction process difficult. We therefore present an algorithm that covers the design model with multiple face strips withshort branches, where each strip corresponds to a wire.
The contributions of this work are summarized as follows. (1) We
present a mesh modeling user interface specialized for beadwork
models by combining gestural operations and physical simulations.
(2) We present an algorithm to convert an existing triangular meshmodel into a design model appropriate for beadwork. The algorithm applies mesh reduction while applying mesh beautification to
obtain a mesh whose edges have almost uniform length. It thenmakes a dual of the triangular mesh to obtain a near-hexagonalmesh model. (3) We present an algorithm based on face stripification to compute the wire paths for a beadwork model designedby the user. (4) We present a step-by-step construction guide to assist the user in the manual construction process. (5) We show thefeasibility and effectiveness of our approach by presenting a real
implementation by test users.

2

per toy model has to be represented as a set of developable
patches. This kind of restriction is often discussed in the design of architecture consisting of freeform surfaces [Liu et al. 2006;
Schiftner et al. 2009]. Pottmann et al. [2010] called this new research area architectural geometry. Related to this trend, recent
work presented methods to slightly modify the geometry of a polygonal mesh to reduce the number of unique polygons contained in theoriginal model [Singh and Schaefer 2010; Eigensatz et al. 2010;
Fu et al. 2010].
Resampling of a polygonal mesh is a well-studied area.
Mesh reduction and simplification methods compute a
low-resolution approximation of a high-resolution original
mesh [Garland and Heckbert 1997; Cohen-Steiner et al. 2004].
However, these methods usually do not consider the uniform
distribution of vertices. Retiling and beautification methods
seek a uniform distribution of vertices on the original mesh
These methods
surface [Turk 1992; Markosian et al. 1999].
assume a reasonably high vertex density and can fail to cover ahigh-curvature region with a low-resolution mesh. Our reduction
is closely related to the problems of isotropic remeshing andVoronoi surface tessellation [Yan et al. 2009; Lévy and Liu 2010;
Nieser et al. 2010]. The resolution of the resampled mesh in theirwork is significantly higher than that in our work. Samplingwith a low resolution mesh is difficult because the subject could
easily loose sharp features that were in the original mesh, which
we address in this work. Igarashi et al. [2003] extended the skinalgorithm [Markosian et al. 1999] to handle high-curvature regions
by adjusting the vertex density depending on the curvature. Our
method is also an extension of the skin algorithm, but it uses a
constant vertex density.

3 Observation of Existing Beadwork
We investigated existing beadworks in textbooks and in local shops
as a basis for the user interface and the algorithm design. We observed that a 3D beadwork model can be seen as a closed manifold polygonal mesh model with mostly uniform edge lengths.
Each edge of the polygonal mesh corresponds to a bead, and eachface corresponds to a cycle formed by the beads. Faces in a lowcurvature region are mostly hexagonal, and pentagons and quads
appear occasionally in high-curvature regions. Non-manifold structures such as linear chains are used occasionally, but they can beseen as extra attachments to the main manifold mesh. Most beadwork models consist of a few separate parts, such as head, body,arms, and legs, and use one wire for each part. A wire passes
through each bead two times to connect the bead to the left- andright-hand side face of the edge (bead).
As shown in Figure 3 [Maki 2004], textbooks use a 2D diagram
to explain how to construct a beadwork model. This is seen as a

Related Work

Various interesting systems have been proposed recently to support the fabrication of physical objects using state-of-the-art graphics techniques. One approach is to take a given 3D model as input and generate a physical model as output, such as a 3D polyomino puzzle [Lo et al. 2009], a bas-relief [Weyrich et al. 2007],
a paper craft [Mitani and Suzuki 2004; Shatz et al. 2006], a popup
card [Li et al. 2010; Li et al. 2011; Iizuka et al. 2011], a stuffed animal [Julius et al. 2005], and a knitted animal [Igarashi et al. 2008].
Another approach is to support the interactive design of a physicalmodel by sketching, such as a garment [Decaudin et al. 2006] or aplush toy [Mori and Igarashi 2007].
The design of a 3D model of a real-world object requires thatcertain physical constraints be satisfied. For example, a pa-

Figure 3: A beadwork and a construction guide in a textbook. Cited
from [Maki 2004] with permission.

flattening of the polygonal mesh. The construction process starts
by putting a bead in the middle of a long wire and then adding
beads one by one to both ends of the wire. These two ends of thewire are color coded. One half of the wire is shown in blue and theother half is shown in red. Construction proceeds by forming thefaces of the polygon one by one with the red and blue wires.

4

Face extrusion

Edge deletion

Edge insertion

Edge split

Vertex merger

WorkflowThis section describes the system from the user’s point of view.
The user designs a 3D beadwork as a simple polygonal mesh calleda design model. An edge of the mesh corresponds to a bead, andthus the edges have mostly uniform lengths (exact length is determined by a physical simulation that considers the interaction between wires and beads). Each face is not necessarily planar. The
user can use either an interactive modeling interface or an automaticconversion to obtain a design model. Next, the user defines the appearance of the model by choosing the shape and color of eachbead. The system guides the manual construction of the physicalbeadwork by displaying a step-by-step guide to the user.

4.1

Primitive addition

Add chain

Face connection

Figure 4: Mesh editing operations.

Interactive Modeling

The user creates the geometry of the beadwork model interactively.
Starting with basic primitives, the user interactively edits the primitives by using gestural operations. The system runs a physical simulation (Section 5.3) after each editing operation and updates themesh on the screen to enforce the constraint. The user only specifies
the topology of the mesh and the vertex positions are automaticallydecided.

Figure 5: Example of a modeling sequence using the gestural interface. The user only specifies the topology of the mesh by using
the gestural interface. The vertex positions are automatically given
by a physical simulation.

Combining Basic Primitives: The user starts a new model by

combining the predefined primitives. Similar method was used in
the modeling system presented by Leblanc et al. [2011], in which
the user defines a shape as a collection of generalized cuboid primitives. We provide a regular polyhedron and some semi-regularpolyhedrons as primitives. All primitives consist of edges of a unit
length. A copy of a selected primitive appears at the center of thescreen. The user can also append a primitive to the model by clicking on a face of the model. The system searches for a face with thesame number of edges in the selected primitive and pastes it on themodel by merging the corresponding faces. Nothing happens when
the selected primitive does not have a face with the same numberof edges. We chose this approach because we observed that mostexisting beadwork models can be seen as a combination of these
simple primitives. Pasting a primitive is useful for designing thehead, arms, and legs of animal models.

triangular mesh into a near-hexagonal mesh with almost uniform
edge lengths (Figure 6). The number of resulting edges is set by theuser.

Figure 6: Examples of automatic conversions from existing 3Dmodels.

Mesh Editing Operations: The user modifies the model by using

the mesh editing operations shown in Figure 4. These operations
are designed to maintain the mesh as a manifold. The overall shapeis already given as a combination of primitives and we expect thatthese editing operations are only used to adjust the shape locally.
We implemented these editing operations as a modeless contextsensitive gestural interaction. The user either clicks on a component(face, edge, or vertex) or draws a short line by a dragging operation,and the system takes the appropriate action. The physical simulation adjusts the overall geometry after each of these operations. We
show an example of a modeling sequence in Figure 5.

We chose to use hexagonal meshes because we observed that existing beadworks, especially large ones, typically consist of hexagonal faces. This is probably because a hexagonal mesh (honeycomb
lattice) is the most efficient structure to hold a flat surface with minimum support materials. We also found that a near-hexagonal meshobtained as a dual of a triangular mesh yields a more aestheticallypleasing beadwork model after running the physical simulation, as
shown in Figure 7. This is probably because wires make the surface
as flat as possible in a hexagonal mesh, but it is not possible to do
so in a triangular mesh due to insufficient flexibility.

4.2

4.3 Appearance Design and Construction Guide

Importing Existing Polygonal Models

The user can also import an existing polygonal mesh model into thesystem. The current implementation requires the model to form amanifold surface and consists of triangular faces. It also expects themesh to be reasonably well sampled. The system then converts the

The system shows the resulting beadwork model on the screen during interactive modeling. The user paints the bead model by using
paint brush tools (Figure 8). Then, the user selects the bead shapeand color, and paints the bead model by dragging the mouse. The

(a)Figure 7: Comparison of triangular and mostly hexagonal meshes
after the physical simulation. The hexagonal mesh is obtained as adual of the triangular mesh.

(c)

(b)

(d)

(e)

(f)

Figure 9: An example of the visual construction guide. (a) Initialstate. (b),(c),(f) Blue wire passes a newly added bead. (d) Red wire
passes a newly added bead. (e) Red wire passes an existing bead.

5 Algorithm
shape and color of the beads designated by the mouse cursor arechanged. We also provide a flood fill operation. Our current implementation uses pre-defined shapes and colors, but we plan tosupport customized bead shapes and colors in the future.

The system maintains three different model representations. The
first one is the design model, which is a polygonal mesh model
shown to the user during interactive modeling (Figure 1(a)). Eachedge of the design model corresponds to a bead and each vertex
corresponds to a set of wire segments connecting the surrounding
beads. The second representation is the structure model, which
is another polygonal mesh model that represents a more detailed
structure (Figure 1(b)). This model is used for computing the appropriate shape of the beadwork by considering the physical constraints among beads. A structure model consists of bead edges,
each of which represents a bead, and wire edges, each of which
represents a wire fragment between two beads. The third representation is the beadwork model, which consists of beads connected
together by wires with an appropriate wire path (Figures 1(c) and(d)). This section first describes the algorithm to convert an existing 3D model to a design model. It then describes the constructionof the structure model and the physical simulation of the structure
model. Finally, it describes the computation of the wire path necessary for construction of the beadwork model.

5.1 Converting a 3D Model to a Beadwork Model
Figure 8: Screenshot of our system in the painting mode.

The system guides the manual construction of a physical beadworkby showing step-by-step instruction. The traditional printed beadwork instructions in textbooks use a specialized 2D diagram representation as the guide (Figure 3), but it is very tedious and difficult because the user needs to keep track of the relation between
beads in the physical 3D beadwork and those in the 2D instruction.
Our step-by-step instruction takes advantage of the expressivenessof interactive 3D graphics and makes it easier to understand theconstruction procedure. This interactive guide is inspired by recent work on assembly instruction [Agrawala et al. 2003], cutaway
illustration [Li et al. 2007], and exploded diagrams [Li et al. 2008].
The construction guide shows which wire passes which bead ineach step as 3D graphics. Figure 9 shows an example sequence.
The user can view each step from an arbitrary viewing direction.
The user presses the “next” button to proceed to the next step andpresses the “prev” button to return to the previous step. The construction starts by placing a bead in the middle of a long wire (Figure 9(a)). One side of the wire is blue and the other side is red.
The system shows the initial length of each side. The construction proceeds by inserting the blue or the red wire into an existingor new bead. A loop shows the wire that is used in the step (Figure 9(b) through (f)), and an arrow indicates that the wire passes abead newly added to the beadwork (Figures 9(b), (c), (d), and (f)).
Otherwise, the wire passes a bead already included in the beadwork(Figure 9(e)).

Our goal is to convert a 3D triangular mesh model into a designmodel, which is a low-resolution near-hexagonal mesh with almost
uniform edge length. The number of edges in the resulting designmodel is given by the user. The process consists of two steps (Figure 10). First, the system applies mesh reduction to the input mesh,while applying mesh beautification to make the edge length nearuniform. Second, the system constructs a near-hexagonal mesh bymaking a dual of the reduced triangular mesh.

Input mesh#edges 3111

Reduction mesh#edges 600

Dual-polyhedron

Apply simulation

Figure 10: Automatic conversion.
The mesh reduction process iteratively removes the shortest edge
while applying mesh beautification after each iteration. We use thealgorithm described in [Markosian et al. 1999] with the offset set
to zero for the beautification. The algorithm repeatedly adjusts the
position and connectivity of the mesh to obtain a mesh with a nearuniform edge length and a near-uniform vertex distribution while
preserving the original overall shape. Specifically, the system firstmakes a copy (called a skin mesh) of the input mesh (called a skeleton mesh) and moves the skin vertices to the centers of surrounding

vertices while updating its connectivity on the fixed skeleton mesh.
We make three changes to the original skin algorithm to satisfy ourneeds, First, we only apply edge swap and do not apply edge split
and edge collapse in the beautification process so that it does notchange the number of edges during beautification. This works wellwhen the edges in the input mesh are sufficiently short. Otherwise, it is necessary to refine the mesh as a pre-process. Second,
we move the skin vertices only on the skeleton vertices discretely
for efficiency. This is also because the skin mesh becomes very
coarse in our case and the center of neighboring skin vertices athigh curvature region goes deep inside of the skeleton mesh, making the resulting skin mesh non-uniform after pushing the center
to the skeleton surface (Figure 11). We therefore discretely evaluate nearby skeleton vertices and pick the one that produces themost uniform distribution of skin vertices on the skeleton surface.
Specifically, for each nearby skeleton vertex we compute distances
to the neighboring skin vertices and pick the maximum. We thentake the skin vertex that returns the minimum of these maximums.
This discrete method works for us because we only need final meshconnectivity and specific vertex positions are less important.

Figure 11: Vertex relocation. The original Skin algorithm moves
the vertex to the center of neighboring vertices and then pushes
it to the skeleton surface (left). Our method discretely evaluates
nearby skeleton vertices and picks the one that minimizes the largest
distance to the neighboring skin vertices (right).
Finally, we explicitly detect cases where a protrusion of the skeleton mesh sticks out of the skin mesh and pull the skin mesh to thetip of the protrusion to cover it. This problem occurs because theskin vertices always stay on the skeleton mesh but skin edges andfaces can go inside of the skeleton mesh (Figure 12). To fix thisefficiently, we monitor the distance from each skeleton vertex tothe nearest skin vertex and constrain the skin vertex to the skeleton
vertex position when the distance exceeds a predefined threshold α(2-5% of bounding box of the input mesh). The original paper used
local search to keep track of a skeleton vertex nearest to each skinvertex. We use the same algorithm to keep track of a skin vertex
nearest to each skeleton vertex.
Construction of the near-hexagonal mesh is straightforward. The
system simply replaces vertices and faces of the triangular meshwith faces and vertices of the hexagonal mesh, respectively. Eachvertex of the hexagonal mesh has valence three by construction,and each face typically has five to seven edges. The system thenperforms a physical simulation (Section 5.3) to obtain the final geometry. Strictly speaking, we want to have uniform edge lengths in
the hexagonal dual mesh, so the edge length of the triangular meshshould vary depending on the vertex valence. However, we ignore
this in the current implementation because the valences are typically 5 to 7 and the differences are small. In addition, uniformity ofthe edge length in the hexagonal mesh is not rigorous, because thelength changes after the physical simulation.

5.2

Construction of the Structure Model

The structure model is generated by adding a wire edge to eachcorner of a face in the design model (Figure 13, left). Each valencen vertex is replaced by n wire edges and n new vertices between
them. This construction naturally connects two wire edges to each

Skeleton mesh

Original Skin algorithm

Our algorithm

Figure 12: The original Skin algorithm can fail to cover a protrusion in the skeleton mesh. We explicitly identify such a case and fix
a skin mesh vertex to the tip of the protrusion.

end of a bead edge so that a wire passes through each bead twotimes, as in existing beadworks. The initial position of a new vertex
is given by moving the original vertex slightly toward the centerof the corresponding edge. We handle linear chains separately after
applying the above procedure to the design model (Figure 13, right).
The system connects each linear chain to one of the wire edges thatshare a vertex in the design model, i.e., the wire edge is split andconnected to an end of a linear chain.

Figure 13: Construction of the structure model without (left) andwith (right) a chain. Orange and green edges are bead edges andwire edges, respectively.

5.3 Physical Simulation of the Structure Model
The system adjusts the shape of the structure model to satisfy thephysical constraints among neighboring beads: beads do not intersect each other and beads connected by a wire are as closely locatedas possible. We achieve this by running a simple mass-spring simulation cycle 500 times after each mesh editing operation. The system then updates the design model by moving its vertex positions
to the center of corresponding vertices of the structure model.
We apply the following three forces to the vertices of the structure
model in the simulation. The first force is edge springs to keep theedges to the desired lengths. The rest length of a bead edge is set
to the length of the bead, and the rest length of a wire edge is set
to zero. The second force is angular springs that keep the wires as
straight as possible. The system examines the angles between eachwire edge and the bead edges connected to it, and applies a force tokeep them straight. The third force is a repulsion force to preventthe neighboring beads from penetrating each other.

5.4 Computing the Wire Paths
A wire path defines the order in which a wire connects the beads tohold them in place. Based on careful examination of existing beadwork designs, we made the following three goals for the algorithm.
First, wires should pass through a bead for the minimum numberof times necessary to hold the bead. In our case, it is always two,
except for chains. Second, the minimum number of wires should be
used to reduce the need for cutting and tying a wire. Third, the wire
path should be designed so that the bead in the beadwork during theconstruction is as stable as possible. We consider a bead to be stable
when the position of the bead is stably fixed to a specific location by
the wires; that is, the bead belongs to a completed face (Figure 14).

An unstable bead makes manual construction extremely difficult
because the user has to manually hold it. It is therefore crucial todesign a wire path that minimizes the occurrence of unstable beads
during construction. The second and third requirements conflictwith each other, and so our method balances the two while always
satisfying the first requirement.The following wire path planningalgorithm works for an arbitrary manifold surface regardless of thevertex valence or the surface genus.

(a) Design model(b) Structure model(c) Wire graph(d) An Euler path of (c)3stable bead4

unstable bead

1

2

5
6

Figure 14: Stable and unstable beads appearing during construction.
Given the design model (Figure 15(a)), we start the process withthe structure model (Figure 15(b)). The structure model defines the
local wire connectivity. A global wire path (Figure 15(c)) is given
as a loop that meets all wire edges once and all bead edges twice.
This is the Eulerian cycle of the wire graph (Figure 15(d)), obtainedby contracting the bead edges into vertices, with an additional constraint that a wire going into a bead should go out from the otherside of the bead. The existence of an Eulerian cycle is guaranteedby the construction because each bead edge always has four wireedges. Various methods exist for obtaining such an Eulerian cycle.
However, an arbitrary Eulerian cycle (e.g., Figure 15(d)) can be inconvenient in the manual construction process because it can cause
many unstable beads during construction (Figure 15(e)). We carefully examined existing beadwork designs and found that the problem of reducing unstable beads can be solved by using a face strip(Figures 15(f) and (g)). The design model is covered by a face strip,
and then a wire path is placed so that it completes the faces in the
strip one by one. This method makes all the beads in the previously
visited faces stable during construction (Figure 15(h)). In cases thatthe model is not fully covered by a single strip, the system adds remaining faces as a branch to the strip, and places the wire path sothat it strays off from the strip, visits the faces in the branch, andgoes back to the strip (Figure 16). Such branches cause unstablebeads, and so we restrict the length of a branch to one. We create
independent face strips with branches for the remaining area until
strips and their branches cover all the faces. Figure 17 shows examples of the stripification results. The first strip covers most of
the surface and additional strips cover protrusions such as ears andarms.
The computation of a single face strip without any branch corresponds to finding a Hamiltonian path on the dual graph obtainedby replacing the faces with vertices of the design model. However, it is not guaranteed that such a path exists. A practicalalternative is constructing a spanning tree with some branches,and various heuristics have been presented for improving therendering performance [Evans et al. 1996] and the data compression [Taubin and Rossignac 1998]. We also use a heuristic method
specialized for our problem. Our method is a greedy expansion
starting from a base face, followed by adding faces adjacent to theface at the end of the strip. We select one among the candidate faces
so that the boundary length is minimized. The boundary length isgiven as the total length of the edges between the current face strip
and the remaining faces. This keeps the intermediate beadwork
model compact, thus making manual construction easier. We apply
backtracking when the expansion is trapped into a dead end. We
run this greedy expansion search starting from all faces and use themost successful result.

(e) Intermediatestatus of (d)(f) Typical wire path(g) Face strip
strucutre of (f)(h) Intermediatestatus of (f)Figure 15: Details of the wire path-planning algorithm.

(a)

(b)

(c)

(d)

(e)

Figure 16: Stripification process. (a) Initial strip. (b) Adding
branches. (c) Second strip and its branches. (d) Wire paths forthe strips. (e) Modified wire paths to cover the branches.

(34, 0)(95, 4), (4, 0)(149, 3)Figure 17: Stripification results. The thick tan lines show the main
strips and the thin lines show the branches. Each tuple corresponds
to a strip (the number of faces in the strip and the number of its
branches).

6 Results
The prototype system is implemented using Java on a laptop (1.2
GHz CPU, 2 GB RAM). Figure 18 show some example beadwork
models designed and constructed by using the system. Designingthese models required 10 to 20 minutes, which included creative experimentation and exploration. Manual construction of each modelby following the guide required a few hours. The beadwork bear isan exception: it was bought at a local shop. We created the modelby referring to the product, which required approximately 90 minutes. Table 1 shows the performance measurements of the designed
models in Figures 1 and 18. Modeling and wire path planning werecompleted almost instantly in most cases, whereas they lasted a few
seconds in the complicated case.
Figure 2 shows example beadworks created from existing 3D models. These are CG models rendered using commercial software. We
used 600 beads for these models to obtain reasonable results. Ideally we wanted to use fewer beads to make the manual construction
easier, but it was difficult to obtain aesthetically pleasing results
by using the mesh reduction approach. Extreme simplification re-Figure 19: Photo of the real beadworks. The diameter of a bead is
4mm.

Figure 18: Example models designed by the authors. Top: designmodels. Middle: beadwork models. Bottom: real beadworks.

Table 1: Performance measurements of the models in Figures 1
and 18.
# beads
Simulation (sec.)
Wire (sec.)

Dog

PenguinLizard

Mouse

Bear

203
1.3
0.7

66
0.5
0.2

77
0.5
0.1

96
0.7
0.3

372
2.5
5.6

quires artistic skill, as in the design of low-resolution bitmap images(pixel arts), and it is necessary to develop completely a different algorithm. Physical construction took approximately 15 hours eachfor the bunny and dragon (Figure 19). Table 2 shows the performance measurements and relevant statistics. Table 3 shows that theconverted design models are mostly hexagonal.

7

by the subjects and the time required to design each: the first three
are photos of the real beadwork and the others are CG models. Table 4 shows the gestural operations for each beadwork. The mostused operation during the study was “Add primitive.” This operation was used to design the rough forms at the beginning. Other
operations were used to refine the details. The “Add chain” operation was used to add detailed parts at the finish. Although thisoperation generates a non-manifold mesh, it served an importantrole in designing the beadwork.

seal (20min)cat (20min)

bear (25min)

User Experience

We asked five test users to try the interactive modeling system andobtained their feedback. They used interactive geometry modelingto create their original design. The users were university students
in the Department of Computer Science who did not have any experience in making beadwork. The users were given a five-minutetutorial and free practice for another five minutes. All of the subjects learned the operations instantly without any difficulties. Then,
we asked the users to design their own original beadwork until they
were satisfied with the design. Figure 20 shows the results designed

Table 2: Performance measurements and relevant statistics to convert existing 3D models into beadwork models in Figure 2.
Init #edges# beads
distance α
fixed #vertices
Convert (ms)· Reduction· Dual· Sim
Wire (ms)DragonArmadillo

Horse

Squirrel

Bunny

Bear

2796
600
0.02
102
2930
1462
28
1440
7468

2992
600
0.05
23
3086
1585
25
1476
10833

3000
600
0.05
11
3013
1522
23
1468
14527

3063
600
0.05
3
2943
1426
24
1493
4677

3111
600
0.02
81
3092
1589
34
1469
14006

5964
600
0.03
20
7939
6396
26
1517
7768

CG

CG

airplane (25min)flower (25min)Figure 20: 3D models designed by the subjects and the time required to design each. All models were the subjects’ original designs.
Most comments from the subjects were positive, such as “It wasvery helpful that the system displayed the bead 3D model when
I edited the mesh model,” and “I could concentrate on designing
shapes without thinking about the structure of the beadwork.” We
believe that our system successfully enabled these novice users todesign their own original beadwork. Some users offered suggestions, such as “It would be nice if the system provided an operation
to add flat planes,” and “It was difficult to control the location ofbeads precisely while I completed my beadwork.” These suggestions are possible enhancements for varying the modeling operations. Three users constructed the designed beadworks manuallyby referring to the step-by-step guide. We provided large beads(approximately 10 mm in diameter) to make the work easy. The
beadworks of the first three models in Figure 20 were successfully
constructed within a half day.

Table 3: The ratio of hexagons and other polygons in the converted design models in Figure 2.

hhhh # of sides per face
hhhh
hhh
Model

3

4

5

6

7

8

9

10

Bunny
DragonBear
Armadillo
Horse
Squirrel

3 (1%)
9 (5%)
1 (0%)
10 (5%)
5 (2%)
3 (1%)

13 (6%)
20 (10%)6 (3%)
12 (6%)
5 (2%)
5 (2%)

36 (18%)23 (12%)42 (21%)27 (13%)30 (15%)49 (24%)106 (52%)
98 (49%)114 (56%)
100 (50%)127 (63%)
107 (53%)

33 (16%)31 (16%)34 (17%)42 (21%)29 (14%)24 (12%)8 (4%)
10 (5%)
4 (2%)
7 (3%)
4 (2%)
10 (5%)

2 (1%)
4 (2%)
1 (0%)
3 (1%)
2 (1%)
4 (2%)

1 (0%)
1 (1%)
0 (0%)
1 (0%)
0 (0%)
0 (0%)

By interviewing professional beadwork designers, we confirmedthat our system is very useful for designing beadwork, even for professionals. In their company, a 3D polygon model was first createdusing a standard 3D modeling software. A professional designer
then designed a beadwork model based on the 3D model. In thisway, it was confirmed that both methods (gestural modeling andautomatic conversion) are compatible with current practice and are
immediately applicable.

Table 4: Gestural operations for each beadwork in Figure 20.

8

Users

Seal

Cat

Bear

Airplane

FlowerUndo
Add primitive
Add chain
Edge deletion
Face extrusion
Edge split
Vertex merge
Edge insertion

27
3
5
31
17
2
15
0

21
21
13
0
5
0
0
8

47
10
6
5
41
2
0
16

19
25
9
16
32
21
0
0

39
67
25
2
4
17
0
3

Limitations and Future Work

Our current interactive modeling interface was designed for general polygonal meshes and not specifically designed for hexagonal
meshes. We did not find this very problematic because the users
only designed small beadworks in interactive editing and the requirement for a hexagonal mesh is not very important in such small
beadworks. A hexagonal mesh is important for larger beadworks
and it might be useful to implement some mechanism to facilitate
construction and editing of hexagonal meshes in the future.

is symmetric, so automatic symmetrization of the model during interactive editing could be very helpful. Symmetry could also be
useful for computing better wire paths.
The final reduced mesh shape is determined by the combination ofparameters and the total number of beads specified by the user. If
the user specifies a very small number of beads, the final mesh cancontain self-intersections, as shown in Figure 21, because we currently do not consider collisions between faces and edges. If the
input model contains thin parts, such as the legs of a horse, it isbetter to use chains, as shown in the mouse model in Figure 18. We
plan to extend the conversion algorithm to produce chains automatically by considering the skeletal structure of the input mesh.
Creating complicated objects byassembling simple primitives withwires is a very general idea andthe method presented in this paper could be useful for designingphysical objects other than beadwork. For example, the sameuser interface and algorithm canbe used for the design of a model
consisting of equal-length straws
Figure 22: Straw model.
tied together by a string, as shownin Figure 22. An important difference is that quads and pentagons are not stable in a straw model.
Nevertheless, we plan to extend our techniques to support the design of such physical objects, including a potential form of architecture.

Acknowledgments
We are grateful to Maneesh Agrawala for his helpful advice. We
would also like to thank the professional beadwork designers,
Meiko Aikawa, Katsuko Uchida, Kimiko Nara and Yumiko Satouof Tougenkyou, Inc., for their insightful comments. Finally, wewish to express our appreciation to the test users for their cooperation and to the anonymous reviewers for their valuable feedback.
This work was supported in part by a Grant-in-Aid for JSPS Fellows.

References
Figure 21: Failure cases of simplification. The number of edges is
200 and the parameter α is 0.02 in both models.
Our target in this work is very basic beadwork models. Many more
techniques are used in real beadwork, such as combining beads ofdifferent sizes and creating non-manifold structures other than simple open chains. It is our future work to support these advanced
techniques. Wire may need to visit some edges more than twice
when there are non-manifold vertices in the mesh. Most beadwork

AGRAWALA , M., P HAN , D., H EISER , J., H AYMAKER , J.,K LINGNER , J., H ANRAHAN , P., AND T VERSKY, B. 2003.
Designing effective step-by-step assembly instructions. ACM
Trans. Graph. 22, 3, 828–837.
C OHEN -S TEINER , D., A LLIEZ , P., AND D ESBRUN , M. 2004.
Variational shape approximation. ACM Trans. Graph. 23, 3,
905–914.
D ECAUDIN , P., J ULIUS , D., W ITHER , J., B OISSIEUX , L., S HEF FER , A., AND C ANI , M.-P. 2006. Virtual Garments: A fullygeometric approach for clothing design. Comput. Graph. Forum25, 3, 625–634.

M ORI , Y., AND I GARASHI , T. 2007. Plushie: an interactive design
system for plush toys. ACM Trans. Graph. 26, 3, 45:1–45:8.

E IGENSATZ , M., K ILIAN , M., S CHIFTNER , A., M ITRA , N. J.,
P OTTMANN , H., AND PAULY, M. 2010. Paneling architectural
freeform surfaces. ACM Trans. Graph. 29, 4, 45:1–45:10.

N IESER , M., PALACIOS , J., P OLTHIER , K., AND Z HANG , E.
2010. Hexagonal global parameterization of arbitrary surfaces.
In ACM SIGGRAPH ASIA 2010 Sketches, 5:1–5:2.

E VANS , F., S KIENA , S., AND VARSHNEY, A. 1996. Optimizing
triangle strips for fast rendering. In Proc. of the 7th Conference
on Visualization ’96, 319–326.

P OTTMANN , H., H UANG , Q., D ENG , B., S CHIFTNER , A., K IL IAN , M., G UIBAS , L., AND WALLNER , J. 2010. Geodesic
patterns. ACM Trans. Graph. 29, 4, 43:1–43:10.

F REESE , A. 2007. Lovable Beaded Creatures. Sterling Pub Co
Inc.

S CHIFTNER , A., H ÖBINGER , M., WALLNER , J., AND
P OTTMANN , H. 2009. Packing circles and spheres on surfaces.
ACM Trans. Graph. 28, 5, 139:1–139:8.

F U , C.-W., L AI , C.-F., H E , Y., AND C OHEN -O R , D. 2010. K-set
tilable surfaces. ACM Trans. Graph. 29, 4, 44:1–44:6.
G ARLAND , M., AND H ECKBERT, P. S. 1997. Surface simplification using quadric error metrics. In Proc. of SIGGRAPH ’97,
209–216.

S HATZ , I., TAL , A., AND L EIFMAN , G. 2006. Paper craft models
from meshes. Vis. Comput. 22, 9, 825–834.
S INGH , M., AND S CHAEFER , S. 2010. Triangle surfaces withdiscrete equivalence classes. ACM Trans. Graph. 29, 4, 46:1–
46:7.

I GARASHI , T., AND H UGHES , J. F. 2003. Smooth meshes for
sketch-based freeform modeling. In Proc. of the 2003 Symposium on Interactive 3D Graphics, 139–142.

TAUBIN , G., AND ROSSIGNAC , J. 1998. Geometric compression
through topological surgery. ACM Trans. Graph. 17, 2, 84–115.

I GARASHI , Y., I GARASHI , T., AND S UZUKI , H. 2008. Knitting a
3D model. Comput. Graph. Forum 27, 7, 1737–1743.

T URK , G. 1992. Re-tiling polygonal surfaces. SIGGRAPH Comput. Graph. 26, 2, 55–64.

I IZUKA , S., E NDO , Y., M ITANI , J., K ANAMORI , Y., AND F UKUI ,Y. 2011. An interactive design system for pop-up cards with aphysical simulation. Vis. Comput. 27, 6-8, 605–612.

W EYRICH , T., D ENG , J., BARNES , C., RUSINKIEWICZ , S., ANDF INKELSTEIN , A. 2007. Digital bas-relief from 3D scenes.
ACM Trans. Graph. 26, 3.

J ULIUS , D., K RAEVOY, V., AND S HEFFER , A. 2005. D-charts:
Quasi-developablemesh segmentation. Comput. Graph. Forum24, 3, 581–590.

YAN , D.-M., L ÉVY, B., L IU , Y., S UN , F., AND WANG , W. 2009.
Isotropic remeshing with fast and exact computation of restrictedvoronoi diagram. In Proc. of the Symposium on Geometry Processing, 1445–1454.

L EBLANC , L., H OULE , J., AND P OULIN , P. 2011. Modeling withblocks. Vis. Comput. 27, 6-8, 555–563.
L ÉVY, B., AND L IU , Y. 2010. Lp centroidal voronoi tessellationand its applications. ACM Trans. Graph. 29, 4, 119:1–119:11.
L I , W., R ITTER , L., AGRAWALA , M., C URLESS , B., AND
S ALESIN , D. 2007. Interactive cutaway illustrations of complex 3D models. ACM Trans. Graph. 26, 3.
L I , W., AGRAWALA , M., C URLESS , B., AND S ALESIN , D.
2008. Automated generation of interactive 3D exploded view
diagrams. ACM Trans. Graph. 27, 3, 101:1–101:7.
L I , X.-Y., S HEN , C.-H., H UANG , S.-S., J U , T., AND H U , S.-M.
2010. Popup: automatic paper architectures from 3D models.
ACM Trans. Graph. 29, 4, 111:1–111:9.
L I , X.-Y., J U , T., G U , Y., AND H U , S.-M. 2011. A geometricstudy of v-style pop-ups: theories and algorithms. ACM Trans.
Graph. 30, 4, 98:1–98:10.
L IU , Y., P OTTMANN , H., WALLNER , J., YANG , Y.-L., AND
WANG , W. 2006. Geometric modeling with conical meshes
and developable surfaces. ACM Trans. Graph. 25, 3, 681–689.
L O , K.-Y., F U , C.-W., AND L I , H. 2009. 3D polyomino puzzle.
ACM Trans. Graph. 28, 5, 157:1–157:8.
M AKI , Y. 2004. The Motifs of Puppy. Gakken (in Japanese).
M ARKOSIAN , L., C OHEN , J. M., C RULLI , T., AND H UGHES ,J. 1999. Skin: a constructive approach to modeling free-form
shapes. In Proc. of SIGGRAPH ’99, 393–400.
M ITANI , J., AND S UZUKI , H. 2004. Making papercraft toys frommeshes using strip-based approximate unfolding. ACM Trans.
Graph. 23, 3, 259–263.