Experiments
Writing a path tessellator is hard. On the other hand, it makes it possible to experiment with things that would not be possible should we choose to rely on a third party tessellator (like the one provided by Direct2D).
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 interior 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 transfer 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.
If we know that part of the geometry is always going to be hidden because of a clipping rectangle, we could easily add a clip to the tessellator's API in order to not spend CPU time tessellating edges that are outside of the clip, and generate less geometry.
It's probable that we'll just end up having a very large default clip always applied to ensure that no point go beyond the range that can be represented with the internal fixed point representation.
An extension to the Clipped tessellation could be to tile the geometry. Each tile would be a clipped tessellation of a certain rectangular region of the path, and each tile could be tessellated in parallel. For very large vector graphics with many paths, being able to cull out tiles that are outside of the viewport could be useful. Currently it is easy to tile the output at the level of the GeometryBuilder (at the output of the tessellator), but this means that we have to tessellate the entire path in order to start showing tiles (which may be good enough). Tiling the geometry before the tessellation pass would make it possible to tessellate tiles on-demand.