Since starting work on Flow, our focus for the rendering engine has been on HTML/CSS. The number of basic shapes and painting styles used in HTML/CSS is quite small, which has allowed us to create a highly specialised engine using the GPU for all painting tasks. We’ve also supported elements in Flow for a while, but until recently all canvas rendering was performed on the CPU.
Optimising rendering in canvas using the GPU is a very different task to rendering HTML/CSS since most rendering in canvas is done by creating vector paths on-the-fly using drawing commands, such as, moveTo(), lineTo(), bezierCurveTo(). For instance to draw a 100×100 square the commands would be something like: moveTo(0,0), lineTo(100,0), lineTo(100,100), lineTo(0,100), lineTo(0,0). However paths can be much more complicated than this – they can cross over themselves and also contain multiple closed loops to form holes within other loops. Once the vector path is created, the paths can then be filled or stroked.
Filling arbitrary vector paths is a difficult task to perform efficiently on a GPU. The basic draw primitives of GPUs are triangles, so the challenge becomes how to draw a set of triangles to cover the vector path. One way to do this would be to directly subdivide the path into triangles (triangulation). For simple paths like squares or other convex polygons triangulation would be simple. For more complicated paths which are concave, have self-intersections or holes, triangulation can be computationally expensive, and the work must be performed on the CPU.
The method we used in Flow is based on the “Stencil and Cover” technique as described by Nvidia. This is an ingenious method which avoids the need for triangulation of the path, and means complicated paths can be rendered quickly.
The technique makes use of an extra pixel buffer available to GPUs – the stencil buffer. This buffer is not displayed directly on screen, but instead stores extra information per pixel, and can then be used as a mask when drawing the final coloured pixels to the screen. For the purpose of the following example we can assume this buffer contains only a single bit of information per pixel.
To create this stencil buffer mask we perform the following steps:
- Pick an arbitrary point A. Somewhere near the centre of the path is typical.
- Draw a triangle into the stencil buffer between point A, a point on the path and the next point along the path.
- Repeat the process for every point on the path, so that we cover the entire path.
Seems simple doesn’t it? However the interesting bit is what happens to the value in the stencil buffer. Wherever a triangle is drawn into the stencil buffer we ‘flip’ the value of the buffer. So any areas that are covered by an odd number of triangles will end up having a value of 1 in the stencil buffer, and all areas covered by an even number of triangles will have a value of 0.
Below is a visualisation of what’s happening in the stencil buffer as these triangles are drawn. As you can see, when a triangle is drawn over an area it flips from black to white, or white to black.
As you’ll notice, once the triangles have all been drawn for a closed path the only filled area remaining is inside the path! Any area outside the path that was temporarily filled always gets flipped back to unfilled. No matter where we choose the point A this is always the case.
Once the stencil buffer has been populated it can then be used as a mask, either to do a solid fill or something more complicated like a gradient.
This is all a bit of an over-simplification, since we haven’t discussed how we deal with drawing curves, or anti-aliased fill edges, but the basic mechanism remains the same.
At the moment we only use this technique for canvas acceleration, but we’re planning to use it to render SVG as well.
If you’d like to automatically receive our posts by email please join our mailing list.
