Controllable morphing of compatible planar triangulations.
Two planar triangulations with a correspondence between the pair of vertex sets are compatible (isomorphic) if they are topologically equivalent. This work describes methods for morphing compatible planar triangulations with identical convex boundaries in a manner that guarantees compatibility throughout the morph. These methods are based on a fundamental representation of a planar triangulation as a matrix that unambiguously describes the triangulation. Morphing the triangulations corresponds to interpolations between these matrices.We show that this basic approach can be extended to obtain better control over the morph, resulting in valid morphs with various natural properties. Two schemes, which generate the linear trajectory morph if it is valid, or a morph with trajectories close to linear otherwise, are presented. An efficient method for verification of validity of the linear trajectory morph between two triangulations is proposed. We also demonstrate how to obtain a morph with a natural evolution of triangle areas and how to find a smooth morph through a given intermediate triangulation.
Figure

7 shows this on a concrete example. Conjecture 3.5 allows to choose the maximum m, namely
that guarantees a valid morph. A simple algorithm to flnd M sequentially checks morphs for
every m > 1, incrementing m by 2. The number of morphs checked may be signiflcantly reduced to
ACM Transactions on Graphics, Vol. X, No. X, xxx 2001.
Controllable Morphing of Compatible Planar Triangulations  11
(a) (b) (c) (d) (e)
Fig. 7. Morphs generated by raising neighborhood matrices to various powers. (a), (b) The source and the target triangula-
tions. Correspondence is color coded. (c) The convex combination morph at 0:5. (d) An invalid morph is generated by
raising neighborhood matrices to power valid morph is generated by raising neighborhood matrices
to power Zoom in on the triangulations in (d) and (e). (h) Trajectories of the convex combination
morph. (i), (j) Trajectories of morphs generated by raising neighborhood matrices to power
Note the positions of the trajectories relative to the straight lines (the linear morph).
O(log M). First, we flnd an upper bound mmax by doubling m until the morph is invalid. Then, the
resulting M is found by binary search in the interval [mm2ax ; mmax].
Furthermore, a morph that is even closer to the linear morph than a morph deflned by may
be obtained. Consider the following deflnition of A(t):
This equation averages the neighborhood matrices of the valid morph deflned by with the
neighborhood matrices of the invalid morph, deflned by 2. Using power m for neighborhood
matrices and a parameter d, equation (14) may be viewed as a morph with a non-integer power for
neighborhood matrices m 1). In order to obtain a morph, which is the closest possible
to the linear morph, the maximal parameter d may be chosen by binary search in the interval [0; 1],
verifying the morph validity at every step. See Figure 11(b) for a morph generated by this scheme.
3.4 Morphing with an Intermediate Triangulation
This section demonstrates how to flnd a morph between two triangulations T0 and T1 such that at a
the morph interpolates a given triangulation Tm. The triangulations T0, T1 and Tm are
compatible and with identical boundaries. A naive solution is to flnd two convex combination morphs
independently: the flrst|between T0 and Tm, and the second morph|between Tm and T1. The problem
with this is that while the two independent morphs are continuous and smooth, the combined morph will
usually have a C1 discontinuity at the intermediate vertices.
In order to flnd a smooth morph, it is necessary to smoothly interpolate A0, Am and A1 in A(T0).
Consequently, the corresponding elements of the three matrices should be smoothly interpolated. Given
three points (0; i;j(0)), (tm; i;j(tm)) and (1; i;j(1)) in R2, it is necessary to flnd an interpolation
i;j(t) for all t 2 [0; 1], see Figure 8. Since the entries of the matrices are barycentric coordinates, the
interpolation must satisfy 0  i;j(t)  1. An interpolation within the bounded region [0; 1]  [0; 1] may
be found as a piecewise Bezier curve, since any Bezier curve is located in the convex hull of its control
points.
An important point is that interpolations for the matrix entries are performed independently. But
every row i, 1  i  n, of A(t), being barycentric coordinates of the interior vertex i, should sum to
unity. Due to the independent interpolations, this might not be the case. Normalizing the elements of
each row can solve this problem. The normalized entry i;j(t) is deflned as follows:
12  V. Surazhsky and C. Gotsman
i;j(t)PSfrag replacements i;j(tm)
Fig. 8. An interpolation of three points (0; i;j(0)), (tm; i;j(tm)) and (1; i;j(1)) when 0  tm  1 is in the bounded
region [0; 1]  [0; 1].
Fig. 9. (top) A smooth morph interpolates an intermediate triangulation given at The morph trajectories. The dashed lines are the edges of the source, target and
intermediate triangulations.
Since i;j(t) is smooth, the sum of i;j(t)'s is also smooth. Therefore the normalized i;j(t) is a smooth
interpolation. See an example demonstrating a smooth morph in Figure 9.
4. MORPHING WITH LOCAL CONTROL
A well-behaved morphing scheme should have properties like those described in Section 3.2. Trajectories
traveled by the interior vertices should be smooth and even (not jerky and not bumpy). It would be
useful if the scheme would be linear-reducible. When the linear morph is invalid, the natural requirement
is to generate a morph as close as possible to the linear one. It would also be useful to be able to control
triangle areas in such a way that they transform naturally (uniformly) during the morph. This may
help to prevent shrinking/swelling of triangles, that result in an unnatural-looking morph. The schemes
presented in this section allow the control of trajectories of the interior vertices, triangle areas etc. in a
local manner.
To flnd a morph between two triangulations T0 and T1 means to flnd a curve A(t) for 0  t  1 in A(T0)
with endpoints in A(T0) and A(T1). We will do this by constructing each row of A(t) (corresponding to
each interior vertex) separately.
We deflne T 0(G0; }0) to be a subtriangulation of a triangulation T (G; }) if T 0 is a valid triangulation,
G0 is a subgraph of G and the coordinates of the corresponding vertices of T 0 and T are identical. The
triangulations T0 and T1 may be decomposed into n subtriangulations in the following manner: each
interior vertex corresponds to a subtriangulation that consists of the interior vertex, its
neighbors and edges connecting these vertices, see Figure 10. A subtriangulation deflned above is said to
Sn
be a star denoted by Zi. Namely, every star Zi corresponds to the interior vertex i, and
be stars of the triangulation T0; stars Zi(1) are deflned analogously for
T1. Clearly, Zi(0) and Zi(1) are two isomorphic triangulations, since they are the same subgraph of
two isomorphic triangulations T0 and T1. Barycentric coordinates of the interior vertex in star Zi with
respect to the boundary vertices of that star are also barycentric coordinates of the interior vertex i
Controllable Morphing of Compatible Planar Triangulations  13
Fig. 10. A triangulation is decomposed into stars; each interior vertex deflnes a separate star.
in a triangulation T with respect to its neighbors. Thus all Zi(0)'s when 1  i  n together deflne a
neighborhood matrix A0 in A(T0); Zi(1) for 1  i  n deflne A1 respectively. In the same manner,
we would like to deflne A(t) for a speciflc t using stars Zi(t), 1  i  n. The question is how to
flnd Zi(t) for 0 < t < 1 such that it will deflne barycentric coordinates with some intermediate values
between barycentric coordinates of Zi(0) and Zi(1). Obviously, a smoth morph of two stars Zi(0) and
should su-ce to obtain this. But only a smooth A(t) will deflne a smooth morph between the
triangulations. For that reason it is important to use a method to generate barycentric coordinates of
the interior vertices that is at least C1-continuous, such as that described in Section 2.1. A morphing
scheme that generates A(t) by morphing separately the stars of two triangulations is said to be a local
scheme.
There is a simple way to morph two stars Z(0) and Z(1). First, translate the two stars in such a way
that the interior vertices of the both stars are at the origin. Then a morph may be deflned by linear
interpolation of the polar coordinates of the corresponding boundary vertices. One can flnd a proof for
the correctness of this morph in [Shapira and Rappoport 1995; Floater and Gotsman 1999; Surazhsky
1999], where there are also recommendations on how to choose the polar coordinates in order to obtain
a valid morph. Note that the validity of star morphs, based on the translation of interior vertices to the
origin, depends only on how angle components of the polar coordinates of the boundary vertices vary
during the morphs. Arbitrary variations in the radial direction of the boundary vertices do not afiect the
validity of the morph.
4.1 The Local Linear-Reducible Scheme
The local scheme morphs separately the corresponding stars of T0 and T1 and is based on the translation
of the source and target stars to the origin. Two translated stars Zi(0) and Zi(1) are morphed in the
following manner. If the linear morph of two stars is valid, we adopt it. Otherwise, an arbitrary valid
morph is taken. It can be the morph that averages the polar coordinates of the boundary vertices, as
described in Section 4; or translated trajectories of the boundary vertices during the convex combination
morph. In the latter case the row corresponding to the star Zi in A(t) is equal to the i'th row of A(t)
generated by the convex combination morph.
The following theorem shows that this scheme is linear-reducible.
Theorem 4.1 The linear morph of two triangulations T0 and T1 is valid ifi the linear morphs of all
component stars are valid.
Proof. Validity: If the linear morph between T0 and T1 is valid, then any triangulation T (t) for
compatible with T0 (and T1) and thus may be decomposed into valid stars. Each
is a valid morph between Zi(0) and Zi(1). If all morphs of the stars Zi(t) are valid,
then we have a legal neighborhood matrix function A(t) for 0  t  1, and thus T (t) is valid.
Linearity: Let pi;j be the coordinates of the vertex i in the star Zj. First, we prove that if the morph
between T0 and T1 is linear then the morphs of all stars are linear. We have
for 0  t  1. Every star Zj(t) is translated in such a way that the interior vertex is at the origin. Thus,
14  V. Surazhsky and C. Gotsman
Combining both equations:
For the opposite direction, we prove that if the morphs of all stars are linear then the morph between
T0 and T1 is linear. The linear morphs of the stars imply that:
Let T (t) be the linear morph between T0 and T1, namely,
It remains to show that A(t), deflned by the stars Zj(t) for 1  j  n, satisfles
will show that every star Zj(t) deflnes the same barycentric coordinates of the interior vertex i as the
corresponding star j of T (t), and thus A(t) 2 A(T (t)). Clearly, Zj(t) is isomorphic with the corresponding
star j of T (t). The following states that the vertex coordinates of Zj(t) are translated coordinates of the
corresponding star j of T (t). Due to the initial translations of the interior vertices to the origin:
We can now express (16) as:
Hence, after the translation of pj(t) the coordinates of every vertex in the star Zj(t) are equal to the co-ordinates
of the corresponding vertex in T (t). Since barycentric coordinates are invariant to a translation
(as a special case of a-ne transformations), the stars Zj(t) for 1  j  n deflne A(t) 2 A(T (t)).
This work presents two linear-reducible schemes: the scheme described in Section 3.3 and the scheme
introduced in this section. It is important to emphasize the principal difierence between these two
schemes. The flrst scheme approaches the linear morph using neighborhood matrices raised to a power.
This approaching signiflcantly afiects all trajectories of the interior vertices and is a global approach to
the linear morph. It allows to choose a degree of approximation to the linear morph by specifying the
power of the neighborhood matrices. However, even the morph closest to the linear morph does not allow
each individual trajectory to be as 'linear' as possible. The global convergence may be blocked by a single
problematic trajectory (which invalidates the morph), preventing the others from being straightened
further, see Figures 11(a) and 11(b). On the other hand, the local linear-reducible scheme, morphing the
component stars separately, may afiect a group of trajectories of adjacent vertices almost independently
of other trajectories of the morph. However, the local scheme does not attempt to approximate the
linear morph for stars for which the linear morph is invalid. Thus, vertices of triangulation regions
that cannot be morphed linearly have trajectories similar to those generated by the convex combination
morph, and vertices of regions that may be morphed linearly have trajectories very close to straight lines,
see

Figure

11(c). Knowing the properties of both the linear-reducible schemes, it is possible to choose
the most suitable for speciflc triangulations and speciflc applications.
These two schemes may also be combined to obtain a morph that is closer to the linear morph than
a morph generated separately by each of the schemes. First, the scheme of Section 3.3 is used to
generate a valid morph TP (t) with a maximal power for neighborhood matrices. Then the scheme of
this section is applied, morphing each of the stars separately. For stars for which the linear morph is
invalid, corresponding trajectories from TP (t) are used. For the rest of the stars, the linear morph is
used. The resulting morph is valid, since the morphs of all component stars are valid. The morph in

Figure

11(d) was generated using this combined scheme.
Controllable Morphing of Compatible Planar Triangulations  15
(a) (b) (c) (d)
Fig. 11. Trajectories of various morphs approaching the linear morph. The dashed lines are the edges of the source and
target triangulations. (a) Trajectories of the convex combination morph. (b) Trajectories of the valid morph generated by
raising neighborhood matrices to power trajectories are closer to straight lines than the trajectories of the
convex combination morph. However, the two lower trajectories could still potentially be straight lines without afiecting the
validity of the morph. (c) Trajectories of the valid morph generated using the local linear-reducible scheme. The two lower
trajectories are straight lines, but the rest are identical to the corresponding trajectories of the convex combination morph.
(d) Trajectories of the valid morph generated by combination of two linear-reducible schemes. The two lower trajectories
are linear. The rest approach straight lines similar to the corresponding trajectories of the morph with power 1:3.
4.2 Testing Validity of the Linear Morph
The linear-reducible scheme, described in the previous section, morphs an individual star linearly only if
the linear morph is valid. A natural question is how to determine whether the linear morph between Z(0)
and Z(1) will be valid or not. Clearly, the naive test which verifles whether Z(1 ) is a valid triangulationis not enough. To verify whether Z(t) is a valid triangulation for all 0  t  1 is impossible in practice,
since [0; 1] is a continuum. Appendix A presents a robust and fast (linear time complexity) method to
perform the test. This method can also be applied to check the validity of linear morphs for general
triangulations. According to Theorem 4.1 it is su-cient to check the validity of the linear morphs for all
corresponding stars of the two triangulations. The complexity of this test is O(V (T )), namely, linear in
the size of the triangulations.
4.3 Improving Triangle Area Behavior
This section describes a method for improving the behavior of the triangle areas during the morph. The
triangle areas do not always evolve uniformly during the morph when using the methods described in
the previous sections. In fact, the triangle areas may evolve linearly only when the triangulations have
a single interior vertex. For a speciflc triangle i, we would like its area, denoted by Si, to behave for
This cannot be satisfled for all triangles of the triangulation for all 0 < t < 1. Consider the following
equation for the area of a triangle with vertices i, j and k:
Areas of triangles with two boundary vertices are transformed uniformly only when the third vertex travels
linearly with a constant velocity. Areas of triangles with a single boundary vertex are quadratically (not
uniformly) transformed, since the two non-boundary vertices travel linearly with constant velocities, by
(21).
The problem of the triangle area improvement may be formulated as follows. Denote by Si(t) the
ACM Transactions on Graphics, Vol. X, No. X, xxx 2001.
Gotsman
desired area of a triangle i that evolves linearly:
Thus, a morph between two triangulations should minimize a cost function such as:
We now show how to improve the triangle area evolution using the local scheme, such that the resulting
morph is at least closer to (23) than the convex combination morph.
Since it is di-cult to improve the triangle areas for the entire triangulation, the improvement may be
done separately for the stars of the triangulation. This is performed after a morph of a speciflc star is
deflned. To preserve the validity of the morph, '-components of the boundary vertices are preserved.
The improvement is done by a variation of the boundary vertices in the radial direction relative to the
origin.
First, we consider an improvement such that all triangles within the star have exactly the desired areas,
namely, the area of each triangle is Si(t). This approach, however, has a serious drawback. While every
triangle has its desired area within the star, its shape signiflcantly difiers from the shape it assumes in
the entire triangulation. Furthermore, since a triangle belongs to a number of stars, its shapes in the
difierent stars might contradict each other considerably. Therefore the resulting morph is very unstable.
The trajectories that the interior vertices travel are tortuous. The triangle areas are far from uniform
and hardly better than those generated by the convex combination morph.
All this means that the evolution of the triangle areas within the stars must also take into account the
triangle shapes. For a speciflc triangle i, one of its vertices is the interior vertex of the star, that is placed
at the origin for 0  t  1. The angle adjacent to the interior vertex cannot be changed, because it may
afiect the validity of the morph. Therefore an improvement of the triangle area is achieved by a variation
of the lengths of its two edges adjacent to the interior vertex. Every edge adjacent to the interior vertex
belongs to exactly two triangles. Consequently, the length of the edge after an improvement for one
triangle does not always coincide with the length of the edge within the second triangle. We improve the
triangle areas separately for each triangle, and the resulting length of the edge is the average of the two
lengths.
We propose a simple method that improves the area of a single triangle and also preserves the triangle
shape. This method changes the positions of the triangle vertices in the radial direction such that the
triangle area evolves linearly and the lengths of the radial edges maintain the proportions they would
have had, had the edge lengths evolved linearly. Let a and b be the lengths of the edges, and  be the
angle between them. The area of the triangle is:S = a b sin() (24)Denote by a(t) and b(t) the lengths of the edges as they evolve linearly:
The resulting a(t) and b(t) are the lengths of the edges such that the triangle area is S(t) deflned by
(22). In order to flnd a(t) and b(t) it is necessary to solve the following system of equations with the
unique solution.2 S(t)
to satisfy
preserving the relation between the edges:
See an example of a morph generated using this method in Figure 12.
5. EXPERIMENTAL RESULTS: MORPHING POLYGONS
In practice, morphing is performed more frequently on planar flgures than on planar triangulations.
Luckily, many types of planar flgures may be embedded in triangulations as a subset of the triangulation
edges. Thus the problem of morphing planar flgures may be reduced to that of morphing triangulations,
and the edges not part of the flgure are ignored in the resulting morph. Two popular cases of planar
flgures are planar polygons and planar stick flgures. The former is a cycle of edges, and the latter a
ACM Transactions on Graphics, Vol. X, No. X, xxx 2001.
Controllable Morphing of Compatible Planar Triangulations  17
Fig. 12. A morph with good area behavior is generated using the local scheme with the
method for area improvement. Compare with Figure 7 showing the convex combination
morph between these triangulations.
connected straight line graph. Embedding these types of flgures in a triangulation in an e-cient manner
is a di-cult problem in itself, and has been treated separately by us in [Gotsman and Surazhsky 2001]
and [Surazhsky and Gotsman 2001]. Here we will assume that these embeddings have been done, and
investigate the efiect of the various triangulation morphing techniques described in the previous sections
on the results.

Figure

13 shows morphs between two polygons|the shapes of the two letters U and S. Figure 14
shows morphs between two stick flgures|the shapes of a scorpion and a dragony. These examples
have been embedded in planar convex tilings [Floater and Gotsman 1999] (the faces are not necessarily
triangles), for which all the theory developed in this paper holds too. Being convex, these tilings may
be easily triangulated if needed. In both examples the linear morph self-intersects (Figure 13(a) and

Figure

14(a)). The convex combination morph is valid, but has an unpleasant behavior (Figure 13(b)
and

Figure

14(b)). The local scheme, which averages the polar coordinates of star boundary vertices,
provides good results when parts of the flgures should be rotated during the morph. Figure 13(c) and

Figure

14(c) demonstrate that this results in a rather natural morph. Unfortunately, the morph of

Figure

13(c) undergoes some exaggerated shrinking. This may be avoided by using the local scheme with
area improvement, as in Figure 13(d).

Figure

14(d) shows how to approach the linear morph while still preserving the morph validity, by
using the scheme that raises the neighborhood matrices to power 17. Note that the tail travels a path
similar to that of the linear morph, but by shrinking avoids self-intersection. Also note that some parts
of the rest of the triangulations self-intersect, since the trajectories of all interior vertices approach the
linear ones. But since we are interested only in the validity of the stick flgure itself, we can ignore the
behavior of other edges.
6. CONCLUSION
We have described a robust approach for morphing planar triangulations. This approach always yields a
valid morph, free of self-intersections, based on the only known analytical method for generating morphs
guaranteed to be valid [Floater and Gotsman 1999]. The approach, having many degrees of freedom, may
be used to produce a variety of morphs, and, thus, can be tuned to obtain morphs with many desirable
characteristics.
6.1 Discussion
Morphing thru an intermediate triangulation poses the following interesting problem. Find a morph
through an intermediate triangulation at a given time tm, in which only a subset of the interior vertices
have prescribed positions. This contrasts with the scenario treated in Section 3.4, where all vertices of
the intermediate triangulation have prescribed positions. While constraining only a subset of the vertices
might seem easier than constraining all the vertices, it is actually more di-cult, since if all vertices are
constrained, the user supplies a complete geometry compatible with the triangulation. Supplying only
part of the vertex geometry leaves the algorithm the task of flnding compatible geometries for the other
vertices, which is di-cult, especially since they might not exist.
This (static) problem is interesting in its own right, and has applications in the generation of texture
coordinates. It is only recently that Eckstein et al. [2001] have shown how to solve this problem by the
introduction of (extraneous) Steiner vertices. The solution with a minimal number of Steiner vertices,
Gotsman
(a)
(b)
(c)
(d)
Fig. 13. Morphing simple polygons|the shapes of two letters S and U: (a) The linear morph is invalid | the polygon
self-intersects. (b) The convex combination morph is valid, but unnatural. (c) Morph generated by the local scheme that
averages polar coordinates. It behaves naturally, accounting for the rotation of the lower part of the S, but shrinks in an
exaggerated manner. (d) Morph generated by the local scheme with area improvement. It is similar to the morph in (c),
but with much less shrinking of the shape.
and in particular, with none when it is possible, is still open. In general, the main di-culty stems from
the fact that our morphing techniques use neighborhood matrices, which always result in a global solution
to the morphing problem, making it virtually impossible to precisely control an individual vertex location
(or trajectory).
In Section 3.3, two conjectures are used to generate a morph that approaches the linear morph. Numerous
examples support these conjectures, but a proof still eludes us. Since the matrices used to generate
morphs by that method are not legal neighborhood matrices, the proof requires more a profound comprehension
of the method.
Section 4.3 presents a heuristic for improving the evolution of triangle areas. Further analysis of the
correlation between vertex trajectories as well as triangle area behavior within the stars and behavior of
these elements in the triangulation, may provide insight to more successful heuristics, perhaps even some
optimal approximation to the desired triangle areas.
It is important to make the techniques presented in this work applicable to real-world scenarios. As
mentioned in Section 5, the techniques have already been applied to morph simple planar polygons and
stick flgures by embedding them in triangulations. In practice, the triangulations are built around them.
For example, the triangulations in which simple polygons are embedded are constructed by compatibly
triangulating the interior of the polygons and an annular region in the exterior of the polygon between
the polygon boundary and a flxed convex enclosure. See [Gotsman and Surazhsky 2001; Surazhsky and
Gotsman 2001] for more details. These works have yet to be extended to morph planar flgures with
arbitrary (e.g. disconnected) topologies.
Controllable Morphing of Compatible Planar Triangulations  19
(a)
(b)
(c)
(d)
Fig. 14. Morphing between flgures of a scorpion and a dragony: (a) The linear morph is invalid | the flgure self-
intersects. (b) The convex combination morph is valid, but unnatural. (c) Morph generated by the local scheme that
averages polar coordinates. It behaves naturally, accounting for the rotation of the tail. (d) Morph generated by the raising
the neighborhood matrices to power 17. Note that the tail travels a path similar to that of the linear morph (a), but it
shrinks in order to avoid self-intersection.
Morphing triangulations is usually useful as a means to morph planar flgures, and in that case the flxed
convex boundary is not restrictive. However, if the objective is to actually morph two triangulations (e.g.
for image warping), then a flxed common convex boundary might be restrictive. Fortunately, using the
methods of [Gotsman and Surazhsky 2001; Surazhsky and Gotsman 2001], it is possible to overcome this
by embedding the source and target triangulations with difierent boundaries, in two larger triangulations
with a common flxed boundary. In practice this is done by compatibly triangulating the annulus between
the original and new boundary, possibly introducing Steiner vertices. See Figure 15.
6.2 Future Work
A challenging research subject would be to extend the techniques of this work to three dimensions,
certainly, starting from an extension of [Tutte 1963]. Furthermore, it would be interesting to address the
problems in [Aronov et al. 1993; Babikov et al. 1997; Souvaine and Wenger 1994; Etzion and Rappoport
1997] for 3D.


A. TESTING VALIDITY OF THE LINEAR MORPH OF A STAR
Let v0 be the interior vertex of the stars with degree d. The corresponding boundary vertices are indexed
without loss of generality as in a counterclockwise order with respect to the interior vertex. Let
be the boundary vertex coordinates during the linear morph. We denote
by i(t); 'i(t)    polar coordinates of the vertex i.  Let 'i(t) be the angle of a triangle
i adjacent to the interior vertex. Note that all calculations with indices are performed modulo d. It is
ACM Transactions on Graphics, Vol. X, No. X, xxx 2001.
20  V. Surazhsky and C. Gotsman
Fig. 15. Embedding two compatible triangulations (shaded regions) with difierent boundaries into larger triangulations
with a common flxed boundary.
assumed that the polar coordinates of the vertices for are chosen in such a way that
is necessary to check that the linear morph preserves the
triangle orientations, namely, it should be verifled that 0 < i(t) <  for 0  t  1. To verify this, it
is su-cient to check the extrema of i(t) on [0; 1]. The extremum points may be found by solving the
equation
For notational simplicity, we denote b. Due to the linear traversals of the vertices,
we have:
The '-component of the polar coordinates is expressed as:
The next step is to derive '0b(t)'0a(t). But the sign(z) function is not convenient for the derivation. To
overcome this problem we perform some substitutions for '(t).  Since j'a(1)  'a(0)j <  we can rotate
both vertices va(0) and va(1) by the same angle !a round the origin such that the vertices are placed
in the upper half plane, namely, the y-components of the vertices are positive. We denote the rotated
coordinates by (x~; y~) with the polar '-component '~. Thus, we have
Since the rotation is an a-ne transformation, it is easy to see that for the line segment deflned by (27):
Clearly, due to y~a(0) > 0, y~a(1) > 0 and (27). Consequently, 'a(t) deflned as
in (29) may now be expressed as:
may easily be derived and after the simpliflcation we get:
Due to the rotational invariance of the nominator and the denominator, we can return to the original
(not rotated) coordinates:
Controllable Morphing of Compatible Planar Triangulations  21
The similar procedure of a rotation may be performed for the vertex b, since for b it also holds that
Therefore we can write
The expression x~2(t) being -components of the polar coordinates, is strictly positive. Hence, 35
is equivalent to:
Since x(t) and y(t) are linear in t, (36) is a quadratic equation in t and may be solved analytically.


--R


On compatible triangulations of simple polygons.
Constructing piecewise linear homeomorphisms of polygons with holes.



Texture mapping with hard constraints.
On compatible star decompositions of simple polygons.

Parameterization and smooth approximation of surface triangulation.
How to morph tilings injectively.

Polygon morphing using a multiresolution representation.
Guaranteed intersection-free polygon morphing
Introduction to linear and nonlinear programming.
Joint triangulations and triangulation maps.

2D shape blending: an intrinsic solution to the vertex path problem.
A physically based approach to 2D shape blending.
Shape blending using the star-skeleton representation
Constructing piecewise linear homeomorphisms.
Surface interpolation based on new local coordinates.
Morphing planar triangulations.
Morphing stick flgures using optimized compatible triangulations.
Image morphing with feature preserving texture.
How to draw a graph.
accepted May
--TR
Joint triangulations and triangulation maps
A physically based approach to 2MYAMPERSANDndash;D shape blending
Feature-based image metamorphosis
On compatible triangulations of simple polygons
2-D shape blending
Parametrization and smooth approximation of surface triangulations
Three-dimensional distance field metamorphosis
Foldover-free image warping
How to morph tilings injectively
As-rigid-as-possible shape interpolation
On Compatible Star Decompositions of Simple Polygons
Morphing Stick Figures Using Optimized Compatible Triangulations

--CTR
David Vronay , Shuo Wang, Designing a compelling user interface for morphing, Proceedings of the SIGCHI conference on Human factors in computing systems, p.143-149, April 24-29, 2004, Vienna, Austria
Jeff Danciger , Satyan L. Devadoss , Don Sheehy, Compatible triangulations and point partitions by series-triangular graphs, Computational Geometry: Theory and Applications, v.34 n.3, p.195-202, July 2006
Anna Lubiw , Mark Petrick , Michael Spriggs, Morphing orthogonal planar graph drawings, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.222-230, January 22-26, 2006, Miami, Florida
Hayley N. Iben , James F. O'Brien , Erik D. Demaine, Refolding planar polygons, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
Vitaly Surazhsky , Joseph (Yossi) Gil, Type-safe covariance in C++, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
linear Morph;morphing;compatible triangulations;self-intersection elemination;controllable Morphing;isomorphic triangulations;local Control