Converting stroked primitives to filled primitives

Diego Nehab

IMPA, Rio de Janeiro, Brazil

Abstract: Vector graphics formats offer support for both filled and stroked primitives. Filled primitives paint all points in the region bounded by a set of outlines. Stroked primitives paint all points covered by a line drawn over the outlines. Editors allow users to convert stroked primitives to the outlines of equivalent filled primitives for further editing. Likewise, renderers typically convert stroked primitives to equivalent filled primitives prior to rendering. This conversion problem is deceivingly difficult to solve. Surprisingly, it has received little to no attention in the literature. Existing implementations output too many segments, do not satisfy accuracy requirements, or fail under a variety of conditions, often spectacularly. In this paper, we present a solution to the stroke-to-fill conversion problem that addresses these issues. One of our key insights is to take into account the evolutes of input outlines, in addition to their offsets, in regions of high curvature. Furthermore, our approach strives to maintain continuity between the input and the set of painted points. Our implementation is available in open source.

Fig 1. We analyzed 22 distinct third-party strokers. (a) 14 of them confuse the stroke-to-fill conversion problem with the curve-offsetting problem, and produce incorrect results near high-curvature regions. (b) The remaining 8 do treat high-curvature regions, but offer no accuracy guarantees, and often output too many segments. (c) Our stroker correctly handles these regions using evolutes. (d) All but 2 strokers ignore inner joins between segments, leaving unexpected gaps. (e) Our stroker detects when such joins are visible (even between curved segments) and outputs them. (f) All but 2 strokers fail spectacularly in the vicinity of intra-segment cusps and “almost cusps”. (g) Following the standards to the letter produces discontinuous results at cusps. (h) Our stroker robustly detects cusps and “almost cusps” to produce continuous, intuitive results.

There are too many interesting test cases to fit in a publication. Instead, most of our tests are available as supplemental materials.

Each stroker was tested against a batch of difficult examples (Many of these tests were adapted from the NVprDEMOs suite.) This “stills” dataset includes, for each test–implementation combination, the bare result of stroking a test with a given implementation, the input and output outlines, and a comparison against the result produced by our ground-truth renderer. It can be browsed by individually by stroker or in a single page by test (Make sure to scroll to the right after opening one of these images!) We have recently added educational mode animations for some of these test cases.

An even better way to evaluate the robustness of an implementation is to test multiple steps in an animation. Therefore, we generated a variety of animated test cases, also in the bare, outline, and compare varieties. This “animations” dataset offers a mesmerizing glimpse of the workings of each implementation.

Finally, to encourage further work in the topic, we provide the inputs used to generate the “stills”, “animations”, and “timings” datasets, as well as the full source-code for our implementation and test harness.