OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

1

Compatible Embedding for 2D Shape Animation
William Baxter, Pascal Barla, and Ken-ichi Anjyo
Abstract—We present new algorithms for the compatible embedding of 2D shapes. Such embeddings offer a convenient way tointerpolate shapes having complex, detailed features. Compared to existing techniques, our approach requires less user input, isfaster, more robust, and simpler to implement, making it ideal for interactive use in practical applications. Our new approach consistsof three parts. First, our boundary matching algorithm locates salient features using the perceptually-motivated principles of scalespace and uses these as automatic correspondences to guide an elastic curve matching algorithm. Second, we simplify boundaries
while maintaining their parametric correspondence and the embedding of the original shapes. Finally, we extend the mapping toshapes’ interiors via a new compatible triangulation algorithm. The combination of our algorithms allows us to demonstrate 2D shapeinterpolation with instant feedback. The proposed algorithms exhibit a combination of simplicity, speed, and accuracy that has not beenachieved in previous work.
Index Terms—matching, interpolation, morphing, in-betweening, cross-parameterization, multi-scale analysis, scale-space, compatible
triangulation.

F

1

I NTRODUCTIONW

HILE techniques for 3D have great appeal, 2D
tools are still used extensively in the creationof various kinds of animation. Some tasks are simply
easier in 2D: the tools are simpler, the algorithms are
simpler, and the content itself is simpler and, therefore,
easier and faster to work with. Examples of ongoinguse include digital compositing in CG productions, celanimation and web graphics, and animated billboards
as impostors in complex scenes (e.g. [1]). Nevertheless,there remain many ways in which current 2D techniques
can be improved upon.
Recently the intuitive 2D deformation algorithm from
Igarashi et al.[2] was added to Adobe’s After Effects tothe delight of users. However, despite the many virtuesof the technique, it ultimately offers a fairly limited
range of deformations. Deforming a shape to match aparticular silhouette, for instance, is nearly impossible. A
natural evolution would be to allow the user to modify
the silhouette directly, or even supply a completely
different silhouette, automatically updating the shape’s
interior accordingly. This can be accomplished using a
2D shape morphing algorithm.
While image morphing techniques [3], [4], [5], [6], [7],which apply a warping function to a simple rectangular domain, have been widely deployed in commercial
tools, shape morphing techniques, where the domain is acomplex shape, have been less widely adopted. This is
despite the numerous shape morphing techniques whichhave been proposed in research papers (e.g. [8], [9], [10],[11], [12], [13]).
We believe the lack of adoption can be attributed tolack of a sufficiently simple, efficient, and robust solution• W. Baxter and K. Anjyo are with OLM Digital, Inc., Tokyo, Japan.
E-mail: {baxter,anjyo}@olm.co.jp• P. Barla is with INRIA Bordeaux University.
E-mail: pascal.barla@labri.fr

to the problem of establishing the correspondence, or
mapping, between two irregular shapes. Previous algorithms for matching have required the user to manuallyspecify a large number of correspondences, or madestrong assumptions about the nature of the inputs (e.g.
similarity of shape, or orientation, etc.) that cause thealgorithms to perform poorly when not met ([14], [9],[10]). Other algorithms are simply too slow for interactive use [15], [16], [17], [18]. Many algorithms havealso dealt only with inputs which are simple polygons
containing a small number of well-defined edges [14],[8], [9], [11], [12], but real-world inputs arising frompractical demands are far more complex than this, often
containing highly detailed and/or indistinct boundaries,
like clouds, trees or long hair blowing in the wind.
The main observation motivating our approach is thatexact geometric algorithms are infeasible when shapes
have such complex boundaries. These details are best
handled in image space. Yet, drastic global geometricchanges are often desired, and since these are difficult forpure image-space methods, a hybrid approach is needed.
In this paper, we propose a solution to the correspondence problem that is suitable for complex 2D
shapes, is fast, and requires less user interaction thanprevious techniques. The key philosophy behind ourapproach is to embed underlying shapes within looselyapproximating boundaries rather than try to exactly
match the geometry feature-for-feature. Our contributions lie in three new algorithms that exhibit a combination of simplicity, speed, and accuracy that has notbeen achieved in previous work (see Section 2):• A boundary matching algorithm (Section 3), that finds
correspondences by quickly locating and optimally
matching salient features on shape boundaries. It
allows an artist to establish boundary correspondences with significantly less manual input thanexisting techniques.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

A compatible simplification algorithm (Section 4) that
efficiently simplifies boundaries while maintaining
their parametric correspondence and embedding thefull-resolution input shapes. It decouples the complexity of the final embedding from the complexityof the inputs.
• A compatible triangulation algorithm (Section 5) that
extends the boundary correspondence to cover
shapes’ interiors. It is not only more efficient than all
previous methods on practical inputs, but also significantly simpler than the previous best algorithms.
We believe the combination of these three algorithms isof significant importance for the widespread adoption ofrecent interpolation techniques [11], [19], [20].
•2P REVIOUS WORK

Much of the work in shape morphing falls into two
categories: 2D morphing of images [5] and 3D morphingof meshes [21]. 2D shape morphing, lies in between thesetwo, being both two-dimensional, like image morphing(e.g., [3], [4]), while having geometry which must be
taken into account, as in mesh morphing (e.g., [22], [23],[24]). Our approach takes full advantage of the 2D natureof the problem, in a way similar to previous work suchas [9], [10], [11], [12].
Shape matching Elastic distance methods have been
a popular way to match shape boundaries (e.g.,[14], [10],[25]). These techniques are fast and simple, but requireparameters to balance curvature error against stretchingerror. It is difficult or impossible to find parameters thatwork well for a wide variety of inputs. Moreover, theywork poorly in the presence of noise (see Fig. 2(c)).
In the literature on content-based image retrieval [26], anumber of methods based on the medial axis have been
proposed (e.g, [15], [18]); however, the medial axis issensitive both to noise and to slight variations in shape,and methods for robust matching based on the medial
axis are slow and difficult to implement.
Curvature scale-space is an effective way to deal
with noise, and sophisticated algorithms have been proposed using both a full scale-space [16] and just feature points [17]. However, these methods are also too
computationally demanding for interactive applications.
Our approach combines the simplicity and efficiencyof elastic distance with the robustness of scale-spacefeature-based methods.
Shape simplification
Many techniques have beendeveloped for geometric simplification of 2D lines andpolygons (e.g. [27], [28], [29]). These methods find an
approximation that minimizes deviation in terms of
Euclidean or perceptual metrics. However, we seek notonly to minimize deviation, but also to completely enclose, or embed, the full-resolution input shapes, while
additionally preserving their parametric correspondence.
For 2D boundaries, [10] performs compatible simplification by subsampling, with the predictable result thatembedding is lost. In [11], [22] meshes are simplified

2compatibly, but the former does not simplify the boundary, and the latter does not embed. The progressive hull of[30] provides an embedding simplification for 3D meshes
that is similar to our method, though it only applies
to a single input and is based on edge collapses rather
than vertex removals. Our vertex removals lead morenaturally to a compatible, parameterization-preserving
simplification. We are not aware of any previous simplification algorithms which both generate an embedding
and work compatibly on multiple inputs. We believe ouralgorithm to be the first.
Shape triangulation Previous methods for compatible triangulation generally either map polygons onto
a common domain [31], [10], [11], or use divide-andconquer compatible partitioning [32], [12]. The first category is conceptually simple but not optimal in terms ofruntime (O(n3 )) or in number of Steiner vertices introduced (O(n2 )). The latter methods are better (O(n2 log n)time and often no Steiner vertices), but are algorithmically quite complex.
Our algorithm uses recursive partitioning like thelatter. Efficiency is similar (O(n2 ) on typical inputs,
O(n3 ) generally), and it also generates outputs with nearminimal Steiner vertices, often zero. Yet it is significantly
simpler. Though the Surazhsky-Gotsman algorithm [12]is already a simplification of a previous algorithm [32],it still requires implementation of many non-trivial data
structures and algorithms described in [33], [34], [35],[36] in addition to the O(n) triangulation of either [37]or [38]. In contrast, our algorithm requires no subroutine
more complex than vertex visibility [39], [40], for whichcode can be readily be found on the web (e.g. [41]).
Furthermore, based on our experience, the reliance on
only very simple geometric visibility calculations also
appears to have the merit of making our algorithm morerobust in the face of complex inputs.

3

B OUNDARY M ATCHING

Our approach to boundary matching is a compromise
between the robustness of curvature scale-space analysis
and the efficiency of elastic curve distance methods. It
works in two steps. First, we locate the set of featurepoints along each shape boundary by extracting stable
curvature extrema. This is done by analyzing extrema“signatures” through scale-space. Second, we use a newfeature-based elastic curve distance, which finds automatic correspondences between feature points on eachshape boundary.
Compared to previous work, the first step is faster due
to our simple signature measure, while being easier toimplement and similarly robust to noise. The second stepis as fast as previous methods, but requires no complex
parameter tuning, less user input, and is more accurate
since the matching is guaranteed to go through featurepoints.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

(a)

(b)

3

(c)

(d)

Fig. 1. Boundary analysis: (a) A boundary extracted from an image: discretization causes many fine-scale curvature
extrema (green dots). (b) The fingerprint image of curvature extrema across scales. Stability of extrema A and B cannot
determined from this fingerprint data alone. (c) Comparing signatures: B (bottom) exhibits behavior characteristicof stable extrema; A does not. (d) Circles indicate feature points extracted by our signature analysis, with radii
proportional to feature strength.

3.1

Finding feature points

Our first step is to find feature points on each shape toserve as candidate correspondence points (Fig. 1). These
points are curvature extrema, which represent boundary
concavities (minima) or convexities (maxima). However,noise and detailed variations in line style tend to create
many such extrema that do not correspond to an intuitive notion of “feature” (Fig. 1(a)). Smoothing can help
with the noise problem, but the difficulty is in choosing
a proper scale for the smoothing.
A robust alternative consists in analyzing a boundary
curve smoothed at multiple scales to find stable featurepoints. This is the approach taken in scale-space methods, where stable feature points are found by tracking
boundary extrema at increasing scales. In the original
approach of Mokhtarian et al. [16], the tracked extrema
are inflection points (zero-crossings of curvature). Morerecently, Zabulis et al. [17] have argued that curvature
extrema lead to more intuitive feature points; they show
how the evolution of these extrema through scale reveals
the most important structures of a shape’s boundary.
Fig. 1(b) shows such an evolution with a so-called“fingerprint” image, where each curve corresponds toa single extremum.
While these methods deal with noise robustly, they
are also quite slow, requiring up to a minute to findfeatures in our tests. This is because they detect stablefeatures by computing the scale-space out to very coarse
scales. Our key observation is that stable extrema havea specific behavior along the scale dimension: their curvature starts with a peak, and is progressively smoothedout (Fig. 1(c)). We call this the extremum’s signaturefunction. We assert that the signatures of stable extrema
resemble decaying exponentials (Fig. 1(c),bottom). This canbe understood by noting that sharp boundary features
resemble delta functions in a curvature plot, and thus
decay exponentially with increasing scale. In contrast,
unstable extrema typically have flat or non-decaying
signatures (Fig. 1(c),top).

Using our signature analysis, we can detect stable features reliably at much finer scales and thus our compute
times rarely exceed a second. Moreover, the analysis also
produces a measure of feature strength that is valuable forthe subsequent matching step of our algorithm.
Computing signatures: We begin with a densely sampled, closed polyline with uniform arc-length parameterization. This can be extracted from an image using
standard techniques. We then build a curvature scalespace and track curvature extrema at increasing scales
as in [17]. As proposed in [16], we extract extrema
only in the vicinity of extrema found at the previous
finer scale, which significantly speeds up the process.
Our contribution is in the final step where we analyze
signatures to determine feature strengths and reject weakextrema, as explained below.
To decide whether an extremum is a good candidate feature point, we analyze its signature function.
For feature extraction we use curvature magnitudes,
disregarding sign. To ease the analysis and improve
numerical stability, we map curvature magnitudes from[0..∞) to [0..1) using the tanh function. The particulars of
the remapping function are not critical since ultimately
we only consider curvature magnitudes relative to one
another (see Section 3.2). We thus take an extremum’s
signature data to be s(σi ) = | tanh c(σi )| where c(σi )is the curvature measured at the discrete scale σi (redcurves in Figure 1(c)).
In order to compare a curvature extremum to the ideal,
we fit the measured data to an exponential signaturemodel of the form s∗ (σ) = exp (ax + b). We immediately
reject any extrema with a ≥ 0 (Fig. 1(c),top). We fit using
a weighted least-squares minimization of an error funcPNtion of the form e(a, b) = i=1 w(σi )(ax + b − log s(σi ))2 ,with w(x) = ((N − x)/N )2 , so that values near theminimum scale (where the shape is less smoothed out)
have more influence. As mentioned, we use a to rejectunstable extrema, but we also use b, to determine thefeature strength. The feature strength f is defined by its

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

4

Fig. 2. Boundary matching: (a) Two input shapes and their boundary correspondence computed with our matchingalgorithm. User correspondences are circled in red, while automatic correspondences are identified by numbers,
and delimit boundary segments of similar color. (b) Cost matrix of our approach for a subset of the boundary: darkblobs represent attractors around potential correspondences and the matching path goes exactly through curvature
extrema. (c) Cost matrix for curvature-based matching: the path (in red) does not go exactly through the desired
correspondences and is sensitive to noise.
peak value, the value at x = 0, i.e. f = s∗ (0) = exp (b).
Figure 1(d) shows the feature points extracted with ourapproach. The radius of each circle locator is proportional to the strength of the corresponding extremum.
3.2

Extracting automatic correspondences

From the multi-scale analysis, for each shape we get a setof feature points along with their strength and sign ofcurvature (indicating convexity). We normalize featurestrengths by dividing by the maximum strength value
over the shape pair, and we use a small threshold (fmin =0.05) to discard extrema that obviously come from noise,
but we keep most of the extrema. The main purposeof our elastic matching algorithm is then to make useof this information to automatically extract meaningfulcorrespondence points. The full boundary mapping is
obtained by establishing a uniform parameterization inbetween each successive pair of correspondences (Fig. 2).
The only information a user need specify is the first pairof correspondence points.
The problem of finding a boundary mapping is thensolved using a dynamic programming approach: a cost
matrix is built where each cell stores the dissimilarity
between every possible pair of points on each boundary, and the dynamic programming algorithm finds amatching path of least cost (Fig. 2(b-c)) that links thefirst pair of points to the last pair (i.e., user-given correspondences). Classic curve matching techniques (e.g.[14],[10], [25]) set up a cost matrix where each individual
cost is based on an arc-length, curvature or orientation
dissimilarity (Fig. 2-c). Instead of using raw curvature,orientation or arc-length as features to be matched, we
use the feature strength derived in Section 3.1.
We require that both features be strong in order toconsider the pair a potential correspondence. We turnthis constraint into a confidence measure defined byc(p, q) = min{f (p), f (q)} where p and q are two points

on different boundaries, f is the feature strength. The
min function acts as a fuzzy AND operator. Moreover,
we enforce c(p, q) = 0 whenever p and q are not featurepoints or have opposite signs of curvature. Our goal isthen to make use of this confidence measure to build
a cost matrix, with the additional constraint that thematching runs exactly through automatically selectedpairs of feature points, and that each feature point isused at most once.
Building the cost matrix: The intent is that the higher
the confidence value, the more likely the matching willgo through it. This is translated to a cost measure by first
filling the cost matrix with a maximum cost of 1 for eachpossible pair of points, and then positioning inverted
Gaussian blobs everywhere c(p, q) 6= 0. These blobs act
like “attractors” as they reduce costs toward 0 around thecenter of the Gaussian (Fig. 2(b)). The standard deviationof a Gaussian blob corresponds to the attraction strengthof a candidate correspondence, so we make it propor1
tional to the confidence measure: σ(p, q) = K
c(p, q). The
constant K is used to normalize attractors’ influence, andwe make it equal to the minimum
P of average
P confidences1
in each shape K = min{ n1 p f (p), m
q f (q)}. This
heuristic proved to work well in all our examples. Moreover, to ensure that the matching runs exactly throughselected correspondences, we penalize point pairs where
only one point is a feature, setting the cost to 1. This
corresponds to the white horizontal and vertical lines in
Figure 2(b).
Comparison of matching paths in Figure 2(b-c)
demonstrate the advantage of our boundary matchingprocedure: it extracts significant correspondences moreaccurately, while requiring no parameter tuning andbeing fast enough for interactive editing. Perhaps more
importantly, in tests we were always able to find asatisfactory matching with our algorithm, which was not
the case with the other algorithms we evaluated. More

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008|v|=96

5|v|=12

Fig. 3.
Compatible simplification: A result fromour compatible, embedding, parameterization-preserving
boundary simplification. (left) Initial shapes. (right) Simplified shapes.

Fig. 4. Simplification via vertex removal: The original
polygon (dark blue) and boundary after removal (red).
The cost of a removal is taken to be the area added by
the operation. Highly convex vertices like (e) are poor
candidates for simplification, and the area cost metricreflects this.

results and comparisons can be found in Section 6.

4

C OMPATIBLE BOUNDARY SIMPLIFICATIONThe output of the matching algorithm of the previous section is a densely sampled pair of corresponding boundary polygons. For generating the subsequentcompatible tessellation it is preferable to work with asimplified version of this matching, but the simplification must maintain parametric correspondence whilestill completely enclosing the original shapes. To satisfy
these requirements, we present a new algorithm forcompatible boundary simplification (Fig. 3).
The key idea is that when vertices are removed
through simplification, we restore the local embedding
by moving neighboring vertices along their normals. In
particular, for maximal efficiency we consider moving
only the immediate neighbors of a removed vertex.
Moving normal to the boundary is the key element thatserves to preserve the parametric identity of each point.
We follow the general structure of progressive meshsimplification [42], assigning costs to each simplification
operation—in our case vertex removals—and using apriority heap with greedy selection to generate a simplification sequence. The cost of each vertex removal
operation is taken to be the change (increase) in polygon
area that will result (see Fig. 4). For the overall compatible simplification cost we take the maximum cost of thetwo (inputs are normalized to have approximately thesame scale). Once the removal sequence is computed,
the heap may be discarded, and the recorded collapse
sequence can be used to quickly switch between different simplification levels. In practice, the time spent for
simplification is negligible in the overall pipeline, but it
significantly speeds up the subsequent triangulation.
Restoring local embedding: After removing a verpLƍ SL+snLnLtex, p0 , we need to repR+tnR SRƍnRpstore the embedding prop0
pL
pR
erty for convex vertices.
Concave vertices as in Figure 4(a) can simply be removed. Figures 4(b-e) show several convex examples.

As mentioned, we restore embedding by perturbing
the immediate neighbors, pL and pR , along their unit
normals, nL and nR , so that new vertex positions are
p0L = pL + snL and p0R = pR + tnR . This gives us
a two-parameter search space, (s, t) for “good” vertex
positions. We choose to place the vertices so as to equallydistribute the amount of perturbation between pL and pR(i.e. make s = t) subject to the constraint that the segment−−−→
p0L p0R intersects p0 . This leads to a quadratic equation ins:
0⊥= s2 (nR · n⊥
L ) + (pL − pR ) · (p0 − pL )
− s (nR − nL ) · (p0 − pL )⊥ + (pL − pR ) · n⊥
L ,where (x, y)⊥ = (y, −x). The minimum positive root is
the solution sought. If no positive root exists it means
the normals are separated by an angle of greater than
180 degrees. In these cases we relax the normal direction
constraint. We do this by turning both normals inward
by a fixed amount (we use a step size of 45 degrees) andtrying the procedure again. Each time we turn the angles
inward, we add a large penalty to this vertex’s removal
cost to ensure we use collapses that do not require going
off-normal first.
Modifications: First, we can obtain an
inscribed simplification (right) simply byreversing the direction of the boundary
normals used. Second, the algorithm
trivially generalizes to N -way compatible
simplification by taking the maximum of
N vertex costs rather than of two.

5

C OMPATIBLE TRIANGULATION

We establish interior correspondence using compatible triangulation. Given two polygons with compatible
boundaries as input, we recursively and compatibly
partition the two polygons using compatible link paths
as in [32], [12]. Recursion on a branch terminates whenboth inputs are triangles, which have a trivial linear
mapping. We introduce a new algorithm for findingOLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

6

Fig. 5. Visibility polygons and windows: The visibility
polygons V (u) and V (v) for vertices u and v and thewindows wu (v) and wv (u) are indicated. The red ‘+’
indicates where our algorithm places the Steiner vertex
for this case.

Fig. 6. Compatible triangulation torture test: Resultsof our algorithm on shapes that are difficult to triangulatecompatibly due to necessity of k-links, k > 2. Numbers
indicate vertex correspondences; colors indicate triangle
correspondences. 32 Steiner vertices were added.

compatible link paths, which is significantly simpler
than the previous algorithms and also more efficient on
typical inputs.
Terminology: A link path is an interior polyline thatjoins two vertices, and compatible link paths are twosuch paths which join corresponding pairs of vertices
in two polygons. The link distance is the number of line
segments in a link polyline. As a shorthand, we refer to alink path with a link distance of k as a “k-link”. A k-linkrequires the introduction of k − 1 Steiner vertices. The
goal is to triangulate by finding compatible partitions
with minimal k. It is beneficial to minimize the numberof Steiner vertices because it reduces not only the runtime and memory usage of the algorithm itself but also
the run time of any subsequent mesh processing, such as
non-linear optimization of parametric stretch (e.g. [43],[22]), which can be a significant bottleneck in the overall
processing pipeline.
Our algorithm works in three stages. First, we compute per-vertex visibility polygons and use these tofind compatible 1-links. Second, if no compatible 1link is found, we look for compatible 2-links. Thesecan be found by looking for intersections of the vertex
visibility polygons. Third, in the rare case that neither
a compatible 1- or 2-link exists, we resort to a generalk-link finding mechanism which builds pseudo-optimal
k-links out of combinations of the existing 1- and 2links by solving the classic all-pairs-shortest-paths graphproblem.
Stage 1: As a first step, we compute the visibility
polygon of each vertex in each polygon [39], [40]. A
visibility polygon is the set of points, all of which havedirect line-of-site from some given feature (see Figure 5).
A vertex visibility polygon can be computed in O(n) for
each of n vertices, so this step requires O(n2 ) work. We
also modify the basic algorithm to simultaneously record
the complete n×n visibility matrix for each polygon as itproceeds, making later determination of direct visibility
between any two vertices an O(1) operation. In fact
we record not just visibility in these matrices, but bestestimate minimal link distances between pairs of vertices

as we find them, for use in stage 3.
Specifically, let the two link distance matrices be D00
and D1 . At this stage, we record a 1 in any element Dij
1or Dij for which vertices i and j have direct visibility
in the corresponding shape, and min(|i − j|, n − |i − j|)for those which do not. The latter is simply the distancefrom i to j walking along the boundary in the shorter
direction. We refer to these as trivial k-links. Partitioning
using these is not generally useful, so is to be avoided.
But they serve as an upper bound on the link distance
between any two vertices.
The approach is greedy. If we can find a corresponding
pair of vertices in each polygon that have direct visibility(i.e. the pair is a 1-link in both polygons), then we use
it. Given the visibility matrix from the preprocess, allpairs can be easily checked in O(n2 ) time. Often there
are many compatible 1-links. In this case, like [12], wechoose a pair that results in the most balanced split of
the polygons in terms of number of vertices on each side.
For practical inputs, a compatible 1-link can almost
always be found; however, Steiner vertices must sometimes be added to one or both polygons to create acompatible partitioning (see Figure 8, or Figure 6 for aparticularly challenging case). If no compatible 1-links
are found then we proceed to stage 2.
Stage 2: The second stage of our algorithm looks forvertex pairs (u, v) with minimal link distance of two, or
2-links. 2-link visibility means that there is some point
q in polygon P which is visible from both vertex u andvertex v. The locus of such points is the intersection of
the visibility polygons for u and v. Thus all 2-links could
be found by calculating the intersections of the vertex
visibility polygons. However, polygon intersection in
general requires O(n2 ) time, so this would lead to O(n4 )complexity to test all pairs. Fortunately, for this case we
can test for intersection in O(1), by simply intersecting
two particular edges.
These two particular edges are the so-called windowsthat separate u from v, inside P (Fig. 5). A window wu (v)is an edge of the visibility polygon V (u) that separates
vertex u from vertex v. This edge exists whenever u andOLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008v do not have direct line-of-sight visibility in P , andis always unique [34], [33]. The same holds for wv (u).
Using these facts and some other results from Suri, we
prove the following lemma in [44]:Lemma 1: The two windows wu (v) and wv (u) intersect
iff there exists a minimal 2-link path between u and v.
Lemma 1 is the key insight that gives us an O(1) algorithm for determining whether two visibility polygons
intersect: they intersect if and only if wu (v) and wv (u)do. This leads to an overall O(n2 ) run time for stage 2.
Note that the windows separating each pair of vertices
are easily found as a byproduct of the vertex visibility
algorithm run in stage 1. If a compatible 2-link is found,
we place the Steiner vertex along the ray that bisects theangle between the two window edges (Fig. 5).
While performing this search we also update thevisibility matrices from the first stage with the newly
acquired 2-link visibility information. If no compatible
2-links are found, then we proceed to stage 3.
Stage 3: The main idea is to find compatible k-links
where k > 2 by simply combining the existing 1- and2-link paths. If we can get from u to w via a 2-link andw to v using a 1-link then we know we can get from u
to v in 3 steps. This is the description of a classic graphdistance problem. Our link distance matrix encodes theinitial distances in the graph and we wish to solve the allpairs-shortest-paths problem on that graph. The FloydWarshall algorithm finds these in O(n3 ).
Once a non-trivial pair of compatible k-link paths isfound, we place the Steiner vertices. The path consistsof a combination of 1-link and 2-link portions. We firstplace the central vertex of the 2-link portions using thetechnique mentioned above. All remaining vertices lie on
the polygon boundary initially and these can be adjusted
towards the interior of the polygon by various means.
Extensions:
The triangulations generated by ouralgorithm are nearly minimal; however, they usually
include many long thin triangles which are undesirable for applications. To improve the mesh quality, we
use a a variation of the compatible refinement schemein [12]. Quality meshes can be generated much more
efficiently working coarse-to-fine in this way than in
the approaches which start with a fine mesh of low
quality [31], [10], [11]. Figure 8 shows some compatible
triangulations generated by our algorithm both before
and after refinement. Additionally we have implemented
a simple scheme for incorporating interior correspondences, similar to that of [10]. Essentially, when there
are interior correspondences we perform a pre-processthat eliminates the holes and interior points by cutting
bridges to them.

6

R ESULTS AND DISCUSSION

To demonstrate the benefits of the newly introduced
algorithms, we have created a system which implements
both the rigid morphing of [11] with improvements detailed in [45], as well as the rigid deformation technique7

Fig. 7. Matching comparison: A comparison with amatching result taken from Zabulis et al. [17] (left) vs.
our algorithm (right). No manual correspondences were
specified. Our algorithm obtains very similar results but ina fraction of the time.
TABLE 1
Boundary matching comparisons
Input
Cat standing
Ant-spider
Pony
Bird
Barking dog
Elephant-giraffe
Kicking man

Our method
=2
=5
=2
=2
=4
=4
=1

Curvature
>6
> 13
=5
=5
>7
>7
>3

Tangent
>6
> 13
=8
=2
>6
>7
> 10

The number of manual correspondences required to obtain a satisfactory boundary matching. The indication “= n” means it took exactly ncorrespondences; “> n” means that after n manual correspondences,
the result still contained regions with significant artifacts that could
not be eliminated without manually specifying the correspondence ofnearly every point in the region. The inputs used for the comparison
are those shown in Fig. 8, from top to bottom.

of [2]. Deformation techniques can be used to create new
inputs for morphing which are trivially compatible, allowing for the simple creation of animations that are impossible with either technique alone. Figures 7–12 show
various results of our boundary matching, simplification,and triangulation algorithms. Videos demonstrating oursystem can be found at http://www.olm.co.jp/en/rd/
2008/06/compatible embedding.html.
Boundary matching: Though it is impossible forany automatic algorithm to guess the user’s intention
correctly 100% of the time, with our technique, a single
user correspondence is often sufficient. Fortunately, applying the dynamic programming algorithm is also very
fast (milliseconds), so users can obtain instant feedback
while adding and removing correspondences. The scalespace matching algorithm of [17] can achieve similar
results (see Fig. 7), but the method is not fast enoughto be used interactively. On the other hand we find theprevious techniques that are interactive require many
more manual correspondences than our method, andoften fail to produce a satisfying matching, even after
manual specification of many correspondences. Table 1
summarizes these findings. It compares the number ofuser-given correspondences necessary to obtain a satisfying matching for three different methods: ours (featurebased), curvature-based, and tangent-based elastic curve
matching.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

(a)

8

(b)

(c)

Fig. 8. Embedding results: (a) boundary matching (b) compatible triangulation of compatibly simplified boundaries (c)mesh refinement and morphing. Note how our compatible triangulation handles extreme stretching (e.g. spider shape,
second row). From top to bottom, these examples required 2, 5, 2, 2, 4, 4, and 1 manual boundary correspondences,and no interior correspondences. The initial tesselations required 0,3,4,4,4,2, and 0 Steiner vertices.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 20089

Our algorithm

Surazhsky-Gotsman '04

Steiner vertices: 14800Steiner vertices:

13

3

1

Steiner vertices:

61

2

3

Steiner vertices: 118

01

Steiner vertices: 529

2

1

Steiner vertices: 299

3

2

Steiner vertices: 126

32

N/A

Aronov et al. '93

Fig. 9. Compatible tesselation comparisons: Comparing our results with those of Aronov et al. [31] and SurazhskyGotsman [12]. Our algorithm generates tesselations similar to [12], but with a significantly simpler algorithm. The last
image in column 3 was created using Surazhsky and Gotsman’s implementation of [12]. “N/A” indicates that both our
implementation of [12] and theirs failed due to numerical robustness issues.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

10

TABLE 2Tesselation and Smoothing Timing Comparison
Verts

Steiner verts

Smoothed verts

70
81
92
110
121
140
162
199

0/232
0/294
4/412
0/580
2/704
3/975
1/1394
4/2043

110/342
121/415
136/544150/730
163/865
183/1155
203/1596
243/2282

t tess(msec)
14/25
19/34
24/48
29/75
41/98
54/14760/24092/384t smooth(msec)
279/2212
231/3406
473/5508
408/10723
448/13689
521/17066
627/34036
686/46587

Timing information for tesselation and subsequent smoothing using
two different tesselation techniques. We compare our algorithm withthat of Aronov et al. [31]. Results are in the form (ours/Aronov). For
both tesselations, smoothing was done using a variation on the methodof Surazhsky et al. [12]. The test was performed on the pair of cats atthe top of Fig. 8, simplified to different numbers of initial vertices by
the compatible simplification algorithm of Section 4.

50e3
40e3
30e3
20e3
10e3
0

Fig. 10. Tesselation timing comparison: Plots of theleft two columns of Table 2.
The first observation is that our method requires
fewer user interactions than the other two (between 2
and 3 times fewer manual correspondences). However,even more important is that with our method, it wasalways possible to find a satisfying matching using asmall number of manual correspondences. The reason isthat we only do direct matching on significant features
or user specified correspondences. Our technique effectively falls-back to uniform parametrizations where there
are no significant features. In contrast, with matchingalgorithms based directly on matching curvatures, arclengths, or tangents globally, it is easy for the matchingto get hung up on noisy features, or to discount good
matches simply because of slight differences in feature
magnitude.
Compatible triangulation: In [11] it is noted that “themost time-consuming step is optimizing triangle shape”.
With the combination of our boundary simplificationand subsequent near-optimal triangulation, even thisstep (i.e. our mesh refinement based on [12]) takes justa few tenths of a second (see Table 2 and Fig. 10).
In comparison, with a method that generates a large
number of Steiner vertices like that of [31] used by [11],the time for smoothing easily reaches tens of seconds,
which is unacceptable for an interactive application.
With a more complex smoothing metric to reduce thecross-distortion, as in [30], the difference would likely
be even more dramatic.
Regarding simplicity of implementation, it took one

co-author of this paper two days to implement [31], one
week for our new algorithm, and three months to implement [12]. In fact, we have subsequently learned thateven the authors of [12] themselves did not implement
the Suri minimal-link algorithm described in the paper,
because it was deemed too complex [46]. Though [31] isclearly the simplest of the algorithms, the time required
to smooth the resulting meshes can be prohibitive. On
the other hand, the relatively complicated data structures
involved in [12] proved challenging to implement anddebug, and appear to be more prone to numerical degeneracies than our algorithm, as can be seen in Fig. 9.

7

C ONCLUSIONS AND FUTURE WORK

We presented a set of algorithms for the compatible
embedding of 2D shapes, a necessary intermediate stepfor the morphing of practical inputs having complex
silhouettes. Fig. 12 demonstrates the effectiveness of ourcoarse embedding approach on several such shapes withrelatively complex silhouettes.
The major advantage of our approach is that it allows
a user to create shape morphings easily and efficiently
with just a few clicks. Each step in our processing
pipeline is fast enough to provide a user with a truly
interactive system for viewing and modifying results,
which is important for the intended use as part of ananimation system. A second significant advantage is thesimplicity of each of the algorithms.
However, our current system has some limitations.
Our full vision of a compatible embedding animation
system has yet to be realized. In this paper we focused on
the geometric aspects of the problem, neglecting imagespace. Thus, for example, some “ghosting” artifacts canstill be seen in our results that use texture cross-fading.
Our geometric techniques handle the large-scale mapping between shapes, but ultimately the finer details, the“residual”, should be handled in image space, perhaps
by warping the underlying textures, or by more sophisticated texture blending schemes. We are also interested in
improving our approach to better handle shapes of varying genus, though the compatible embedding alreadygives us a way to handle small differences by simply
treating holes as texture.
Additionally, our current approach only works for apair of inputs. For more complex animations it would
be advantageous be able to construct compatible embeddings of several shapes at a time and morph between
them as in [24], [47]. We are currently in the process of
implementing this extension.
From a user-interface standpoint, it would be beneficial to have an advanced layering system that simplifies
assembly of multiple compatible embeddings into composite animations. Also useful would be a boundarybased deformation tool similar to [13]. Such features
would greatly expand the creative potential for users,
leading to a qualitatively new approach to the creationof 2D animations.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

Also, we have assumed a texture-based representationof the details. However, the parameterization provided
by the underlying compatible triangulation can also be
used as a coordinate system for vector drawing elements. Thus compatible embeddings can also be used
for interpolation-based animation of vector drawings.

ACKNOWLEDGMENTS
This work was supported in part by the Japan Scienceand Technology Agency, CREST project.

R EFERENCES[1]

L. Kavan, S. Dobbyn, S. Collins, J. Zara, and C. O’Sullivan,“Polypostors: 2D polygonal impostors for 3D crowds,” in 2008
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games,
February 2008.
[2] T. Igarashi, T. Moscovich, and J. F. Hughes, “As-rigid-as-possible
shape manipulation,” Proc. SIGGRAPH ’05, pp. 1134–1141, 2005.
[3] T. Beier and S. Neely, “Feature-based image metamorphosis,” inProc. SIGGRAPH ’92, New York, NY, USA, 1992, pp. 35–42.
[4] S.-Y. Lee, K.-Y. Chwa, and S. Y. Shin, “Image metamorphosis using
snakes and free-form deformations,” in Proc. SIGGRAPH ’95, 1995,
pp. 439–448.
[5] G. Wolberg, “Image morphing: A survey,” The Visual Computer,vol. 14, no. 8, pp. 360–372, 1998.
[6] S. Schaefer, T. McPhail, and J. Warren, “Image deformation using
moving least squares,” in Proc. SIGGRAPH ’06, 2006, pp. 533–540.
[7] H. Fang and J. C. Hart, “Detail preserving shape deformation inimage editing,” Proc. SIGGRAPH ’07, vol. 26, no. 3, p. 12, 2007.
[8] T. W. Sederberg, P. Gao, G. Wang, and H. Mu, “2-D shape
blending: an intrinsic solution to the vertex path problem,” inProc. SIGGRAPH ’93, 1993, pp. 15–18.
[9] E. Goldstein and C. Gotsman, “Polygon morphing using a multiresolution representation,” in Proc. Graphics Interface, 1995, pp.
247–254.
[10] A. Tal and G. Elber, “Image morphing with feature preserving
texture,” in Computer Graphics Forum (Eurographics ’99), vol. 18(3),1999, pp. 339–348.
[11] M. Alexa, D. Cohen-Or, and D. Levin, “As-rigid-as-possible shapeinterpolation,” in Proc. SIGGRAPH ’00, 2000, pp. 157–164.
[12] V. Surazhsky and C. Gotsman, “High quality compatible triangulations,” Eng. w. Computers, vol. 20, no. 2, pp. 147–156, Apr.
2004.
[13] M. Eitz, O. Sorkine, and M. Alexa, “Sketch based image deformation,” in Proc. Vision, Modeling and Visualization, 2007, pp. 135–142.
[14] T. W. Sederberg and E. Greenwood, “A physically based approachto 2-D shape blending,” in Proc. SIGGRAPH ’92, 1992, pp. 25–34.
[15] T. B. Sebastian, P. N. Klein, and B. B. Kimia, “Recognition ofshapes by editing their shock graphs,” IEEE Trans. Pattern Anal.
Mach. Intell., vol. 26, no. 5, pp. 550–571, 2004.
[16] F. Mokhtarian and A. K. Mackworth, “A theory of multiscale,curvature-based shape representation for planar curves,” IEEE
Trans. Pattern Anal. Mach. Intell., vol. 14, no. 8, pp. 789–805, 1992.
[17] X. Zabulis, J. Sporring, and S. C. Orphanoudakis, “Perceptually
relevant and piecewise linear matching of silhouettes,” Pattern
Recognition, vol. 38, no. 1, pp. 75–93, 2005.
[18] M. van Eede, D. Macrini, A. Telea, C. Sminchisescu, and S. S.
Dickinson, “Canonical skeletons for shape matching,” in ICPR ’06:
Proceedings of the 18th International Conference on Pattern Recognition, Washington, DC, USA, 2006, pp. 64–69.
[19] C. Gotsman and V. Surazhsky, “Guaranteed intersection-free polygon morphing,” Computers and Graphics, vol. 25, no. 1, pp. 67–75,
2001.
[20] T. Surazhsky, V. Surazhsky, G. Barequet, and A. Tal, “Blending
polygonal shapes with different topologies,” Computers and Graphics, vol. 25, no. 1, pp. 29–39, 2001.
[21] M. Alexa, “Recent advances in mesh morphing,” Computer Graphics Forum, vol. 21, no. 2, pp. 173–197, 2002.
[22] J. Schreiner, A. Asirvatham, E. Praun, and H. Hoppe, “Intersurface mapping,” Proc. SIGGRAPH ’04, pp. 870–877, 2004.

11[23] D. Xu, H. Zhang, Q. Wang, and H. Bao, “Poisson shape interpolation,” in SPM ’05: Proceedings of the 2005 ACM symposium on Solidand physical modeling, 2005, pp. 267–274.
[24] R. W. Sumner, M. Zwicker, C. Gotsman, and J. Popović, “Meshbased inverse kinematics,” in Proc. SIGGRAPH ’05, 2005, pp. 488–495.
[25] T. B. Sebastian, P. N. Klein, and B. B. Kimia, “Alignment-based
recognition of shape outlines,” in IWVF-4: Proceedings of the 4thInternational Workshop on Visual Form. London, UK: SpringerVerlag, 2001, pp. 606–618.
[26] R. C. Veltkamp and M. Hagedoorn, State of the art in shape
matching. London, UK: Springer-Verlag, 2001, pp. 87–119.
[27] D. Douglas and T. Peucker, “Algorithms for the reduction of thenumber of points required to represent a digitized line or its
caricature,” Canadian Cartographer, vol. 10,, no. 2, pp. 112–122,
1973.
[28] A. Finkelstein and D. H. Salesin, “Multiresolution curves,” in Proc.
SIGGRAPH ’94, 1994, pp. 261–268.
[29] P. Barla, J. Thollot, and F. Sillion, “Geometric clustering forline drawing simplification,” in Proc. Eurographics Symposium on
Rendering, 2005.
[30] P. V. Sander, X. Gu, S. J. Gortler, H. Hoppe, and J. Snyder,“Silhouette clipping,” in Proc. SIGGRAPH ’00, New York, NY,
USA, 2000, pp. 327–334.
[31] B. Aronov, R. Seidel, and D. Souvaine, “On compatible triangulations of simple polygons,” Computational Geometry: Theory andApplications, vol. 3, pp. 27–35, 1993.
[32] H. Gupta and R. Wenger, “Constructing piecewise linear homeomorphisms of simple polygons,” J. Algorithms, vol. 22, no. 1, pp.
142–157, 1997.
[33] S. Suri, “On some link distance problems in a simple polygon,”IEEE Trans. Robotics and Automation, vol. 6, no. 1, pp. 108–113, Feb
1990.
[34] ——, “A linear time algorithm with minimum link paths inside
a simple polygon,” CVGIP, vol. 35, no. 1, pp. 99–110, 1986.
[35] L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan,“Linear time algorithms for visibility and shortest path problems
inside simple polygons,” in SCG ’86: Proc. Symposium on Comp.
Geom., 1986, pp. 1–13.
[36] L. Guibas, E. McCreight, M. Plass, and J. Roberts, “A new
representation for linear lists,” in Proc. 9th ACM Symp. on Theoryof Computing, 1977, pp. 49–60.
[37] B. Chazelle, “Triangulating a simple polygon in linear time,”
Discrete Comp. Geom., vol. 6, no. 5, pp. 485–524, 1991.
[38] N. M. Amato, M. T. Goodrich, and E. A. Ramos, “A randomized
algorithm for triangulating a simple polygon in linear time,”
Discrete & Comp. Geometry, vol. 26, no. 2, pp. 245–265, 2001.
[39] B. Joe and R. B. Simpson, “Corrections to Lee’s visibility polygon
algorithm,” BIT, vol. 27, no. 4, pp. 458–473, 1987.
[40] C. A. Hipke, “Computing visibility polygons with LEDA,”
1996. [Online]. Available: http://ad.informatik.uni-freiburg.de/mitarbeiter/hipke/ hipke.work.vis polygon.ps.gz[41] Bonn, University of, “Applets for visibility in simple polygons,”
2008. [Online]. Available: http://web.informatik.uni-bonn.de/I/
GeomLab/VisPolygon/[42] H. Hoppe, “Progressive meshes,” Proc. SIGGRAPH ’96, pp. 98–
108, 1996.
[43] P. V. Sander, J. Snyder, S. J. Gortler, and H. Hoppe, “Texture
mapping progressive meshes,” in Proc. SIGGRAPH ’01, 2001, pp.
409–416.
[44] W. Baxter, P. Barla, and K. Anjyo, “Notes on compatible mappingof 2D shapes,” OLM Digital, Inc., Tech. Rep. OLMTRE-2008-002,
2008. [Online]. Available: http://www.olm.co.jp/en/rd/2008/
06/compatible embedding notes.html[45] W. Baxter, P. Barla, and K. ichi Anjyo, “Rigid shape interpolation
using normal equations,” in Proc. Symp. Non-Photorealistic Animation and Rendering, 2008, pp. 59–64.
[46] V. Surazhsky, personal communication, June 2008.
[47] W. Baxter and K. Anjyo, “Latent doodle space,” Computer Graphics
Forum, vol. 25, no. 3, pp. 477–485, 2006.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

12

Fig. 11. Simple morphing result: Morphing result using compatible meshes generated by our techniques, with linear
texture blending. First and last frames show triangulations. This result required just a single boundary correspondence(blue dot). The original inputs were hand-drawn by an artist.

William Baxter received the PhD in computerscience from the University of North Carolina
at Chapel Hill in 2004. He has been employed
as a Senior Researcher in the R&D group at
OLM Digital, Inc. in Tokyo, Japan since January
2005. His main research interests are NPR, HCI,and physically based models, with a particularinterest in how these can be used to enhanceand support creative activities.

Pascal Barla received the PhD in computerscience from INRIA Grenoble University in 2006,
and has recently started as a researcher at INRIA Bordeaux Sud-Ouest, in the IPARLA team.
His main research interest is expressive rendering, with a strong interest in human vision.

Ken-ichi Anjyo received the PhD in informationengineering from Nagoya University in 1994,
and has been working for OLM Digital, Inc.,
since 2000. At OLM Digital he is the lead of
the Research and Development division, responsible for making visual effects and in-house
software tools. His research focus is the construction of mathematical and computationallytractable models for computer graphics.

OLM TECHNICAL REPORT - OLMTR2008-001 - JUNE 23, 2008

2 BCs /

6 ICs

13

7 BCs /

3 ICs

4 BCs /

2 ICs

Fig. 12. Additional morphing results: Morphing results on more complex inputs. Boundary (BC) and interior (IC)correspondences are indicated.