“Motion patches: building blocks for virtual environments annotated with motion data” by Lee, Choi and Lee

Real time animation of human figures in virtual environments is an important problem in the context of computer games and virtual environments. Recently, the use of large collections of captured motion data has increased realism in character animation. However, assuming that the virtual environment is large and complex, the effort of capturing motion data in a physical environment and adapting them to an extended virtual environment is the bottleneck for achieving interactive character animation and control. We present a new technique for allowing our animated characters to navigate through a large virtual environment, which is constructed using a set of building blocks. The building blocks, called motion patches, can be arbitrarily assembled to create novel environments. Each patch is annotated with motion data, which informs what actions are available for animated characters within the block. The versatility and flexibility of our approach are demonstrated through examples in which multiple characters are animated and controlled at interactive rates in large, complex virtual environments.

1. Abaci, T., Cíger, J., and Thalmann, D. 2005. Planning with smart objects. In WSCG (Short Papers), 25–28.Google Scholar
2. Arikan, O., and Forsyth, D. A. 2002. Interactive motion generation from examples. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 483–490. Google ScholarDigital Library
3. Arikan, O., Forsyth, D. A., and O’Brien, J. F. 2003. Motion synthesis from annotations. ACM Transactions on Graphics (SIGGRAPH 2003) 22, 3, 402–408. Google ScholarDigital Library
4. Arikan, O., Forsyth, D., and O’Brien, J. 2005. Pushing people around. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 59–66. Google ScholarDigital Library
5. Bandi, S., and Thalmann, D. 1997. A configuration space approach for efficient animation of human figures. In Proc. of IEEE Non Rigid and Articulated Motion Workshop, IEEECS Press. Google ScholarDigital Library
6. Bindiganavale, R., Granieri, J. P., Wei, S., Zhao, X., and Badler, N. I. 1994. Posture interpolation with collision avoidance. In Proceedings of Computer Animation ’94, 13–20.Google Scholar
7. Chenney, S. 2004. Flow tiles. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 233–242. Google ScholarDigital Library
8. Choi, M. G., Lee, J., and Shin, S. Y. 2003. Planning biped locomotion using motion capture data and probabilistic roadmaps. ACM Transactions on Graphics 22, 2, 182–203. Google ScholarDigital Library
9. Duda, R. O., Hart, P. E., and Stork, D. G. 2000. Pattern Classification. Wiley-Interscience. Google ScholarDigital Library
10. Grochow, K., Martin, S. L., Hertzmann, A., and Popović, Z. 2004. Style-based inverse kinematics. ACM Transactions on Graphics (SIGGRAPH 2004) 23, 3, 522–531. Google ScholarDigital Library
11. Hsu, E., Gentry, S., and Popović, J. 2004. Example-based control of human motion. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 69–77. Google ScholarDigital Library
12. Jung, M. R., Badler, N. I., and Noma, T. 1994. Animated human agents with motion planning capability for 3d-space postural goals. The Journal of Visualization and Computer Animation 5, 4, 225–246.Google ScholarCross Ref
13. Kalisiak, M., and Van De Panne, M. 2001. A grasp-based motion planning algorithm for character animation. The Journal of Visualization and Computer Animation 12, 3, 117–129.Google ScholarCross Ref
14. Kim, T., Park, S. I., and Shin, S. Y. 2003. Rhythmic-motion synthesis based on motion-beat analysis. ACM Transactions on Graphics (SIGGRAPH 2003) 22, 3, 392–401. Google ScholarDigital Library
15. Koga, Y., Kondo, K., Kuffer, J., and Latombe, J. 1994. Planning motions with intensions. Proceedings of SIGGRAPH ’94 28 (July), 395–408. Google ScholarDigital Library
16. Kovar, L., and Gleicher, M. 2004. Automated extraction and parameterization of motions in large data sets. ACM Transactions on Graphics (SIGGRAPH 2004) 23, 3, 559–568. Google ScholarDigital Library
17. Kovar, L., Gleicher, M., and Pighin, F. 2002. Motion graphs. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 473–482. Google ScholarDigital Library
18. Kuffner, J. J., Nishiwaki, K., Kagami, S., Inaba, M., and Inoue, H. 2001. Footstep planning among obstacles for biped robots. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS’01).Google Scholar
19. Kwon, T., and Shin, S. Y. 2005. Motion modeling for on-line locomotion synthesis. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 29–38. Google ScholarDigital Library
20. Lai, Y.-C., Chenney, S., and Fan, S. 2005. Group motion graphs. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 281–290. Google ScholarDigital Library
21. Latombe, J. C. 1991. Robot Motion Planning. Kluwer Academic Publishers. Google ScholarDigital Library
22. Lau, M., and Kuffner, J. J. 2005. Behavior planning for character animation. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 270–280. Google ScholarDigital Library
23. Lee, J., and Lee, K. H. 2004. Precomputing avatar behavior from human motion data. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 79–87. Google ScholarDigital Library
24. Lee, J., and Shin, S. Y. 1999. A hierarchical approach to interactive motion editing for human-like figures. In Proceedings of SIGGRAPH 99, 39–48. Google ScholarDigital Library
25. Lee, J., Chai, J., Reitsma, P. S. A., Hodgins, J. K., and Pollard, N. S. 2002. Interactive control of avatars animated with human motion data. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 491–500. Google ScholarDigital Library
26. Noser, H., Renault, O., Thalmann, D., and Thalmann, N. M. 1995. Navigation for digital actors based on synthetic vision, memory, and learning. Computer & Graphics 19, 1, 7–19.Google ScholarCross Ref
27. Park, S. I., Shin, H. J., Kim, T., and Shin, S. Y. 2004. On-line motion blending for real-time locomotion generation. Computer Animation and Virtual Worlds 15, 3, 125–138. Google ScholarDigital Library
28. Pettre, J., Laumond, J.-P., and Simeon, T. 2003. A 2-stages locomotion planner for digital actors. In SCA ’03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 258–264. Google ScholarDigital Library
29. Pullen, K., and Bregler, C. 2002. Motion capture assisted animation: Texturing and synthesis. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 501–508. Google ScholarDigital Library
30. Reitsma, P. S. A., and Pollard, N. S. 2004. Evaluating motion graphs for character navigation. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 89–98. Google ScholarDigital Library
31. Shao, W., and Terzopoulos, D. 2005. Autonomous pedestrians. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 19–28. Google ScholarDigital Library
32. Stone, M., DeCarlo, D., Oh, I., Rodriguez, C., Stere, A., Lees, A., and Bregler, C. 2004. Speaking with hands: Creating animated conversational characters from recordings of human performance. ACM Transactions on Graphics (SIGGRAPH 2004) 23, 3, 506–513. Google ScholarDigital Library
33. Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum (Eurographics 2004) 23, 3, 519–528.Google Scholar
34. Sung, M., Kovar, L., and Gleicher, M. 2005. Fast and accurate goal-directed motion synthesis for crowds. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 291–300. Google ScholarDigital Library
35. Tarjan, R. 1972. Depth first search and linear graph algorithms. SIAM Journal of Computing 1, 146–160.Google ScholarCross Ref
36. Thorne, M., Burke, D., and Van De Panne, M. 2004. Motion doodles: An interface for sketching character motion. ACM Transactions on Graphics (SIGGRAPH 2004) 23, 3, 424–431. Google ScholarDigital Library
37. Wang, J., and Bodenheimer, B. 2004. Computing the duration of motion transitions: An empirical approach. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 337–346. Google ScholarDigital Library
38. Yamane, K., Kuffner, J. J., and Hodgins, J. K. 2004. Synthesizing animations of human manipulation tasks. ACM Transactions on Graphics (SIGGRAPH 2004) 23, 3, 532–539. Google ScholarDigital Library