Changeset 112182 in webkit


Ignore:
Timestamp:
Mar 26, 2012 5:16:30 PM (12 years ago)
Author:
vangelis@chromium.org
Message:

[chromium] Simplify and fix CCLayerSorter
​https://bugs.webkit.org/show_bug.cgi?id=82114

Source/WebCore:

A significant cleanup, simplification and improvement of the CCLayerSorter code.
Simplified the LayerShape structure to use WebCore's FloatQuad for all overlap tests.
By treating every layer as two triangles, the old overlap code did a lot of redundant work
including testing two of the vertices of the layer and its diagonal twice. The new overlap
tests check:

  1. The four corners of each of the two layers against the other layer.
  2. The four edges of each layer against the edges of the other layer.

Unlike the old code, the new code has no early-outs in the overlap tests as those where causing
us to miss legitimate overlaps.
A new technique for breaking dependency cycles introduced by intersecting layers is implemented.
Instead of arbitrarily breaking cycles by choosing the node in the graph with the smallest number of
incoming edges (i.e. layers that need to be drawn before it) we chose the one with the smallest sum
of graph edge weights (defined as the max depth difference between two layers). Layers that intersect
have their respective graph edge weight set to zero, making them more likely to be picked for breaking
the cycles (it's not a perfect solution but it seems to perform much better than the previous one).

In addition to being overly complex and doing reduntant work, the old code was missing a
perspective divide when computing the coordinates of the layer's corners in the projected plane
which was the source of a lot of mis-sorted results.

In all, these improvements, fix a lot of outstanding issues with layer sorting, on pages such as:
​http://www.keithclark.co.uk/labs/3dcss/demo/
​http://2012.beercamp.com
​https://developer.mozilla.org/fr/demos/detail/the-box/launch

Tests: CCLayerSorter unit tests.

Reviewed by Kenneth Russell.

  • platform/graphics/chromium/cc/CCLayerSorter.cpp:

(WebCore):
(WebCore::perpProduct):
(WebCore::edgeEdgeTest):
(WebCore::CCLayerSorter::checkOverlap):
(WebCore::CCLayerSorter::LayerShape::LayerShape):
(WebCore::CCLayerSorter::LayerShape::layerZFromProjectedPoint):
(WebCore::CCLayerSorter::createGraphNodes):
(WebCore::CCLayerSorter::createGraphEdges):
(WebCore::CCLayerSorter::sort):

  • platform/graphics/chromium/cc/CCLayerSorter.h:

(WebCore::CCLayerSorter::CCLayerSorter):
(CCLayerSorter):
(LayerShape):
(WebCore::CCLayerSorter::GraphNode::GraphNode):
(GraphNode):
(WebCore::CCLayerSorter::GraphEdge::GraphEdge):
(GraphEdge):

Source/WebKit/chromium:

Adjustments to the CCLayerSorter unit tests to account for API changes in the
CCLayerSorter class.

Reviewed by Kenneth Russell.

  • tests/CCLayerSorterTest.cpp:

(WebCore):
(WebCore::TEST):

Location:
trunk/Source
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r112178 r112182  
     12012-03-26  Vangelis Kokkevis  <vangelis@chromium.org>
     2
     3        [chromium] Simplify and fix CCLayerSorter
     4        https://bugs.webkit.org/show_bug.cgi?id=82114
     5
     6        A significant cleanup, simplification and improvement of the CCLayerSorter code.
     7        Simplified the LayerShape structure to use WebCore's FloatQuad for all overlap tests.
     8        By treating every layer as two triangles, the old overlap code did a lot of redundant work
     9        including testing two of the vertices of the layer and its diagonal twice. The new overlap
     10        tests check:
     11        1. The four corners of each of the two layers against the other layer.
     12        2. The four edges of each layer against the edges of the other layer.
     13        Unlike the old code, the new code has no early-outs in the overlap tests as those where causing
     14        us to miss legitimate overlaps.
     15        A new technique for breaking dependency cycles introduced by intersecting layers is implemented.
     16        Instead of arbitrarily breaking cycles by choosing the node in the graph with the smallest number of
     17        incoming edges (i.e. layers that need to be drawn before it) we chose the one with the smallest sum
     18        of graph edge weights (defined as the max depth difference between two layers). Layers that intersect
     19        have their respective graph edge weight set to zero, making them more likely to be picked for breaking
     20        the cycles (it's not a perfect solution but it seems to perform much better than the previous one).
     21
     22        In addition to being overly complex and doing reduntant work, the old code was missing a
     23        perspective divide when computing the coordinates of the layer's corners in the projected plane
     24        which was the source of a lot of mis-sorted results.
     25
     26        In all, these improvements, fix a lot of outstanding issues with layer sorting, on pages such as:
     27        http://www.keithclark.co.uk/labs/3dcss/demo/
     28        http://2012.beercamp.com
     29        https://developer.mozilla.org/fr/demos/detail/the-box/launch
     30
     31        Tests: CCLayerSorter unit tests.
     32
     33        Reviewed by Kenneth Russell.
     34
     35        * platform/graphics/chromium/cc/CCLayerSorter.cpp:
     36        (WebCore):
     37        (WebCore::perpProduct):
     38        (WebCore::edgeEdgeTest):
     39        (WebCore::CCLayerSorter::checkOverlap):
     40        (WebCore::CCLayerSorter::LayerShape::LayerShape):
     41        (WebCore::CCLayerSorter::LayerShape::layerZFromProjectedPoint):
     42        (WebCore::CCLayerSorter::createGraphNodes):
     43        (WebCore::CCLayerSorter::createGraphEdges):
     44        (WebCore::CCLayerSorter::sort):
     45        * platform/graphics/chromium/cc/CCLayerSorter.h:
     46        (WebCore::CCLayerSorter::CCLayerSorter):
     47        (CCLayerSorter):
     48        (LayerShape):
     49        (WebCore::CCLayerSorter::GraphNode::GraphNode):
     50        (GraphNode):
     51        (WebCore::CCLayerSorter::GraphEdge::GraphEdge):
     52        (GraphEdge):
     53
    1542012-03-26  Fady Samuel  <fsamuel@chromium.org>
    255

  • trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp

    r108886 r112182  
    4747namespace WebCore {
    4848
    49 bool CCLayerSorter::pointInTriangle(const FloatPoint& point,
    50                                     const FloatPoint& a,
    51                                     const FloatPoint& b,
    52                                     const FloatPoint& c)
    53 {
    54     // Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html
    55     float x0 = c.x() - a.x();
    56     float y0 = c.y() - a.y();
    57     float x1 = b.x() - a.x();
    58     float y1 = b.y() - a.y();
    59     float x2 = point.x() - a.x();
    60     float y2 = point.y() - a.y();
    61 
    62     float dot00 = x0 * x0 + y0 * y0;
    63     float dot01 = x0 * x1 + y0 * y1;
    64     float dot02 = x0 * x2 + y0 * y2;
    65     float dot11 = x1 * x1 + y1 * y1;
    66     float dot12 = x1 * x2 + y1 * y2;
    67     float denominator = dot00 * dot11 - dot01 * dot01;
    68     if (!denominator)
    69         // Triangle is zero-area. Treat query point as not being inside.
    70         return false;
    71     // Compute
    72     float inverseDenominator = 1.0f / denominator;
    73     float u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator;
    74     float v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator;
    75 
    76     return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f);
    77 }
    78 
    7949inline static float perpProduct(const FloatSize& u, const FloatSize& v)
    8050{
    8151    return u.width() * v.height() - u.height() * v.width();
    82 }
    83 
    84 inline static float innerProduct(const FloatSize& u, const FloatSize& v)
    85 {
    86     return u.width() * v.width() + u.height() * v.height();
    87 }
    88 
    89 
    90 inline static bool pointInColinearEdge(const FloatPoint& p, const FloatPoint& a, const FloatPoint& b)
    91 {
    92     // if ab is not vertical.
    93     if (a.x() != b.x())
    94         return (p.x() >= min(a.x(), b.x()) && p.x() <= max(a.x(), b.x()));
    95 
    96     return (p.y() >= min(a.y(), b.y()) && p.y() <= max(a.y(), b.y()));
    9752}
    9853
    … …  
    10762    float denom = perpProduct(u, v);
    10863
    109     // If denom == 0 then the edges are parallel.
    110     if (!denom) {
    111         // If the edges are not colinear then there's no intersection.
    112         if (perpProduct(u, w) || perpProduct(v, w))
    113             return false;
    114 
    115         if (pointInColinearEdge(a, c, d)) {
    116             r = a;
    117             return true;
    118         }
    119         if (pointInColinearEdge(b, c, d)) {
    120             r = b;
    121             return true;
    122         }
    123         if (pointInColinearEdge(c, a, b)) {
    124             r = c;
    125             return true;
    126         }
    127         if (pointInColinearEdge(d, a, b)) {
    128             r = d;
    129             return true;
    130         }
    131 
     64    // If denom == 0 then the edges are parallel. While they could be overlapping
     65    // we don't bother to check here as the we'll find their intersections from the
     66    // corner to quad tests.
     67    if (!denom)
    13268        return false;
    133     }
     69
    13470    float s = perpProduct(v, w) / denom;
    13571    if (s < 0 || s > 1)
    … …  
    14581}
    14682
    147 float CCLayerSorter::calculateZDiff(const LayerShape& layerA, const LayerShape& layerB, float earlyExitThreshold)
    148 {
    149     LayerIntersector intersector(layerA, layerB, earlyExitThreshold);
    150     intersector.go();
    151     return intersector.zDiff;
    152 }
    153 
    154 CCLayerSorter::LayerIntersector::LayerIntersector(const LayerShape& layerA, const LayerShape& layerB, float earlyExitThreshold)
    155     : layerA(layerA)
    156     , layerB(layerB)
    157     , zDiff(0)
    158     , earlyExitThreshold(earlyExitThreshold)
    159 {
    160 }
    161 
    162 void CCLayerSorter::LayerIntersector::go()
    163 {
    164     (triangleTriangleTest(layerA.c1, layerA.c2, layerA.c3, layerB.c1, layerB.c2, layerB.c3)
    165      || triangleTriangleTest(layerA.c3, layerA.c4, layerA.c1, layerB.c1, layerB.c2, layerB.c3)
    166      || triangleTriangleTest(layerA.c1, layerA.c2, layerA.c3, layerB.c3, layerB.c4, layerB.c1)
    167      || triangleTriangleTest(layerA.c3, layerA.c4, layerA.c1, layerB.c3, layerB.c4, layerB.c1));
    168 }
    169 
    170 // Checks if segment pq intersects any of the sides of triangle abc.
    171 bool CCLayerSorter::LayerIntersector::edgeTriangleTest(const FloatPoint& p, const FloatPoint& q, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)
    172 {
     83// Checks whether layer "a" draws on top of layer "b". The weight value returned is an indication of
     84// the maximum z-depth difference between the layers or zero if the layers are found to be intesecting
     85// (some features are in front and some are behind).
     86CCLayerSorter::ABCompareResult CCLayerSorter::checkOverlap(LayerShape* a, LayerShape* b, float zThreshold, float& weight)
     87{
     88    weight = 0;
     89
     90    // Early out if the projected bounds don't overlap.
     91    if (!a->projectedBounds.intersects(b->projectedBounds))
     92        return None;
     93
     94    FloatPoint aPoints[4] = {a->projectedQuad.p1(), a->projectedQuad.p2(), a->projectedQuad.p3(), a->projectedQuad.p4() };
     95    FloatPoint bPoints[4] = {b->projectedQuad.p1(), b->projectedQuad.p2(), b->projectedQuad.p3(), b->projectedQuad.p4() };
     96
     97    // Make a list of points that inside both layer quad projections.
     98    Vector<FloatPoint> overlapPoints;
     99
     100    // Check all four corners of one layer against the other layer's quad.
     101    for (int i = 0; i < 4; ++i) {
     102        if (a->projectedQuad.containsPoint(bPoints[i]))
     103            overlapPoints.append(bPoints[i]);
     104        if (b->projectedQuad.containsPoint(aPoints[i]))
     105            overlapPoints.append(aPoints[i]);
     106    }
     107
     108    // Check all the edges of one layer for intersection with the other layer's edges.
    173109    FloatPoint r;
    174     if ((edgeEdgeTest(p, q, a, b, r) && checkZDiff(r))
    175         || (edgeEdgeTest(p, q, a, c, r) && checkZDiff(r))
    176         || (edgeEdgeTest(p, q, b, c, r) && checkZDiff(r)))
    177         return true;
    178 
    179     return false;
    180 }
    181 
    182 // Checks if two co-planar triangles intersect.
    183 bool CCLayerSorter::LayerIntersector::triangleTriangleTest(const FloatPoint& a1, const FloatPoint& b1, const FloatPoint& c1, const FloatPoint& a2, const FloatPoint& b2, const FloatPoint& c2)
    184 {
    185     // Check all edges of first triangle with edges of the second one.
    186     if (edgeTriangleTest(a1, b1, a2, b2, c2)
    187         || edgeTriangleTest(a1, c1, a2, b2, c2)
    188         || edgeTriangleTest(b1, c1, a2, b2, c2))
    189         return true;
    190 
    191     // Check all points of the first triangle for inclusion in the second triangle.
    192     if ((pointInTriangle(a1, a2, b2, c2) && checkZDiff(a1))
    193         || (pointInTriangle(b1, a2, b2, c2) && checkZDiff(b1))
    194         || (pointInTriangle(c1, a2, b2, c2) && checkZDiff(c1)))
    195         return true;
    196 
    197     // Check all points of the second triangle for inclusion in the first triangle.
    198     if ((pointInTriangle(a2, a1, b1, c1) && checkZDiff(a2))
    199         || (pointInTriangle(b2, a1, b1, c1) && checkZDiff(b2))
    200         || (pointInTriangle(c2, a1, b1, c1) && checkZDiff(c2)))
    201         return true;
    202 
    203     return false;
    204 }
    205 
    206 // Computes the z difference between point p projected onto the two layers to determine
    207 // which layer is in front. If the new z difference is higher than the currently
    208 // recorded one the this becomes the point of choice for doing the comparison between the
    209 // layers. If the value of difference is higher than our early exit threshold then
    210 // it means that the z difference is conclusive enough that we don't have to check
    211 // other intersection points.
    212 bool CCLayerSorter::LayerIntersector::checkZDiff(const FloatPoint& p)
    213 {
    214     float za = layerZFromProjectedPoint(layerA, p);
    215     float zb = layerZFromProjectedPoint(layerB, p);
    216 
    217     float diff = za - zb;
    218     float absDiff = fabsf(diff);
    219     if ((absDiff) > fabsf(zDiff)) {
    220         intersectionPoint = p;
    221         zDiff = diff;
    222     }
    223 
    224     if (absDiff > earlyExitThreshold)
    225         return true;
    226 
    227     return false;
    228 }
    229 
    230 
    231 // Returns the Z coordinate of a point on the given layer that projects
     110    for (int ea = 0; ea < 4; ++ea)
     111        for (int eb = 0; eb < 4; ++eb)
     112            if (edgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4],
     113                             bPoints[eb], bPoints[(eb + 1) % 4],
     114                             r))
     115                overlapPoints.append(r);
     116
     117    if (!overlapPoints.size())
     118        return None;
     119
     120    // Check the corresponding layer depth value for all overlap points to determine
     121    // which layer is in front.
     122    float maxPositive = 0;
     123    float maxNegative = 0;
     124    for (unsigned o = 0; o < overlapPoints.size(); o++) {
     125        float za = a->layerZFromProjectedPoint(overlapPoints[o]);
     126        float zb = b->layerZFromProjectedPoint(overlapPoints[o]);
     127
     128        float diff = za - zb;
     129        if (diff > maxPositive)
     130            maxPositive = diff;
     131        if (diff < maxNegative)
     132            maxNegative = diff;
     133    }
     134
     135    float maxDiff = (fabsf(maxPositive) > fabsf(maxNegative) ? maxPositive : maxNegative);
     136
     137    // If the results are inconsistent (and the z difference substantial to rule out
     138    // numerical errors) then the layers are intersecting. We will still return an
     139    // order based on the maximum depth difference but with an edge weight of zero
     140    // these layers will get priority if a graph cycle is present and needs to be broken.
     141    if (maxPositive > zThreshold && maxNegative < -zThreshold)
     142        weight = 0;
     143    else
     144        weight = fabsf(maxDiff);
     145
     146    // Maintain relative order if the layers have the same depth at all intersection points.
     147    if (maxDiff <= 0)
     148        return ABeforeB;
     149
     150    return BBeforeA;
     151}
     152
     153CCLayerSorter::LayerShape::LayerShape(float width, float height, const TransformationMatrix& drawTransform)
     154{
     155    FloatQuad layerQuad(FloatPoint(-width * 0.5, height * 0.5),
     156                        FloatPoint(width * 0.5, height * 0.5),
     157                        FloatPoint(width * 0.5, -height * 0.5),
     158                        FloatPoint(-width * 0.5, -height * 0.5));
     159
     160    // Compute the projection of the layer quad onto the z = 0 plane.
     161    projectedQuad = drawTransform.mapQuad(layerQuad);
     162    projectedBounds = projectedQuad.boundingBox();
     163
     164    // Compute the normal of the layer's plane.
     165    FloatPoint3D c1 = drawTransform.mapPoint(FloatPoint3D(0, 0, 0));
     166    FloatPoint3D c2 = drawTransform.mapPoint(FloatPoint3D(0, 1, 0));
     167    FloatPoint3D c3 = drawTransform.mapPoint(FloatPoint3D(1, 0, 0));
     168    FloatPoint3D c12 = c2 - c1;
     169    FloatPoint3D c13 = c3 - c1;
     170    layerNormal = c13.cross(c12);
     171
     172    transformOrigin = c1;
     173}
     174
     175// Returns the Z coordinate of a point on the layer that projects
    232176// to point p which lies on the z = 0 plane. It does it by computing the
    233177// intersection of a line starting from p along the Z axis and the plane
    234178// of the layer.
    235 float CCLayerSorter::LayerIntersector::layerZFromProjectedPoint(const LayerShape& layer, const FloatPoint& p)
     179float CCLayerSorter::LayerShape::layerZFromProjectedPoint(const FloatPoint& p) const
    236180{
    237181    const FloatPoint3D zAxis(0, 0, 1);
    238     FloatPoint3D w = FloatPoint3D(p.x(), p.y(), 0) - layer.origin;
    239 
    240     float d = layer.normal.dot(zAxis);
    241     float n = -layer.normal.dot(w);
    242 
    243     // Check if layer is parallel to the z = 0 axis
     182    FloatPoint3D w = FloatPoint3D(p) - transformOrigin;
     183
     184    float d = layerNormal.dot(zAxis);
     185    float n = -layerNormal.dot(w);
     186
     187    // Check if layer is parallel to the z = 0 axis which will make it
     188    // invisible and hence returning zero is fine.
    244189    if (!d)
    245         return layer.origin.z();
     190        return 0;
    246191
    247192    // The intersection point would be given by:
    … …  
    249194    // z coordinate and p's z coord is zero, all we need is the value of n/d.
    250195    return n / d;
    251 }
    252 
    253 CCLayerSorter::CCLayerSorter()
    254     : m_zRange(0)
    255 {
    256 }
    257 
    258 CCLayerSorter::ABCompareResult CCLayerSorter::checkOverlap(GraphNode* a, GraphNode* b)
    259 {
    260     if (!a->shape.boundingBox.intersects(b->shape.boundingBox))
    261         return None;
    262 
    263     // These thresholds are defined relative to the total Z range. If further Z-fighting
    264     // bugs come up due to precision errors, it may be worth considering doing an ulp
    265     // error measurement instead.
    266     float exitThreshold = m_zRange * 0.01;
    267     float nonZeroThreshold = max(exitThreshold, 0.001f);
    268 
    269     float zDiff = calculateZDiff(a->shape, b->shape, exitThreshold);
    270 
    271     if (zDiff > nonZeroThreshold)
    272         return BBeforeA;
    273     if (zDiff < -nonZeroThreshold)
    274         return ABeforeB;
    275 
    276     return None;
    277 }
    278 
    279 CCLayerSorter::LayerShape::LayerShape(const FloatPoint3D& p1, const FloatPoint3D& p2, const FloatPoint3D& p3, const FloatPoint3D& p4)
    280     : normal((p2 - p1).cross(p3 - p1))
    281     , c1(FloatPoint(p1.x(), p1.y()))
    282     , c2(FloatPoint(p2.x(), p2.y()))
    283     , c3(FloatPoint(p3.x(), p3.y()))
    284     , c4(FloatPoint(p4.x(), p4.y()))
    285     , origin(p1)
    286 {
    287     boundingBox.fitToPoints(c1, c2, c3, c4);
    288196}
    289197
    … …  
    310218        if (renderSurface) {
    311219            drawTransform = renderSurface->drawTransform();
    312             layerWidth = 0.5 * renderSurface->contentRect().width();
    313             layerHeight = 0.5 * renderSurface->contentRect().height();
     220            layerWidth = renderSurface->contentRect().width();
     221            layerHeight = renderSurface->contentRect().height();
    314222        } else {
    315223            drawTransform = node.layer->drawTransform();
    316             layerWidth = 0.5 * node.layer->bounds().width();
    317             layerHeight = 0.5 * node.layer->bounds().height();
     224            layerWidth = node.layer->bounds().width();
     225            layerHeight = node.layer->bounds().height();
    318226        }
    319227
    320         FloatPoint3D c1 = drawTransform.mapPoint(FloatPoint3D(-layerWidth, layerHeight, 0));
    321         FloatPoint3D c2 = drawTransform.mapPoint(FloatPoint3D(layerWidth, layerHeight, 0));
    322         FloatPoint3D c3 = drawTransform.mapPoint(FloatPoint3D(layerWidth, -layerHeight, 0));
    323         FloatPoint3D c4 = drawTransform.mapPoint(FloatPoint3D(-layerWidth, -layerHeight, 0));
    324         node.shape = LayerShape(c1, c2, c3, c4);
    325    
    326         maxZ = max(c4.z(), max(c3.z(), max(c2.z(), max(maxZ, c1.z()))));
    327         minZ = min(c4.z(), min(c3.z(), min(c2.z(), min(minZ, c1.z()))));
    328     }
    329     if (last - first)
    330         m_zRange = fabsf(maxZ - minZ);
     228        node.shape = LayerShape(layerWidth, layerHeight, drawTransform);
     229
     230        maxZ = max(maxZ, node.shape.transformOrigin.z());
     231        minZ = min(minZ, node.shape.transformOrigin.z());
     232    }
     233
     234    m_zRange = fabsf(maxZ - minZ);
    331235}
    332236
    … …  
    336240    LOG(CCLayerSorter, "Edges:\n");
    337241#endif
     242    // Fraction of the total zRange below which z differences
     243    // are not considered reliable.
     244    const float zThresholdFactor = 0.01;
     245    float zThreshold = m_zRange * zThresholdFactor;
     246
    338247    for (unsigned na = 0; na < m_nodes.size(); na++) {
    339248        GraphNode& nodeA = m_nodes[na];
    … …  
    344253            if (!nodeB.layer->drawsContent() && !nodeB.layer->renderSurface())
    345254                continue;
    346             ABCompareResult overlapResult = checkOverlap(&nodeA, &nodeB);
     255            float weight = 0;
     256            ABCompareResult overlapResult = checkOverlap(&nodeA.shape, &nodeB.shape, zThreshold, weight);
    347257            GraphNode* startNode = 0;
    348258            GraphNode* endNode = 0;
    … …  
    359269                LOG(CCLayerSorter, "%d -> %d\n", startNode->layer->debugID(), endNode->layer->debugID());
    360270#endif
    361                 m_edges.append(GraphEdge(startNode, endNode));
     271                m_edges.append(GraphEdge(startNode, endNode, weight));
    362272            }
    363273        }
    … …  
    369279        edge.from->outgoing.append(&edge);
    370280        edge.to->incoming.append(&edge);
     281        edge.to->incomingEdgeWeight += edge.weight;
    371282    }
    372283}
    … …  
    391302// Sorts the given list of layers such that they can be painted in a back-to-front
    392303// order. Sorting produces correct results for non-intersecting layers that don't have
    393 // cyclical order dependencies. Cycles and intersections are broken aribtrarily.
     304// cyclical order dependencies. Cycles and intersections are broken (somewhat) aribtrarily.
    394305// Sorting of layers is done via a topological sort of a directed graph whose nodes are
    395306// the layers themselves. An edge from node A to node B signifies that layer A needs to
    … …  
    451362                m_activeEdges.remove(outgoingEdge);
    452363                removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming);
     364                outgoingEdge->to->incomingEdgeWeight -= outgoingEdge->weight;
    453365
    454366                if (!outgoingEdge->to->incoming.size())
    … …  
    463375        // If there are still active edges but the list of nodes without incoming edges
    464376        // is empty then we have run into a cycle. Break the cycle by finding the node
    465         // with the least number incoming edges and remove them all.
    466         unsigned minIncomingEdgeCount = UINT_MAX;
     377        // with the smallest overall incoming edge weight and use it. This will favor
     378        // nodes that have zero-weight incoming edges i.e. layers that are being
     379        // occluded by a layer that intersects them.
     380        float minIncomingEdgeWeight = FLT_MAX;
    467381        GraphNode* nextNode = 0;
    468382        for (unsigned i = 0; i < m_nodes.size(); i++) {
    469             if (m_nodes[i].incoming.size() && (m_nodes[i].incoming.size() < minIncomingEdgeCount)) {
    470                 minIncomingEdgeCount = m_nodes[i].incoming.size();
     383            if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < minIncomingEdgeWeight) {
     384                minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight;
    471385                nextNode = &m_nodes[i];
    472386            }
    … …  
    481395        }
    482396        nextNode->incoming.clear();
     397        nextNode->incomingEdgeWeight = 0;
    483398        noIncomingEdgeNodeList.append(nextNode);
    484399#if !defined( NDEBUG )
    485         LOG(CCLayerSorter, "Breaking cycle by cleaning up %d edges from %d\n", minIncomingEdgeCount, nextNode->layer->debugID());
     400        LOG(CCLayerSorter, "Breaking cycle by cleaning up incoming edges from %d (weight = %f)\n", nextNode->layer->debugID(), minIncomingEdgeWeight);
    486401#endif
    487402    }

  • trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.h

    r108886 r112182  
    2727
    2828#include "FloatPoint3D.h"
     29#include "FloatQuad.h"
    2930#include "FloatRect.h"
    3031#include "cc/CCLayerImpl.h"
    … …  
    3839    WTF_MAKE_NONCOPYABLE(CCLayerSorter);
    3940public:
    40     CCLayerSorter();
     41    CCLayerSorter() : m_zRange(0) { }
    4142
    4243    typedef Vector<CCLayerImpl*> LayerList;
    … …  
    4445    void sort(LayerList::iterator first, LayerList::iterator last);
    4546
    46     // Helper methods, public for unit testing.
    47     static bool pointInTriangle(const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&);
    48 
    4947    // Holds various useful properties derived from a layer's 3D outline.
    5048    struct LayerShape {
    5149        LayerShape() { }
    52         LayerShape(const FloatPoint3D&, const FloatPoint3D&, const FloatPoint3D&, const FloatPoint3D&);
     50        LayerShape(float width, float height, const TransformationMatrix& drawTransform);
    5351
    54         FloatPoint3D normal;
    55         FloatPoint c1, c2, c3, c4;
    56         FloatPoint3D origin;
    57         FloatRect boundingBox;
     52        float layerZFromProjectedPoint(const FloatPoint&) const;
     53
     54        FloatPoint3D layerNormal;
     55        FloatPoint3D transformOrigin;
     56        FloatQuad projectedQuad;
     57        FloatRect projectedBounds;
    5858    };
    5959
    60     static float calculateZDiff(const LayerShape&, const LayerShape&, float earlyExitThreshold);
     60    enum ABCompareResult {
     61        ABeforeB,
     62        BBeforeA,
     63        None
     64    };
     65
     66    static ABCompareResult checkOverlap(LayerShape*, LayerShape*, float zThreshold, float& weight);
    6167
    6268private:
    … …  
    6470
    6571    struct GraphNode {
    66         explicit GraphNode(CCLayerImpl* cclayer) : layer(cclayer) { }
     72        explicit GraphNode(CCLayerImpl* cclayer) : layer(cclayer), incomingEdgeWeight(0) { }
    6773
    6874        CCLayerImpl* layer;
    … …  
    7076        Vector<GraphEdge*> incoming;
    7177        Vector<GraphEdge*> outgoing;
     78        float incomingEdgeWeight;
    7279    };
    7380
    7481    struct GraphEdge {
    75         GraphEdge(GraphNode* fromNode, GraphNode* toNode) : from(fromNode), to(toNode) { };
     82        GraphEdge(GraphNode* fromNode, GraphNode* toNode, float weight) : from(fromNode), to(toNode), weight(weight) { };
    7683
    7784        GraphNode* from;
    7885        GraphNode* to;
    79     };
    80 
    81     struct LayerIntersector {
    82         LayerIntersector(const LayerShape&, const LayerShape&, float);
    83 
    84         void go();
    85 
    86         float layerZFromProjectedPoint(const LayerShape&, const FloatPoint&);
    87         bool triangleTriangleTest(const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&);
    88         bool edgeTriangleTest(const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&);
    89         bool checkZDiff(const FloatPoint&);
    90 
    91         FloatPoint intersectionPoint;
    92         const LayerShape& layerA;
    93         const LayerShape& layerB;
    94         float zDiff;
    95         float earlyExitThreshold;
     86        float weight;
    9687    };
    9788
    … …  
    10596    EdgeMap m_activeEdges;
    10697
    107     float m_zDiffEpsilon;
    108 
    10998    void createGraphNodes(LayerList::iterator first, LayerList::iterator last);
    11099    void createGraphEdges();
    111100    void removeEdgeFromList(GraphEdge*, Vector<GraphEdge*>&);
    112 
    113     enum ABCompareResult {
    114         ABeforeB,
    115         BBeforeA,
    116         None
    117     };
    118     ABCompareResult checkOverlap(GraphNode*, GraphNode*);
    119101};
    120102

  • trunk/Source/WebKit/chromium/ChangeLog

    r112142 r112182  
     12012-03-26  Vangelis Kokkevis  <vangelis@chromium.org>
     2
     3        [chromium] Simplify and fix CCLayerSorter
     4        https://bugs.webkit.org/show_bug.cgi?id=82114
     5
     6        Adjustments to the CCLayerSorter unit tests to account for API changes in the
     7        CCLayerSorter class.
     8
     9        Reviewed by Kenneth Russell.
     10
     11        * tests/CCLayerSorterTest.cpp:
     12        (WebCore):
     13        (WebCore::TEST):
     14
    1152012-03-26  James Robinson  <jamesr@chromium.org>
    216

  • trunk/Source/WebKit/chromium/tests/CCLayerSorterTest.cpp

    r108886 r112182  
    3535namespace {
    3636
    37 TEST(CCLayerSorterTest, PointInTriangle)
    38 {
    39     FloatPoint a(10.0, 10.0);
    40     FloatPoint b(30.0, 10.0);
    41     FloatPoint c(20.0, 20.0);
    42 
    43     // Point in the center is in the triangle.
    44     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), a, b, c));
    45 
    46     // Permuting the corners doesn't change the result.
    47     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), a, c, b));
    48     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), b, a, c));
    49     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), b, c, a));
    50     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), c, a, b));
    51     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), c, b, a));
    52 
    53     // Points on the edges are not in the triangle.
    54     EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 10.0), a, b, c));
    55     EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(15.0, 15.0), a, b, c));
    56     EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(25.0, 15.0), a, b, c));
    57 
    58     // Points just inside the edges are in the triangle.
    59     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 10.01), a, b, c));
    60     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(15.01, 15.0), a, b, c));
    61     EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(24.99, 15.0), a, b, c));
    62 
    63     // Zero-area triangle doesn't intersect any point.
    64     EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(15.0, 10.0), a, b, FloatPoint(20.0, 10.0)));
    65 }
    66 
    67 TEST(CCLayerSorterTest, CalculateZDiff)
    68 {
    69     // This should be bigger than the range of z values used.
    70     const float threshold = 10.0;
     37// Note: In the following overlap tests, the "camera" is looking down the negative Z axis,
     38// meaning that layers with smaller z values (more negative) are further from the camera
     39// and therefore must be drawn before layers with higher z values.
     40
     41TEST(CCLayerSorterTest, BasicOverlap)
     42{
     43    CCLayerSorter::ABCompareResult overlapResult;
     44    const float zThreshold = 0.1f;
     45    float weight = 0;
    7146
    7247    // Trivial test, with one layer directly obscuring the other.
    73 
    74     CCLayerSorter::LayerShape front(
    75         FloatPoint3D(-1.0, 1.0, 5.0),
    76         FloatPoint3D(1.0, 1.0, 5.0),
    77         FloatPoint3D(1.0, -1.0, 5.0),
    78         FloatPoint3D(-1.0, -1.0, 5.0));
    79 
    80     CCLayerSorter::LayerShape back(
    81         FloatPoint3D(-1.0, 1.0, 4.0),
    82         FloatPoint3D(1.0, 1.0, 4.0),
    83         FloatPoint3D(1.0, -1.0, 4.0),
    84         FloatPoint3D(-1.0, -1.0, 4.0));
    85 
    86     EXPECT_GT(CCLayerSorter::calculateZDiff(front, back, threshold), 0.0);
    87     EXPECT_LT(CCLayerSorter::calculateZDiff(back, front, threshold), 0.0);
    88 
    89     // When comparing a layer with itself, zDiff is always 0.
    90     EXPECT_EQ(CCLayerSorter::calculateZDiff(front, front, threshold), 0.0);
    91     EXPECT_EQ(CCLayerSorter::calculateZDiff(back, back, threshold), 0.0);
    92 
    93     // Same again but with two layers that intersect only at one point (0,0).
    94     // This *does* count as obscuring, so we should get the same results.
    95 
    96     front = CCLayerSorter::LayerShape(
    97         FloatPoint3D(-1.0, 0.0, 5.0),
    98         FloatPoint3D(0.0, 0.0, 5.0),
    99         FloatPoint3D(0.0, -1.0, 5.0),
    100         FloatPoint3D(-1.0, -1.0, 5.0));
    101 
    102     back = CCLayerSorter::LayerShape(
    103         FloatPoint3D(0.0, 1.0, 4.0),
    104         FloatPoint3D(1.0, 1.0, 4.0),
    105         FloatPoint3D(1.0, 0.0, 4.0),
    106         FloatPoint3D(0.0, 0.0, 4.0));
    107 
    108     EXPECT_GT(CCLayerSorter::calculateZDiff(front, back, threshold), 0.0);
    109     EXPECT_LT(CCLayerSorter::calculateZDiff(back, front, threshold), 0.0);
    110     EXPECT_EQ(CCLayerSorter::calculateZDiff(front, front, threshold), 0.0);
    111     EXPECT_EQ(CCLayerSorter::calculateZDiff(back, back, threshold), 0.0);
     48    TransformationMatrix neg4Translate;
     49    neg4Translate.translate3d(0, 0, -4);
     50    CCLayerSorter::LayerShape front(2, 2, neg4Translate);
     51
     52    TransformationMatrix neg5Translate;
     53    neg5Translate.translate3d(0, 0, -5);
     54    CCLayerSorter::LayerShape back(2, 2, neg5Translate);
     55
     56    overlapResult = CCLayerSorter::checkOverlap(&front, &back, zThreshold, weight);
     57    EXPECT_EQ(CCLayerSorter::BBeforeA, overlapResult);
     58    EXPECT_EQ(1, weight);
     59
     60    overlapResult = CCLayerSorter::checkOverlap(&back, &front, zThreshold, weight);
     61    EXPECT_EQ(CCLayerSorter::ABeforeB, overlapResult);
     62    EXPECT_EQ(1, weight);
     63
     64    // One layer translated off to the right. No overlap should be detected.
     65    TransformationMatrix rightTranslate;
     66    rightTranslate.translate3d(10, 0, -5);
     67    CCLayerSorter::LayerShape backRight(2, 2, rightTranslate);
     68    overlapResult = CCLayerSorter::checkOverlap(&front, &backRight, zThreshold, weight);
     69    EXPECT_EQ(CCLayerSorter::None, overlapResult);
     70
     71    // When comparing a layer with itself, z difference is always 0.
     72    overlapResult = CCLayerSorter::checkOverlap(&front, &front, zThreshold, weight);
     73    EXPECT_EQ(0, weight);
     74}
     75
     76TEST(CCLayerSorterTest, RightAngleOverlap)
     77{
     78    CCLayerSorter::ABCompareResult overlapResult;
     79    const float zThreshold = 0.1f;
     80    float weight = 0;
     81
     82    TransformationMatrix perspectiveMatrix;
     83    perspectiveMatrix.applyPerspective(1000);
     84
     85    // Two layers forming a right angle with a perspective viewing transform.
     86    TransformationMatrix leftFaceMatrix;
     87    leftFaceMatrix.rotate3d(0, 1, 0, -90).translateRight3d(-1, 0, -5);
     88    CCLayerSorter::LayerShape leftFace(2, 2, perspectiveMatrix * leftFaceMatrix);
     89    TransformationMatrix frontFaceMatrix;
     90    frontFaceMatrix.translate3d(0, 0, -4);
     91    CCLayerSorter::LayerShape frontFace(2, 2, perspectiveMatrix * frontFaceMatrix);
     92
     93    overlapResult = CCLayerSorter::checkOverlap(&frontFace, &leftFace, zThreshold, weight);
     94    EXPECT_EQ(CCLayerSorter::BBeforeA, overlapResult);
     95}
     96
     97TEST(CCLayerSorterTest, IntersectingLayerOverlap)
     98{
     99    CCLayerSorter::ABCompareResult overlapResult;
     100    const float zThreshold = 0.1f;
     101    float weight = 0;
     102
     103    TransformationMatrix perspectiveMatrix;
     104    perspectiveMatrix.applyPerspective(1000);
     105
     106    // Intersecting layers. An explicit order will be returned based on relative z
     107    // values at the overlapping features but the weight returned should be zero.
     108    TransformationMatrix frontFaceMatrix;
     109    frontFaceMatrix.translate3d(0, 0, -4);
     110    CCLayerSorter::LayerShape frontFace(2, 2, perspectiveMatrix * frontFaceMatrix);
     111
     112    TransformationMatrix throughMatrix;
     113    throughMatrix.rotate3d(0, 1, 0, 45).translateRight3d(0, 0, -4);
     114    CCLayerSorter::LayerShape rotatedFace(2, 2, perspectiveMatrix * throughMatrix);
     115    overlapResult = CCLayerSorter::checkOverlap(&frontFace, &rotatedFace, zThreshold, weight);
     116    EXPECT_NE(CCLayerSorter::None, overlapResult);
     117    EXPECT_EQ(0, weight);
     118}
     119
     120TEST(CCLayerSorterTest, LayersAtAngleOverlap)
     121{
     122    CCLayerSorter::ABCompareResult overlapResult;
     123    const float zThreshold = 0.1f;
     124    float weight = 0;
    112125
    113126    // Trickier test with layers at an angle.
    … …  
    121134    //
    122135    // C is in front of A and behind B (not what you'd expect by comparing centers).
    123     // A and B don't overlap, so they're incomparable (zDiff = 0).
    124 
    125     const float yHi = 10.0;
    126     const float yLo = -10.0;
    127     const float zA = 1.0;
    128     const float zB = -1.0;
    129 
    130     CCLayerSorter::LayerShape layerA(
    131         FloatPoint3D(-10.0, yHi, zA),
    132         FloatPoint3D(-2.0, yHi, zA),
    133         FloatPoint3D(-2.0, yLo, zA),
    134         FloatPoint3D(-10.0, yLo, zA));
    135 
    136     CCLayerSorter::LayerShape layerB(
    137         FloatPoint3D(2.0, yHi, zB),
    138         FloatPoint3D(10.0, yHi, zB),
    139         FloatPoint3D(10.0, yLo, zB),
    140         FloatPoint3D(2.0, yLo, zB));
    141 
    142     CCLayerSorter::LayerShape layerC(
    143         FloatPoint3D(-5.0, yHi, 5.0),
    144         FloatPoint3D(5.0, yHi, -5.0),
    145         FloatPoint3D(5.0, yLo, -5.0),
    146         FloatPoint3D(-5.0, yLo, 5.0));
    147 
    148     EXPECT_EQ(CCLayerSorter::calculateZDiff(layerA, layerA, threshold), 0.0);
    149     EXPECT_EQ(CCLayerSorter::calculateZDiff(layerA, layerB, threshold), 0.0);
    150     EXPECT_LT(CCLayerSorter::calculateZDiff(layerA, layerC, threshold), 0.0);
    151 
    152     EXPECT_EQ(CCLayerSorter::calculateZDiff(layerB, layerA, threshold), 0.0);
    153     EXPECT_EQ(CCLayerSorter::calculateZDiff(layerB, layerB, threshold), 0.0);
    154     EXPECT_GT(CCLayerSorter::calculateZDiff(layerB, layerC, threshold), 0.0);
    155 
    156     EXPECT_GT(CCLayerSorter::calculateZDiff(layerC, layerA, threshold), 0.0);
    157     EXPECT_LT(CCLayerSorter::calculateZDiff(layerC, layerB, threshold), 0.0);
    158     EXPECT_EQ(CCLayerSorter::calculateZDiff(layerC, layerC, threshold), 0.0);
     136    // A and B don't overlap, so they're incomparable.
     137
     138    TransformationMatrix transformA;
     139    transformA.translate3d(-6, 0, 1);
     140    CCLayerSorter::LayerShape layerA(8, 20, transformA);
     141
     142    TransformationMatrix transformB;
     143    transformB.translate3d(6, 0, -1);
     144    CCLayerSorter::LayerShape layerB(8, 20, transformB);
     145
     146    TransformationMatrix transformC;
     147    transformC.rotate3d(0, 1, 0, 40);
     148    CCLayerSorter::LayerShape layerC(8, 20, transformC);
     149
     150    overlapResult = CCLayerSorter::checkOverlap(&layerA, &layerC, zThreshold, weight);
     151    EXPECT_EQ(CCLayerSorter::ABeforeB, overlapResult);
     152    overlapResult = CCLayerSorter::checkOverlap(&layerC, &layerB, zThreshold, weight);
     153    EXPECT_EQ(CCLayerSorter::ABeforeB, overlapResult);
     154    overlapResult = CCLayerSorter::checkOverlap(&layerA, &layerB, zThreshold, weight);
     155    EXPECT_EQ(CCLayerSorter::None, overlapResult);
    159156}
    160157
Note: See TracChangeset for help on using the changeset viewer.