Tessellator
This page is a work in progress and is lacking a lot of information, it will hopefully improve over time. The tessellator's code itself also has some inline comments that explain how the different cases are dealt with.
We vaguely refer to "the tessellator" in this wiki to talk about the algorithm that tessellate a Path into a fill operation. The tessellator's job is to output a sequence of triangles in a way that is practical for consumption by various GPU APIs such as OpenGL or Direct3D. The tessellator itself is self-contained and independent of the underlying GPU backend.
The tessellation primitives are all implemented in the lyon_tessellation crate under the tessellation/src/ folder of this repository.
This document will focus on the general purpose fill tessellator implemented in path_fill.rs.
See also the Wikipedia page on the topic of polygon triangulation (we use triangulation and tessellation interchangeably).
The algorithm is based on the properties of monotone polygons
The y-monotone approach is well explained in the book Computational Geometry, Algorithms and Applications. This book was the main source of knowledge when implementing the first versions of the tessellator. There are also some good explanations scattered around the web. A popular tessellator implementation also based on monotone polygons is the GLU tessellator which libtess2 is based on (mentioned here for reference). Lyon's tessellator, while exploiting the same mathematical properties, chose a very different approach when it comes to the actual implementation of the logic and data structures. GLU's tessellator makes heavy use of half-edge meshes with several passes to solve different geometrical problems (one pass to separate the initial shape into non-self-intersecting shapes, another pass to separate these shapes into y-monotone shapes, another pass to tessellate these shapes, etc.), while lyon's tessellator does not store the connectivity information in a data-structure and computes everything in a single pass.
Obviously, we can't simply take any three vertices and connect them to make a triangle until all vertices have been processed. A triangle's edge formed by connecting two vertices must not intersect other edges (and, of course, must not be outside the polygon), so we need to make sure somehow that these intersections don't occur. Testing each new edge for intersections against all other edges in the polygon would be much too expensive. We need to process vertices and edges in a way that provides us with interesting invariants so that we don't need to go through the entire geometry at every step.
The tessellation is a sweep-line algorithm traversing the shape from top to bottom (by increasing y coordinate).
The sweep line can be seen as an imaginary horizontal line that scans the polygon from top to bottom stopping at each vertex (or event). In terms of code, the sweep line is represented as a sequence of pairs of edges that intersect the imaginary line. At each event the sweep line is updated to account for the edges that don't intersect it anymore and the edges that begin intersecting it. the edges on the sweep line are sorted by increasing x coordinate (from left to right).
The animation above illustrates a sweep line algorithm traversing a simple polygon vertex after vertex. Edges that intersect the sweep line are highlighted in orange and edges that are entering the sweep line are highlighted in blue.
Using a sweep-line strategy helps with reducing the complexity of the problem at hand. As we traverse the shape, we have a local understanding of its geometry (at the level of the sweep line and above) which gives us enough guarantees to be able to generate triangles that don't intersect with other edges without having to test against every edge in the shape.
A Span is the area between two edges of the sweep-line representing the intersection between a piece of the inside of the and the sweep line.
The tessellator takes as parameter, a list of edges sorted from top to bottom. All coordinates are internally expressed as fixed point numbers. The main tessellator loop accumulates all of the edges that start at the current position of the sweep line, processes the of all the accumulated events at once and move on to the next position.
This "processing the current position" part contains most of the interesting logic. We first go through the sweep line to find edges that terminate at the current position, remove them from the sweep line and add the new edges we accumulated. Depending on the number of edges below and above the sweep line, the process of removing and adding edges happens in different ways. (TODO: explain this, In the mean-time, refer to the implementation of tessellation::path_fill::FillTessellator::process_vertex in path_fill.rs).
Currently the fill tessellator only works on flattened paths. Curves are flattened before the tessellation algorithm is run for a given approximation tolerance which is dependent on the zoom level. This is not ideal because
- When zooming in, the path should be re-tessellated in order to satisfy the same approximation threshold per device pixel.
- The tessellation algorithm needs to process a lot more edges than if it was working with curves directly.
- The resulting tessellation tends to contain more thin triangles than I'd like.
The plan is to improve this by having the sweep line work with quadratic bezier segments instead of only line segments. The idea is to separate the tessellation of the curve segments form the rest of the interrior of the shape, as shown on the right in the figure below:
On left side a flattened shape, and on the right the same shape with the curves in orange separated from the rest of the shape in blue. Each curve area is described by a triangle formed by the three quadratic curve points. Working this way the tessellator's sweep line has a lot less data to traverse, and the resulting tessellation of the blue part tends to avoid the thin triangle issue. The other advantages are:
- The blue part of the tessellation is resolution-independent, we can tessellate it once and never have to compute it again regardless of the zoom level.
- We can choose how to deal with the curves themselves (the orange part).
- Tessellate them on the CPU.
- trivial and cheap on the CPU side,
- the bottleneck would probably be transferring the vertices rather than tessellating them.
- the areas near the curvy edges still suffer from thin triangles
- Tessellate them using a tessellation shader if available
- no more CPU->GPU trasnfer concerns
- still suffering from the thin triangles issue near the curvy edges
- Render the curves analytically in the fragment shader.
- no more thin triangle issue
- potentially expensive shader
- pre-render quadratic curve "masks" in a texture atlas at the required resolutions and sample from it.
- no thin triangles.
- need to try it out and see if it looks good. We probably only need to render a quadratic curve at a few resolutions.
- very simple shader, no need to treat the blue and orange areas separately.
- do the same texture atlas approach with signed distance fields instead of a mask
- a bit more complicated but may yield better results, not sure.
The bottom-line is, there are many ways we can go about rendering curves with different trade-offs, the important part is to put the infrastructure in place to separate rendering the curves and filling the rest of the shape.
StrokeTessellator is a simplified and implemente implementation of strokes that extrude a strip of triangles along the path. This works well if the stroke is opaque, but isn't correct if the stroke is semi-transparent with self-overlapping areas, because these overlapping areas are covered by triangles several times (which is not what we want if the triangles are going to be rendered with alpha-blending).
At the moment, the only way I can think of to support this properly is to turn the stroke into a fill shape and tessellate it with the fill tessellator.
- Path tessellation can also be implemented using the ear-clipping algorithm or constrained delaunay triangulation. This library does not implement them.
- Stencil-and-cover is a popular way to do path rendering because it is fairly easy to implement. However it requires a lot more memory accesses and render target switches. It is also hard to implement any anti-aliasing other than msaa (not impossible but hard enough to negate the initial simplicity advantage). The comparison between tessellation-based and stencil-based path rendering is a fair bit more complicated than this, and it would be worth experimenting with the stencil approach as well in some cases.
- Some other shader-based approaches pack the curve information in a texture and use complicated fragment shaders to do the rendering. These techniques are interesting but heavily depend on floating point precision and robust drivers (due to the complexity of the shaders). In practice none of the implementations I have seen work reliably across a wide range of gpu hardware and drivers (especially problematic on mobile).