Methods
of Shape Metamorphosis Based on Bounded Space-time Blending
G. Pasko,
IT
Institute, Kanazawa Institute
of Technology,
A. Pasko,
Hosei
University, Tokyo, Japan
pasko@k.hosei.ac.jp
T. Kunii,
IT Institute,
Contents
- Abstract
- Introduction
- Other works
- Shape metamorphosis using bounded space-time blending
- Algorithm extensions
- Conclusion
- Acknowledgements
- References
We develop a new approach to shape
metamorphosis using bounded blending operations in space-time. The key steps of
the metamorphosis algorithm are: dimension increase by converting two input kD shapes into half-cylinders in (k+1)D space-time,
applying bounded blending union with added material to the half-cylinders, and
making cross-sections for getting intermediate shapes under the transformation.
This approach is further extended in two directions. First, the problem of
“jump” in animation or the rapid transition between shapes in the given
interval is solved using “smoothed” versions of half-cylinders which undergo
bounded blending. Second, the approach is extended to 3D initial and final
shapes with the bounded blending union operation applied to the corresponding
“smoothed” 4D space-time half-cylinders.
General transformations
between given shapes in animation and free-form modeling include simple linear
transformations (translation, scaling, rotation), non-linear transformations
such as free-form transformations and other non-linear space mappings, and
metamorphosis or morphing (transformation of one given shape into another). The
specific aspects of the shape transformation problem considered in this paper
are the following. The initial shapes can have arbitrary topology not
corresponding to each other. No restrictions should be imposed on the input
shape model, the shapes can be defined as 2D polygons, implicit surfaces, or
constructive solids in 2D or 3D. We do not require the shapes to be aligned or
overlap, in fact, they can occupy different positions in space. The one-to-one
correspondence established between the boundary points or other shape features
is not required. We consider a combined transformation including metamorphosis
and nonlinear motion.
A brief survey of existing
approaches to shape metamorphosis is given in the next section. Implicit
surfaces [2] and FRep solids [7] seem to be most
suitable for the given task. In this work, we present and further develop the
new method of shape metamorphosis proposed in [9], which is based on increasing
the object dimension, function-based bounded blending, and consequent
cross-sectioning for animation. Here, we extend this approach in two
directions. First, the problem of rapid transition between shapes in the given
interval is solved using “smoothed” versions of half-cylinders which undergo
bounded blending. Second, the approach is extended to 3D initial and final
shapes and bounded blending union between corresponding 4D space-time
half-cylinders. Examples of 2D and 3D metamorphosis using the proposed approach
are given.
The approaches to 2D
metamorphosis include physically-based methods [11,12], star-skeleton
representation [13], warping and distance field interpolation [3],
wavelet-based [17], and surface reconstruction methods [14]. A detailed survey
on 3D metamorphosis can be found in [6]. The existing approaches are based on
one or several of the following assumptions: equivalent topology (mainly
topological disks or balls are considered), polygonal shape representation,
shape alignment (shapes have common coordinate origin and significantly overlap
in most of the case studies), possibility of shape matching (establishing of
shape vertex-vertex, control points or other features correspondence), the
resulting transformation should be close to the motion of an articulated
figure.
Figure 1. Three steps of
biological amoeba motion.
The specific
aspects of the shape transformation problem considered in this paper are the
following:
·
initial 2D shapes can have arbitrary topology not corresponding to each other;
·
the shapes can be defined as 2D polygons, implicit curves, or constructive 2D
solids;
·
the shapes are not aligned or overlap, and can occupy different positions on
the plane;
·
there is no correspondence established between the boundary points or other
shape features;
·
a combined transformation is considered including metamorphosis and non-linear
motion similar to the behavior of a biological amoeba illustrated in Fig. 1.
The desired type of behavior
can be obtained using skeletal implicit surfaces [16] with manual or automatic
establishing of correspondence between scalar field source points. Metamorphosis of more general shapes based on skeletal
implicit surfaces can be handled using hierarchical tree structures similar to
those used in FRep. Galin
et al. [5] proposed to automatically establish correspondence between such tree
structures of the source and the target objects with additional manual control
from the animator. Metamorphosis of
arbitrary FRep objects can be described using the
linear (for two initial solids) or bilinear (for four initial solids) function
interpolation [4], but it can produce poor results for not aligned objects with
different topology. Turk and O’Brien [15] proposed a more sophisticated approach based on
interpolation of surface points (with assigned time coodinates) using radial
bases functions in 4D space. This method is applicable to not aligned surfaces
with different topology. However, for the initially given implicit surfaces
this requires time consuming surface sampling and interpolation steps.
3. Shape
metamorphosis using bounded space-time blending
A blending
operation in shape modeling generates smooth transition between two curves or
surfaces. Note that sometimes the term “blending” is used to designate
metamorphosis of 2D shapes, but we use it here in the way traditional to
geometric and solid modeling. Blending versions of set-theoretic operations
(intersection, union, and difference) on solids approximate exact results of
these operations by rounding sharp edges and vertices. Such operations are
usually used in computer-aided design for modeling fillets and chamfers. In the
case of blending union of two disjoint solids with added material, a single
resulting solid with a smooth surface can be obtained. This property of the blending
union operation is the basis of our approach to the shape metamorphosis.
Figure 2. Initial 2D shape
(union of two disks) and final 2D shape (cross) for metamorphosis.
Figure 3. Two
half-cylinders with the given 2D shapes as cross-sections
Let us illustrate step by step
the approach we proposed in [9] (Figs. 2-5):
1)
two initial shapes are given on the xy-plane
(union of two disks and a cross in Fig. 2);
2)
each shape is considered as a cross-sections of a half-cylinder in 3D space (a
cylinder bounded by a plane from one side) as it is
shown in Fig. 3;
3)
the axes of both cylinders are parallel to some common straight line in 3D
space, for example, to the coordinate z-axis, and the bounding
planes of two half-cylinders are placed at some distance to give space for
making the blend;
4)
apply the added material bounded blending union operation to the half-cylinders
(Fig. 4);
5)
adjust parameters of the blend such that a satisfactory intermediate 2D shape
is obtained in one or several 2D cross sections by planes orthogonal to z-axis
(Fig. 5);
6)
considering additional z-coordinate as time, make consequent orthogonal
cross-sections along z-axis (Fig. 5)
and combine them into 2D animation.
Figure 4. Bounded blending
union of two half-cylinders. Note the sharp upper and lower edge in the areas
of the boundaries of the half-cylinders at z=0 and z=1
|
|
|
|
|
z=-10 |
z=-1 |
z=0 |
|
|
|
|
|
z=0.5 |
z=1 |
z=10 |
Figure 5. Cross-sections of
the bounded blending union – steps of metamorphosis.
Note that most of shape transformation happens in the [0,1] interval
The following
definition of the bounded blending set-theoretic operation is used:
(1)
where 
is an R-function corresponding
to the type of the set-theoretic operation [10, 7], the arguments of the
operation 
and 
are
defining functions of two initial solids, and 
is
a displacement function depending on the defining function of the bounding
solid 
.
The formulation for blending operations with the blend
bounded by an additional bounding solid was used as proposed in [8]. An appropriate displacement function can be taken in the
form:
(2)
with 
(3)
where
and
with numerical parameters 
and 
controlling
the blend symmetry, and 
allowing the user to
interactively control the influence of the function 
on
the overall shape of the blend. This definition of the function 
and the definition (2) of the
displacement function 
are not unique and can be
changed, if it is necessary in particular applications.
The application of the bounded
blending union to the half-cylinders for the shape metamorphosis is illustrated
by Figs. 4 and 5. The half-cylinders are bounded by the planes z=0 and z=1
to make the gap [0,1] along z-axis between them. The bounding solid
for the blend in this case is an infinite slab orthogonal to z-axis and
defined by the function as an intersection of two halfspaces with the definitions 
and
. The blending displacement from the
exact union of two half-cylinders takes zero value at the boundaries of the
bounding solid (planes z=-10 and z=10). This
results in the exact initial 2D shapes obtained at the cross-sections
outside the bounding solid: two disks for 
and the
cross for 
(first and last images in Fig. 5
respectively). The parameters 
- of the bounded blend influence the
blend shape and respectively the shape of the intermediate cross-sections. Note
that whatever interval is selected for the bounded blend along z-axis in
3D space, it can always be scaled to match the required time interval for the
shape transformation on a 2D plane.
The main problem with the
bounded blending (Fig. 4) and resulting animation (Fig. 5) is that the most significant
part of the shape transformation happens in the [0,1] interval with the 2D
shape changing rapidly from the initial to the final cross-section, which
results in the visible “jump” in animation during this time interval. The main
reason is that the bounded blending is applied to a half-cylinder bounded by a
plane orthogonal to the axis. This set-theoretic subtraction of one cylinder
half results in the sharp edge of the half-cylinder boundary (as seen in Fig.
3) with this edge remaining a significant feature of the blended half-cylinders
(see edges at the top and bottom parts of the shape in Fig. 4 left).
To avoid the described problem of the “jump” in the animation or of the
rapid transition between shapes in the given interval,
we propose in 3.1 to use “smoothed” versions of half-cylinders which undergo
bounded blending. Then, in 3.2 the general approach is extended to 3D initial
and final shapes and the bounded blending union operation is applied to
corresponding “smoothed” 4D space-time half-cylinders.
To avoid the sharp
edges in the initial half-cylinders and in the resulting bounded blending, we
propose to apply more “smooth” operation between the cylinder and the bounding
planar half-space. The pure set-theoretic subtraction resulting in the sharp
edge can be replaced by the bounded blending subtraction.
For example, the
half-cylinder with the cross shape (Fig. 3) was generated by the pure
subtraction of the halfspace 
, which instead can
be replaced by the bounded blending subtraction based on equations (1) and (2),
where defines an infinite cylinder, 
is
subtracted from the cylinder, and 
is the bounding
solid for the blended subtraction, which defines the area of “smoothing”.
The resulting
shape of the “smoothed” half-cylinder is shown in Fig. 6 (top-right). Fig. 6
(bottom) also shows possible shapes of the “smoothed” half-cylinders depending
on different parameters of the bounded blending subtraction.
Figure 6. Two “smoothed”
half-cylinders with the given 2D shapes as cross-sections (compare with Fig.
3).
Figure 7. Bonded blending
between “smoothed” half-cylinders (compare with Fig. 4).
The resulting bounded
blending union of two “smoothed” half-cylinders is shown in Fig. 7, which, if
compared with Fig. 4 (left) does not have sharp edges and has wide controlled
area of the cross-sectional shapes transition. This new property is illustrated
by the frames of animation in Fig. 8 obtained from cross-sections of the object
(Fig. 7) along the time axis. The animation does not have the interval of the
“jump” or the rapid change and the transition between the given 2D shapes can
be easily controlled using parameters of blending subtraction (“smoothing”
operations) and blending union between “smoothed” half-cylinders.
|
|
|
|
|
z=-10 |
z=-1 |
z=0 |
|
|
|
|
|
z=0,5 |
z=1 |
z=10 |
Figure 8. Frames of animation based on the bounded blending
between “smoothed” half-cylinders: no “jump” in animation is observed.
As no assumptions were made in
the proposed approach about the dimensionality of the initial shapes, we can
apply it to 3D objects. The bounded space-time blending procedure for initial
3D shapes consists of the following steps analogous to those applied for 2D
shapes and illustrated in Fig. 9:
1)
two initial 3D shapes are given in xyz-space (see the
initial cube and the union of two tori in Fig. 9);
2)
each shape is considered as a 3D cross-section of a half-cylinder defined in 4D
space-time (a cylinder bounded by a plane from one side along the time axis);
3)
the bounding planes of two half-cylinders are placed at some distance along
time axis to provide a time interval for making the blend;
4)
the 4D half-cylinders are smoothed using the bounded blending subtraction of the
planar half-spaces;
5)
the added material bounded blending union operation is applied to the
“smoothed” 4D half-cylinders;
6)
parameters of the blending union are adjusted such that satisfactory
intermediate 3D shapes are obtained in one or several cross sections along the
time axis (see Fig. 9 showing four intermediate shapes);
7)
consequent orthogonal cross-sections along the time axis are made
and combined into a 3D animation.
Note that similar to the 2D
case, topological changes of 3D objects are handled automatically. The initial
cube in Fig. 9 has genus 0, while the final object has genus 4.
Figure 9. Metamorphosis of
a cube into the union of two tori
Some unwanted
disconnected components can appear during the metamorphosis (as in Fig. 9
middle-left). Let us now try to fine tune the process by adding user controlled
deformations. The appearance of the disconnected component in Fig. 9 can be
explained by quite big distance between the initial cube and the final union of
two tori. We can improve the metamorphosis by adding
time-dependent deformation of the cube in the direction of the tori’s center. This can be done with help of a non-linear
space mapping (“warping”) controlled by a single point attached to the front
face of the cube and moved towards the tori’s center.
The balance between the deformation and the metamorphosis can be found by
selecting appropriate time schedules for both processes. In Fig. 10, we
can observe that the cube is only deformed at the beginning (upper-right frame)
and the actual metamorphosis starts later to avoid the possibility for
disconnected components to appear.
Figure 10. Metamorphosis of
a cube into the union of two tori improved by
applying additional deformation.
We have further
developed the new approach to shape metamorphosis on the basis of the bounded
space-time blending between higher-dimensional objects. The proposed approach
can handle non-overlapping 2D and 3D shapes with arbitrary topology. The
obtained behavior during the transformation process does not imitate the motion
of an articulated figure, but rather has amorphous or amoeba-like character
including non-linear motion and metamorphosis. In this paper, we extended the
proposed approach in two directions: additional control of the metamorphosis is
introduced using “smooth” half-cylinders in space-time, and the metamorphosis
between 3D shapes is described and tested.
There are several issues
requiring further research and development in the proposed direction. The user
control of the entire process including elimination of unwanted disconnected
components will be further investigated. Although the topological changes are
generated automatically, analytical or numerical analysis of the transformation
is needed to extract the critical points along the time axis, which can be
useful for generation of more representative animation and in other
applications.
The HyperFun
modeling language [1] and supporting software tools were used to produce the
animations and the illustrations in this paper.
References
[1] Adzhiev V., Cartwright R., Fausett
E., Ossipov A., Pasko A., Savchenko V. (1999). HyperFun
project: a framework for collaborative multidimensional F-rep modeling,
Implicit Surfaces '99, Eurographics/ACM SIGGRAPH
Workshop, J. Hughes and C. Schlick (Eds.), pp. 59-69
[2] Bloomenthal J. et al. (1997). Introduction
to Implicit Surfaces, Morgan Kaufman.
[3]
Cohen-Or D., Levin D., Solomovici A.(1996) Contour
blending using warp-guided distance field interpolation, IEEE Visualization’96,
IEEE Computer Society, pp. 165-172.
[4] Fausett E., Pasko
A., Adzhiev V. (2000). Space-time and higher
dimensional modeling for animation, Computer Animation 2000, University of
Pennsylvania, PA USA, May 3-5 , pp.156-165.
[5] Galin E., Leclercq A., Akkouche S. (2000) Morphing the BlobTree,
Computer Graphic Forum, vol. 19, No. 4, pp. 257-270.
[6] Lazarus F., Verroust A. (1998) 3D Metamorphosis : a survey, The Visual
Computer . vol. 14, No 8-9, pp 373-389.
[7] Pasko A., Adzhiev V., Sourin A., Savchenko V. (1995). Function
representation in geometric modeling: concepts, implementation and
applications, The Visual Computer, vol.11, No.8, pp.429-446.
[8] Pasko G., Pasko A., Ikeda
M., Kunii T. (2002). Bounded blending operations, Shape Modeling International
2002, IEEE Computer Society, pp. 95-103.
[9] Pasko G., Pasko A., Ikeda M., Kunii T. (2003) 2D shape transformation
using 3D blending, Proceedings of MMM 2003, 9-th International Conference on
Multimedia Modeling (January 7-10, 2003, Taipei, Taiwan), Tamkang
University, 2003, pp. 390-401.
[10] Rvachev V. L. (1974). Methods
of Logic Algebra in Mathematical Physics, Naukova Dumka,
[11]
Sederberg T., Greenwood E. (1992). A
physically-based approach to 2-D shape blending, SIGGRAPH’92, Computer
Graphics, vol. 26, No. 2, 1992, pp. 25-34.
[12]
Sederberg T., Gao P., Wang
G., Mu H. (1993). 2-D shape blending: an intrinsic
solution to the vertex path problem, SIGGRAPH’93, Computer Graphics
Proceedings, pp. 15-18.
[13]
Shapira M., Rappoport A.
(1995). Shape blending using the star-skeleton representation, IEEE Computer
Graphics and Applications, vol. 15, No. 2, pp. 44-50.
[14]
Surazhsky T., Surazhsky V.,
Barequet G., Tal A. (2001).
Blending polygonal shapes with different topologies, Computers and Graphics,
vol. 25, No. 1, pp. 29-39.
[15]
Turk G., J.
O’Brien (1999) Shape transformation using variational implicit functions,
SIGGRAPH’99, Proceedings of the 26th annual
conference on Computer graphics and interactive techniques, ACM Press, pp. 35 – 342.
[16] Wyvill B., McPheeters C., Wyvill G. (1986) Animating soft objects, The
Visual Computer, vol. 2, pp. 235-242.
[17] Yuefeng Zhang, Yu Huang (2000) Wavelet
shape blending, The Visual Computer, vol. 16, No. 2, pp. 106-115.