“Vector graphics complexes” by Dalstein, Ronfard and Panne
Conference:
Type(s):
Title:
- Vector graphics complexes
Session/Category Title: Interactive Modeling
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
