Bug 122613 – [CSS Shapes] Improve the performance of image valued shapes with large shape-margins

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Hans Muller]

TBD

[Hans Muller]

The horizontal runs of pixels that are defined by shape-image-threshold for an image valued shape are stored internally as lists of x1,x2 "intervals" (see ShapeInterval.h). The internal representation of the per-row lists of intervals is called RasterShapeIntervals. An image valued shape is represented a RasterShape instance which has one RasterShapeIntervals object for its intrinsic above-threshold shape, another for its (intrinsic) shape after being expanded by shape-margin, and another after being contracted by shape-padding. The shape-padding and shape-margin RasterShapeIntervals objects are created as needed.

To create the shape-margin RasterShapeIntervals object we effectively replace each interval in the intrinsic shape with a filled rounded rectangle. The interval defines the horizontal axis of the rounded rectangle, it's width and height are expanded by shape-margin, and its corner radius is the shape-margin. The union of all the rounded rectangles, one per intrinsic shape interval, defines the shape-margin shape.  The current implementation computes the shape-margin RasterShapeIntervals object in the most straightforward way possible. The intervals for each rounded rectangle are progressively unioned together, for each interval in the intrinsic shape.

Currently only the leading or trailing edge of the shape-margin object is used to compute the layout of lines. This is because shape-margin expands the shape specified with shape-outside, and shape-outside is only used with left/right floats (all this per the "CSS Shapes Module Level 1 spec", see http://dev.w3.org/csswg/css-shapes-1/). The implication of this for the implementation is that we replace each row's interval list from the intrinsic shape with a single interval defined by the first interval's X1 coordinate and the last interval's X2 coordinate. So the process of computing the shape-margin shape can be reduced to computing the union of one rounded rectangle per image row. The rounded rectangles themselves are represented by a list of intervals, so the entire process is just computing the union of pairs of intervals.

To make the process more efficient, particularly for large shape-margin values, we can skip rounded rectangle intervals whose contribution to the result will be redundant. The attached figure should clarify this.

[Hans Muller]

Created attachment 214268 [details]
Figure 1 - overall margin boundary process

[Hans Muller]

Created attachment 214270 [details]
Figure 2 - Contribution of one interval to the overall margin boundary

[Hans Muller]

Created attachment 214271 [details]
Figure 3 - Opportunity for optimization: overlapping margin boundary contributions

[Hans Muller]

Created attachment 214316 [details]
Patch

The cost of computing the shape-margin boundary of an image-valued shape-outside is now proportional to (2 * shape-margin + image.height) rather than (2 * shape-margin * image.height). The performance improvement comes from skipping sequences of rounded-rectangle intervals that will not contribute to the final result. Each non-empty row in the original image contributes one rounded-rectangle whose corner radius is shape-margin, height is 2 * shape-margin, and width is 2 * shape-margin plus the width of the limits of the intervals on the row.

Renamed private method RasterShape::getIntervals() to intervalsAt() to be a little more consistent with WebKit naming conventions.

There are no new tests since is just an internal refactoring.

[Andreas Kling]

Comment on attachment 214316 [details]
Patch

r=me. Love the detailed write-up :)

[WebKit Commit Bot]

Comment on attachment 214316 [details]
Patch

Clearing flags on attachment: 214316

Committed r157574: <http://trac.webkit.org/changeset/157574>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.