About a year ago I published
"Introduction to lyon: 2D vector graphics rendering on the GPU in rust"
on this blog. Lyon was in version 0.8.8 back then and I recently published 0.13.0.
In 2018 my activity on the project has varied depending on the time and energy I have had left after work and other activities. As it turns out, working on getting WebRender shipped in Firefox is at the same time amazing and very demanding, and what's left of my brain after a good day of work isn't always up to some of the ambitions I have planned for lyon. Fortunately I am not the only one who contributed to the project, and while progress was slow on the most ambitious plans, I did spend some time on smaller features and polish.
I'll get to these big plans towards the end of this post. In the mean time let's look at some of the highlights of what changed in lyon in 2018.
lyon_geom
I want to start with an epic contribution from Tom Klein: The addition of a robust cubic bézier intersection algorithm using fat line clipping. You can read about this journey in the original pull request and followup improvements. Suffice to say, I'm impressed with the quality and rigor of the work Tom put in this feature.
Tom also added an elliptic arc to cubic bézier approximation (doc link).
There were other additions such as tight bounding rectangle calculation for elliptic arcs, improvements and fixes to the various curve approximation algorithms and a lot of API ergonomic improvements.
This year has confirmed the trend that a number of people are using lyon_geom without the rest of lyon. The way the lyon crates are separated seems to have paid off in letting people who only want curve math tools get a minimal dependency.
lyon_tessellation
To me, the fill tessellator is the most important piece of the whole project. The majority of the changes to the fill tessellator were bug fixes, almost all of them related to dreadful numerical precision issues when paths have many self-intersections and in particular when a lot of these self-intersections are almost at the same position. This type of paths isn't representative of human generated content but the robustness of the tessellator is important to me and I want to keep improving it.
As far as API changes are concerned, I added the possibility to chose the type of the generated indices of the vertex/index buffer pairs. Before that, indices were always u16 and some users ran into the limit when generating large amount of geometry with a single path or when tessellating too many paths in the same vertex and index buffer pair. The tessellator now internally works with u32 indices and the convenience BuffersBuilder and VertexBuffers output can be parametrized over the index type to provide the choice of u16, u32 or anything else that can be converted to a VertexId.
In addition, the GeometryBuilder trait and the tessellators are set up to properly handle running out of indices, interrupting the tessellation and returning an error instead of causing a panic as it previously did.
This might sound like a detail but several people ran into it and the way the tessellator used to panic when running out of vertex ids was confusing so I am happy that this is now a thing of the past. My initial worry was that the added glue to forward and handle errors would regress performance (which it initially did by about 6%), but with a small amount profiling and tweaks I got the performance back within noise range of the original scores (on the benchmarks in the repository).
lyon_path
This crate has received more attention than usual lately.
The first thing people who update from earlier versions of lyon will notice is probably that lyon::path::default::Path is now lyon::path::Path. But there have been some more interesting developments than this namespace change.
The iterator APIs got a pretty major revamp. Previously the various flavors of path iterators would let you iterate over events such as MoveTo(Point), Close, LineTo(Point) and equivalent curve segments types, in a postscript fashion similar to how the paths are created, in which we don't repeat the start of the event since we already provided it as the end of the previous one.
This was simple to implement since it maps to how the path is stored, but pretty much every consumer of the API would have to keep track of both the previous end of segment and the starting position of the curve to do any meaningful work with the segments of the path.
The PathEvent enum looked like this:
pub enum PathEvent {
MoveTo(Point),
Close,
LineTo(Point),
QuadraticTo(Point, Point), // control point, to
// etc.
}
And now looks like this:
pub enum PathEvent {
MoveTo(Point),
Close(LineSegment<f32>),
Line(LineSegment<f32>),
Quadratic(QuadraticBezierSegment<f32>),
// etc.
}
In other words, I shifted the burden of tracking this information from the user to the iterator implementation by making path events contain the actual segments and by providing the closing segment in PathEvent::Close(LineSegment<f32>).
I also removed PathSegment::Arc (elliptic arcs automatically get approximated with a sequence of cubic bézier curves) and simplified the PathIterator trait which is now a simple extension trait implemented for all Iterator<Item = PathEvent>.
There is also a new Cursor API which makes it possible to refer to specific positions within a path and work with portions of paths instead of always iterating over the entire path from the beginning.
A helper to approximate the length of a path using adaptive curve flattening was added, although Raph Levien wrote about a faster way to evaluate the length of bézier curve segments which he implemented in in the kurbo crate. Perhaps some of this good stuff will make its way into lyon as well eventually.
In the long term I want to experiment with more changes to the path data structure, for example making it generic over the vertex type to allow f64 coordinates and potentially arbitrary per-point attributes (for example one could want to store colors, line width, etc.).
lyon_algorithms
A new crate was introduced this year! lyon_algorithms contains a number of path related transformations and algorithms such as generating hatching and dotting patterns, splitting paths, computing bounding boxes, ray casting and walking along a path at constant speed.
I wrote most of these algorithms for fun. I don't think I will pursue the same robustness goals as the fill tessellator there (path splitting has some very difficult edge cases when several segments overlap exactly for example), but I think that they are good enough to be useful to a lot of people.
I'd love to add more algorithms there, like boolean operations, path simplification, path smoothing, path interpolation, and so on.
I have used these algorithms to generate procedural shapes and print them with my axidraw and it's a ton of fun. Hopefully, some people in the plotting community will find them useful.
Work in progress
I mentioned at the beginning of the post that I have been making slow progress on two fronts:
A new fill tessellator
This work is happening in the new-tess branch. The main motivations for this are:
- Better robustness against numerical precision issues. In broad strokes, the idea is to organize the algorithm so that it can detect and recover from precision bugs that break the invariants of the algorithm. It is a little hard to describe, but in a nutshell the approach is to accept that some arithmetic will produce results that break the invariant of the algorithm and split iterations of the main loop into an analysis phase where we get a chance to detect the error, backtrack one step and recover from it, and a mutation phase. In contrast the current tessellator interleaves mutations of its internal state with analysis of the geometry in a way that makes it hard to interrupt the iteration and recover if a bad state is detected.
- Support arbitrary vertex attributes. Today it is hard to associate external data such as colors or bone weights for animation to each vertex and use it in the output of the tessellator.
- Move away from fixed point numbers which the current tessellator uses internally. I originally thought that they would be the key to taming precision issues, but it didn't work out that well, and introduced new issues like a limited range of numbers that the tessellator can represent internally.
- Support for more fill rules (even-odd is the only currently supported fill rule in the current tessellator).
- Handling quadratic bézier curves directly in the tessellator. The tessellator would be able to either flatten curves on the fly during tessellation, or produce a mesh in which the curves could be evaluated in a fragment shader or tessellation shader. This goal longer term than the others, though.
So far the new tessellator is able to tessellate all of the non-self intersecting curves I have thrown at it (good thing lyon has a pretty large test suite), but doesn't detect intersections yet, and that's on purpose: ignoring intersections is a great way to mess the internal state of the algorithm up and see if it can recover and continue from there. I'll implement detecting and handling intersections eventually of course. I have put no effort in performance yet (will get to that when the new tessellator is close to being usable), it doesn't handle curves and I haven't settled on a way to model the API to support arbitrary vertex attributes when vertices are added during tessellation (again because of self-intersections).
Higher quality monotone tessellation
By "higher quality", I mean reducing the amount of thin triangles that are generated by the algorithm. Long thin triangles have undesirable properties. For example they tend to produce precision issues when used in certain algorithms like physics simulation, and be slower to render on the GPU.
The monotone polygon decomposition approach used in lyon has a tendency to produce long horizontal triangles in some cases. I have a prototype that improves upon this but fails in some cases. To be continued.
Wrapping up
2018 Was a good year for lyon. In this post I put forth Tom Klein's contribution, but other people also helped get the project where it is today. If your name is on the contributor list, then you are awesome and I thank you.
Hopefully 2019 will be the year where the new tessellator matures and replaces the current one and maybe the start of a small vector graphics rendering crate built on top of gfx-hal.