“Vector graphics complexes” by Dalstein, Ronfard and Panne

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




    Vector graphics complexes

Session/Category Title: Interactive Modeling




    Basic topological modeling, such as the ability to have several faces share a common edge, has been largely absent from vector graphics. We introduce the vector graphics complex (VGC) as a simple data structure to support fundamental topological modeling operations for vector graphics illustrations. The VGC can represent any arbitrary non-manifold topology as an immersion in the plane, unlike planar maps which can only represent embeddings. This allows for the direct representation of incidence relationships between objects and can therefore more faithfully capture the intended semantics of many illustrations, while at the same time keeping the geometric flexibility of stacking-based systems. We describe and implement a set of topological editing operations for the VGC, including glue, unglue, cut, and uncut. Our system maintains a global stacking order for all faces, edges, and vertices without requiring that components of an object reside together on a single layer. This allows for the coordinated editing of shared vertices and edges even for objects that have components distributed across multiple layers. We introduce VGC-specific methods that are tailored towards quickly achieving desired stacking orders for faces, edges, and vertices.


    1. Adobe Systems Inc., 2013. Adobe Illustrator: Help and tutorials.Google Scholar
    2. Asente, P., Schuster, M., and Pettit, T. 2007. Dynamic planar map illustration. ACM Trans. Graph. 26, 3 (July), 30:1–30:10. Google ScholarDigital Library
    3. Baudelaire, P., and Gangnet, M. 1989. Planar maps: An interaction paradigm for graphic design. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM, New York, NY, USA, CHI ’89, 313–318. Google ScholarDigital Library
    4. Dalstein, B., Ronfard, R., and van de Panne, M. 2014. Point-curve-surface complex: A cell decomposition for non-manifold two-dimensional topological spaces. Tech. rep., University of British Columbia.Google Scholar
    5. De Floriani, L., Morando, F., and Puppo, E. 2003. Representation of non-manifold objects through decomposition into nearly manifold parts. In Proceedings of the Eighth ACM Symposium on Solid Modeling and Applications, ACM, New York, NY, USA, SMA ’03, 304–309. Google ScholarDigital Library
    6. 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, Springer Berlin Heidelberg, 403–420.Google Scholar
    7. Durand, F. 2002. An invitation to discuss computer depiction. In Proceedings of the 2nd International Symposium on Non-photorealistic Animation and Rendering, ACM, New York, NY, USA, NPAR ’02, 111–124. Google ScholarDigital Library
    8. Edelsbrunner, H., and Harer, J. 2010. Computational Topology: An Introduction. Applied mathematics. American Mathematical Society.Google Scholar
    9. 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 (July), 83:1–83:8. Google ScholarDigital Library
    10. Granados, M., Hachenberger, P., Hert, S., Kettner, L., Mehlhorn, K., and Seel, M. 2003. Boolean operations on 3D selective Nef complexes: Data structure, algorithms, and implementation. In Algorithms – ESA 2003, vol. 2832 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 654–666.Google Scholar
    11. Guibas, L., and Stolfi, J. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi. ACM Trans. Graph. 4, 2 (Apr.), 74–123. Google ScholarDigital Library
    12. Gursoz, E. L., Choi, Y., and Pinz, F. B. 1990. Vertex-based representation of non-manifold boundaries. In Geometric Modeling for Product Engineering, Eselvier, Amsterdam, 107–130.Google Scholar
    13. Gursoz, E. L., Choi, Y., and Pinz, F. B. 1991. Boolean set operations on non-manifold boundary representation objects. Comput. Aided Des. 23, 1 (Feb.), 33–39. Google ScholarDigital Library
    14. Hoffman, D. D. 2000. Visual Intelligence: How We Create what We See. Norton.Google Scholar
    15. Igarashi, T., and Mitani, J. 2010. Apparent layer operations for the manipulation of deformable objects. ACM Trans. Graph. 29, 4 (July), 110:1–110:7. Google ScholarDigital Library
    16. Inkscape, 2013. http://www.inkscape.org/en/.Google Scholar
    17. Karsch, K., and Hart, J. C. 2011. Snaxels on a plane. In Proceedings of the 9th ACM SIGGRAPH/Eurographics Symposium on Non-Photorealistic Animation and Rendering, ACM, New York, NY, USA, NPAR ’11, 35–42. Google ScholarDigital Library
    18. Koenderink, J., and Doorn, A. 2008. The structure of visual spaces. Journal of Mathematical Imaging and Vision 31, 2–3, 171–187. Google ScholarDigital Library
    19. Lee, S. H., and Lee, K. 2001. Partial entity structure: A compact non-manifold boundary representation based on partial topological entities. In Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, ACM, New York, NY, USA, SMA ’01, 159–170. Google ScholarDigital Library
    20. 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
    21. Marcheix, D., and Gueorguieva, S. 1995. Topological operators for non-manifold modeling. Proceedings of the Third International Conference in Central Europe on Computer Graphics and Visualisation ’95 1 (Feb.), 173–186.Google Scholar
    22. McCann, J., and Pollard, N. 2009. Local layering. ACM Trans. Graph. 28, 3 (July), 84:1–84:7. Google ScholarDigital Library
    23. Nef, W. 1978. Beiträge zur Theorie der Polyeder: mit Anwendungen in der Computergraphik. Beiträge zur Mathematik, Informatik und Nachrichtentechnik. Lang.Google Scholar
    24. 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 (Feb.), 4:1–4:11. Google ScholarDigital Library
    25. 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
    26. Porter, T., and Duff, T. 1984. Compositing digital images. SIGGRAPH Comput. Graph. 18, 3 (Jan.), 253–259. Google ScholarDigital Library
    27. Rossignac, J., and O’Connor, M. 1989. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In Geometric Modeling for Product Engineering, Proceedings of the IFIP Workshop on CAD/CAM, IBM T.J. Watson Research Center, 145–180.Google Scholar
    28. Rossignac, J. 1997. Structured topological complexes: A feature-based API for non-manifold topologies. In Proceedings of the Fourth ACM Symposium on Solid Modeling and Applications, ACM, New York, NY, USA, SMA ’97, 1–9. Google ScholarDigital Library
    29. Shreiner, D., Woo, M., Neider, J., and Davis, T. 2004. Tesselators and quadrics. In The OpenGL Programming Guide, Fourth Edition. Addison-Wesley, ch. 11, 487–514.Google Scholar
    30. Silva, F. G. M., and Gomes, A. J. P. 2003. Adjacency and incidence framework: A data structure for efficient and fast management of multiresolution meshes. In Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia, ACM, New York, NY, USA, GRAPHITE ’03, 159–166. Google ScholarDigital Library
    31. SVG Working Group, 2011. Scalable Vector Graphics (SVG) 1.1 (Second Edition). http://www.w3.org/TR/SVG11/.Google Scholar
    32. Takayama, K., Panozzo, D., Sorkine-Hornung, A., and Sorkine-Hornung, O. 2013. Sketch-based generation and editing of quad meshes. ACM Trans. Graph. 32, 4 (July), 97:1–97:8. Google ScholarDigital Library
    33. Weiler, K. 1985. Edge-based data structures for solid modeling in curved-surface environments. Computer Graphics and Applications, IEEE 5, 1 (Jan), 21–40. Google ScholarDigital Library
    34. Whited, B., Noris, G., Simmons, M., Sumner, R. W., Gross, M., and Rossignac, J. 2010. BetweenIT: An interactive tool for tight inbetweening. Computer Graphics Forum 29, 2, 605–614.Google ScholarCross Ref
    35. Wiley, K., and Williams, L. R. 2006. Representation of interwoven surfaces in 2 1/2 D drawing. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM, New York, NY, USA, CHI ’06, 65–74. Google ScholarDigital Library

ACM Digital Library Publication: