neugierig.org: Chromium Notes

Today's post is a guest post from Adam Langley, whose recent post about SSL extensions we're doing is also likely of interest to readers of this blog.

Clipping.

Most graphics libraries perform 'immediate' anti-aliased clipping. If you set a clipping path which involves a curve then you can draw shapes that intersect it and the edges will be anti-aliased. However, Skia (the graphics library which we use for Chrome on Linux and Windows) doesn't do this because anti-aliased clipping is just an approximation.

Consider the figure with the four squares, below.

At the top left is an anti-aliased clipping region. The darker the pixel, the more is covered by the path. If we were to fill the region with green, we would get the image at the bottom left. When drawing, we consider how much of the clipping region covers each pixel and convert that to an alpha value. For a pixel which was half covered by the clipping region we would calculate 50% × background_color + 50% × green.

However, consider what happens when we first fill with red (top right) and then with green (bottom right). We would expect that the result would be the same as filling with green - the second fill should cover the first. But for pixels which are fractionally covered by clipping region, this isn't the case.

The first fill, with red, works correctly as detailed above. But when we come to do the second fill, the background_color isn't the original background color, but the slightly red color resulting from the first fill. Both CoreGraphics and Cairo have this bug.

It might seem trivial, but if you end up covering anti-aliased clipping regions multiple times you end up with unsightly borders around the clip paths.

The second problem with anti-aliasing, even when done correctly, is that it makes it impossible to put polygons next to each other. The anti-aliased edges end up with hairline seams because the detail of the edge has been lost.

In order to ameliorate this we have a hack in place for Chrome. When a clipping path is requested we create a layer on top of the painting bitmap. All paints while the clip is in effect write to the layer. When the clipping state is popped we perform an anti-aliased clearing outside the clipping path and merge the layer down. We have a few tricks up our sleeve: we'll only create a single layer for multiple clipping paths in the same level of the clipping stack (because we can clean outside of them all when popping the stack). Also, the 'clip outside' operation is still Skia-native, thus aliased.

The single layer trick isn't strictly correct, but it saves memory and worked at the time. It depends on the fact that WebKit applies all the clipping paths for a level of the clipping stack before drawing anything.

As people work on WebKit, this is falling apart. The assumption that the single layer trick depends on isn't always valid any more. Also, people are starting to use clipOut and having two different clipping methods in play ends badly.

Compounding that, the layer code never worked for <canvas> at all. Canvas calls don't manage the clipping stack as WebKit does. In fact, canvas code might not ever bother to pop the clipping stack. So, for canvas, we still use immediate, 1-bit clipping.

(Also, the anti-aliased seams made deanm cry and I couldn't break his beautiful demos.)

So, we might consider adding immediate mode anti-aliased clipping to Skia. Sure, it's an approximation, but it appears that it might be an approximation worth having.

When a clip is in effect, an SkRegion is iterated over and results in a series of rectangles into which the drawing is performed. These rectangles, in the case of a clipping path, are one row high and consist of the scanlines of the path.

These scan lines are cached in the SkRegion when the clipping path is set. It stores them in an array of ints, which appear to be formatted as <Y value> <Number of X spans> <X1 start> <X2 end> .... These spans are generated by creating a dummy SkBlitter and feeding that, and the clipping path, to an SkScan. The dummy blitter records the scan lines that that SkScan calls back with (rather than painting as an SkBlitter would typically do).

So, as you can see, the 1-bit clipping concept is baked pretty deeply in here.

If we wanted the SkRegion iteration to result in an alpha array for each scanline we have a problem. The SkRegion is called for each new scanline, but the SkScan wants to call back for each scanline. Options:

• Store the whole alpha channel in memory (a bitmap as large as the clipping region, or as large as the whole bitmap for a clipOut)
• Rewrite the SkScan to invert the flow of control (rather you than me, sir)
• Switch stacks inside of Skia (you think you have bugs now, wait till you see these ones!)

Also, the latter two involve rescanning the path for each drawing operation. I suspect that will seriously damage your speed.

The only saving grace is that the alpha channel consists of mostly 0xff. Only on the edges are there any other values. So the first option, with suitable compression smarts, might be reasonable.

However, I only allocated a Friday to this problem and that's probably several weeks of work to do.

In the mean time, we can continue to use layers with a couple of modifications. Firstly, the single layer trick doesn't work any more. The rest of WebKit adds clips after drawing and expects them to work. That means that each clip has to allocate a new layer.

Secondly, we can't mix clipping modes any more. That means that clipOut can't be immediate and, if we have a top-level clipOut, the layer is as big as the underlying bitmap. It also means that the rectangle clips have to be converted into paths, which is much slower.

So, in the interim, we will probably throw CPU and memory at the problem although everyone is pretty maxxed out for 6.x.