Bug 99343 – [CSS Exclusions] Polygon edges should span colinear vertices

• Component: CSS
• Status: RESOLVED FIXED

[Hans Muller]

At the moment, ExclusionPolygonEdges always (just) connect adjacent vertices.  When a sequence of 3 or more colinear vertices appears, the polygon edge should be defined in terms of the first and last colinear vertices.  This reduces the size of the overall ExclusionPolygon data structure, and will make looking up polygon edges - see m_edgeTree.allOverlaps() - more efficient.

Note that this can be a little tricky when the colinear vertices wrap around the end of the polygon.  For example this CSS polygon has 5 edges.  

  polygon(10px 10px, 20px 10px, 30px 10px, 15px 30px, 0px 10px)

Its ExclusionPolygon representation should be a simple triangle:

  polygon(0px 10px, 30px 10px, 15px 30px)

[Hans Muller]

Created attachment 171982 [details]
Patch

ExclusionPolygonEdges now span coincident and collinear vertices. Currently pairs of vertices are only considered coincident if their coordinates are exactly equal. Similarly, a vertex is only considered collinear with an edge if the area of the triangle defined by the three vertices is exactly zero.  In the future it may be useful to relax the comparison with zero.

[Dirk Schulze]

Before I review this. Do you preserve the overall direction of the vertex?

[Hans Muller]

(In reply to comment #2)
> Before I review this. Do you preserve the overall direction of the vertex?

Yes.

[Dirk Schulze]

Comment on attachment 171982 [details]
Patch

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

Looks good, just some comments.

> Source/WebCore/ChangeLog:24
> +        (WebCore::ExclusionPolygon::ExclusionPolygon): Skip coincident,collinear vertices when building the list of edges.

coincident,collinear space missing.

> Source/WebCore/rendering/ExclusionPolygon.cpp:84
> +        if (areCollinearPoints(vertexAt(vertexIndex1), vertexAt(vertexIndex2), vertexAt(vertexIndex3)))
> +            vertexIndex2 = vertexIndex3;
> +        else
> +            break;

why not 

if (!(...))
    break;

vertexIndex2 = ...

> Source/WebCore/rendering/ExclusionPolygon.cpp:103
> +    if (!m_empty) {
> +        unsigned edgeIndex = 0;

looks like you can return earlier here:

if (m_empty)
    return;

> Source/WebCore/rendering/ExclusionPolygon.cpp:129
> +    if (!m_empty) {

Ditto.

[Hans Muller]

Created attachment 172352 [details]
Patch

I've made the suggested changes.

[Dirk Schulze]

Comment on attachment 172352 [details]
Patch

r=me

[WebKit Review Bot]

Comment on attachment 172352 [details]
Patch

Clearing flags on attachment: 172352

Committed r133490: <http://trac.webkit.org/changeset/133490>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.