FP-JamesAndrews
From CS294-10 Visualization Fa07
Contents |
[edit] Proposal
[edit] Group Members
- James Andrews
[edit] Description
[edit] Motivation
Motion graphs are great for getting good animation from a database, but it's hard to understand what the structure & connectivity of your graph will look like.
[edit] Overview
A normal piece of motion capture, video, etc, will have a linear path from frames 1 to the last frame (here: frame 10). There is only one valid traversal, so we can represent the graph of possible playbacks with this simple two-node digraph.
A motion graph defines additional valid paths, such as these drawn from frames 4 to 1 and 8 to 10. Here I draw the paths from the original “linear path” with double-line edges; note that these edges contain multiple frames of animation, while the single-line edges do not.
We can redraw the graph in Figure 2 with single-line edges clustered in groups; this is logical since they should represent very similar frames by the nature of a motion graph. When these clusterings get too large, I can break them apart with a segmentation algorithm, and when they get inconvenient I may break them arbitrarily; however I think for the default view they will be intuitive and helpful.
To represent the motion data along with the structural data of the graph, I want to place representative images at each cluster (for example: the average of those nodes). Additionally, I want to place a representation of the animation along the double-line edges; this could be a set of “representative” frames from that animation. The user should be able to understand each linear animation that was input in to the motion graph just by by following the double-line edges.
Now that I have defined a visual representation of the various states and animations within the motion graph, I want to use this to highlight details of the motion graph that are relevant to a motion-graph designer. For example, it is common to 'prune' motion graphs of nodes which, once reached, offer no path back to the majority of the graph -- in my example, nodes 8 and 10 would be pruned, and only the first four frames of the graph would be usable. This system could allow the user to see this by coloring edges according to the number of frames required to "undo" traversing that edge (i.e., to get back to the node after leaving), and could additionally highlight sections of the graph that would be pruned. It is also important to know how long it will take to traverse between two sections of the graph; although doing so will break apart some clusters, I can re-arrange the nodes in a circular structure around a clicked frame, according to distance, like what was done for the London subway map.
[edit] Details on Drawing "Rich" Edges
A ‘film strip’ view of an animation lays out a rendering of each frame in order; for 3D views we pick a consistent, character-relative viewpoint, which can be edited globally.
We can directly lay out our film strip view along graph edges to integrate graph structure and animation content. Unfortunately, this makes it difficult to curve edges, and could quickly become overwhelming as the graph grows.
To simplify our graphs, we will pick out ‘key’ edge frames, and only draw them. Frames are rated for interest by a function which considers (1) rate of change, so active areas are focused on, (2) temporal dissimilarity to already selected frames, and (3) spatial / geometric dissimilarity to already selected frames. The notion of “already selected” requires us to re-compute a similarity ordering each time we want to display another frame along an edge, but ensures that the most distinct set of frames will be displayed. Note that the frames at the nodes themselves, for the purposes of this algorithm, should always be considered as ‘already selected’ edge frames.
In practice, this algorithm should be done for the whole graph simultaneously, also potentially considering the user's clicks to guide focus, so that edges which are relatively uninteresting and do not need to be filled in with frames are skipped while edges which are especially fast-changing get the detail they need to be understood.
Unfortunately, this solution creates discontinuities in the edges at frame borders, making it more difficult to follow edge paths. It also does not preserve the edge’s function as a ‘time axis’ as the graph layout may arbitrarily distort the distances between 1, 3, 7, and 10.
To create continuous edges, we ‘bulge’ the double lines of the edges to surround drawn frames. To preserve our sense of time between frames, we put tick marks along edges; we can further shade between the double lines according to distance to a tick mark, as shown in the detail inset between frames 5 and 6. This should evoke the visual metaphor of a rubber band which has been stretched, and so be a natural additional indicator of the extent to which time is stretched. Along the same lines, distance between the double lines (marked as h, for height) can be varied with distance between marks (d), making long segments which cover much time skinnier than compressed segments which cover little time.
When possible, edge crossings should be maneuvered to avoid frame ‘bulges.’ To make it easy to follow edges, U-shaped “hops” as seen in circuit diagrams will be used, along with erasure of the ‘underneath’ edge lines where they are occluded.
[edit] Details on Sub-Clustering
Note that (unlike above) illustrations in this section use numbers which do not represent actual frame numbers; they just indicate an ordering of nodes.
The clustering idea breaks down when graphs are too well-connected.
For example, Figure 6 becomes this mess of self-loops back to one main cluster.
Let’s consider this more complex cluster.
We can perform a segmentation algorithm on the cluster, such as normalized cut, to break the cluster into smaller clumps.
Instead of circling the cluster normally, we let our ‘circle’ trace out the details of the smaller clumps; each clump is circled and the circles are joined as needed by small, smoothly blended rectangles (just big enough for the necessary single-line arrows to fit inside). After this process, the double-edged connections no longer all appear as homogenous self-loops.
[edit] New Visualization Ideas
I think this project contributes several new visualization ideas, such as the following:
- Integration of details such as animation frames directly with graph structure, while maintaining smooth edge lines
- Integration of time-step stretching with 'rubber band' shading
- Graph layout which is conscious of 'edge detail'
- Clustering graphs by 'short edges'
- Breaking apart clusters as organically shaped sub-clusters (visually similar to 2D metaballs) to maintain cluster outline while displaying the graph structure inside the cluster
- Using a graph display to allow a user to quickly understand and evaluate potential problems in a motion graph
[edit] Initial Problem Presentation
[edit] Midpoint Design Discussion
Midpoint progress notes:
Implementation has:
(1) Motion loading and rendering (2) Basic gui, skeleton of graph loading / display code
Next steps in implementation:
(1) Implement force directed graph layout (2) Experiment with clustering, etc.
Current source is living at http://www.eecs.berkeley.edu/~jima/MographVis.zip
Design ideas remain as reflected in the extensive notes above, although some of the stranger ideas (like arranging cluster outlines organically to reflect internal graph structure) are prioritized below others.
- Slides: [1]
[edit] Final Deliverables
- Link to source code and executable: [2]
- Link to final paper in pdf form: [3]
- Link to final slides or poster: [4]
