Morphing 3-D Objects in C++

Glenn presents a C++ morphing program that simulates a "melting" effect (and its reverse) on 3-D objects. The program, which compiles and runs on UNIX machines, PCs, and the Amiga, generates objects analogous to key frames in animation sequences.

July 01, 1994
URL:http://www.drdobbs.com/cpp/morphing-3-d-objects-in-c/184409268

Figure 1

Figure 1

JUL94: Morphing 3-D Objects in C++

Morphing 3-D Objects in C++

There's more than one way to 'melt' a cat

Glenn M. Lewis

In the movie Terminator 2: Judgment Day, there's a well-known scene in which the T1000 terminator has become a puddle of liquid metal on a checkerboard floor. The puddle suddenly begins oozing upward, defying gravity, and forming the general outline of a man. The liquid metal then solidifies to a humanoid shape, and "grows" skin to become the clearly defined image of a man.

In this article, I present a C++ program that simulates this effect on certain three-dimensional objects, such as the melting chess piece in Figure 1. For lack of a better term, I call this the "melt effect," even though the actual film sequence is the reverse of melting. Of course, once this program has created all the intermediate objects, you can run the morph in whichever direction you choose.

There are two kinds of morphing: 2-D and 3-D. In a 2-D morph, control points are placed in two images at locations that correlate between the two, usually in the form of a mesh. The 2-D morph algorithm calculates intermediate images, that, when viewed in succession, smoothly change the first image into the second. A 3-D morph starts with a representation of two 3-D objects, creating new 3-D models that, when rendered and viewed in succession, smoothly change the first object into the second. (For a backgrounder on morphing, see "Morphing in 2-D and 3-D," by Valerie Hall, DDJ, July 1993.)

The C++ program presented here, which compiles and runs on UNIX boxes, PCs, and the Amiga, processes objects represented using the IFF format generated by Impulse Inc.'s (Minneapolis, MN) Imagine rendering package. As with other rendering programs, Imagine takes a description of an abstract 3-D world consisting of objects, textures, light sources, a camera, and the like, and creates a 2-D image of that world as seen from a camera's perspective.

My "melt" program extends the Imagine program's limited built-in morphing facility. One major restriction of Imagine's facility is that two morphable objects must have the same topology: Each object of a morphable pair must have the same number of points, edges, and faces, and each of these elements must have a one-to-one correspondence with its counterpart, including the same hierarchical order within the object. Although a severe limitation, this still greatly facilitates Imagine's implementation of morphing--all that's necessary is a simple linear interpolation between the corresponding points in each object. However, this kind of interpolation is not enough to achieve the puddle effect, which is a highly nonlinear transformation. Consequently, my program generates objects that are roughly analogous to key frames in an animation sequence and asks Imagine to interpolate between those "key-frame objects." You can request that Imagine put any number of frames in between, but the more intermediate objects you create with my melt program, the better the resulting effect.

To get true Hollywood-class special effects, it's often necessary to combine algorithmic transformation and "manual" touchup (using image-editing tools). Plus, you need a lot of experience and artistic talent to achieve the most natural-looking effects. All this is beyond the scope of my effort, which is restricted to the algorithmic approach only. One drawback to the purely algorithmic approach is that not all objects are well suited to melting. I've found that the melt effect works best on objects that are "star-shaped," where at least one point in the interior of the object can be selected such that all rays cast from this point in any direction intersect the object once and only once. It also helps if the shape is generally cylindrical or box-like. I have tried this effect on complex objects (such as a model of the NCC-1701-D Enterprise, by Carmen Rizzolo), and the effect is more of a curiosity than it is usable.

Running the melt program requires two arguments: the original object's filename, and the base filename to use when creating the new "in-between" morphed objects (which defaults to root_). A third optional parameter is the number of frames over which the user wishes to morph; this argument's default is 10, which means that root_000.iob through root_009.iob are generated automatically. The original object can be considered the final object in the sequence. Note that the effect is much more convincing when the sequence is viewed in reverse numerical order--that is, when you start with the original object and morph toward the puddle (the "000" object). This, of course, is why I named the program "melt."

Objects and Formats

IFF (short for "Interchange File Format") is a tagged file format that's relatively straightforward to read. IFF allows programs to parse a file without having to recognize all data fields within the file; unfamiliar sections can simply be skipped. IFF shares this characteristic with formats such as TIFF and RIFF.

The IFF file structure is very simple. The first four bytes must be the characters FORM, followed by a 4-byte unsigned long that represents the length of the remaining IFF file. All numeric data in IFF files are stored in Big-endian (Motorola) format, with most significant byte (MSB) first and least significant byte (LSB) last. Following the file size is a field specifying the type of form. The type of form used by my program and by Imagine to store objects in is called FORM TDDD. The rest of the file is made up of IFF "chunks" that comprise the TDDD form. Each chunk consists of a 4-byte identification (ID) string labeling the chunk, followed by its size as an unsigned long. All IFF chunks are required to start on even-byte boundaries within the file; therefore, odd-sized chunks are padded with a 0 byte.

ReadWrite, a program that's part of my T3DLIB package (available via anonymous ftp from ftp.wustl.edu or ftp.luth.se in the pub/aminet/qfx/3dobj directory) dumps out the TDDD chunks present in an Imagine object. The program creates an ASCII representation of the object, called a "T3D" or "Textual Three-Dimension Data Description" file. If you run it with the --v command-line flag, the program displays chunks that Impulse has added which ReadWrite does not yet understand (because at the time of this writing, Impulse has not released the full spec for the TDDD format).

The Melt Code

Melt.cc (Listing One) and point.cc (Listing Two) are the two principal modules of the melt program. The complete system, including list.cc and object.cc, is available electronically; see "Availability."

One of the reasons I implemented this program in C++ was that earlier I had written T3DLIB, a C shareware library of object-conversion and manipulation routines for Imagine objects. Although I thought about building upon this package, I decided against it because I wanted a program designed to focus on object manipulation that would simply ignore (yet retain) TDDD chunks that it did not care about and thus maintain compatibility with future changes to the TDDD file format. T3DLIB is not well suited for this because it loads in an object entirely into an internal database that represents the full TDDD file format and later traverses that hierarchy to write the object out. So any time new TDDD chunks are added, T3DLIB must be updated to support them.

Also, I considered what would be involved in simply creating a copy of an object within T3DLIB by duplicating the full internal object hierarchy, and I got a headache thinking of the time involved. I knew about C++ constructors and destructors, and decided that copying an object would be a perfect application for these great features.

The Principal Classes

The three principal classes in the melt program are Point, List, and Object. The design of these classes offloads a lot of bookkeeping chores from the main algorithm. A Point object is simple: It consists only of the x, y, and z values of a point, plus routines to initialize, load, and write from/to a file, and get and put individual FRACTs from/to a file. A FRACT is a 4-byte fixed-decimal real-value format that Imagine uses in its TDDD files. To convert it to a double, simply cast the 4-byte long to a double and multiply by 65,536. In other words, a FRACT represents a real number via a 16-bit integer portion and a 16-bit fractional portion. Obviously, this constrains the range of FRACT values from --32768 to +32767. Care was taken to implement the low-level get_fract() and put_fract() routines in a CPU-independent form, so that this code runs on both Big-endian and Little-endian CPU architectures without modification.

The List class provides a simple mechanism to keep track of a list of Point arrays. Note that since we are only interested in the PNTS subchunks from the TDDD file, you can simply ignore all other IFF subchunks and store the PNTS arrays in the correct order. Then, to perform any kind of object manipulation, the first step is to read in all the PNTS arrays. When creating modified versions of the object, you must read the original at the same time as writing the modified version, filling in all the original data skipped over when searching for PNTS. The beauty of the List class is its constructors. Given a file pointer, the List class will read in the current PNTS subchunk being pointed to in the TDDD file. Given another List reference, however, the List class will make a new copy of the given list! This makes the programmer's task much easier when you start dealing with entire objects in the Object class.

The Object class includes the remainder of the TDDD-handling "smarts," plus constructors and destructors that make manipulating Imagine object PNTS a breeze for the programmer. Given a filename, the Object constructor reads in an entire Imagine object file, setting up the lists to point to the PNTS arrays properly, and keeping them in the correct order, as found in the file. It also saves the name of the original file for later use when writing out a modified copy of an Object. Given a reference to another Object class, Object copies the entire hierarchy very simply, taking advantage of the List constructor.

The most complex part of the Object class is the Output routine. When an Object is to be written to a file, the filename of the original object has already been copied with the constructor, so the original file is simply opened for read operations while the new object is opened for write. Instead of simply skipping over IFF chunks as was done during the reading of the file, bytes are now copied from the input to the output until the first PNTS subchunk is encountered. At this time, instead of copying the original file, the new internal point data from the first List object is written out. Then the original file is copied until the next PNTS subchunk is encountered, and so on, until the end of the file has been reached. This paradigm can easily be extended to keep track of any TDDD subchunks of interest, but in this case, only the PNTS subchunk is needed for modification.

One particularly useful feature of both the List and Object classes is that, while they load an object, they continuously update the MBB (minimum bounding box) information for the object. So when the object has been completely loaded, the Object class already "knows" the MBB of the object, and can easily calculate the center of this MBB. This information is then used by the melt algorithm.

The Melt Algorithm

The melt program first parses its arguments, then loads in the object to be morphed with the Object constructor. The next step is to loop over the number of frames desired, keeping track of the percentage of completion of the morph as it moves from the puddle back to the original object shape. For each iteration, we make a duplicate of the original object, again with an Object constructor, call the Tweak_Object function, output the modified object, and then delete it.

Tweak_Object() is the heart of the melt program. It iterates over all points in the object and modifies them based on the percent variable, which specifies how far this object is into the morph. If 0 percent is specified, the object is the puddle; 100 percent (percent variable equals 1.0) means that the object is in its original, untouched form. Of course, there is no need to call Tweak_Object with a percent value of 100 percent, so you just generate objects up to, but not including, this value. The Object class provides the first_point() and next_point() functions; these work in cooperation with the List class to easily iterate over all points without concerning the programmer with the start and end boundaries of each PNTS List.

I experimented with the actual algorithm used to move each point. I started out with a simple hermite curve to modify the radius of a given point based upon its vertical (z) height, which created a smooth transition with zero slopes both at the top and bottom of the object. This looked good closest to the "puddle" portion of the morph, but as the object grew vertically, its volume seemed to grow instead of remaining constant.

I then experimented with the function of an ellipse to give tangents to the z-axis at the top portion of the object and tangents to the x-y plane at the bottom of the object. This looked best near the higher-numbered objects. I calculated on paper how to keep the area constant under the curve such that the volume under the swept curve is also constant. I then made a smooth transition from the hermite function in lower-numbered objects to the ellipse function in higher-ordered objects, making sure to match up the top and bottom radii of the two functions. This was the effect I was looking for. The last step is to gradually "fade" (interpolate) from the swept-curve functions to the original object's real x- and y-coordinates. This nicely completes the effect.

This algorithm works best, as mentioned earlier, with star-shaped objects. You can get two examples of this on the Aminet file servers via anonymous ftp from ftp.wustl.edu or ftp.luth.se in the pub/aminet/gfx/3dobj directory. This directory contains four files: ChessMelt.readme, ChessMelt.lha, CowMelt.readme, and CowMelt.lha. ChessMelt contains a full set of chess pieces that have been melted into puddles with this program. CowMelt contains the Cow object that comes with Imagine 2.0. The effect on the chess pieces worked as intended, but the effect on the cow is rather bizarre. I will let you judge for yourselves. (My ReadWrite program is also available in the pub/aminet/gfx/3d directory as part of the T3DLIB package.)

Conclusion

The three classes--Point, List, and Object--create an excellent starting point for experimenting with IFF objects. In their present form, points can be manipulated in many different ways. However, a wealth of other information available in the TDDD files is begging to be processed as well. You could extend the program to alter not just points, but to also add, delete, and modify edges and faces. Also, you could work with color, reflectance, and transparency. You could even try experimenting with particle simulations, inverse kinematics, and dynamic constraints.

Figure 1: The "melt" effect in action. (a) (b) (c) (d)

Listing One


//----------------------------------------------------------------------
// melt.cc - T2-like melt effect (excerpted listing)   By Glenn M. Lewis 
//----------------------------------------------------------------------
#include <iostream.h>
#include <fstream.h>
#include <assert.h>
#include <ctype.h>
#include "t3dxx.h"
//----------------------------------------------------------------------
int num_frames = 0;
void Tweak_Object(int frame, Object &obj);
Object *mainobj=0;
extern "C" { int atoi(char*); }
char in_filename[100], out_root[100];
//----------------------------------------------------------------------
int main(int argc, char *argv[])
{
    int frame;

    Object *TmpObject;
    char filename[100];

    in_filename[0] = '\0';
    out_root[0] = '\0';
    num_frames = 10;
    for (int i=1; i<argc; i++) {
        if (isdigit(argv[i][0])) num_frames = atoi(argv[i]);
        else if (argv[i][0] == '-')
         cerr << "Unknown option: '" << argv[i] << "' ignored.\n";
        else if (!in_filename[0]) strcpy(in_filename, argv[i]);
        else if (!out_root[0]) strcpy(out_root, argv[i]);
        else {
                 Usage:
                 cerr << "Usage: " << argv[0] 
              << " [<num_frames>] infile outfile_root" << endl;
        return (-1);
        }
    }
    if (num_frames < 1 || !in_filename[0] || !out_root[0]) goto Usage;
    
    mainobj = new Object(in_filename);

    for (frame=0; frame<num_frames; frame++) {
        cerr << "Creating frame #" << frame << "...\n";
        TmpObject = new Object(*mainobj);   // Copy loaded Object
        assert(TmpObject != 0);
        Tweak_Object(frame, *TmpObject);
        sprintf(filename, "%s%03d.iob", out_root, frame);
        TmpObject->Output(filename);
        delete TmpObject;       // Destroy it
    }
    delete mainobj;
    return(0);
}
//----------------------------------------------------------------------
inline double interpolate(double percent, double zero_val, double one_val)
{
    return(percent*one_val + (1.0-percent)*zero_val);
}
//----------------------------------------------------------------------
inline double mini_hermite(double r, double top_r)
{
    if (r<top_r) return(0.0);
    assert(top_r != 1.0);
    r = (r-top_r)/(1.0-top_r);  // Renormalize
    return((3-r-r)*r*r);
}
//----------------------------------------------------------------------
void project_point_to_radius(double newr, Point& newp1)
{
    double r;
    if (newp1.x==0.0 && newp1.y==0.0) 
    return;                             // It *is* the center!
    // Normalize the direction vector...

    r = newr/sqrt(newp1.x*newp1.x + newp1.y*newp1.y);
    newp1.x *= r;
    newp1.y *= r;
    // z is unchanged
}
//----------------------------------------------------------------------
inline double calc_ellipse_r(double percent, double r, double a)
{
    return((0.9*percent + 1.1*(1.0-r)*a)*mainobj->max_radius());
}
//----------------------------------------------------------------------
inline double calc_ellipse_z(double r)
{   // The following was derived to keep the area under an ellipse constant.
    return(1.0-sqrt(1.0 - r*r));
}
//----------------------------------------------------------------------
inline double calc_hermite_r(double BOT_RAD, double TOP_RAD, double z_percent)
{   double r = 1.0 - z_percent;
    // the following was (TOP_RAD + BOT_RAD*r);
    return (BOT_RAD*r < TOP_RAD ? TOP_RAD : BOT_RAD*r); 
}
//----------------------------------------------------------------------
inline double calc_hermite_z(double BOT_RAD, double TOP_RAD, double z_percent)
{
    double r = 1.0 - z_percent;
    return(1.0 - mini_hermite(r, TOP_RAD/BOT_RAD));
}
//----------------------------------------------------------------------
const double K=2.0;
double last_z_percent;
//----------------------------------------------------------------------
void Tweak_Object(int frame, Object &obj)
{
    ofstream out, oute, outh;
    Point *point, newp1;
    double ellipse_r, ellipse_z;
    double hermite_r, hermite_z;
    double newr, z_percent;
    double percent = (double)frame/(double)num_frames;  // from 0...1
    double ZSIZE = percent*mainobj->height();           // Original mainobj!
    // Note that TOP_RAD must NOT ever equal BOT_RAD!
    double TOP_RAD = 0.9*percent*mainobj->max_radius(); // Original mainobj!
    double fade = percent;
    double BOT_RAD = interpolate(percent, K*mainobj->max_radius(),
                     mainobj->max_radius());
    double a = (1.0 - percent*percent)/(percent + (1.0/K));
    assert(TOP_RAD != BOT_RAD);
    assert(mainobj->height() != 0);
    assert(mainobj->max_radius() != 0);
    last_z_percent = -1.0;
    
    for (obj.first_point(point); point; obj.next_point(point)) {
      newp1.x = point->x - mainobj->xcenter();   // translate point to origin
      newp1.y = point->y - mainobj->ycenter();
      newp1.z = point->z - mainobj->zmin();


      z_percent = newp1.z/mainobj->height();
      
      ellipse_r = calc_ellipse_r(percent, z_percent, a);
      ellipse_z = calc_ellipse_z(z_percent);            // 0..1
      hermite_r = calc_hermite_r(BOT_RAD, TOP_RAD, z_percent);
      hermite_z = calc_hermite_z(BOT_RAD, TOP_RAD, z_percent);  // 0..1

      newr    = interpolate(fade, hermite_r, ellipse_r);
      newp1.z = ZSIZE * interpolate(fade, hermite_z, ellipse_z);

      project_point_to_radius(newr, newp1);

      newp1.x += mainobj->xcenter();
      newp1.y += mainobj->ycenter();
      newp1.z += mainobj->zmin();
      // We now have the new point location... fade to object.
      point->x = interpolate(fade, newp1.x, point->x);
      point->y = interpolate(fade, newp1.y, point->y);
      point->z = interpolate(fade, newp1.z, z_percent*ZSIZE+mainobj->zmin());
    }
}

Listing Two


//--------------------------------------------------------------------
// point.cc - the Point class  for "melt" program.     By Glenn Lewis
//--------------------------------------------------------------------
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include "t3dxx.h"
//----------------------------------------------------------------
double Point::get_fract(ifstream& inFile)
{
  unsigned char ch;
  unsigned long l;
  long l2;
  inFile.get(ch);  l = (unsigned long)ch;
  inFile.get(ch);  l = (l<<8)|(unsigned long)ch;
  inFile.get(ch);  l = (l<<8)|(unsigned long)ch;

  inFile.get(ch);  l = (l<<8)|(unsigned long)ch;
  l2 = (long)l;
  return (ROUNDIT((double)l2*(1.0/65536.0)));
}
//----------------------------------------------------------------
void Point::put_fract(double num, ofstream& outFile)
{
  long l;
  l = (long)(num*65536.0);
  outFile.put((unsigned char)((l>>24)&0xFF));
  outFile.put((unsigned char)((l>>16)&0xFF));
  outFile.put((unsigned char)((l>> 8)&0xFF));
  outFile.put((unsigned char)((l    )&0xFF));
}
//----------------------------------------------------------------
void Point::load(ifstream& inFile)
{
  x = get_fract(inFile);
  y = get_fract(inFile);
  z = get_fract(inFile);
}
//----------------------------------------------------------------
void Point::write(ofstream& outFile)
{
  put_fract(x, outFile);
  put_fract(y, outFile);
  put_fract(z, outFile);
}