|
|
|
| |
|
|
|
|
|
|
|
| The
Main Idea |
|
|
Shape transformation is very cool. It can be really exciting
to see one shape turn into another. Smoothly turning one image
into another is called morphing, and it's a very popular
technique. But turning one shape into another is harder.
In general, no program is every going to "solve"
the shape metamorphosis problem, because it's as much of an
artistic issue as a technical one. When we turn one shape
into another, we're saying something about those two shapes,
and how they're related. If we turn a teakettle into an ogre,
where should the kettle's spout go? Should it become his nose?
The axe in his hand? One of his legs? These are all reasonable
answers: only the person using the system can decide what
it ought to be.
I thought it would be handy to come up with a simple-to-use,
general-purpose tool for simple types of transformations,
where we don't really care a lot about how features line up.
This could be used for simple objects, or objects in the background
of a scene. It could also be used to get a start on the metamorphosis
transformation, so that the computer can do a bunch of the
work and then an artist can come in and change it here and
there to tune it up, and not have to do all the early grunt
labor by hand. I wanted something simple and fast, and steered
way clear of the difficult "feature matching" problem,
which is a treacherous reef that has claimed many ships.
The basic scheme is this: to turn object A into object B,
first "grow" object A to its convex hull (this is
the shape you'd get if you surrounded A in shrink-wrap, but
didn't let the material bulge in anywhere - in other words,
it's the tightest "shell" around A). Then smoothly
change this polyhedron into the convex hull of B, and then
"ungrow" that hull to reveal shape B. Because of
how this is all done, everything is smooth and continuous
- nothing pops or suddenly snaps from one shape to another.
|
| Results |
|
|
|
Here's an example of turning an egg into a dragon.
The egg is a simple surface of revolution. The dragon
is a polygon model by David Forsey.
The process is that the egg streatches and grows into
roughly the shape of the dragon, and then the actual
dragon himself emerges. Everything is smooth and continuous.
|
 |
|
|
| Details |
|
|
Let's look at the process in 2D first.
I'll look at how to turn a square into a triangle. In the figure
below, part a is the square, and part b is the triangle. We
start up by finding the convex hulls as a set of lines. The
intersection of the four lines in b (the part on the inside
of the line is shaded) makes up the square (and similarly for
f). The convex hulls here are easy because the starting shapes
themselves are convex. Now we "transplant" each of
these hulls, moving each line into position to enclose the other
object as tightly as possible. So the three lines for the triangle
are packed around the square in c, and vice-versa in g. We can
see the result of both hulls packed around both objects in d
and h. Note that the square in d comes from the intersection
of all seven lines, as does the triangle in h.
|
|
 |
|
Now let's do the transformation! All that's required is that
we move the seven lines in d to their corresponding positions
in h. The figure below shows three steps along the way. Notice
that this is easy and fast to compute, the intermediate objects
are always convex, and everything is smooth as can be.
|
|
 |
|
Now we can do the whole thing in 3D, using planes rather than
lines. Here I've shown how to transform a cube into a pyramid
built on a five-sided base. Note that the two objects are geometrically
distinct: they have different numbers of faces, polygons, and
edges. That's not an issue for this algorithm. Notice that the
point of the pyramid is also no problem, because there's no
feature-matching in this algorithm.
|
|
 |
|
Here's a little torture test for the algorithm, It passes through
seven completely different solid polyhedra, smoothly blending
from one to the next.
|
|
 |
|
To turn an object into its convex hull, or to turn the hull
back into the object, we need a smooth and continuous way to
get from one extreme to the other. I decided to create a series
of "moves", each of which flexes a pair of adjoining
faces from one configuration to the next (see the documentation
for details). The bottom line is that a shape going to its hull
gradually "fills in" the holes, and and one coming
back uncovers them. Here's an example of a simple spiral turning
into its convex hull. Against, everything is continuous and
smooth - each of these shapes grows in a continuous way from
the others, in either direction.
|
|
 |
| More
Info |
|
|
The details of this system, as well as source code in the
Mesa language, are all in a couple of patents owned by Xerox
PARC, as I did this work while a researcher there. See:
- Glassner, A., ''Moves for Converting Concave
Polyhedra to Their Convex Hulls'', Patent 5,428,717
- Glassner, A., ''Sequencing and Scheduling
Moves for Converting Concave Polyhedra to Their Convex Hulls'',
Patent 5,317,681
|
|
|
|
|
|
|
|
|
|
|
