[CSS Exclusions] Add support for computing first included interval position for polygons

• Component: CSS
• Status: RESOLVED FIXED

[Hans Muller]

Replace the ExclusionPolygon::firstIncludedIntervalPosition() stub.  A description of the algorithm I anticipate implementing is here: http://hansmuller-webkit.blogspot.com/2012/08/revised-algorithm-for-finding-first.html

[Hans Muller]

Created attachment 184022 [details]
Patch

[Hans Muller]

Created attachment 184027 [details]
Patch

Removed an unused ExclusionPolygon field.

[Bear Travis]

Comment on attachment 184027 [details]
Patch

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

Only made it through the intersection code so far, but looks good. I've commented on some small tweaks you may consider.

> LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html:6
> +    if (window.internals)
> +        window.internals.settings.setCSSExclusionsEnabled(true);

This isn't necessary in the expectation file.

> LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html:44
> +        </br/>&nbsp;&nbsp;&nbsp;X<br/>&nbsp;&nbsp;<span id="blue">XX</span><br/>&nbsp;XXX

Would it be cleaner to wrap this in a pre tag rather than use the nbsp entity?

> LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001.html:37
> +        X <span id="blue">XX</span> XXX

You probably want class for 'blue', 'shape-inside', and 'shape-outline' as ids should only be used once per document.

> Source/WebCore/rendering/ExclusionPolygon.cpp:65
> +static inline bool isPointOnLineSegment(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)

It would help if the argument names distinguished which point you were testing to be on the line segment.

> Source/WebCore/rendering/ExclusionPolygon.cpp:384
> +static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)

Returning > 0 seems a little odd, since I typically think of numbers increasing from left to right. But if it's a common polygon geometry term, don't sweat it.

> Source/WebCore/rendering/ExclusionPolygon.cpp:389
> +bool ExclusionPolygon::pointInPolygon(const FloatPoint& point) const

Where does this algorithm come from? If you can just include a reference in your changelog, that would be helpful.

> Source/WebCore/rendering/ExclusionPolygon.cpp:427
> +        if (!leftSideValues[i])

Does a collinear vertex not count as overlapping?

> Source/WebCore/rendering/ExclusionPolygon.cpp:445
> +    float den = determinant(thisDelta, otherDelta);

the jump from the mentioned paper to determinants was non-obvious to me and took a little head-scratching. Might be worth noting in the code or in the changelog.

> Source/WebCore/rendering/ExclusionPolygon.cpp:446
> +    if (!den)

what if the two lines are collinear?

[Hans Muller]

(In reply to comment #3)
> (From update of attachment 184027 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=184027&action=review

> 
> > LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html:6
> > +    if (window.internals)
> > +        window.internals.settings.setCSSExclusionsEnabled(true);
> 
> This isn't necessary in the expectation file.

Thanks, I've removed all occurrences.

> > LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html:44
> > +        </br/>&nbsp;&nbsp;&nbsp;X<br/>&nbsp;&nbsp;<span id="blue">XX</span><br/>&nbsp;XXX
> 
> Would it be cleaner to wrap this in a pre tag rather than use the nbsp entity?

The pre tag is confusing (at least to me) in the way it handles leading white space, and spaces are rather critical here.  I was able to use it in two of the tests, and it definitely improves readability.

> > LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001.html:37
> > +        X <span id="blue">XX</span> XXX
> 
> You probably want class for 'blue', 'shape-inside', and 'shape-outline' as ids should only be used once per document.

Yes, I've fixed that.  And I've removed the extraneous "blue" styles from the files that don't use them.

> > Source/WebCore/rendering/ExclusionPolygon.cpp:65
> > +static inline bool isPointOnLineSegment(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)
> 
> It would help if the argument names distinguished which point you were testing to be on the line segment.

I've renamed the line line segment endpoint parameters vertex1 and vertex2. Although names like lineSegmentEndpoint1,2 would be more meaningful, they kill the readability of the point arithmetic expressions.

> > Source/WebCore/rendering/ExclusionPolygon.cpp:384
> > +static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
> 
> Returning > 0 seems a little odd, since I typically think of numbers increasing from left to right. But if it's a common polygon geometry term, don't sweat it.

There's no secret geometer's convention at work here although I have seen this function coded similarly elsewhere.

> > Source/WebCore/rendering/ExclusionPolygon.cpp:389
> > +bool ExclusionPolygon::pointInPolygon(const FloatPoint& point) const
> 
> Where does this algorithm come from? If you can just include a reference in your changelog, that would be helpful.

There are a million variations on this simple point in polygon algorithm.  I don't know a definitive reference for exactly this variant, but http://paulbourke.net/geometry/polygonmesh/ is a good source for point in polygon algorithms in general.

> > Source/WebCore/rendering/ExclusionPolygon.cpp:427
> > +        if (!leftSideValues[i])
> 
> Does a collinear vertex not count as overlapping?

Yes.  In other words if the first fit rectangle touches a polygon edge (it's guaranteed to for at least one edge) that's OK.

> > Source/WebCore/rendering/ExclusionPolygon.cpp:446
> > +    if (!den)
> 
> what if the two lines are collinear?

In the abstract I think that's OK, since there's no intersection "point" in that case.  It may be necessary to deal with this when reflex vertex detection is included, since one could create a shape that pinned the first fit location between a pair of opposing reflex vertices.  As a practical matter, this is unlikely to come up very often.

[Hans Muller]

Created attachment 184068 [details]
Patch

Incorporated Bear's feedback.

[Dirk Schulze]

Comment on attachment 184068 [details]
Patch

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

Some style comments. I am not so familiar with the algorithms and need to trust you here.

> Source/WebCore/rendering/ExclusionPolygon.cpp:397
> +    for (unsigned i = 0; i < numberOfEdges(); i++) {

++i

> Source/WebCore/rendering/ExclusionPolygon.cpp:404
> +                windingNumber += 1;

why not windingNumber++ and

> Source/WebCore/rendering/ExclusionPolygon.cpp:407
> +                windingNumber -= 1;

windingNumber-- ? Use the main advantage of C++ over C :D

> Source/WebCore/rendering/ExclusionPolygon.cpp:427
> +    int s = 0;

other name for s please.

> Source/WebCore/rendering/ExclusionPolygon.cpp:431
> +        int sgn = leftSideValues[i] > 0 ? 1 : -1;

We don't have a competition for finding the shortest name :D More descriptive name please.

> Source/WebCore/rendering/ExclusionPolygon.cpp:447
> +    float den = determinant(thisDelta, otherDelta);

Why den? det would make more sense (used in math anyway). I would even prefer float determinant = this->determinant() but don't know where it is specified.

> Source/WebCore/rendering/ExclusionPolygon.cpp:453
> +    float ua = determinant(otherDelta, vertex1Delta) / den;
> +    float ub = determinant(thisDelta, vertex1Delta) / den;

can you choose more descriptive names here please?

> Source/WebCore/rendering/ExclusionPolygon.cpp:467
> +    for (unsigned i = 0; i < overlappingEdges.size(); i++) {

++i

> Source/WebCore/rendering/ExclusionPolygon.cpp:500
> +    for (unsigned i = 0; i < numberOfEdges(); i++) {

++i

> Source/WebCore/rendering/ExclusionPolygon.cpp:514
> +        for (unsigned j = 0; j < offsetEdgePair.size(); j++)

++j

> Source/WebCore/rendering/ExclusionPolygon.cpp:525
> +    for (unsigned i = 0; i < offsetEdges.size() - 1; i++) {

++i

> Source/WebCore/rendering/ExclusionPolygon.cpp:526
> +        for (unsigned j = i + 1; j < offsetEdges.size(); j++) {

++j

[Hans Muller]

Created attachment 184277 [details]
Patch

Made the changes that Dirk recommended.

[WebKit Review Bot]

Attachment 184277 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html', u'LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001.html', u'LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002-expected.html', u'LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002.html', u'LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003-expected.html', u'LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003.html', u'Source/WebCore/ChangeLog', u'Source/WebCore/platform/graphics/FloatSize.h', u'Source/WebCore/rendering/ExclusionPolygon.cpp', u'Source/WebCore/rendering/ExclusionPolygon.h']" exit_code: 1
Source/WebCore/rendering/ExclusionPolygon.cpp:452:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Total errors found: 1 in 11 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Dirk Schulze]

Comment on attachment 184277 [details]
Patch

Please fix the style issue before landing. r=me.

[Hans Muller]

Created attachment 184303 [details]
Patch

[WebKit Review Bot]

Comment on attachment 184303 [details]
Patch

Clearing flags on attachment: 184303

Committed r140606: <http://trac.webkit.org/changeset/140606>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.