Skeletal Animation for the Exploration of Graphs

This paper is the result of a research made by Damian Merrick and Tim Dwyer on the use of skeletal animation for the exploration of three-dimensional visualizations of graphs. This paper explores the possibility of a physical metaphor for navigation with a graph visualization. For that, they formulated and implemented three algorithms for performing skeletal animation in graph visualization systems, testing them with a group of users to determine the relative benefits and disadvantages. The paper can be downloaded from the following link.

Skeletal animation is a concept that has been implemented to provide the illusion of natural motion for computer-generated characters in films and computer games. And due to the fact that a skeleton is a structure that we, as humans, observe and manipulate constantly in the real world, this paper suggest that skeletal motion, simulated adequately, would be a natural and realistic physical metaphor. A physical metaphor allows users to relate the interaction mechanism with phenomena that occur in the real world, providing perceptual cues that will increase the intuitiveness of the visualization system.

The three algorithms formulated were: one based on a method called Cyclic Coordinate Descent(CCD), another based on the nonlinear optimization method, and the third a naïve dynamics-based implementation implemented as a natural extension to an existing 3D graph visualization system.

The approach taken by CCD is to solve a localized optimization problem at each bone in the articulated chain. At each step of the algorithm the bone in question is rotated (and with it all bones and joints below it in the chain) such that the distance between the end-effector (the last joint on the chain) and the desired position of the end-effector is minimized. This process starts from the bottom bone in the chain and works towards the top, then repeats over again, until the end-effector is within some threshold distance of its desired position.

After the tests, the CCD method is believed it to be the most intuitive and the most successful in maintaining the users mental maps over successive configurations of the skeleton. One significant flaw is that it is possible for error in positioning of end-effectors to accumulate, allowing bones to stretch a substantial distance from their original length.

The nonlinear programming method takes the approach of formulating the skeletal system as a set of model parameters, constraints and an objective function. These are passed on to a nonlinear optimization module, which attempts to produce a new set of model parameters that minimizes the objective function.

After the tests, the results from this method were rather discouraging, as the motion produced was jumpy and non-intuitive, compared with the smooth transitions of the other two algorithms. However, the nonlinear programming method did have the advantage of being able to keep bone lengths constant. This is due to the fact that these lengths need not be specified in the model parameters (and hence will not be changed).

The third algorithm explored a simple dynamics-based approach to providing a skeletal metaphor. That approach was implemented as an addition to the 3D graph visualization package Wilma, that makes use of a force directed algorithm for the layout of graphs, representing edges as springs connecting nodes.

After the tests, it was verified that this method still allowed a very large amount of stretch in bones. However it seemed to appeal to users as a reasonable technique for graph interaction and was reasonably intuitive. Smooth transitions were produced, due to the force-based layout, which aided retention of the mental map.