This is another post about lyon, a rust crate which helps you tessellate vector paths into triangle meshes that can be easily rendered on the GPU. Today I am going to focus on paths.

Paths

Paths describe the outline of arbitrary shapes. A lot of users of lyon just create simple polygons with straight line edges and no holes.

let mut builder = Path::builder();
builder.move_to(point(0.0, 0.0));
builder.line_to(point(10.0, 0.0));
builder.line_to(point(10.0, 10.0));
builder.line_to(point(0.0, 10.0));
builder.close();

let path = builder.build();

But you can describe a lot more than that, for example with bézier curves:

let mut builder = Path::builder();
builder.move_to(point(0.0, 0.0));
builder.quadratic_bezier_to(point(10.0, 0.0), point(10.0, 10.0));
builder.cubic_bezier_to(point(0.0, 10.0), point(2.0, 0.0), point(1.0, 0.0));
builder.close();

let path = builder.build();

A path isn't necessarily a single shape:

let mut builder = Path::builder();
// A square..
builder.move_to(point(0.0, 0.0));
builder.line_to(point(10.0, 0.0));
builder.line_to(point(10.0, 10.0));
builder.line_to(point(0.0, 10.0));
builder.close();
// .. and a triangle next to it.
builder.move_to(point(20.0, 0.0));
builder.line_to(point(30.0, 0.0));
builder.line_to(point(25.0, 5.0));
builder.close();

let path = builder.build();

You can also carve holes in shapes:

let mut builder = Path::builder();
// A square..
builder.move_to(point(0.0, 0.0));
builder.line_to(point(10.0, 0.0));
builder.line_to(point(10.0, 10.0));
builder.line_to(point(0.0, 10.0));
builder.close();
// .. and a smaller square inside of it, carving a hole.
builder.move_to(point(2.0, 2.0));
builder.line_to(point(2.0, 8.0));
builder.line_to(point(8.0, 8.0));
builder.line_to(point(8.0, 2.0));
builder.close();

let path = builder.build();

To make life easier for people interacting with SVG or just used to a richer set of commands, there is an adapter wrapping a path builder and translating SVG's extended set of drawing commands into PathBuilder's lower level set.'

let mut builder = Path::builder().with_svg();

builder.move_to(point(0.0, 0.0));
builder.relative_line_to(vector(10.0, 0.0));
builder.vertical_line_to(10.0);
builder.relative_arc_to(vector(25.0, 25.0), Angle::degrees(-30.0), ArgFlags { large_arc: false, sweep: true }, vector(50.0, -25.0));
builder.relative_quadratic_bezier_to(vector(10.0, 0.0), vector(10.0, 10.0));
builder.smooth_relative_quadratic_bezier_to(vector(-10.0, 10.0));
// etc.
builder.close();

let path = builder.build();

Nothing too fancy here, it's the familiar interface you may have already worked with using SVG, cairo, skia, qpainter or some other piece of vector graphics software.

Iterating paths

This interface is kind of straightforward and for a lot of algorithms it corresponds to how the path is consumed:

for event in &path {
    match event {
        PathEvent::Begin { at } => {
            println!("begin a sub-path at {:?}", at);
        }
        PathEvent::Line { from, to } => {
            println!("line from {:?} to {:?}", from, to);
        }
        PathEvent::Quadratic { from, ctrl, to } => {
            println!("quadratic bézier curve {:?} {:?} {:?}", from, ctrl1, ctrl2, to);
        }
        PathEvent::Cubic { from, ctrl1, ctrl2, to } => {
            println!("cubic bézier curve {:?} {:?} {:?} {:?}", from, ctrl1, ctrl2, to);
        }
        PathEvent::End { last, first, close } => {
            if close {
                println!("Close the sub-path with a line from {:?} to {:?}", last, first);
            } else {
                println!("End the sub-path at {:?}", last);
            }
        }
    }
}

Notice how the iterator's PathEvent is a bit different from the path building interface.

• It provides the starting endpoint of each segment (from) which was implicit in the building API. If you want to do anything useful while iterating over the edges of a path, you have to know about all endpoints of the edge. In some Older versions of lyon, the iterator would not provide with this endpoint and every algorithm had to manually keep track of the destination endpoint of each segment to know the starting endpoint of the next segment. it isn't very hard to do, but the same logic was duplicated enough times in lyon that I decided to simply do it once in the iterator instead.
• Instead of a Close event we have and End event with a boolean indicating whether the sub-path is closed. Some algorithms, such as the fill tessellator or the hatcher, need to conceptually close all sub-paths. It wouldn't be possible to fill an open path since it has no surface. To insert that closing edge you need to keep track of the starting endpoint of the current sub-path. Just like edge starting endpoints, it' not too bad, just store it in a variable every time the Begin comes up, but it's nice to have it done in a single place by the iterator. But this isn't all of it: the classic postscript-style path building API doesn't explicitly end paths that aren't closed:

let mut builder = Path::builder();
builder.move_to(point(0.0, 0.0));
builder.line_to(point(10.0, 0.0));
builder.line_to(point(10.0, 10.0));
builder.line_to(point(0.0, 10.0));
// A move_to indicates the start of a new path, and implies the end of the current
// one, even if we didn't end it explicitly.
builder.move_to(point(20.0, 0.0));
builder.line_to(point(30.0, 0.0));
builder.line_to(point(25.0, 5.0));

let path = builder.build();

Algorithms iterating over paths therefore would need to keep track of whether a sub-path is active when running into a move-to event. Yet another thing duplicated a handful of times in lyon's code base, that was simplified by being handled before iteration, to the benefit of all algorithms consuming paths. Right now, when iterating one of lyon's path data structures, you are guaranteed that all sub-paths begin and end with a PathEvent::Begin/PathEvent::End pair.

How can we guarantee this, though? What if a segment is added without starting the sub-path. What is the current position (the position of the starting end-point of the segment)?

let mut builder = Path::builder();
builder.move_to(point(1.0, 1.0));
builder.line_to(point(2.0, 2.0));
builder.close();

// A segment, without starting a sub path!
builder.quadartic_bezier_to(point(10.0, 0.0), point(10.0, 10.0));

or simply:

let mut builder = Path::builder();
// First segment of the path without starting a sub path!
builder.quadartic_bezier_to(point(10.0, 0.0), point(10.0, 10.0));

In the first case above, lyon considers that closing the previous sub-path resets the current position to where the closing edge ended, the starting position of the sub-path (1.0, 1.0). In the second case, there isn't a very good answer. lyon currently defaults to (0.0, 0.0) in some of the path data structures, or panics in others. That isn't very satisfying. In the next version of lyon, the segment will be omitted but the rest of sub-path will still be built normally, starting at the end of the omitted path. Other vector graphics APIs deal with it in various ways: SVG considers the whole path invalid (empty), skia always default to (0.0, 0.0) as the starting position of any sub-path without a move-to event, while Canvas2D and cairo insert a move to whatever next thing has an x and a y coordinate (for example the control point (10.0, 0.0) in the example above) which is my least favorite solution, but I am sure opinions differ on the topic.

Whichever way one deals with this, it likely requires checking whether there is an open sub-path for each segment (not only when starting/ending a sub-path and when finishing the path). Bummer, but this cost is sunk by lyon's path builders and you don't have to worry too much about it.

It's been bothering me for a while because while when you are loading some vector file format or user-generated content you want to handle edge cases as gracefully as possible, in a lot of other scenarios it would be better to have simple debug assertions in the path builder and provide a stricter but faster path building interface. In addition, since there are different ways to deal with these edge cases, some users of lyon may end up wrapping the path builder into their own, to sanitize paths so that they strictly adhere to a particular specification like SVG, Canvas2D or skia's path building API.

In addition, lyon recently added the possibility of attaching custom attributes to path endpoints, as well as associating endpoints with IDs so that algorithms such as the tessellators can generate vertices with any kind of data (vertex colors, texture coordinates, bone weights, etc.).

let mut builder = Path::builder(2);
let a = builder.move_to(point(0.0, 0.0));
let b = builder.line_to(point(10.0, 10.0));
let path = builder.build();
println!("Moved to {:?}, added a line to {:?}", path[a], path[b]);

let mut builder = Path::builder_with_attributes(2);
let a = builder.move_to(point(0.0, 0.0), &[1.0, 2.0]);
let b = builder.line_to(point(10.0, 10.0), &[3.0, 2.0]);
let path = builder.build();
println!("Moved to {:?} with attributes {:?}, added a line to {:?} with attributes {:?}", path[a], path.attributes(a), path[b], path.attributes(b));

Returning endpoint ids makes sense for commands like quadratic_bezier_to which add a single endpoint, what about arcs that are internally approximated with multiple bézier curves?

Simplifying the code and API

Like most code, lyon_path went through a lot of iterations and exploration, inevitably adding complexity here and there. I decided to go though API again and see if I could remove features and abstractions that I think didn't turn out to be useful.

The traits

It is always so tempting to add traits just because it feels like it makes sense.

Today, lyon_path has

• FlatPathBuilder which only has move-to, line-to and close commands.
• PathBuilder which adds quadratic béziers, cubic béziers and arcs on top of FlatPathBuilder. It is close to what the Path type can exactly represent, with arcs on top.
• SvgBuilder adding SVG's lot relative position and smooth commands, horizontal lines, vertical lines, etc. on top of PathBuilder.
• PolygonBuilder to build polygons from a slice of points. without bothering with move-to, close, etc.
• Build which is a separate trait so that its build method can return the PathType associated type, effectively preventing the the trait from being used as a trait object, without applying this restriction to the other traits.

What do we really need in lyon? - A way to abstract over the path type that is being built. - Ideally place this abstraction so that sanitizing code doesn't need to be repeated for each path builder implementation. - Be able to use path builders as trait objects while building arbitrary path types (the separate Build trait. Good, let's keep it). - A way to easily interact with SVG content.

The current trait hierarchy was introduced with sort of "feature levels" in mind. But in reality it isn't very useful to have an abstraction over builders that don't support curves, when lyon has all of the tools needed for a path data structure to approximate curves with line segments. Let's remove FlatPathBuilder.

The next version of lyon will very likely have the following traits instead:

// Isolating the builder was worth it. We can use the other traits as trait objects which
// is valuable, so it stays.
pub trait Build {
    type PathType;
    fn build(self) -> Self::PathType;
}

// The strict low-level path building API.
// Very fast implementation for lyon's default path data structure, panics if sub-paths
// aren't properly started/ended.
pub trait PathBuilder {
    // Begin/End matching the iterator API
    fn begin(&mut self, to: Point) -> EndpointId;
    fn end(&mut self, close: bool);
    // The types of edges that are actually supported in lyon's path types.
    fn line_to(&mut self, to: Point) -> EndpointId;
    fn quadratic_bezier_to(&mut self, ctrl: Point, to: Point) -> EndpointId;
    fn cubic_bezier_to(&mut self, ctrl1: Point, ctrl2: Point, to: Point) -> EndpointId;
    // For performance reasons it is good to be able to hint at the builder implementation
    // how much memory to pre-allocate.
    fn reserve(&mut self, _endpoints: usize, _ctrl_points: usize) {}

    /// Returns a builder that approximates all curves with sequences of line segments.
    fn flattened(self, tolerance: f32) -> Flattened<Self> where Self: Sized {
        Flattened::new(self, tolerance)
    }

    /// Returns a builder that applies a transfor to all points.
    fn transformed<T: Transform>(self, transform: &T) -> Transformed<Self, T> where Self: Sized {
        Transformed::new(self, transform)
    }

    /// Returns a builder that approximates all curves with sequences of line segments.
    fn with_svg(self) -> WithSvg<Self> where Self: Sized {
        WithSvg::new(self)
    }
}

// Batteries-included API that you may be familiar with. Path data structures don't need to
// implement it, an adapter is provided that lowers to the `PathBuilder`.
pub trait SvgPathBuilder {
    fn move_to(&mut self, to: Point);
    fn close(&mut self);
    fn line_to(&mut self, to: Point);
    fn quadratic_bezier_to(&mut self, ctrl: Point, to: Point);
    fn cubic_bezier_to(&mut self, ctrl1: Point, ctrl2: Point, to: Point);
    fn relative_move_to(&mut self, to: Vector);
    fn relative_line_to(&mut self, to: Vector);
    fn relative_quadratic_bezier_to(&mut self, ctrl: Vector, to: Vector);
    fn relative_cubic_bezier_to(&mut self, ctrl1: Vector, ctrl2: Vector, to: Vector);
    fn smooth_cubic_bezier_to(&mut self, ctrl2: Point, to: Point);
    fn smooth_relative_cubic_bezier_to(&mut self, ctrl2: Vector, to: Vector);
    fn smooth_quadratic_bezier_to(&mut self, to: Point);
    fn smooth_relative_quadratic_bezier_to(&mut self, to: Vector);
    fn horizontal_line_to(&mut self, x: f32);
    fn relative_horizontal_line_to(&mut self, dx: f32);
    fn vertical_line_to(&mut self, y: f32);
    fn relative_vertical_line_to(&mut self, dy: f32);
    fn arc_to(&mut self, radii: Vector, x_rotation: Angle, flags: ArcFlags, to: Point);
    fn relative_arc_to(&mut self, radii: Vector, x_rotation: Angle, flags: ArcFlags, to: Vector);

    // other methods omitted.
}

// Putting it together:
let mut builder = Path::builder()
    .flattened(0.1)
    .transformed(&rotation)
    .with_svg();

Can we go further

One thing that I didn't initially take into consideration, was on where in between these abstractions should we deal with all of these edge cases I described above (missing move-to commands, etc). Currently the answer is that it is dealt with below all abstractions, and the code is repeated over all builder types with various levels of consistency. That's not so great. What would be useful is an abstraction separating between strict zero-cost path building where the user is required to properly open and close sub-paths from sanitizing code that would interact with this it. Ideally this low-level trait would match the iteration API for consistency and stay true to what is happening under the hood. High level path building interfaces can be built on top of the low level path building trait. Users would opt into a more permissive and familiar API, and its associated cost.

Isolating the Build trait was worthwhile, let's keep it.

The polygon builder trait? Meh. No code in lyon need an abstraction for that (it doesn't mean the path builder types shouldn't have a method to add a polygon, we just don't need that abstraction, and anyone outside of lyon can trivially add it).

SvgBuilder or some kind of all-battery-included abstraction that helps with interacting with SVG content may be useful. I'm not fully decided yet,