Bug 100763 - [CSS Exclusions] Store ExclusionPolygonEdge vertices in clockwise order
Summary: [CSS Exclusions] Store ExclusionPolygonEdge vertices in clockwise order
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Hans Muller
URL:
Keywords:
Depends on: 100039
Blocks:
  Show dependency treegraph
 
Reported: 2012-10-30 08:42 PDT by Hans Muller
Modified: 2012-11-06 15:47 PST (History)
4 users (show)

See Also:


Attachments
Patch (8.23 KB, patch)
2012-10-30 21:51 PDT, Hans Muller
krit: review-
krit: commit-queue-
Details | Formatted Diff | Diff
Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG) (1.08 KB, image/svg+xml)
2012-11-05 08:30 PST, Hans Muller
no flags Details
Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG) (1.08 KB, image/svg+xml)
2012-11-05 08:32 PST, Hans Muller
no flags Details
Self-intersecting polygon example with fill-rule = evenodd, nonzero (SVG) (1.08 KB, image/svg+xml)
2012-11-05 08:53 PST, Hans Muller
no flags Details
Patch (8.79 KB, patch)
2012-11-06 09:49 PST, Hans Muller
darin: review+
Details | Formatted Diff | Diff
Patch (8.83 KB, patch)
2012-11-06 11:53 PST, Hans Muller
no flags Details | Formatted Diff | Diff
Patch (8.81 KB, patch)
2012-11-06 15:22 PST, Hans Muller
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Hans Muller 2012-10-30 08:42:43 PDT
The ExclusionPolygon's internal logic, notably getVertexIntersectionVertices(), assumes that ExclusionPolygonEdge vertices are stored in clockwise order. Currently this is assumption is not enforced.
Comment 1 Hans Muller 2012-10-30 21:51:44 PDT
Created attachment 171581 [details]
Patch
Comment 2 Hans Muller 2012-10-31 10:24:44 PDT
(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.
Comment 3 Dirk Schulze 2012-11-05 07:04:27 PST
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)?
Comment 4 Hans Muller 2012-11-05 08:30:10 PST
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.
Comment 5 Hans Muller 2012-11-05 08:32:15 PST
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.
Comment 6 Dirk Schulze 2012-11-05 08:36:33 PST
(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?
Comment 7 Hans Muller 2012-11-05 08:53:08 PST
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.
Comment 8 Dirk Schulze 2012-11-05 15:31:22 PST
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.
Comment 9 Hans Muller 2012-11-06 09:49:29 PST
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.
Comment 10 Darin Adler 2012-11-06 10:25:18 PST
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.
Comment 11 Hans Muller 2012-11-06 11:53:03 PST
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.
Comment 12 Hans Muller 2012-11-06 15:22:26 PST
Created attachment 172659 [details]
Patch

I've updated the "reviewed by" lines in the ChangeLogs to specify Darin Adler as the reviewer.
Comment 13 Dirk Schulze 2012-11-06 15:24:41 PST
Comment on attachment 172659 [details]
Patch

rs=me
Comment 14 WebKit Review Bot 2012-11-06 15:47:31 PST
Comment on attachment 172659 [details]
Patch

Clearing flags on attachment: 172659

Committed r133682: <http://trac.webkit.org/changeset/133682>
Comment 15 WebKit Review Bot 2012-11-06 15:47:36 PST
All reviewed patches have been landed.  Closing bug.