What we did
Our project was to implement Motion Graphs, which, as we learned in class, allow us to string together a set of animations to generate a arbitrarily long, smoothly-transitioning final animation. We put our project into the framework of Rachel's GeneralMotionResearch library. This allowed us to use her Skeleton, MotionParser, FootSkateSolver and Camera classes to bootstrap our work. We then added graph structures, including motion edges and nodes, point-cloud registration, and an implementation of Tarjan's algorithm.Motion Edges
In our implementation, motion edges contain a skeleton that holds on to a sequence of frames. Each frame defines a set of transformations, one for each of the joints of that skeleton. When we add nodes to an edge, we end up splitting that edge into two and throwing away the original. Each smaller edge contains a new skeleton which holds a subset of the frames of the original.
Nodes
For convenience, nodes contain a set of edges entering the node and a set of edges leaving the node. This allows us to easily choose from among the outgoing set when we walk to the graph, and also makes coding Tarjan's algorithm much simpler.Point-cloud Registration
As in Lucas's Motion Graphs paper, we perform registration by comparing point clouds in each frame of the original skeletons. For each pair of aligned point clouds, we calculate the difference between them. The set of candidate transitions is the set of local minima of this distance function that fall below a user-defined threshold. For those clouds that can be aligned, we create two candidate edges -- one going each way -- which store both a blending of the frames in the original skeleton, as well as a transformation that moves the destination skeleton into the source skeleton's frame of reference. We use this transformation when playing back the motion graph to keep the playing frame of reference consistent: after traversing an edge we multiply its frame into our master transform, ensuring alignment when we play subsequent edges.Tarjan's Algorithm
Because our resultant graph can contain inaccessible regions (both sources and sinks), we prune that graph using a variant of Tarjan's algorithm. As in the paper, Tarjan's is run in multiple passes, once for each set of unique labels within the graph. Each pass finds the largest strongly-connected component from those edges that have the same labels, and will remove any of those edges that are not part of that component. By running this on every set of labels, we prune the graph, while retaining the property that there's alwaysProblems we encountered
Most of our problems weren't with the theory of motion graphs, but with implementing them in the existing motion framework. Our two most difficult bugs were the result of an inconsistent assignment operator and delete function and a backwards slerp function. In the general motion research library, the assignment operator for skeletons copies their joints by reference, but the delete operator deletes every joint in the skeleton. Therefore, if a skeleton on the stack is set equal to another skeleton, both skeletons' joints are incorrectly deleted when the function returns. The spherical linear interpolation function simply accepts its arguments in a counterintuitive order.Aside from that, we initially neglected to interpolate across a window of frames to generate transitions, instead blending smoothly between transition points. This caused strange, stuttering output, as the edge transforms did not line up.
Our results
Here is our movie produced using a combination of running and kicking motions. We feel that this video demonstrates the correctness of our code. Several artifacts, particularly the abnormally fast motions this skeleton exhibits, remain. This problem could be solved by correctly dealing with momentum, but we did not attempt this.References
"Motion Graphs", Lucas Kovar"On Finding the Strongly Connected Components in a Directed Graph", Esko Nuutila, Eljas Soisalon-Soininen