Procedural skeletons: kinematic extensions to CGA-shape grammars

ABSTRACT

Procedural modeling for architectural scenes was as yet limited to static objects only. We introduce a novel extension layer for shape grammars which creates a skeletal system for posing and interactive manipulation of generated models. Various models can be derived with the same set of parametrized rules for geometric operations. Separation of geometry generation and pose synthesis improves design efficiency and reusability. Moreover, by formal analysis of production rules we show how to efficiently update complex kinematic hierarchies created by the skeletons, allowing state-of-the-art interactive visual rule editing.

References

1. Beirão, J., and Duarte, J. 2005. Urban grammars: towards flexible urban design. Proc. 23rd Int. eCAADe Conf, 491--500.
2. Bloomenthal, J. 1999. Skeletal methods of shape manipulation. Proceedings Shape Modeling International '99. International Conference on Shape Modeling and Applications, 44--47.
3. Chadwick, J. E., Haumann, D. R., and Parent, R. E. 1989. Layered construction for deformable animated characters. ACM SIGGRAPH Computer Graphics 23, 3 (Juli), 243--252.
4. Collins, G., and Hilton, A. 2001. Models for character animation. Software Focus 2, 2, 44--51.
5. Denavit, J., and Hartenberg, R. 1955. A kinematic notation for lower-pair mechanisms based on matrices. J Appl Mech 23, 215--221.
6. Downing, F., and Flemming, U. 1981. The bungalows of buffalo. Environment and Planning B 8, 3, 269--293.
7. Durikovic, R., Kaneda, K., and Yamashita, H. 1998. Animation of Biological Organ Growth Based on L-systems. Computer Graphics Forum 17, 3 (August), 1--13.
8. Fisher, D., 2008. Dynamic architecture. http://www.dynamicarchitecture.net/ accessed in March 2010.
9. Lipp, M., Wonka, P., and Wimmer, M. 2008. Interactive visual editing of grammars for procedural architecture. ACM Transactions on Graphics (TOG) 27, 3, 102.
10. Maestri, G. 1999. Digital Character Animation 2: Essential Techniques. New Riders, Indianapolis.
11. Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Van Gool, L. 2006. Procedural modeling of buildings. ACM Transactions on Graphics (TOG) 25, 3, 614--623.
12. Měch, R., and Prusinkiewicz, P. 1996. Visual models of plants interacting with their environment. In Proceedings of SIGGRAPH'96, ACM, 397--410.
13. Noser, H., and Thalmann, D. 1999. A rule-based interactive behavioral animation system for humanoids. IEEE Transactions on Visualization and Computer Graphics 5, 4, 281--307.
14. Noser, H., Thalmann, D., and Turner, R. 1992. Animation based on the Interaction of L-systems with Vector Force Fields. In Proc. Computer Graphics International, Springer-Verlag New York, Inc., vol. 92, 747--761.
15. Prusinkiewicz, P., and Lindenmayer, A. 1991. The Algorithmic Beauty of Plants. Springer-Verlag, New York, NY, USA.
16. Prusinkiewicz, P., Hammel, M., and Mjolsness, E. 1993. Animation of plant development. In Proceedings of SIGGRAPH'93, ACM, vol. 93, 351--360.
17. Prusinkiewicz, P., Mündermann, L., Karwowski, R., and Lane, B. 2001. The use of positional information in the modeling of plants. In Proceedings of SIGGRAPH'01, ACM, vol. 12, 289--300.
18. Sakaguchi, T., and Ohya, J. 1999. Modeling and animation of botanical trees for interactive virtual environments. Proceedings of the ACM symposium on Virtual reality software and technology - VRST '99, 139--146.
19. Smidt, W. 1998. Verallgemeinerte inverse Kinematik für Anwendungen in der Robotersimulation und der virtuellen Realität. Master thesis, Universität Dortmund.
20. Stiny, G. 1975. Pictorial and formal aspects of shape and shape grammars and aesthetic systems. PhD thesis, University of California, Los Angeles.
21. Vanegas, C. A., Aliaga, D. G., Wonka, P., Waddell, P., and Watson, B. 2010. Modeling the Appearance and Behavior of Urban Spaces. Computer Graphics Forum 29, 1, 25--42.
22. 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.
23. Whiting, E., Ochsendorf, J., and Durand, F. 2009. Procedural modeling of structurally-sound masonry buildings. ACM Transactions on Graphics 28, 5, 1.
24. Wonka, P., Wimmer, M., Sillion, F., and Ribarsky, W. 2003. Instant architecture. ACM Transactions on Graphics 22, 3 (Juli), 669--677.
25. Zhao, J., and Badler, N. I. 1994. Inverse kinematics positioning using nonlinear programming for highly articulated figures. ACM Transactions on Graphics 13, 4 (Oktober), 313--336.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

    • Shape modeling

• Theory of computation

  • Formal languages and automata theory

    • Formalisms

      • Rewrite systems

    • Grammars and context-free languages

  • Randomness, geometry and discrete structures

    • Computational geometry