Home Research Art Bio

Vector Graphics Complexes

Boris Dalstein, Rémi Ronfard, Michiel van de Panne

ACM Transactions of Graphics, 33, 4 (SIGGRAPH 2014)

Quick links: [ Paper ] [ Tech report ] [ Slides ] [ Poster ]

teaser image

SIGGRAPH presentation

PowerPoint slides available here.

Paper video



Our open source implementation VPaint is available at www.vpaint.org

The successors of VPaint, VGC Illustration and VGC Animation, are being developed at VGC


article first page preview

Vector Graphics Complexes

Boris Dalstein, Rémi Ronfard, Michiel van de Panne

ACM Transactions of Graphics, 33, 4 (SIGGRAPH 2014)

[ PDF ] [ BibTeX ]

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.

Technical report

PCS preview

Point-Curve-Surface Complex: A Cell Decomposition for Non-Manifold Two-Dimensional Topological Spaces

Boris Dalstein, Rémi Ronfard, Michiel van de Panne

University of British Columbia, technical report (2014)

[ PDF ] [ BibTeX ]

We introduce the point-curve-surface complex (PCS complex), a cell complex tailored for a canonical decomposition of ``regular'' non-manifold two-dimensional topological spaces (i.e., the class of topological spaces that admits a simplicial 2-complex decomposition). PCS complexes are obtained by gluing together points, curves and surfaces, very similarly to CW complexes, except that the cells are not restricted to be topological disks. Also, gluing constraints that cells must satisfy to form a valid complex are much stricter than with CW complexes. We conjecture that this specific combination of flexibility and constraints ensures uniqueness of a minimal decomposition, obtained via atomic simplifications performed in any order.

The PCS complex admits a combinatorial description, called the abstract PCS complex. It is made of vertices, closed edges, open edges defined by a start and an end vertex, and faces defined by an orientability, a genus, and a boundary defined as a sequence of cycles, where a cycle is either a vertex, an oriented closed edge possibly repeated, or a looping sequence of consecutive oriented open edges. It provides a compact language to describe non-manifold two-dimensional topological spaces up to homeomorphism. We detail the create/delete, glue/unglue and cut/uncut topological operators on this combinatorial structure.

A vector graphics complex (VGC) is an abstract PCS complex without the information of orientability and genus, since it is irrelevant for vector graphics. Therefore, these two concepts are fundamentally equivalent, and topological operators on abstract PCS complexes can also be applied to VGCs. As such, this report provides insight and theoretical relevance to most of the design decisions behind the VGC, as well as a thorough description of the topological operators on the VGC, described in terms of abstract PCS complexes.


poster vgc