Skeletal animation for the exploration of graphs

ABSTRACT

The topic of skeletal animation and its associated techniques have previously been applied in the area of animating computer-generated characters for motion pictures and computer games. This paper investigates the use of similar techniques in the scope of exploring three-dimensional visualisations of graphs.A system is discussed which, after generating an initial 3D layout for a graph, creates a structural "skeleton" of the graph and allows a user to push, pull and drag nodes of the skeleton in order to manipulate the layout. Skeletal animation is used to smoothly animate the graph layout according to the movement applied by the user as well as various underlying constraints forced on the graph's skeleton. Several algorithms for performing this skeletal animation are proposed, and evaluated to determine the relative benefits and disadvantages of each.

References

1. Badler, N., Manoochehri, K. and Walters, G. (1987): Articulated figure positioning by multiple constraints. IEEE Comput. Graph. Appl. 7(6), pages 28--38.]]
2. Brady, M., Holierbach, J., Johnson, T., Lozano-Perez, T., and Mason, M., editors (1982): Robot Motion: Planning and Control. MIT Press, Cambridge.]]
3. Broyden, C. G. (1970): The convergence of a class of double-rank minimization algorithms 2. the new algorithm. J. Inst. Math. Appl. 6, pages 222--231.]]
4. Cockburn, A. and McKenzie, B. J. (2001): 3d or not 3d? evaluating the effect of the third dimension in a document management system. In CHI, pages 434--441.]]
5. Dwyer, T. (2000): Three dimensional uml using force directed layout. Technical Report TR2001/25, Department of Computer Science, The University of Melbourne, Parkville, Australia.]]
6. Dwyer, T. (2001): Three dimensional UML using force directed layout. In Eades, P. and Pattison, T., editors, Australian Symposium on Information Visualisation, (invis.au 2001), Sydney, Australia. ACS.]]
7. Eades, P., Lai, W., Misue, K. and Sugiyama, K. (1991): Preserving the mental map of a diagram. Technical Report IIAS-RR-91-16E, International Institute for Advanced Study of Social Information Science, Fujitsu Laboratories Ltd.]]
8. Fletcher, R. (1970): A new approach to variable metric algorithms. Comput. J. 13, pages 317--322.]]
9. Frick, A., Ludwig, A., and Mehldau, H. (1994): A fast adaptive layout algorithm for undirected graphs. In Proceedings of GD'94, volume 894, pages 388--403. Springer-Verlag, Berlin.]]
10. Goldfarb, D. (1970): A family of variable metric methods derived by variational means. SLAM J. Appl. Math. 17, 4, pages 739--764.]]
11. Herman, I., Marshall, M. S., Melancon, G., Duke, D. J., Delest, M., and Domenger, J.-P. (1999): Skeletal images as visual cues in graph visualization. In Gröller, E., Löffelmann, H., and Ribarsky, W., editors, Data Visualization '99, pages 13--22. Springer-Verlag Wien.]]
12. Klein, C. A. and Huang, C. H. (1983): Review of pseudoinverse control for use with kinematically redundant manipulators. IEEE Trans. Syst., Man, and Cybern., vol. SMC-13, no. 2, pages 245--250.]]
13. Merrick, D. (2002): Skeletal Animation for the Exploration of Graphs. Honours Thesis. School of Information Technologies, The University of Sydney.]]
14. Misue, K., Eades, P., Lai, W., and Sugiyama, K. (1995): Layout adjustment and the mental map. Journal of Visual Languages and Computing, 6(2):183--210.]]
15. Paul, R. P. (1981): Robot Manipulators, Mathematics, Programming and Control. The MJT Press, Cambridge.]]
16. Sciavicco, L. and Siciliano, B. (1987): A dynamic solution to the inverse kinematic problem for redundant manipulators. In Proc. IEEE Int. Conf. Robotics and Automation, Raleigh, North Carolina, pages 1081--1087.]]
17. Shanno, D. F. (1970): Conditioning of quasinewton methods for function minimization. Math. Comput. 24, pages 647--664.]]
18. Walshaw, C. (2000): A multilevel algorithm for force-directed graph drawing. In Proceedings of Graph Drawing 2000, volume 1984, pages 171--182. Springer-Verlag, Berlin.]]
19. Wang, L. C. T. and Chen, C. C. (1991): A combined optimization method for solving the inverse kinematics problem of mechanical manipulators. IEEE Transactions on Robotics and Automation, 7(4):489--499.]]
20. Ware, C, Franck, G. (1994): Viewing a graph in a virtual reality display is three times as good as a 2-D Diagram. In IEEE Conference on Visual Languages, pp. 182--183.]]
21. Ware, C, Hui, D., and Franck, G. (1993): Visualizing object oriented software in three dimensions. In Proc. IBM Centre for Advanced Studies Conf, CASCON.]]
22. Welman, C. (1993): Inverse kinematics and geometric constraints for articulated figure manipulation. Master's thesis, School of Computing Science, Simon Fraser University.]]
23. Wolovich, W. and Elliott, H. (1984): A computational technique for inverse kinematics. In Proc. 23rd. Conf. on Decision and Control, Las Vegas, NV.]]
24. Zhao, J. and Badler, N. I. (1994): Inverse kinematics positioning using nonlinear programming for highly articulated figures. ACM Transactions of Graphics (TOG), 13(4):313--336.]]

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Human-centered computing

• Mathematics of computing

  • Discrete mathematics

    • Graph theory