Robust Planar Maps for 3D Vectorization
ACM Transactions on Graphics 2026
SIGGRAPH 2026 Best Paper Award
This paper describes a strategy for vectorizing 3D scenes with proper occlusion. Given a collection of curves derived from 3D geometry (silhouettes, isolines, material boundaries, etc.), we produce a 2D vector image that partitions the image plane into a planar map of solid shaded regions. The method is agnostic to surface representation, handling for instance curves obtained from polygonal, NURBS or subdivision surfaces. The output likewise supports curve segments of arbitrary parametric type. Our key observation is that the spatial hierarchy used to accelerate curve-curve intersections provides the fundamental representation of the planar map itself. This approach provides geometric flexibility, since general curve-curve intersection problems are replaced with simpler curve-line intersection. Simultaneously, it provides robustness since cells of the spatial hierarchy define a well-defined planar map, even in the presence of numerical errors. For instance, it automatically handles “curve soup” where segment endpoints are not explicitly connected in the input file. The method scales to a large number of primitives, and is output sensitive: it resolves intersections only up to a user-defined precision—while still providing topologically valid output. We evaluate the method on a collection of challenging tests, showing that it is both more robust and orders of magnitude more efficient than existing curve arrangement techniques, such as those found in CGAL.
PDF (19.8MB)
IP Status
Patent pending. A U.S. provisional patent application has been filed for this technology.
@article{Fuchs:2026:RPM,
author = {Fuchs, Robert and Crane, Keenan},
title = {Robust Planar Maps for 3D Vectorization},
journal = {ACM Trans. Graph.},
volume = {45},
number = {4},
year = {2026},
publisher = {ACM},
address = {New York, NY, USA},
}
Figures
To generate a planar map, we need only perform line-curve intersections with edges (top right), enabling us to handle heterogeneous mixtures of geometry defined by any type of curve.
The spatially adaptive nature of our BSP-based approach enables it to scale to extreme levels of geometric detail, here resolving a detailed schematic for a mouse (left) into well-defined screen-space regions with extraordinarily fine features (right).
A robust planar map that preserves large, connected regions is useful not only for display and stylization, but also makes it easier for a designer to edit and interact with vector artwork. Here for instance the exploded view shows a clean segmentation into manageable pieces.
Even for 2D arrangements, our method is typically one to two orders of magnitude faster than the polyline and Bézier arrangement algorithms implemented in CGAL—and far more robust.
The robustness and flexibility of our method makes it possible to vectorize effects that are essentially impossible for existing methods, such as global illumination effects. Here, for instance, we correctly extract and shade regions bound by specular reflection lines on a sphere—which bunch up into extremely degenerate bands of curves near the sphere boundary.
We use a BSP tree to simultaneously identify pairs of curves that intersect, and also to approximately compute the coordinates of intersection. To do so, we keep splitting nodes until they contain at most one curve, or until their size goes below an accuracy parameter ε. Any remaining node that contains more than one curve is identified with a “virtual vertex,” which becomes a vertex in our output vectorization.
Our approach is robust to real-world curve data, which can have tiny gaps between curves (here far smaller than a pixel). Here, to mitigate such a gap, we add a small “gap circle” which splits the initial planar graph into additional regions. Identifying regions via ray tracing, and merging contiguous regions, yields a reasonable way of closing the gap—independent of which sample point (1 or 2) we use to determine region identity.
Commercial vector graphics editors fail to provide a good solution for planar maps, since they do not natively handle “soups” of open curves. If we expand curves into thin regions and take their Boolean union, we obtain a poor planar map approximation that omits large regions (here assigned random colors).
Vectorized output with clean, well-defined regions enables 3D objects to be stylized using effects that would be difficult or impossible using conventional ray tracing or rasterization. Here, the brightness of extracted regions is used to select halftoning patterns that dynamically scale with the artwork's display size.
Gallery of additional results—all previous methods failed to generate output for these models. Each of these objects was originally a NURBS surface, with projected curve contours generated via Rhino 3D. Here we take advantage of the vector nature of our output to stylize the final artwork in various ways. The glasses (bottom) are exploded to show four distinct layers of transparency.
Classical arrangement methods, including those implemented in the industry-standard CGAL package, failed for most of the 3D examples shown in this paper, resulting in either a crash or unbounded running time. On simpler examples that did terminate, the resulting planar maps have large missing regions—likely due to poor handling of near-coincident and near-tangential curves that commonly arise due to visibility events.