Bug 100763 – [CSS Exclusions] Store ExclusionPolygonEdge vertices in clockwise order

• Component: CSS
• Status: RESOLVED FIXED

[Hans Muller]

The ExclusionPolygon's internal logic, notably getVertexIntersectionVertices(), assumes that ExclusionPolygonEdge vertices are stored in clockwise order. Currently this is assumption is not enforced.

[Hans Muller]

Created attachment 171581 [details]
Patch

[Hans Muller]

(In reply to comment #1)
> Created an attachment (id=171581) [details]
> Patch

This change just forces a polygon's edges' vertices to be listed in clockwise order.  So the inside of the polygon is always on the "right side" of the line segment from vertexIndex1 to vertexIndex2.

[Dirk Schulze]

Comment on attachment 171581 [details]
Patch

I actually don't understand what you mean with forcing clockwise order. If you do that, don't you miss necessary information to determine fill rules (even odd/nonzero)?

[Hans Muller]

Created attachment 172339 [details]
Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG)

We only support polygons defined by a single list of vertices.   Holes can occur because the polygon self-intersects but not because secondary lists of vertices are included.   Self-intersecting polygons fill correctly, even if the vertex order is reversed, with both fill rules.  I've attached an SVG example.

[Hans Muller]

Created attachment 172340 [details]
Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG) 

Fixed a typo in the previous version of the SVG example.

[Dirk Schulze]

(In reply to comment #4)
> Created an attachment (id=172339) [details]
> Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG)
> 
> We only support polygons defined by a single list of vertices.   Holes can occur because the polygon self-intersects but not because secondary lists of vertices are included.   Self-intersecting polygons fill correctly, even if the vertex order is reversed, with both fill rules.  I've attached an SVG example.

You don't reorder the points, you just shift them. If your code does the same, the description seems misleading. Do you just shift?

[Hans Muller]

Created attachment 172345 [details]
Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG)

Sorry about the previous version of the example, it was incorrect.  This version reverses the order of the polygons' vertices, as does the ExclusionPolygon patch.

[Dirk Schulze]

Comment on attachment 171581 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=171581&action=review

LGTM. Just some snippets.

> LayoutTests/fast/exclusions/shape-inside/shape-inside-counterclockwise-polygon-expected.html:18
> +    var hasSubpixelSupport = false; // test doesn't depend on subpixel layout

Proper sentences please.

> LayoutTests/fast/exclusions/shape-inside/shape-inside-counterclockwise-polygon.html:18
> +    var hasSubpixelSupport = false; // test doesn't depend on subpixel layout

Ditto.

> Source/WebCore/rendering/ExclusionPolygon.cpp:70
> +        for (unsigned i = 1; i < nVertices; i++) {

++i Official style now.

> Source/WebCore/rendering/ExclusionPolygon.cpp:81
> +        unsigned vertexIndex = (clockwise) ? i : nVertices - 1 - i;

Are the braces necessary here? I would rather remove them.

> Source/WebCore/rendering/ExclusionPolygon.cpp:86
> +        m_edges[i].vertexIndex2 = ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;

Ditto.

[Hans Muller]

Created attachment 172606 [details]
Patch

I've made the suggested changes.  Merging with the latest repository, which includes the collinear and coincident vertices changes, required a non-trivial merge.  The most significant change (albeit a small one) was in ExclusionPolygon::findNextEdgeVertexIndex().  The "lastVertexIndex" is actually always zero (because we always start at zero) for both clockwise and counter-clockwise traversals.

[Darin Adler]

Comment on attachment 172606 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=172606&action=review

> Source/WebCore/ChangeLog:22
> +        (WebCore):

Please leave lines like this out of the change log even though the script generates them. For extra credit, get the script fixed to not add these.

> Source/WebCore/ChangeLog:24
> +        (WebCore::appendIntervalX): Made this an inline.

Why?

> Source/WebCore/rendering/ExclusionPolygon.cpp:103
> +    bool clockwise = true;

No reason to define and initialize this here.

> Source/WebCore/rendering/ExclusionPolygon.cpp:111
> +    FloatPoint prevVertex = vertexAt((minVertexIndex -1 + nVertices) % nVertices);

Missing space after the "-" here. Also might be clearer to add nVertices before subtracting 1 so we don’t rely on underflow behavior, even though that behavior is defined.

> Source/WebCore/rendering/ExclusionPolygon.cpp:112
> +    clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVertex - prevVertex) > 0;

The boolean should be initialized here.

[Hans Muller]

Created attachment 172628 [details]
Patch

I've made the suggested changes.  I wasn't exactly sure how to handle processing the bug from here, since I've made changes since the review+, so I just reset both flags.  My apologies if that's not the expected bug flag protocol.

[Hans Muller]

Created attachment 172659 [details]
Patch

I've updated the "reviewed by" lines in the ChangeLogs to specify Darin Adler as the reviewer.

[Dirk Schulze]

Comment on attachment 172659 [details]
Patch

rs=me

[WebKit Review Bot]

Comment on attachment 172659 [details]
Patch

Clearing flags on attachment: 172659

Committed r133682: <http://trac.webkit.org/changeset/133682>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.