Gecko:CSSBorderRenderingWithShaders

Problem Statement

Our border-rendering problem can be reduced to the following parameters:

• For each side, a border style: one of SOLID, DASHED, DOTTED.
• For each side, a list of (color, width) pairs (say listing the colors from outside in). The list is empty if the side has no border.
• An outer rectangle.
• Horizontal and vertical radii for each corner.

Current Situation

nsCSSRenderingBorders.cpp has a lot of code that's fairly complex. It tries to handle various situations using "fast paths" but it's hard to follow and in many complex cases (which show up on real Web sites; e.g. GMail uses rounded borders, multiple colors per side and different colors on different sides all together) performance is rather slow because we use complex cairo operations such as PushGroup and OPERATOR_ADD.

In many cases the borders we're drawing --- especially the difficult bits, the corners (as opposed to sides) --- actually don't cover many pixels. It's worth investigating an alternative approach where we compute the color value of each pixel directly as a function of its coordinates, one pixel at a time, instead of trying to draw the borders using cairo/gfxContext operations.

Approach

1. Divide the border into 8 pieces (some of which may be empty): 4 corners and 4 straight sides. We can do simpler/faster things for the straight-sides pieces than for the corners.
2. For each corner and side:
   1. For each pixel with coordinates (x,y) in that corner or side:
      1. Compute the value of the pixel as if all border styles are SOLID, based on x/y and knowing which corner or side the pixel belongs to
      2. For DASHED/DOTTED styles, compute a mask alpha value indicating how much of the pixel is to be drawn --- 0 if the pixel is completely outside any dash/dot, 1 if the pixel is completely inside a dash/dot, some other values if it's on the edge

Computing Color Values For Side Pixels

Just sample a 1D texture based on the distance of the pixel from the outer rectangle edge.

Computing Color Values For Corner Pixels

Precalculate the line segment where the two sides meet. bug 652650 has experiments and code for the best way to do this. This line segment should be a reasonable place for us to change border styles (dotted/dashed/solid) too (see below).

Assuming the pixel is on one side of that line, compute its distance to the outside border edge (hopefully bug 652650 has a method for that too) and use that to sample the 1D texture for that side.

Then do the same thing assuming the pixel is on the other side of the line.

Then combine the two values based on which side of the line (and how far from the line) the pixel actually is.

Computing Masks

Precalculate where the dots and/or dashes for each side are supposed to go. bug 652650 has experiments and code for this.

Here are the constraints I think are important, most important first:

1. If sides with different styles meet, then the style change should either happen in the middle of a dash or dot, or in a gap between the dashes/dots. We should never have a partial dash or dot standing alone unconnected to another partial dot/dash or a solid side. As noted above, the line segment separating the two sides should pass through the middle (or nearly the middle) of the dots or dashes.
2. Where sides with different styles meet in the middle of a dash or dot, the dot diameter and the dash width should equal the border width at the line segment that separates the sides.
3. When adjacent sides are both dotted and equal width, and the corner has no border-radius, there should be a dot in the corner. Rectangular dotted borders look much better with dots in the four corners.
4. When adjacent sides are both dashed and equal width, and the corner has no border-radius, there should be an L-shaped dash in the corner. Rectangular dashed borders look better with those L-shaped dashes in the corners.
5. When there's a border-radius, if the border-radii and side widths are equal I think we should still have a dot or dash centered in the corner, although this is less important.
6. Gaps between dots/dashes should not shrink below some minimum size as a fraction of the dash length. If a side doesn't have enough room for a gap, make that side solid.
7. If at all possible, dash lengths and gap lengths along a straight side should be integer multiples of device pixels and equal.
8. If at all possible, the distance between dot centers along a straight side should be integer multiples of device pixels and equal.

If the border radii or border-widths are unequal then symmetry around the corner is already lost so it's not bad to lose constraints 3-5. However it would be nice, if the border radii are nearly equal and the border widths are nearly equal, to render close to the rendering if they were equal.

For each side, including the corner areas up to the line segments that separate it from the other sides, we can compute the geometry of the dashes or dots for the side. For each dot, compute the center point and radius. For each dash, compute the center of the dash in terms of "distance around the border", and its length in terms of "distance around the border".

For each pixel, determine for the side(s) it may belong to as we do for colors. Then for a dotted side, compute the dot that it must be closest to and test to see if it's within the dot. For a dashed side, compute the dash it must be closet to (by computing the pixel's "distance around the border") and then whether it's in the dash. (It should not be necessary to compute the pixel's distance perpendicular to the border, since color computation will produce transparent values for pixels off the border.)

One approach to making that fast would be to build two arrays, one listing the geometry data for each dash/dot on the side, and another array mapping "distance around the border" (in integer device pixels) to the index of the dash/dot closest to pixels that far around the border.

Performance On CPU

This might work well enough on the CPU. In just about all cases, we could draw the straight sides reasonably efficiently using Thebes instead of per-pixel calculations, so only corners need the full treatment. (I'd actually avoid huge paths and draw dots/dashes using a repeating image pattern.) Stroking narrow curved paths is pretty slow in cairo already, and most of our corners are small.