
Reminder:
This document may be removed from this site soon
as no permission from the author is recieved.
Looks like that guy wanna get paid for this crap.
Introduction
In this document, I will explain a technique to morph
3D objects in realtime as seen in quite a few demos. Although the actual
geometric morphing is not hard at all, keeping the shading and everything
speedy requires a special trick. I will first explain what morphing really
is, and how it is done. After that, I will tell you how to make it fast.
What is Morphing?
Morphing means that you start out with some object, which can
be anything, and over the course of a number of frames change this object into something
different. It’s kinda like what Odo from Deep Space 9 could do, albeit on a slightly smaller
scale :).
Morphing really is a bit of a fuzzy term, since every operation which changes the geometry
of an object can be considered morphing. Even the squashing of a rubber ball when it hits
the ground. In general though, simple deformations like this are not considered morphing.
I use the term for all operations which change the angles between the faces of an object
(This includes the squashing I mentioned).
The actual deformation of an object's geometry can be done in a number of ways.
The easiest is simply to linearly interpolate the X,Y and Z coordinates of all verts in
an object to those of the second object. Another method converts all coordinates to spherical
coordinates, and interpolates these. The latter can give really cool effects, but it’s rather
hard to implement in an existing 3Dengine I think.
However the morphing is done, you have to make sure that the original object and the object
it is morphed into have the same number of vertices, the same number of faces, and the faces
are constructed from the same vertices. It is possible to simulate for example a cube (12 triangles)
morphing into an isocahedron (20 triangles) by splitting up some of the cubes’ triangles into
multiple smaller ones, so that the cube is constructed from 20 triangles.
How is it usually done?
Assuming the coordinates are interpolated linearly in N frames,
the actual morphing process, complete with shading, goes like this:
First, calculate the delta’s for interpolation of coordinates. This is easy: For each vertex
the start and endvalues of the X,Y and Z coordinates are known. Therefore, the coordinates
of any vertex at a given framenumber are :
X = Xstart + framenumber * (XendXstart)/N;
Y = Ystart + framenumber * (YendYstart)/N;
Z = Zstart + framenumber * (ZendZstart)/N;

In the actual morphing loop, this will look like:
X = Xstart;
Xinc = (Xend  Xstart) / N;
for (i = 1; i<=N; i++)
{
......
X += Xinc;
......
}

And the same for Y and Z. In practice, you’ll probably have a temporary object with
coordinates you continually update using the above formulas. After each update, recalculate
the normals and process your object as usual to display it on the screen. In pseudocode:
for (all verts in the object)
{
Calculate increase values: (startend)/N;
}
TempObject = OriginalObject;
for (i=1; i<=N; i++)
{
[Process TempObject as usual]
[Blast TempObject to screenbuffer]
for (all verts in TempObject)
{
X += Xinc; Y += Yinc; Z+=Zinc;
}
for (all faces in TempObject)
{
[Recalculate facenormal]
}
}

So you start with a certain object (OriginalObject) and after N frames, this object has become
something different. That’s all, morphing is easy :).
Everything I said so far is nothing special, and even rather trivial. But, although all
of this works just fine for flatshading, you’ll hit problems as soon as you want to do
something more advanced like gouraud or fongshading (fong = fake phong). This is because
flatshading only uses the facenormals, while gouraud and fong require the vertexnormals to
be recalculated, which is extremely slow.
Why is it slow to recalculate Vertexnormals?
Calculating facenormals is not very expensive. Considering
the average object is a few hundred faces at most, it is perfectly acceptable to do
this in realtime, especially on today’s fast systems. For the vertexnormals,
things are different. Let’s look at a standard loop for creating vertex normals. Here's
some general case pseudocode that Kurt described in his tutorial on vertex normals.
// Calculating vertex normals using a vertex list and polygon faces
// (vertex indices)
loop through your vertex list
{
vector sum; // initialized to [0,0,0]
int incident = 0;
loop through your face lists
{
for each face vertex, check if its
the same as the vertex as in our
current outer vertex loop.
If it is,
{
sum+=this_face.normal;
incident++;
}
}
this_vertex_normal = sum (components) / incident;
this_vertex_normal.Normalize();
}

So for all vertices the complete facelist is checked. Since the number of vertices and the
number of faces depend closely on each other, this turns out to become a computational
nightmare: an X^2 relation between the number of elements (X) and the cost of the algorithm.
Just for clarity: I’m still talking about morphing objects here. In a normal situation, the
vertexnormals are calculated once at initialization, and rotated the same way as the rest
of the object. No problemo.
And remember, this loop is executed on top of the calculation of the facenormals. All in all, it
would be nice if the inner loop could be eliminated. Happily, there is a way to do this. Let’s
move on to the next part.
So how do I make it fast?
To eliminate that annoying and expensive inner loop I showed you in
the previous chapter, let’s turn the world upside down. Normally, you have a list of vertices,
and a list of polygons. These are roughly of the structure:
class Vertex
{
float X,Y,Z ; //Coordinates in 3Dspace for this vertex
....
}
class Polygon
{
int V1,V2,V3 ; //Indices of the vertices which make up this polygon
....
}

Now the trick to make realtime morphing fast (insert Tadaa.wav here :) is to have for each vertex a
list of polygons in which that vertex is being used. The previous line is essential for the algorithm,
so reread it until you understand perfectly.
This polylist can be predetermined, since it is a good bet that polygons in an object don’t switch
vertices. Your Vertex class now becomes:
class Vertex
{
float X,Y,Z ; //Coordinates in 3Dspace for this vertex
....
int Incident; //Number of polygons that use this vertex
int *PolyIndex; //Linked list of polygonindices
}

Now somewhere in the initialization part of your 3Dobject, the following piece of code, or
something similar, should be added:
loop through your vertex list
{
int this_vertex.incident = 0;
loop through your face lists
{
for each face vertex, check if its
the same as the vertex in our
current outer vertex loop.
If it is,
{
add this face to linked list of this vertex
this_vertex.incident++;
}
}
}

This has to be done only once. Now during morphing, after the normal procedure you would follow
for flatshaded objects I described above, insert the following:
loop through your vertex list
{
this_vertex.normal = (0,0,0);
repeat this_vertex.incident times
{
add normal of current face in linked list
to normal of this vertex and proceed to
next face.
}
this_vertex.normal /= this_vertex.incident;
}

You now have correct vertexnormals for the morphing object in every frame. This allows
you to perform gouraudshading, fongshading, environmentmapping and whatever you do using
vertexnormals.
There are of course other ways to do this, but as far as I know this is the fastest
method which yields correct vertexnormals. I know of at least one demo (Fashion by
Logic Design) which doesn’t recalculate the vertex normals at all. Because they used
an almost spherically symmetrical object, this had the effect of a moving lightsource!
It’s in the hornet archive, so go check it out. It’s pretty cool.
Conclusion
The algorithm I presented here is by no means revolutionary. However, it does
the job quite well in a lot of situations. There are a lot of details left to fill in, but this
depends on the actual implementation. The nice thing about this algorithm is that it can be
implemented in any 3Dsystem with little or no modification to the system itself, because all
the extra steps can be carried out outside the actual renderingpipeline.
The performance I got is a 320face, 160vertex torus morphing in any way desired at full
framerate on a 486/120 (That’s a few years ago :). Admittedly, my implementation at the time
was not a fullfledged 3Dengine. But it indicates that on a modern computer and for
nottoocomplex objects, realtime morphing is feasible, even within complex environments.
This opens up some nice possibilities. What if your friendly collegues in Halflife suddenly
morph into hideous monsters?
If you want to contact me about this tutorial for questions or anything, mail to:
j.bouwens@student.tue.nl
Reader Comments & Questions:
This section is no longer for feedback.
This document may not be reproduced in any way without
explicit permission from flipCode and the author.
All Rights Reserved. Any and all trademarks used belong to their respective owners.
Best viewed at a high resolution (1024x768x16 and higher HIGHLY recommended).
