A3-JamesAndrews
From CS294-10 Visualization Fa07
Contents |
[edit] Final result
[edit] Application
Source: [1]
Note that you probably need the J# 2.0 framework runtime installed to compile the main pathview program. You also need Tao for OpenGL and GLFW, which I used for display. The J# Runtime may be downloaded at [2] and Tao may be downloaded at [3]. I also include the source for Scrapemeta and wiicap -- these are helper programs; I wrote scrapemeta for this project, and wiicap I just modified. Scrapemeta is to grab the metadata for cmu's motion capture files, and give a description file of everything in that hierarchy (although I did not implement the actual brushing / detail on demand features described in the storyboard, this code would be key for adding that functionality)
Binary: [4]
You may also need the J# redistributable [[5]] for the binaries; I'm not sure. .Net itself would definitely be necessary. You will also need cmu's 1gb allasfamc file [6] of motion capture data to sit in c:\, since this program assumes it's there and reads from it.
Later version: [7]
This is a more recent version (put up < 1 day after deadline) version that has things like coloring lines based on size, and should load 10 paths by default instead of 10. Binaries are buried in the debug directory; the c:\allasfamc.zip file is still needed.
[edit] A brief description of your final interactive visualization application.
My code implements the first few steps (0,1,2) from my storyboard. I color lines based on the number of segments they represent -- this helps alleviate issues with lack of 3D shading from GL_LINES (note -- the shaded line version was completed after deadline, like this more detailed description; I'll put a new link to that version some time later.). I also provide keys to change the global interest function, so one can see how the function works. My fundamental unit is a "line segment" which is in practice just a point in space (with direction). I do segment clustering by a simple region growing algorithm in which all points which are not within threshold of an existing region average are given their own region, and otherwise are assigned to the region of best match.
The display of paths itself is a bit buggy; segments that should be connected are not always so; for the most part you should still be able to make out paths where necessary (the points themselves will be drawn if they do not form paths)
Though my implementation is far from perfect, I think that it provides an interesting test of the concept. In particular, it does make several things clear to me:
1. Motion paths for joints (in particular, end effectors) do not in themselves look very recognizable. Removing the contribution of the root position and orientation, while it does normalize the data to some extent, makes understanding the data intuitively even harder. Therefore pure motion paths do not seem like a good representation on their own for static visualization of motion.
2. Motion paths are expensive! Just displaying five joint motions from one file (admittedly with inefficient use of glBegin() glEnd(), and in c#, etc) was surprisingly slow. For real time interaction with the data, a hierarchical approach is critical.
3. My path segment algorithm looses a lot of path detail along edges (fundamentally, not because of bugs) and the shape of the graph can change surprisingly when transitioning between detail levels. A new algorithm would needed; one that keeps shape better and smoothly transitions between detail levels would be ideal.
If I were to come at this problem again, I would have to throw away some of the core algorithms and ideas behind this attempt. Although the program is not in itself very useful, I do consider it an informative prototype.
Controls:
Arrow keys rotate the view
Click a motion path to expand details in the region of your click
Press pageup / pagedown to change threshold sensitivity. Home/End and Insert/Delete also do this, but at different speeds.
Currently it is set to only look at a fixed number of paths from the database, since I did not implement any disk-caching of the draw tree, and it has to do the pre-process whenever you run it; also because it starts to get meaningless (and impossible to refine to highest detail) when you add too many path sets.
[edit] How long did this take?
I have no idea. More than 20 hours?
[edit] What aspects took the most time?
There was a lot of work just in getting the motion paths viewable at all; loading them from the zip file and getting their description information from the web (via a custom program) and then extracting path information from the asf/amc files (which provide joint length and angles) and then setting up an opengl display -- all that was a large part of my time. Also debugging connectivity issues (eg how do I find connectivity between segment groups as they change without traversing below the current level of detail? My solution was simple on paper but has some cases that apparently bite me, and I still haven't figured out what all is wrong with it.)
[edit] Storyboard and prep
[edit] Data Domain
I'm going to use motion paths from the CMU Mo-cap database, at [8]. For a given set of motion files I will hold skeleton root's position and orientation constant and extract 3D paths from representative joints of the skeletons (eg, hands, feet, head) for many motion files, generating reasonable amounts of overlapping paths.
[edit] Interactive visualization application
Features of the application:
0. Static display of 3D paths as curves (tubes) in 3d space.
1. Path aggregation: motion paths will be considered in segments, and similar segments will be aggregated as one larger, average path. The level of aggregation will depend on a path 'interest function'. Radius of path tube will be proportional to the number of paths aggregated in that tube.
2. Change regions of interest by clicking: Clicking a path segment will focus interest in the region around that segment, as well as paths which are aggregated within that segment, thus showing more detail.
3. 'Brushing' selection of paths will highlight paths that come from the same motions -- eg, clicking a hand path will highlight the corresponding path of the other hand, as well as corresponding feet and head paths.
4. Detail panel will show the names of selected paths in a nested tree view by category, subcategory, and description.
5. Optionally, the detail panel may be used as a reverse brushing tool; in this mode it will show all files in the tree view, and selecting categories, subcategories, or files will highlight the corresponding motion paths in the data.
To control the scope of this project, I've listed these features in order of their implementation -- by features 2 or 3 I should already have an interesting visualization tool, so I can implement features beyond that depending on how much time it takes to get to that stage.
[edit] Effectiveness
Explanation of why the interaction techniques will be effective in the context of your data domain:
0. These static curves allow users to visualize all motion paths simultaneously, in the same space, which should allow users to understand and see patterns in the motion as a whole. Since the space of natural human poses is different from the space of possible human poses, this will help the users understand where the natural human poses exist.
1. Since many of these curves will occupy the same space, it will be hard to see individual curves as the number of curves increases. By showing aggregate curves instead, we simplify the view and allow users to pick out common motion paths. (Optionally: Pairs of aggregate path segments which both contain at least one of the same path will have thin lines sparsely connecting them.)
2. Some aggregation may obscure interesting details, but removing aggregation altogether may equally obscure those details. Changing level of aggregation locally can show those interesting details without the irrelevant details of other path-groups.
3. Brushing will allow users to understand the relationship between motion of different body parts, and answer questions like: "When foot motion follows this path, does hand motion also group?" "To what extent can we infer the motion of one joint from the other?"
4. The detail panel will connect the motion paths back to the high level picture -- what motion did these paths come from? It will allow users to understand what types of motions cause the specific motion paths they select.
5. The reverse brushing will allow users to zoom in right away on the types of motion they are interested in (eg, highlight all locomotion motion). It will allow easy comparison of motion types -- eg the user can switch between highlighting running and highlighting walking, to get a sense of where the fundamental differences between the two types of motion exist.
[edit] Algorithm
To perform (hopefully fast) path aggregation, I plan to use the following algorithm:
Pre-process:
1. Break paths into path segments (initially: linear line segments).
2. Define a similarity function for comparing two line segments; make a graph of similar segments. Each node in the graph is a segment; segments connect to their neighboring segments sorted by distance. Segments also note their previous and after segments in their path, if existing.
3. Make a tree of cliques. At the highest level, we have the complete graph. To create lower levels, we constrain the similarity threshold at which we consider two segments connected, and then find cliques at that new threshold. Segments which fall in to multiple different cliques are removed from all cliques except the 'best fit' clique -- the one with the lowest (average? sum of squares?) distance to all neighbors. At each level, we record a bounding for that level.
Runtime -- on updates to the interest function:
1. Traverse the tree until we find a set of cliques whose connection-threshold is lower than the max allowed by the interest function. Since interest is determined locally, max interest within the bounding sphere is used. Interest at any point will be determined as a function of the minimum distance from a set of points, so merely checking the distance between the bounding sphere center and the set of interest points will tell us if we need to go lower in the tree or not. Mark the found cliques as the 'active cliques'.
2. Find connectivity between the active cliques -- we can do this by traversing down to the (1-clique) leaves, recording each leaf's active super-clique, then, for each active super-clique, connecting to the active super-cliques its children connect to. By checking a hash, we can count redundant connections and remember the amount, storing just the first connection + that count, which will be used to change thickness. We can also count the number of leafs contained in the active clique at this stage, and can compute other connectivity information, such as 'where are the related cliques' for brushing purposes.
3. Compute average paths and connected paths for the active cliques. (Potentially use Bezier curves)
Runtime -- per frame:
1. Render the active cliques!
[edit] James Andrews - Nov 04, 2007 01:59:51 am
Just a few afterthoughts / notes about this project:
- When you load up the program, you'll probably just see a single dot; you need to click it for it to specifically focus on an area and show detail. You should also make the console from which you run the program visible, and play with the page up / page down keys until the number it prints is low enough to show the level of detail you want, but not so low the frame rate is zero.
- If you don't want to download the whole cmu mocap database (1 gb), the program should run out of the box with this: http://eecs.berkeley.edu/~jima/allasfamc.zip ... a smaller version which takes advantage of the fact that I only actually use a small subset of the database on the program's default settings.
- There are some screens of how it looks in action here: http://www.eecs.berkeley.edu/~jima/pathview_screens/ ... as you can see, it's hard to make out much from this mess of paths, but I think I can sort of make out the structure of a two circles / rings of higher density where you would expect the hands and feet to be.
