“Interactive manipulation of large-scale crowd animation” by Kim, Seol, Kwon and Lee

  • ©Jongmin Kim, Yeongho Seol, Taesoo Kwon, and Jehee Lee



Session Title:

    Animating Characters


    Interactive manipulation of large-scale crowd animation




    Editing large-scale crowd animation is a daunting task due to the lack of an efficient manipulation method. This paper presents a novel cage-based editing method for large-scale crowd animation. The cage encloses animated characters and supports convenient space/time manipulation methods that were unachievable with previous approaches. The proposed method is based on a combination of cage-based deformation and as-rigid-as-possible deformation with a set of constraints integrated into the system to produce desired results. Our system allows animators to edit existing crowd animations intuitively with real-time performance while maintaining complex interactions between individual characters. Our examples demonstrate how our cage-based user interfaces mitigate the time and effort for the user to manipulate large crowd animation.


    1. Arikan, O., Forsyth, D. A., and O’Brien, J. F. 2003. Motion synthesis from annotations. ACM Trans. Graph. 22, 3, 402–408. Google ScholarDigital Library
    2. Borosán, P., Howard, R., Zhang, S., and Nealen, A. 2010. Hybrid mesh editing. In Proceedings of EUROGRAPHICS Short papers, 41–44.Google Scholar
    3. Botsch, M., Pauly, M., Wicke, M., and Gross, M. 2007. Adaptive space deformations based on rigid cells. Computer Graphics Forum 26, 3, 339–347.Google ScholarCross Ref
    4. Boyd, S. 2003. Relaxations and randomized methods for nonconvex QCQPs. EE392o, Stanford University.Google Scholar
    5. Chenney, S. 2004. Flow tiles. In SIGGRAPH/Eurographics Symposium on Computer Animation ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 233–242. Google ScholarDigital Library
    6. Choi, M. G., Kim, M., Hyun, K., and Lee, J. 2011. Deformable motion: Squeezing into cluttered environments. Comput. Graph. Forum 30, 2, 445–453.Google ScholarCross Ref
    7. Cohen-Or, D. 2009. Space deformations, surface deformations and the opportunities in-between. J. Comput. Sci. Technol. 24, 1 (Jan.), 2–5. Google ScholarDigital Library
    8. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
    9. Gleicher, M. 1998. Retargeting motion to new characters. In Proceedings of SIGGRAPH 98, 33–42. Google ScholarDigital Library
    10. Guy, S. J., Chhugani, J., Kim, C., Satish, N., Lin, M., Manocha, D., and Dubey, P. 2009. Clearpath: highly parallel collision avoidance for multi-agent simulation. In Proceedings of the 2009 SIGGRAPH/Eurographics Symposium on Computer Animation, 177–187. Google ScholarDigital Library
    11. Ho, E. S. L., Komura, T., and Tai, C.-L. 2010. Spatial relationship preserving character motion adaptation. ACM Trans. Graph. 29, 4, 33:1–33:8. Google ScholarDigital Library
    12. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Trans. Graph. 25, 1424–1441. Google ScholarDigital Library
    13. Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L.-Y., Teng, S.-H., Bao, H., Guo, B., and Shum, H.-Y. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3, 1126–1134. Google ScholarDigital Library
    14. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 1134–1141. Google ScholarDigital Library
    15. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4, 78:1–78:8. Google ScholarDigital Library
    16. Jacobson, A., Baran, I., Kavan, L., Popović, J., and Sorkine, O. 2012. Fast automatic skinning transformations. ACM Trans. Graph. 31, 4, 77:1–77:10. Google ScholarDigital Library
    17. Jordao, K., Pettré, J., Christie, M., Cani, M.-P., et al. 2013. Crowd sculpting: A space-time sculpting method for populating virtual environments. EUROGRAPHICS 2014.Google Scholar
    18. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    19. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
    20. Ju, E., Choi, M. G., Park, M., Lee, J., Lee, K. H., and Takahashi, S. 2010. Morphable crowds. ACM Trans. Graph. 29, 6, 140:1–140:10. Google ScholarDigital Library
    21. Kim, M., Hyun, K., Kim, J., and Lee, J. 2009. Synchronized multi-character motion editing. ACM Trans. Graph. 28, 79:1–79:9. Google ScholarDigital Library
    22. Kim, M., Hwang, Y., Hyun, K., and Lee, J. 2012. Tiling motion patches. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 117–126. Google ScholarDigital Library
    23. Kovar, L., and Gleicher, M. 2004. Automated extraction and parameterization of motions in large data sets. ACM Trans. Graph. 23, 3, 559–568. Google ScholarDigital Library
    24. Kovar, L., Gleicher, M., and Pighin, F. 2002. Motion graphs. ACM Trans. Graph. 21, 3, 473–482. Google ScholarDigital Library
    25. Kwon, T., Lee, K. H., Lee, J., and Takahashi, S. 2008. Group motion editing. ACM Trans. Graph. 27, 3, 80:1–80:8. Google ScholarDigital Library
    26. 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
    27. 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 Trans. Graph. 21, 3, 491–500. Google ScholarDigital Library
    28. Lee, K. H., Choi, M. G., Hong, Q., and Lee, J. 2007. Group behavior from video: a data-driven approach to crowd simulation. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 109–118. Google ScholarDigital Library
    29. Lerner, A., Chrysanthou, Y., and Lischinski, D. 2007. Crowds by example. Computer Graphics Forum 26, 3, 655–664.Google ScholarCross Ref
    30. Lerner, A., Fitusi, E., Chrysanthou, Y., and Cohen-Or, D. 2009. Fitting behaviors to pedestrian simulations. Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 199–208. Google ScholarDigital Library
    31. 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
    32. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Proceedings of the fifth Eurographics symposium on Geometry processing, 117–123. Google ScholarDigital Library
    33. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 78:1–78:10. Google ScholarDigital Library
    34. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Proceedings of Eurographics Symposium on Geometry Processing, vol. 27, 1495–1504. Google ScholarDigital Library
    35. Mukai, T., and Kuriyama, S. 2005. Geostatistical motion interpolation. ACM Trans. Graph. 24, 3, 1062–1070. Google ScholarDigital Library
    36. 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
    37. Narain, R., Golas, A., Curtis, S., and Lin, M. C. 2009. Aggregate dynamics for dense crowd simulation. ACM Trans. Graph. 28, 5, 122:1–122:8. Google ScholarDigital Library
    38. Patil, S., Van Den Berg, J., Curtis, S., Lin, M. C., and Manocha, D. 2011. Directing crowd simulations using navigation fields. IEEE Transactions on Visualization and Computer Graphics 17, 2, 244–254. Google ScholarDigital Library
    39. PCL, 2012. Point Cloud Library. http://pointclouds.org/.Google Scholar
    40. Pelechano, N., O’Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. In Proceedings of the First International Workshop on Crowd Simulation, 24–25.Google Scholar
    41. Pelechano, N., Allbeck, J. M., and Badler, N. I. 2007. Controlling individual agents in high-density crowd simulation. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 99–108. Google ScholarDigital Library
    42. Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. In Proceedings of SIGGRAPH 87, 25–34. Google ScholarDigital Library
    43. Safonova, A., and Hodgins, J. K. 2007. Construction and optimal search of interpolated motion graphs. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    44. Shewchuk, J. R. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, May, 203–222. Google ScholarDigital Library
    45. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proceedings of the fifth Eurographics symposium on Geometry processing, 109–116. Google ScholarDigital Library
    46. Sorkine, O., Cohen-Or, D., Lipman, Y., and Alexa, M. 2004. Laplacian surface editing. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Geometry Processing, 175–184. Google ScholarDigital Library
    47. Sturm, J. F. 1999. Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software 11, 1–4, 625–653.Google ScholarCross Ref
    48. Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3, 80. Google ScholarDigital Library
    49. Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. ACM Trans. Graph. 25, 3, 1160–1168. Google ScholarDigital Library
    50. Umetani, N., Kaufman, D., Igarashi, T., and Grinspun, E. 2011. Sensitive Couture for Interactive Garment Editing and Modeling. ACM Trans. Graph. 30, 4. Google ScholarDigital Library
    51. Xu, W., Zhou, K., Yu, Y., Tan, Q., Peng, Q., and Guo, B. 2007. Gradient domain editing of deforming mesh sequences. ACM Trans. Graph. 26, 3. Google ScholarDigital Library

ACM Digital Library Publication: