Changeset 132971 in webkit


Ignore:
Timestamp:
Oct 30, 2012 6:37:51 PM (11 years ago)
Author:
commit-queue@webkit.org
Message:

[CSS Exclusions] Multiple segment polygon layout does not get all segments
​https://bugs.webkit.org/show_bug.cgi?id=100039

Patch by Hans Muller <​hmuller@adobe.com> on 2012-10-30
Reviewed by Dirk Schulze.

Source/WebCore:

Corrected the algorithm for computing included polygon intervals for rectilinear polygons,
and polygons with horizontal edges in general.

Tests: fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-001.html

fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-002.html

  • rendering/ExclusionPolygon.cpp: Removed some internal dead code related to the no-longer-used sortedEdgesMinY Vector.

(WebCore::ExclusionPolygon::ExclusionPolygon): Initialize new ExclusionPolygonEdge edgeIndex field.
(WebCore::getVertexIntersectionVertices): Return the previous, next, and target vertex indices for a vertex intersection.
(WebCore::ExclusionPolygon::computeXIntersections): Refactored the core of this method to improve handling of horizontal edges.
(WebCore::ExclusionPolygon::computeEdgeIntersections): Ignore zero-width edges.

  • rendering/ExclusionPolygon.h: Removed the rightVertexY() method, since it's no longer used.

(WebCore::ExclusionPolygon::edgeAt): New method.
(WebCore::ExclusionPolygon::numberOfEdges): New method.
(ExclusionPolygon): Added support for retrieving edges.
(WebCore::ExclusionPolygonEdge::vertex1): Use vertex1Index.
(WebCore::ExclusionPolygonEdge::vertex2): Use vertex2Index.
(ExclusionPolygonEdge): Renamed index1, index2 fields to vertex1Index, vertex2Index.
(WebCore::ExclusionPolygonEdge::previousEdge): New method.
(WebCore::ExclusionPolygonEdge::nextEdge): New method.

LayoutTests:

Added tests for CSS Exclusion shape-inside polygons with horizontal edges.
Corrected the simple-polygon.js code for computing a polygon's included intervals.

  • fast/exclusions/resources/simple-polygon.js:
  • fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-001-expected.html: Added.
  • fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-001.html: Added.
  • fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-002-expected.html: Added.
  • fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-002.html: Added.
  • fast/exclusions/shape-inside/shape-inside-simple-polygon-004-expected.html:
  • fast/exclusions/shape-inside/shape-inside-simple-polygon-004.html:
Location:
trunk
Files:
4 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r132969 r132971  
     12012-10-30  Hans Muller  <hmuller@adobe.com>
     2
     3        [CSS Exclusions] Multiple segment polygon layout does not get all segments
     4        https://bugs.webkit.org/show_bug.cgi?id=100039
     5
     6        Reviewed by Dirk Schulze.
     7
     8        Added tests for CSS Exclusion shape-inside polygons with horizontal edges.
     9        Corrected the simple-polygon.js code for computing a polygon's included intervals.
     10
     11        * fast/exclusions/resources/simple-polygon.js:
     12        * fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-001-expected.html: Added.
     13        * fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-001.html: Added.
     14        * fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-002-expected.html: Added.
     15        * fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-002.html: Added.
     16        * fast/exclusions/shape-inside/shape-inside-simple-polygon-004-expected.html:
     17        * fast/exclusions/shape-inside/shape-inside-simple-polygon-004.html:
     18
    1192012-10-30  Kenichi Ishibashi  <bashi@chromium.org>
    220

  • trunk/LayoutTests/fast/exclusions/resources/simple-polygon.js

    r131610 r132971  
    3939
    4040// Return two X intercepts of the horizontal line at y. We're assuming that the polygon
    41 // 0 or 2 intercepts for all y.Of course this isn't true for polygons in general,
     41// has 0 or 2 intercepts for all y. Of course this isn't true for polygons in general,
    4242// just the ones used by the test cases supported by this file.
    4343
    4444function polygonXIntercepts(polygon, y) {
    4545    var vertices = polygon.vertices;
    46     var vertex = null;  // first intersecting non-horizontal edge vertex, vertex.y == y
    47     var xIntercepts = [];
    48 
    49     for(var i = 0; i < vertices.length && xIntercepts.length < 2; i++) {
     46    var foundXIntercept = false;
     47    var interceptsMinX, interceptsMaxX;
     48
     49    for(var i = 0; i < vertices.length; i++) {
    5050        var v1 = vertices[i];
    5151        var v2 = vertices[(i + 1) % vertices.length];
    5252
    53         if (vertex == v1 || vertex == v2)
     53        if (Math.max(v1.y, v2.y) < y || Math.min(v1.y, v2.y) > y)
    5454            continue;
    5555
    56         var minY = Math.min(v1.y, v2.y);
    57         var maxY = Math.max(v1.y, v2.y);
    58 
    59         if (maxY < y || minY > y)
    60             continue;
    61 
    62         if (minY == maxY)
    63             return [v1.x, v2.x];
    64 
    65         if (v1.y == y) {
    66             xIntercepts.push(v1.x);
    67             if (!vertex)
    68                 vertex = v1;
    69         }
    70         else if (v2.y == y) {
    71             xIntercepts.push(v2.x);
    72             if (!vertex)
    73                 vertex = v2;
     56        if (v1.y == y && v2.y == y) {  // horizontal edge
     57            if (y != polygon.maxY)
     58                continue;
     59
     60            if (!foundXIntercept) {
     61                interceptsMinX = Math.min(v1.x, v2.x);
     62                interceptsMaxX = Math.max(v1.x, v2.x);
     63                foundXIntercept = true;
     64            }
     65            else {
     66                interceptsMinX = Math.min(v1.x, v2.x, interceptsMinX);
     67                interceptsMaxX = Math.max(v1.x, v2.x, interceptsMaxX);
     68            }
    7469        }
    7570        else {
    76             xIntercepts.push( ((y - v1.y) * (v2.x - v1.x) / (v2.y - v1.y)) + v1.x );
     71            var interceptX;
     72
     73            if (v1.y == y)
     74                interceptX = v1.x;
     75            else if (v2.y == y)
     76                interceptX = v2.x;
     77            else
     78                interceptX = ((y - v1.y) * (v2.x - v1.x) / (v2.y - v1.y)) + v1.x;
     79
     80            if (!foundXIntercept) {
     81                interceptsMinX = interceptsMaxX = interceptX;
     82                foundXIntercept = true;
     83            }
     84            else {
     85                interceptsMinX = Math.min(interceptX, interceptsMinX);
     86                interceptsMaxX = Math.max(interceptX, interceptsMaxX);
     87            }
    7788        }
    7889    }
    7990
    80     if (xIntercepts.length != 2)
     91    if (!foundXIntercept)
    8192        return [];
    8293
    83     return [subpixelRound(Math.min.apply(null, xIntercepts)), Math.floor(Math.max.apply(null, xIntercepts))];
     94    return [subpixelRound(interceptsMinX), Math.floor(interceptsMaxX)];
    8495}
    8596

  • trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-simple-polygon-004-expected.html

    r131610 r132971  
    99    // Concave assymetric simple polygon with horizontal top and bottom edges.  A version of the 001
    1010    // hourglass shape with vertical edges in the center.
    11     var vertices = [{x:40, y:40}, {x:440, y:40}, {x:320, y:160}, {x:320, y:240}, {x:480, y:400}, {x:80, y:400}, {x:200, y:280}, {x:200, y:200}]};
     11    var vertices = [{x:40, y:40}, {x:440, y:40}, {x:320, y:160}, {x:320, y:240}, {x:480, y:400}, {x:80, y:400}, {x:200, y:280}, {x:200, y:200}];
    1212    var lineHeight = 40;
    1313    var hasSubpixelSupport;

  • trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-simple-polygon-004.html

    r131610 r132971  
    99    // Concave assymetric simple polygon with horizontal top and bottom edges.  A version of the 001
    1010    // hourglass shape with vertical edges in the center.
    11     var vertices = [{x:40, y:40}, {x:440, y:40}, {x:320, y:160}, {x:320, y:240}, {x:480, y:400}, {x:80, y:400}, {x:200, y:280}, {x:200, y:200}]};
     11    var vertices = [{x:40, y:40}, {x:440, y:40}, {x:320, y:160}, {x:320, y:240}, {x:480, y:400}, {x:80, y:400}, {x:200, y:280}, {x:200, y:200}];
    1212    var lineHeight = 40;
    1313    var hasSubpixelSupport;

  • trunk/Source/WebCore/ChangeLog

    r132970 r132971  
     12012-10-30  Hans Muller  <hmuller@adobe.com>
     2
     3        [CSS Exclusions] Multiple segment polygon layout does not get all segments
     4        https://bugs.webkit.org/show_bug.cgi?id=100039
     5
     6        Reviewed by Dirk Schulze.
     7
     8        Corrected the algorithm for computing included polygon intervals for rectilinear polygons,
     9        and polygons with horizontal edges in general.
     10
     11        Tests: fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-001.html
     12               fast/exclusions/shape-inside/shape-inside-rectilinear-polygon-002.html
     13
     14        * rendering/ExclusionPolygon.cpp: Removed some internal dead code related to the no-longer-used sortedEdgesMinY Vector.
     15        (WebCore::ExclusionPolygon::ExclusionPolygon): Initialize new ExclusionPolygonEdge edgeIndex field.
     16        (WebCore::getVertexIntersectionVertices): Return the previous, next, and target vertex indices for a vertex intersection.
     17        (WebCore::ExclusionPolygon::computeXIntersections): Refactored the core of this method to improve handling of horizontal edges.
     18        (WebCore::ExclusionPolygon::computeEdgeIntersections): Ignore zero-width edges.
     19        * rendering/ExclusionPolygon.h: Removed the rightVertexY() method, since it's no longer used.
     20        (WebCore::ExclusionPolygon::edgeAt): New method.
     21        (WebCore::ExclusionPolygon::numberOfEdges): New method.
     22        (ExclusionPolygon): Added support for retrieving edges.
     23        (WebCore::ExclusionPolygonEdge::vertex1): Use vertex1Index.
     24        (WebCore::ExclusionPolygonEdge::vertex2): Use vertex2Index.
     25        (ExclusionPolygonEdge): Renamed index1, index2 fields to vertex1Index, vertex2Index.
     26        (WebCore::ExclusionPolygonEdge::previousEdge): New method.
     27        (WebCore::ExclusionPolygonEdge::nextEdge): New method.
     28
    1292012-10-30  Chris Evans  <cevans@google.com>
    230

  • trunk/Source/WebCore/rendering/ExclusionPolygon.cpp

    r132127 r132971  
    4848};
    4949
    50 static bool compareEdgeMinY(const ExclusionPolygonEdge* e1, const ExclusionPolygonEdge* e2)
    51 {
    52     return e1->minY() < e2->minY();
    53 }
    54 
    5550ExclusionPolygon::ExclusionPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
    5651    : ExclusionShape()
    … …  
    6156    m_edges.resize(nVertices);
    6257    m_empty = nVertices < 3;
    63     Vector<ExclusionPolygonEdge*> sortedEdgesMinY(nVertices);
    6458
    6559    if (nVertices)
    … …  
    7064        m_boundingBox.extend(vertex);
    7165        m_edges[i].polygon = this;
    72         m_edges[i].index1 = i;
    73         m_edges[i].index2 = (i + 1) % nVertices;
    74 
    75         sortedEdgesMinY[i] = &m_edges[i];
    76     }
    77 
    78     std::sort(sortedEdgesMinY.begin(), sortedEdgesMinY.end(), WebCore::compareEdgeMinY);
     66        m_edges[i].vertexIndex1 = i;
     67        m_edges[i].vertexIndex2 = (i + 1) % nVertices;
     68        m_edges[i].edgeIndex = i;
     69    }
    7970
    8071    for (unsigned i = 0; i < m_edges.size(); i++) {
    … …  
    119110}
    120111
    121 float ExclusionPolygon::rightVertexY(unsigned index) const
    122 {
    123     unsigned nVertices = numberOfVertices();
    124     const FloatPoint& vertex1 = vertexAt((index + 1) % nVertices);
    125     const FloatPoint& vertex2 = vertexAt((index - 1) % nVertices);
    126 
    127     if (vertex1.x() == vertex2.x())
    128         return vertex1.y() > vertex2.y() ? vertex1.y() : vertex2.y();
    129     return vertex1.x() > vertex2.x() ? vertex1.y() : vertex2.y();
     112static inline bool getVertexIntersectionVertices(const EdgeIntersection& intersection, FloatPoint& prevVertex, FloatPoint& thisVertex, FloatPoint& nextVertex)
     113{
     114    if (intersection.type != VertexMinY && intersection.type != VertexMaxY)
     115        return false;
     116
     117    ASSERT(intersection.edge && intersection.edge->polygon);
     118    const ExclusionPolygon& polygon = *(intersection.edge->polygon);
     119    const ExclusionPolygonEdge& thisEdge = *(intersection.edge);
     120
     121    if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y()))
     122        || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) {
     123        prevVertex = polygon.vertexAt(thisEdge.previousEdge().vertexIndex2);
     124        thisVertex = polygon.vertexAt(thisEdge.vertexIndex1);
     125        nextVertex = polygon.vertexAt(thisEdge.vertexIndex2);
     126    } else {
     127        prevVertex = polygon.vertexAt(thisEdge.vertexIndex1);
     128        thisVertex = polygon.vertexAt(thisEdge.vertexIndex2);
     129        nextVertex = polygon.vertexAt(thisEdge.nextEdge().vertexIndex1);
     130    }
     131
     132    return true;
    130133}
    131134
    … …  
    156159    for (unsigned i = 0; i < overlappingEdges.size(); i++) {
    157160        ExclusionPolygonEdge* edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
    158         if (computeXIntersection(edge, y, intersection))
     161        if (computeXIntersection(edge, y, intersection) && intersection.type != VertexYBoth)
    159162            intersections.append(intersection);
    160163    }
    … …  
    170173    while (index < intersections.size()) {
    171174        const EdgeIntersection& thisIntersection = intersections[index];
    172 
    173175        if (index + 1 < intersections.size()) {
    174176            const EdgeIntersection& nextIntersection = intersections[index + 1];
    … …  
    178180                    index += 2;
    179181                } else {
    180                     // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one VertexMinY intersection.
    181                     if (nextIntersection.type == VertexMaxY)
    182                         intersections[index + 1] = thisIntersection;
     182                    // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection.
    183183                    index++;
    184184                }
    … …  
    188188
    189189        const ExclusionPolygonEdge& thisEdge = *thisIntersection.edge;
    190         bool crossing = !windCount;
     190        bool evenOddCrossing = !windCount;
    191191
    192192        if (fillRule() == RULE_EVENODD) {
    193193            windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
    194             crossing = crossing || !windCount;
     194            evenOddCrossing = evenOddCrossing || !windCount;
    195195        }
    196196
    197         if ((thisIntersection.type == Normal) || (thisIntersection.type == VertexMinY)) {
    198             if (crossing)
     197        if (evenOddCrossing) {
     198            bool edgeCrossing = false;
     199            if (thisIntersection.type == Normal || !inside || index == intersections.size() - 1)
     200                edgeCrossing = true;
     201            else {
     202                FloatPoint prevVertex;
     203                FloatPoint thisVertex;
     204                FloatPoint nextVertex;
     205
     206                if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) {
     207                    if (prevVertex.y() == y)
     208                        edgeCrossing =  (thisVertex.x() > prevVertex.x()) ? nextVertex.y() > y : nextVertex.y() < y;
     209                    else
     210                        edgeCrossing = (nextVertex.y() != y);
     211                }
     212            }
     213            if (edgeCrossing)
    199214                inside = appendIntervalX(thisIntersection.point.x(), inside, result);
    200         } else if (thisIntersection.type == VertexMaxY) {
    201             int vertexIndex = (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? thisEdge.index2 : thisEdge.index1;
    202             if (crossing && rightVertexY(vertexIndex) > y)
    203                 inside = appendIntervalX(thisEdge.maxX(), inside, result);
    204         } else if (thisIntersection.type == VertexYBoth)
    205             result.append(ExclusionInterval(thisEdge.minX(), thisEdge.maxX()));
     215        }
    206216
    207217        index++;
    … …  
    236246            std::swap(x1, x2);
    237247
    238         result.append(ExclusionInterval(x1, x2));
     248        if (x2 > x1)
     249            result.append(ExclusionInterval(x1, x2));
    239250    }
    240251

  • trunk/Source/WebCore/rendering/ExclusionPolygon.h

    r132127 r132971  
    6060    WindRule fillRule() const { return m_fillRule; }
    6161
     62    const ExclusionPolygonEdge& edgeAt(unsigned index) const { return m_edges[index]; }
     63    unsigned numberOfEdges() const { return m_edges.size(); }
     64
    6265    virtual FloatRect shapeLogicalBoundingBox() const OVERRIDE { return internalToLogicalBoundingBox(m_boundingBox); }
    6366    virtual bool isEmpty() const OVERRIDE { return m_empty; }
    … …  
    6669
    6770private:
    68     float rightVertexY(unsigned) const;
    6971    void computeXIntersections(float y, Vector<ExclusionInterval>&) const;
    7072    void computeEdgeIntersections(float minY, float maxY, Vector<ExclusionInterval>&) const;
    … …  
    8890    {
    8991        ASSERT(polygon);
    90         return polygon->vertexAt(index1);
     92        return polygon->vertexAt(vertexIndex1);
    9193    }
    9294
    … …  
    9496    {
    9597        ASSERT(polygon);
    96         return polygon->vertexAt(index2);
     98        return polygon->vertexAt(vertexIndex2);
     99    }
     100
     101    const ExclusionPolygonEdge& previousEdge() const
     102    {
     103        ASSERT(polygon && polygon->numberOfEdges() > 1);
     104        return polygon->edgeAt((edgeIndex + polygon->numberOfEdges() - 2) % polygon->numberOfEdges());
     105    }
     106
     107    const ExclusionPolygonEdge& nextEdge() const
     108    {
     109        ASSERT(polygon && polygon->numberOfEdges() > 1);
     110        return polygon->edgeAt((edgeIndex + 1) % polygon->numberOfEdges());
    97111    }
    98112
    … …  
    103117
    104118    const ExclusionPolygon* polygon;
    105     unsigned index1;
    106     unsigned index2;
     119    unsigned vertexIndex1;
     120    unsigned vertexIndex2;
     121    unsigned edgeIndex;
    107122};
    108123
Note: See TracChangeset for help on using the changeset viewer.