“Group motion editing” by Kwon, Lee, Lee and Takahashi

Animating a crowd of characters is an important problem in computer graphics. The latest techniques enable highly realistic group motions to be produced in feature animation films and video games. However, interactive methods have not emerged yet for editing the existing group motion of multiple characters. We present an approach to editing group motion as a whole while maintaining its neighborhood formation and individual moving trajectories in the original animation as much as possible. The user can deform a group motion by pinning or dragging individuals. Multiple group motions can be stitched or merged to form a longer or larger group motion while avoiding collisions. These editing operations rely on a novel graph structure, in which vertices represent positions of individuals at specific frames and edges encode neighborhood formations and moving trajectories. We employ a shape-manipulation technique to minimize the distortion of relative arrangements among adjacent vertices while editing the graph structure. The usefulness and flexibility of our approach is demonstrated through examples in which the user creates and edits complex crowd animations interactively using a collection of group motion clips.

1. 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
2. Bartels, R. H., Beatty, J. C., and Barsky, B. A. 1987. An introduction to splines for use in computer graphics & geometric modeling. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
3. Belongie, S., Malik, J., and Puzicha, J. 2002. Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell. 24, 4, 509–522. Google ScholarDigital Library
4. Chenney, S. 2004. Flow tiles. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 233–242. Google ScholarDigital Library
5. Courty, N., and Corpetti, T. 2007. Crowd motion capture. Computer Animation and Virtual Worlds 18, 4–5, 361–370. Google ScholarDigital Library
6. Gleicher, M. 1997. Motion editing with spacetime constraints. In I3D ’97: Proceedings of the 1997 Symposium on Interactive 3D graphics, 139–148. Google ScholarDigital Library
7. Hughes, R. L. 2003. The flow of human crowds. Annual Review of Fluid Mechanics 35, 169–182.Google ScholarCross Ref
8. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Transactions on Graphics (SIGGRAPH 2005) 24, 3, 1134–1141. Google ScholarDigital Library
9. Kovar, L., Gleicher, M., and Pighin, F. 2002. Motion graphs. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 473–482. Google ScholarDigital Library
10. Kwon, T., and Shin, S. Y. 2007. A steering model for on-line locomotion synthesis. Computer Animation and Virtual Worlds 18, 4–5, 463–472. Google ScholarCross Ref
11. 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
12. Lee, J., and Shin, S. Y. 1999. A hierarchical approach to interactive motion editing for human-like figures. In SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, 39–48. Google ScholarDigital Library
13. 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
14. Lee, K. H., Choi, M. G., Hong, Q., and Lee, J. 2007. Group behavior from video: a data-driven approach to crowd simulation. In SCA ’07: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 109–118. Google ScholarDigital Library
15. Lerner, A., Chrysanthou, Y., and Lischinski, D. 2007. Crowds by example. Computer Graphics Forum (Eurographics 2007) 26, 3, 655–664.Google Scholar
16. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479–487. Google ScholarDigital Library
17. Mukai, T., and Kuriyama, S. 2005. Geostatistical motion interpolation. ACM Transactions on Graphics (SIGGRAPH 2005) 24, 3, 1062–1070. Google ScholarDigital Library
18. Musse, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. In Computer Animation and Simulation ’97, 39–51.Google Scholar
19. Paris, S., Pettré, J., and Donikian, S. 2007. Pedestrian reactive navigation for crowd simulation: a predictive approach. Computer Graphics Forum (Eurographics 2007) 26, 3, 665–675.Google Scholar
20. Pelechano, N., O’Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. In V-CROWDS ’05: Proceedings of the First International Workshop on Crowd Simulation, 24–25.Google Scholar
21. Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. In SIGGRAPH ’87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, 25–34. Google ScholarDigital Library
22. Rose, C., Guenter, B., Bodenheimer, B., and Cohen, M. F. 1996. Efficient generation of motion transitions using spacetime constraints. In Proceedings of SIGGRAPH 1996, 147–154. Google ScholarDigital Library
23. Rose, C., Cohen, M. F., and Bodenheimer, B. 1998. Verbs and adverbs: Multidimensional motion interpolation. IEEE Computer Graphics & Applications 18, 5, 32–40. Google ScholarDigital Library
24. 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
25. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., R’ossl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In SGP ‘2004: Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 175–184. Google ScholarDigital Library
26. Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. ACM Transactions on Graphics (SIGGRAPH 2006) 25, 3, 1160–1168. Google ScholarDigital Library
27. Xu, W., Zhou, K., Yu, Y., Tan, Q., Peng, Q., and Guo, B. 2007. Gradient domain editing of deforming mesh sequences. ACM Transactions on Graphics (SIGGRAPH 2007) 26, 3, 84. Google ScholarDigital Library