Robust Planar Maps for 3D Vectorization

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.