Morphine

This project is an implementation of a triangle mesh morphing/animation system. The morphing of one triangle mesh to another is accomplished by a Parameterized Interpolating Polyhedron (PIP for short). Minkowski sums provide us with a simple method for interpolating between any initial and final shape, regardless of how complicated their boundaries are. We also use and compare screws to PCC biarcs for moving these morphs through time from one pose to another.

The following table outlines the how I spent my hours on this project:

Studying the assignment description, relevant portions of the course material, papers.	4 hours
Design of the concepts and approaches	2 hours
Programming and documenting your code	8 hours
Debugging	3 hours
Producing images and videos	3 hours
Writing up the report and integrating the whole thing in a webpage	6 hours

A lot of time on this project was spent working on a decent user interface. I set some pretty high goals for how I wanted interaction with the program to feel, and I was able to achieve most of them, but at a pretty high cost in time.

For this project, I decided to start over and build an application from scratch in Objective-C, using Apple's Cocoa environment on top of standard OpenGL calls so that I could build a powerful and flexible user interface (click on the image for a larger view):

Just because I'm proud of the interface, you can click here to see a movie of the interface being used. This movie was recorded in real time on my computer, so its kinda choppy-- it even gives me a bit of motion sickness, but its the only way I know to show off the interface right now.

The interface is pretty complete-- it allows you to position, rotate, and scale objects easily in 3D space, and also provides a variety of options to play with and a timeline slider to smoothly interpolate between poses and objects. Time is in no way discretized in this implementation, so you can put in any timeline length, and any number of frames per second to output to a movie file, a feature that was used in all of the movies on this page (with the exception of the screen capture movie above).

There's still a little to be desired as far as the interface goes. Saving of completed timelines and morphs is complete, but opening them is still a little buggy. Also, putting multiple morphs and motions into the timeline was a difficult user interface problem, so I left that out. A solution to that problem might be to have multple timelines which are strung together and have the slider move from one to the next when playing. I was planning on implementing this, but haven't found the time yet.

The morphing operator was implemented within a class (called Morph) that is initialized with two triangle meshes. The following few lines in the constructor create the mapping between each of the triangle meshes and the vertex and normal arrays used for sending data quickly to the graphics card.

    m2tri2verts = [self createTriVertMappingFrom: tmesh2 to: tmesh1];
    m1tri2verts = [self createTriVertMappingFrom: tmesh1 to: tmesh2];
    edgefaces = [self createEdgeFaceMapping];
    
    [self createVertexNormalTables];

A closer look at the triangle to vertex mapping function is as follows:

- (TriVertMap *)createTriVertMappingFrom:(TriMesh *)from to:(TriMesh *)to
{
    TriVertMap *map = new TriVertMap(from->numTriangles);
    BOOL tagged[to->numVertices];
    
    for (unsigned int ii = 0; ii < from->numTriangles; ii++)
    {
        Vec3 v1 = (from->vrt)[(from->crn)[3*ii+1]] - (from->vrt)[(from->crn)[3*ii]];
        Vec3 v2 = (from->vrt)[(from->crn)[3*ii+2]] - (from->vrt)[(from->crn)[3*ii]];
        Vec3 n = v1 % v2;
        n.normalize();
        
        for (unsigned int jj = 0; jj < to->numVertices; jj++)
            tagged[jj] = NO;
        
        for (unsigned int jj = 0; jj < to->numCorners; jj++)
        {
            if (!tagged[to->crn[jj]])
            {
                if (lsdVertex(n, to, jj))
                    (*map)[ii].push_back(to->crn[jj]);
                tagged[to->crn[jj]] = YES;
            }
        }
    }
    
    return map;
}

... it goes through all of the triangles of the first mesh, and finds vertices in the second mesh that satisfy the LSD property with the current triangle. This routine can be called from tmesh1 to tmesh2 and then from tmesh2 to tmesh1 in order to find all of the triangle-vertex and vertex-triangle mappings. Here's the rather simple code for the lsdVertex function:

BOOL lsdVertex(const Vec3 &nrm, TriMesh *tmesh, unsigned int ii)
{
    unsigned int current = ii;
    do {
        Vec3 e = tmesh->vrt[tmesh->crn[n(current)]] - tmesh->vrt[tmesh->crn[current]];
        if ((nrm | e) >= 0)
            return NO;
        current = n(tmesh->opp[n(current)]);
    } while (current != ii);
    
    return YES;
}

The edge-edge mapping takes place in its own function as well:

- (EdgeFaceMap *)createEdgeFaceMapping
{
    EdgeFaceMap *map = new EdgeFaceMap;
    for (unsigned int ii = 0; ii < tmesh1->numCorners; ii++)
    {
        unsigned int e1c1 = tmesh1->crn[ii];
        unsigned int e1c2 = tmesh1->crn[n(ii)];
        
        for (unsigned int jj = 0; jj < tmesh2->numCorners; jj++)
        {
            unsigned int e2c1 = tmesh2->crn[jj];
            unsigned int e2c2 = tmesh2->crn[n(jj)];
        
            // Edge tangents
            Vec3 t1 = tmesh1->vrt[e1c2] - tmesh1->vrt[e1c1];
            Vec3 t2 = tmesh2->vrt[e2c2] - tmesh2->vrt[e2c1];
            
            // Normal of those two edges
            Vec3 n = t1 % t2;
            n.normalize();
            
            Edge2Face e2f;
            e2f.m1v1 = e1c1;
            e2f.m1v2 = e1c2;
            e2f.m2v1 = e2c1;
            e2f.m2v2 = e2c2;
            
            if ((lsdEdge(n, tmesh1, ii, n(ii))) && (lsdEdge(n, tmesh2, jj, n(jj))))
                map->push_back(e2f);
        }
    }
    
    return map;
}

... this function calls the lsdEdge function to find out whether to form a map between any edge and another:

BOOL lsdEdge(const Vec3 &nrm, TriMesh *tmesh, unsigned int c1, unsigned int c2)
{
    // Find the two triangles bounded by this edge
    unsigned int current = c2;
    for (;;)
    {
        if ((tmesh->vrt[tmesh->crn[c1]] == tmesh->vrt[tmesh->crn[n(current)]]) &&
            (tmesh->vrt[tmesh->crn[c2]] == tmesh->vrt[tmesh->crn[current]]))
            break;
        
        current = n(tmesh->opp[n(current)]);
    }
    
    Vec3 e1s1 = tmesh->vrt[tmesh->crn[n(c1)]] - tmesh->vrt[tmesh->crn[c1]];
    Vec3 e1s2 = tmesh->vrt[tmesh->crn[p(c1)]] - tmesh->vrt[tmesh->crn[c1]];
    
    Vec3 e2s1 = tmesh->vrt[tmesh->crn[n(current)]] - tmesh->vrt[tmesh->crn[current]];
    Vec3 e2s2 = tmesh->vrt[tmesh->crn[p(current)]] - tmesh->vrt[tmesh->crn[current]];
    
    // Normal of triangle 1
    Vec3 n1 = e1s1 % e1s2;
    n1.normalize();
    
    // Normal of triangle 2
    Vec3 n2 = e2s1 % e2s2;
    n2.normalize();
    
    // Calculate inface normals
    Vec3 infn1 = n1 % e1s1;
    infn1.normalize();
    Vec3 infn2 = n2 % e2s1;
    infn2.normalize();
    
    return (((infn1 | nrm) < 0) && ((infn2 | nrm) < 0));
}

... note that this lsd function is much more involved than the lsdVertex function. I won't deny that this function accounted for most of the confusion for the morphing portion of the project. There were many times I need to sit back, relax, and go over it again, and sometimes talking it over with a friend helps too.

That was about it for the morphing phase of the project. Theres lots of other lines of code in the Morph class, of course, but those are involved in displaying the morph and bookkeeping, etc.

I think I had an unfair advantage on this section of the project, since I have done some extensive research on screw motion already. For this project, I decided to reuse lots of the code I have already developed for screw motion. I also used code I have developed for creating biarc wires from piecewise circular curves as an alternative to using screws for the pose-interpolating animations.

As part of a previous project, I have created a class called AbstractWire, which allows you to set a starting and ending pose and choose the wire type, then find an interpolated pose anywhere along the wire. Currently, the aforementioned biarc, screw, and translation only wires are supported, but there may be plans to try out other techniques later.

Putting it all together was simple, because it was all developed in the same program anyway. The Morph class needed to be able to access AbstractWire for the morph to move along the wire as planned. The function that finds the proper pose and loads it into the modelview matrix is as follows:

- (void)loadModelViewAtTime:(GLfloat)t withWireType:(WireType)wt
{
    Mat4 myPose;
    wire->computePose(wt, t, myPose);
    
    // Handle scale
    Mat4 *sc1, *sc2;
    sc1 = [tmesh1 scale];
    sc2 = [tmesh2 scale];
    Vec3 scale1 = (*sc1) * Vec3(1,1,1);
    Vec3 scale2 = (*sc2) * Vec3(1,1,1);
    Vec3 scale = scale1 * (1.0 - t) + scale2 * t;
    Mat4 sc;
    sc.scale(scale[0], scale[1], scale[2]);
    myPose = myPose * sc;
    
    myPose.columns(myPose.columnV3(0), myPose.columnV3(1), -myPose.columnV3(2), myPose.columnV3(3));
    
    GLfloat m[16];
    
    m[0] = myPose[0][0];      m[4] = myPose[0][1];      m[8]  = myPose[0][2];     m[12] = myPose[0][3];
    m[1] = myPose[1][0];      m[5] = myPose[1][1];      m[9]  = myPose[1][2];     m[13] = myPose[1][3];
    m[2] = myPose[2][0];      m[6] = myPose[2][1];      m[10] = myPose[2][2];     m[14] = myPose[2][3];
    m[3] = myPose[3][0];      m[7] = myPose[3][1];      m[11] = myPose[3][2];     m[15] = myPose[3][3];
    
    glMultMatrixf(m);
}

... note that the function handles scaling from one pose to another separately, since the AbstractWire class has no idea of how to handle scale.

	Here is a closeup shot of a morph from a cow shape to a tetrahedron. Note that the triangles of one half of the cow are all mapped to the outer vertex, causing the cow's shape to be visible on that vertex about 3/4 of the way through time. Click on the picture for a larger view!
	This is a good shot of a morph between a goblet and some funny "handles" triangle mesh. The morph travels along a screw motion (the yellow wire). Click on the picture for a movie, or click here for a larger view!
	These shots demonstrate the differences between the biarc and screw methods of interpolating the poses. The biarc method can be preferred because when you tack one motion onto another, the wires, at the joining point, are always guaranteed to be tangent to each other. The screw motion, on the other hand, provides us with a single motion that provides a more constant angular momentum for the object. TOP: BiArc motion, BOTTOM: Screw motion. Click on each picture for an animation!
	This is another comparison of the biarc, screw, and translation only wires types. Click on a picture for a larger view!
	Here's a shot that demonstrates how the morphing process works. The green colored triangles are those which are mapped from triangles on mesh 1 to vertices on mesh 2. The blue triangles are mapped from triangles on mesh 2 to vertices on mesh 1. The red triangles are mapped from edges on one mesh to edges on the other. Click on the picture for a larger view!
	Here's a couple of movies that pay homage to my new video game, PHAGE. For these movies, the models that were chosen are the white blood cell model and the red blood cell model from the game. The bottom movie is colored using the red/green/blue scheme described above. Click on a picture for a movie!
	Some movies that show a morph from the cow shape to a spikey shape. Once again, the bottom movie is colored using the red/green/blue scheme described above. Click on a picture for a movie!
	A classic. The demonstration of a morph between a cube and a sphere. A very simple, but effective demonstration of the red/blue/green coloring scheme is available in the bottom movie. Click on a picture for a movie!
	A cool morph between the random and square-intersect models. Click on the picture for a movie!
	More shots to demonstrate the differences between the wire types. Here the models are the white blood cell model from PHAGE and a sphere model. TOP: BiArc motion, MIDDLE: Screw motion, BOTTOM: Translation only. Click on each picture for an animation!
	As requested by Jarek, here's an animation demonstrating a morph from the dresser model to the sphere. Midway between looks pretty neat... could probably be found in a crazy furniture showroom downtown somewhere. TOP: Dresser-sphere, BOTTOM: Dresser-sphere, colored. Click on each picture for an animation!
	Another requested by Jarek, this is an animation similar to the goblet-handles animation above, but this time the handles model has been aligned vertically with the goblet.

This project was quite a lot of work. I learned a lot about how to better integrate OpenGL selection mechanisms and the Mac OS X Cocoa environment to get a seamless user interface. The actual requirements for the project were comparatively simple to implement, but there were plenty of snags along the way with those as well. It was pretty fun the whole time, though!

Running times of this program were very reasonable. The longest morph calculation took only about 20 seconds, which is pretty good considering how slow my laptop is as of late.

I am glad that I had the chance to code this program on my own. But, a little bit of me wonders how crazy cool it could have been if my former partner Brian Whited and I had worked together!