Gecko:Image Snapping and Rendering

Preamble: General Rendering Principles (dbaron)

1. Paints with different dirty rectangles draw the same values for the device pixels in the intersection of the dirty rects. Otherwise, visual glitches are inevitable.
2. All edges (e.g., of background color, background image, border, foreground image, etc.) at the same subpixel location must be snapped (or not snapped) to the same place. This includes multiple edges of the same element, edges of ancestor/descendant elements, and edges of elements without an ancestor/descendant relationship.
3. Any two edges separated by a width that maps to an exact number of device pixels must snap to locations separated by the same amount (and direction).

Image Snapping And Rendering Requirements

Input:

• Image (actual size in CSS pixels)
• Image initial rectangle (appunits)
• Anchor point within initial rectangle (appunits)
• Logical fill rectangle (appunits)
• Ratio of appunits to device pixels
• Actual dirty rectangle (device units)

Output:

• An image-space to device-space transform (translation and scale)
• A device-space, pixel-aligned rectangle to fill
• A pixel rectangle in tiled image space outside of which gfx should not sample (using EXTEND_PAD as necessary)

For CSS background drawing, the "image initial rectangle" is determined by background-size and the "anchor point" for the image (which is determined by background-position and background-attachment). The "logical fill rectangle" is the intersection of background-clip and the area covered by the image (determined by taking the image initial rectangle and tiling it as per background-repeat).

Requirements:

1. The basic plan is that the image is scaled to fill the initial rectangle, which is tiled over the plane and clipped to the logical fill rectangle. Pixels outside the dirty rectangle need not be drawn. We should approximate that as closely as possible given the limitations of device pixels.
2. Paints with different dirty rectangles draw the same values for the pixels they draw in common. (RATIONALE: Principle #1.)
3. The device pixels that are filled should be the logical fill rectangle rounded to device pixel edges, preserving device pixel centers. (RATIONALE: That's how we "pixel snap" solid rect fills and image drawing should be consistent with solid fills in the pixels that are touched. Satisfies Principles #2 and #3.)
4. Every pixel (in the plane of tiled images) sampled in actual rendering would also be sampled by an ideal rendering to an infinite-resolution device. (RATIONALE: Web authors should not be faced with fringes contributed by pixels they did not intend to be sampled.)
5. The ratio of initial rectangle size in device pixels to image size in CSS pixels, along both axes, must be used as the scale factors for the image space to device space transform. (RATIONALE: Otherwise scaled image tiling will become grossly incorrect at large distances.)
6. When the anchor point, mapped back to image space via the initial rect, lies on an image pixel boundary, the device-space-to-image-space transform should map a device pixel boundary to that image pixel boundary. (RATIONALE: A CSS background-position:right/bottom image should actually be drawn with the rightmost/bottommost set of pixels at the appropriate edge of the element, no matter what scaling is in effect, so we need to be told which edges should line up and make sure they do.)
7. When the scale factors are 1, the translation from device space to image space must be integer multiples of pixels. (RATIONALE: Avoid filtering if possible.)
8. The device fill rectangle, mapped back to image space, must intersect the subimage rectangle. (RATIONALE: If they don't intersect then it's not clear what should be rendered.)

Requirements 5 and 6 imply the following additional requirement:

• If the initial rectangle size in device pixels equals the image size in CSS pixels, then the filled area is rendered as a simple copy of the ideal rendering translated by less than or equal to half a pixel in the horizontal and vertical directions (except where image pixels in the ideal rendering do not contain the center of any device pixel --- i.e. partial pixels). (RATIONALE: If the scale factor in the author's design is exactly the inverse of the scale required by the device, we must avoid scaling and subpixel translation or there will be unnecessary image blurring and performance penalty; in fact, all we're allowed to do is translate the rendering by a minimal amount to pixel-align the image.)

Requirement 5 is perhaps a little stronger than necessary. When the scale factors are not 1, and only one image tile is required (i.e. the initial rectangle equals the logical fill rectangle), we could allow small changes in the scale factors (e.g. setting them to 1 if they're already close to 1 and the other requirements can be satisfied). But it's unclear whether this would be useful or necessary.

Algorithm

An algorithm that satisfied these requirements:

• Compute tiled-space source image pixel rectangle by mapping the logical fill rectangle back to image pixels and rounding out to the nearest image pixel. This will be passed down to gfx to ensure requirement 4 holds --- gfx will limit sampling to this area using EXTEND_PAD or equivalent. (It does not affect the image-space to device-space transform.)
• Compute device pixel fill rectangle by snapping the logical fill rectangle to device pixels, preserving device pixel centers, thus ensuring requirement 3.
• Map the anchor point back to image space (using the initial rect), snap to the nearest image pixel corner and call the result P. Let P' be P, transformed by the same transform that maps the image rectangle to the initial rectangle, then snapped to the nearest device pixel corner. Then the transformation from image space to device space is the transformation whose scale factors are the ratio of initial rectangle size in device pixels to image size in pixels, and which transforms P to P'. (Intuition: choose the nearest image pixel corner to the anchor and align it to device pixels.)
• Compute device pixel draw rectangle by intersecting the device pixel fill rectangle with the dirty rectangle scaled to device pixels and rounded out. This is the area to cairo_fill. But only intersect with the dirty rect if the transformation from image space to device space is a translation by whole pixels; otherwise there may be filtering which would cause edge pixel values to be affected by the dirty rect intersection.

Requirement 2 is satisfied since the dirty rect is only used to constrain the filled area, and only when filtering does not occur. Requirements 3, 4, 5, 6 and 7 are satisfied by construction.

Requirement 8

Requirement 8 is difficult to prove. Here's the proof. We'll consider just one axis and show that the device pixel fill rectangle, transformed to image space, intersects the subimage rectangle along that axis.

The input parameters:

• Let H be the image dimension in pixels
• Let D1 and D2 be the start and end of the initial rectangle in device space
• Let F1 and F2 be the start and end of the logical fill rectangle in device space
• Let A be the anchor point in image space

We require H > 0, D1 < D2 and F1 < F2. The parameters are otherwise unconstrained.

Define our algorithm:

• Define the device pixel fill rectangle F1' = round(F1), F2' = round(F2)
• Define the scale factor S = H/(D2 - D1)
• Define the snapped image anchor point P = round(A)
• Define the snapped device-space anchor point P' = round(D1 + P/S)
• Define the translation T = P - S.P'
• Define the subimage rectangle I1 = floor(S.(F1 - D1)), I2 = ceil(S.(F2 - D1))

If F1' = F2' then there is nothing to draw and requirement 8 is not relevant. So assume F1' < F2'. We must show that the ranges [I1, I2] and [S.F1' + T, S.F2' + T] have non-empty intersection.

Let C = P' - (D1 + P/S). Then -0.5 < C <= 0.5, by the definition of 'round'.

Since F1' < F2' and they're both integers, we must have F2' - 0.5 > F1 (otherwise F1 would have rounded up to F2'). Therefore F2' - C > F1. Therefore S.(F2' - C - D1) > S.(F1 - D1). Therefore S.(F2' - C - D1) > I1. Now S.(F2' - C - D1) = S.(F2' - P' + D1 + P/S - D1) = S.F2' - S.P' + P = S.F2' + T. So S.F2' + T > I1.

Similarly we must have F1' + 0.5 <= F2 (or F2 would have rounded down to F1'). Therefore F1' - C < F2. Therefore S.(F1' - C - D1) < S.(F2 - D1). Therefore S.(F1' - C - D1) < I2. Now S.(F1' - C - D1) = S.(F1' - P' + D1 + P/S - D1) = S.F1' + T. So S.F1' + T < I2.

Hence the ranges have non-empty intersection.