“Vector graphics animation with time-varying topology” by Dalstein, Ronfard and Panne

  • ©Boris Dalstein, Rémi Ronfard, and Michiel van de Panne




    Vector graphics animation with time-varying topology



    We introduce the Vector Animation Complex (VAC), a novel data structure for vector graphics animation, designed to support the modeling of time-continuous topological events. This allows features of a connected drawing to merge, split, appear, or disappear at desired times via keyframes that introduce the desired topological change. Because the resulting space-time complex directly captures the time-varying topological structure, features are readily edited in both space and time in a way that reflects the intent of the drawing. A formal description of the data structure is provided, along with topological and geometric invariants. We illustrate our modeling paradigm with experimental results on various examples.


    1. Agarwala, A., Hertzmann, A., Salesin, D. H., and Seitz, S. M. 2004. Keyframe-based tracking for rotoscoping and animation. ACM Trans. Graph. 23, 3, 584–591. Google ScholarDigital Library
    2. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of SIGGRAPH 2000, 157–164. Google ScholarDigital Library
    3. Asente, P., Schuster, M., and Pettit, T. 2007. Dynamic planar map illustration. ACM Trans. Graph. 26, 3, 30:1–30:10. Google ScholarDigital Library
    4. Baudelaire, P., and Gangnet, M. 1989. Planar maps: An interaction paradigm for graphic design. In Proceedings of CHI ’89, 313–318. Google ScholarDigital Library
    5. Baxter, W., Barla, P., and Anjyo, K.-I. 2009. Compatible embedding for 2d shape animation. IEEE Trans. on Visualization and Computer Graphics 15, 5, 867–879. Google ScholarDigital Library
    6. Bénard, P., Lu, J., Cole, F., Finkelstein, A., and Thollot, J. 2012. Active strokes: Coherent line stylization for animated 3d models. In Proceedings of NPAR ’12, 37–46. Google ScholarDigital Library
    7. Bénard, P., Hertzmann, A., and Kass, M. 2014. Computing smooth surface contours with accurate topology. ACM Trans. Graph. 33, 2, 19:1–19:21. Google ScholarDigital Library
    8. Blair, P. 1994. Cartoon animation. How to Draw and Paint Series. W. Foster Pub.Google Scholar
    9. Bregler, C., Loeb, L., Chuang, E., and Deshpande, H. 2002. Turning to the masters: Motion capturing cartoons. ACM Trans. Graph. 21, 3, 399–407. Google ScholarDigital Library
    10. Buchholz, B., Faraj, N., Paris, S., Eisemann, E., and Boubekeur, T. 2011. Spatio-temporal analysis for parameterizing animated lines. In Proceedings of NPAR ’11, 85–92. Google ScholarDigital Library
    11. Burtnyk, N., and Wein, M. 1971. Computer-generated keyframe animation. Journal of the Society of Motion Picture & Television Engineers 80, 3, 149–153.Google Scholar
    12. Catmull, E. 1978. The problems of computer-assisted animation. SIGGRAPH Comput. Graph. 12, 3, 348–353. Google ScholarDigital Library
    13. Dalstein, B., Ronfard, R., and van de Panne, M. 2014. Vector graphics complexes. ACM Trans. Graph. 33, 4, 133:1–133:12. Google ScholarDigital Library
    14. de Floriani, L., Hui, A., Panozzo, D., and Canino, D. 2010. A dimension-independent data structure for simplicial complexes. In Proceedings of the 19th International Meshing Roundtable, 403–420.Google Scholar
    15. de Juan, C. N., and Bodenheimer, B. 2006. Re-using traditional animation: methods for semi-automatic segmentation and inbetweening. In Proceedings of SCA ’06, 223–232. Google ScholarDigital Library
    16. Eisemann, E., Paris, S., and Durand, F. 2009. A visibility algorithm for converting 3D meshes into editable 2D vector graphics. ACM Trans. Graph. 28, 3, 83:1–83:8. Google ScholarDigital Library
    17. Fausett, E., Pasko, A., and Adzhiev, V. 2000. Space-time and higher dimensional modeling for animation. In Proceedings of Computer Animation 2000, 140–145. Google ScholarDigital Library
    18. Fekete, J.-D., Bizouarn, E., Cournarie, E., Galas, T., and Taillefer, F. 1995. TicTacToon: A paperless system for professional 2D animation. In Proceedings of SIGGRAPH 95, 79–90. Google ScholarDigital Library
    19. Fiore, F. D., Schaeken, P., Elens, K., and Reeth, F. V. 2001. Automatic in-betweening in computer assisted animation by exploiting 2.5D modelling techniques. In Proceedings of Computer Animation 2001, 192–200.Google Scholar
    20. Fu, H., Tai, C.-L., and Au, O. K.-c. 2005. Morphing with laplacian coordinates and spatial-temporal texture. In Proceedings of Pacific Graphics 2005, 100–102.Google Scholar
    21. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3, 1134–1141. Google ScholarDigital Library
    22. Karsch, K., and Hart, J. C. 2011. Snaxels on a plane. In Proceedings of NPAR ’11, 35–42. Google ScholarDigital Library
    23. Koenderink, J. J., and Doorn, A. J. v. 2002. Image processing done right. In Proceedings of the 7th European Conference on Computer Vision, 158–172. Google ScholarDigital Library
    24. Kort, A. 2002. Computer aided inbetweening. In Proceedings of NPAR ’02, 125–132. Google ScholarDigital Library
    25. Kwarta, V., and Rossignac, J. 2002. Space-time surface simplification and edgebreaker compression for 2D cel animations. International Journal of Shape Modeling 8, 2, 119–137.Google ScholarCross Ref
    26. Lasseter, J. 1987. Principles of traditional animation applied to 3d computer animation. SIGGRAPH Comput. Graph. 21, 4, 35–44. Google ScholarDigital Library
    27. Lienhardt, P. 1994. N-dimensional generalized combinatorial maps and cellular quasi-manifolds. International Journal of Computational Geometry & Applications 04, 03, 275–324.Google ScholarCross Ref
    28. Liu, D., Chen, Q., Yu, J., Gu, H., Tao, D., and Seah, H. S. 2011. Stroke correspondence construction using manifold learning. Computer Graphics Forum 30, 8, 2194–2207.Google ScholarCross Ref
    29. McCann, J., and Pollard, N. 2009. Local layering. ACM Trans. Graph. 28, 3, 84:1–84:7. Google ScholarDigital Library
    30. Ngo, T., Cutrell, D., Dana, J., Donald, B., Loeb, L., and Zhu, S. 2000. Accessible animation and customizable graphics via simplicial configuration modeling. In Proceedings of SIGGRAPH 2000, 403–410. Google ScholarDigital Library
    31. Noris, G., Sýkora, D., Coros, S., Whited, B., Simmons, M., Hornung, A., Gross, M., and Sumner, R. W. 2011. Temporal noise control for sketchy animation. In Proceedings of NPAR ’11, 93–98. Google ScholarDigital Library
    32. Noris, G., Hornung, A., Sumner, R. W., Simmons, M., and Gross, M. 2013. Topology-driven vectorization of clean line drawings. ACM Trans. Graph. 32, 1, 4:1–4:11. Google ScholarDigital Library
    33. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: A vector representation for smooth-shaded images. ACM Trans. Graph. 27, 3, 92:1–92:8. Google ScholarDigital Library
    34. Patterson, J. W., Taylor, C. D., and Willis, P. J. 2012. Constructing and rendering vectorised photographic images. The Journal of Virtual Reality and Broadcasting 9, 3.Google Scholar
    35. Pesco, S., Tavares, G., and Lopes, H. 2004. A stratification approach for modeling two-dimensional cell complexes. Computers & Graphics 28, 2, 235–247.Google ScholarCross Ref
    36. Raveendran, K., Wojtan, C., Thuerey, N., and Turk, G. 2014. Blending liquids. ACM Trans. Graph. 33, 4, 137:1–137:10. Google ScholarDigital Library
    37. Reeves, W. T. 1981. Inbetweening for computer animation utilizing moving point constraints. SIGGRAPH Comput. Graph. 15, 3, 263–269. Google ScholarDigital Library
    38. Rivers, A., Igarashi, T., and Durand, F. 2010. 2.5D cartoon models. ACM Trans. Graph. 29, 4, 59:1–59:7. Google ScholarDigital Library
    39. Rossignac, J., and O’Connor, M. 1989. SGC: A Dimension-independent Model for Pointsets with Internal Structures and Incomplete Boundaries. Research report. IBM T. J. Watson Research Center.Google Scholar
    40. Sebastian, T. B., Klein, P. N., and Kimia, B. B. 2003. On aligning curves. IEEE Trans. on Pattern Analysis and Machine Intelligence 25, 1, 116–125. Google ScholarDigital Library
    41. Sederberg, T. W., Gao, P., Wang, G., and Mu, H. 1993. 2-D shape blending: an intrinsic solution to the vertex path problem. In Proceedings of SIGGRAPH 93, 15–18. Google ScholarDigital Library
    42. Southern, R. 2008. Animation manifolds for representing topological alteration. Tech. Rep. UCAM-CL-TR-723, University of Cambridge, Computer Laboratory.Google Scholar
    43. Sýkora, D., Dingliana, J., and Collins, S. 2009. As-rigid-as-possible image registration for hand-drawn cartoon animations. In Proceedings of NPAR ’09, 25–33. Google ScholarDigital Library
    44. Sýkora, D., Ben-Chen, M., Čadík, M., Whited, B., and Simmons, M. 2011. TexToons: practical texture mapping for hand-drawn cartoon animations. In Proceedings of NPAR ’11, 75–84. Google ScholarDigital Library
    45. Thomas, F., and Johnston, O. 1987. Disney Animation: The Illusion of Life. Abbeville Press.Google Scholar
    46. Weiler, K. 1985. Edge-based data structures for solid modeling in curved-surface environments. IEEE Computer Graphics and Applications 5, 1, 21–40. Google ScholarDigital Library
    47. Whited, B., Noris, G., Simmons, M., Sumner, R., Gross, M., and Rossignac, J. 2010. BetweenIT: An interactive tool for tight inbetweening. Computer Graphics Forum 29, 2, 605–614.Google ScholarCross Ref
    48. Yu, J., Bian, W., Song, M., Cheng, J., and Tao, D. 2012. Graph based transductive learning for cartoon correspondence construction. Neurocomputing 79, 0, 105–114. Google ScholarDigital Library
    49. Zhang, S.-H., Chen, T., Zhang, Y.-F., Hu, S.-M., and Martin, R. R. 2009. Vectorizing cartoon animations. IEEE Trans. on Visualization and Computer Graphics 15, 4, 618–629. Google ScholarDigital Library

ACM Digital Library Publication: