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

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