Modified: trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp (96336 => 96337)
--- trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp 2011-09-29 17:04:20 UTC (rev 96336)
+++ trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp 2011-09-29 17:05:41 UTC (rev 96337)
@@ -45,10 +45,10 @@
namespace WebCore {
-static bool pointInTriangle(const FloatPoint& point,
- const FloatPoint& a,
- const FloatPoint& b,
- const FloatPoint& c)
+bool CCLayerSorter::pointInTriangle(const FloatPoint& point,
+ const FloatPoint& a,
+ const FloatPoint& b,
+ const FloatPoint& c)
{
// Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html
float x0 = c.x() - a.x();
@@ -143,9 +143,16 @@
return true;
}
-CCLayerSorter::LayerIntersector::LayerIntersector(GraphNode* nodeA, GraphNode* nodeB, float earlyExitThreshold)
- : nodeA(nodeA)
- , nodeB(nodeB)
+float CCLayerSorter::calculateZDiff(const LayerShape& layerA, const LayerShape& layerB, float earlyExitThreshold)
+{
+ LayerIntersector intersector(layerA, layerB, earlyExitThreshold);
+ intersector.go();
+ return intersector.zDiff;
+}
+
+CCLayerSorter::LayerIntersector::LayerIntersector(const LayerShape& layerA, const LayerShape& layerB, float earlyExitThreshold)
+ : layerA(layerA)
+ , layerB(layerB)
, zDiff(0)
, earlyExitThreshold(earlyExitThreshold)
{
@@ -153,13 +160,12 @@
void CCLayerSorter::LayerIntersector::go()
{
- (triangleTriangleTest(nodeA->c1, nodeA->c2, nodeA->c3, nodeB->c1, nodeB->c2, nodeB->c3)
- || triangleTriangleTest(nodeA->c3, nodeA->c4, nodeA->c1, nodeB->c1, nodeB->c2, nodeB->c3)
- || triangleTriangleTest(nodeA->c1, nodeA->c2, nodeA->c3, nodeB->c3, nodeB->c4, nodeB->c1)
- || triangleTriangleTest(nodeA->c3, nodeA->c4, nodeA->c1, nodeB->c3, nodeB->c4, nodeB->c1));
+ (triangleTriangleTest(layerA.c1, layerA.c2, layerA.c3, layerB.c1, layerB.c2, layerB.c3)
+ || triangleTriangleTest(layerA.c3, layerA.c4, layerA.c1, layerB.c1, layerB.c2, layerB.c3)
+ || triangleTriangleTest(layerA.c1, layerA.c2, layerA.c3, layerB.c3, layerB.c4, layerB.c1)
+ || triangleTriangleTest(layerA.c3, layerA.c4, layerA.c1, layerB.c3, layerB.c4, layerB.c1));
}
-
// Checks if segment pq intersects any of the sides of triangle abc.
bool CCLayerSorter::LayerIntersector::edgeTriangleTest(const FloatPoint& p, const FloatPoint& q, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)
{
@@ -204,8 +210,8 @@
// other intersection points.
bool CCLayerSorter::LayerIntersector::checkZDiff(const FloatPoint& p)
{
- float za = layerZFromProjectedPoint(nodeA, p);
- float zb = layerZFromProjectedPoint(nodeB, p);
+ float za = layerZFromProjectedPoint(layerA, p);
+ float zb = layerZFromProjectedPoint(layerB, p);
float diff = za - zb;
float absDiff = fabsf(diff);
@@ -225,17 +231,17 @@
// to point p which lies on the z = 0 plane. It does it by computing the
// intersection of a line starting from p along the Z axis and the plane
// of the layer.
-float CCLayerSorter::LayerIntersector::layerZFromProjectedPoint(GraphNode* layer, const FloatPoint& p)
+float CCLayerSorter::LayerIntersector::layerZFromProjectedPoint(const LayerShape& layer, const FloatPoint& p)
{
const FloatPoint3D zAxis(0, 0, 1);
- FloatPoint3D w = FloatPoint3D(p.x(), p.y(), 0) - layer->origin;
+ FloatPoint3D w = FloatPoint3D(p.x(), p.y(), 0) - layer.origin;
- float d = layer->normal.dot(zAxis);
- float n = -layer->normal.dot(w);
+ float d = layer.normal.dot(zAxis);
+ float n = -layer.normal.dot(w);
// Check if layer is parallel to the z = 0 axis
if (!d)
- return layer->origin.z();
+ return layer.origin.z();
// The intersection point would be given by:
// p + (n / d) * u but since we are only interested in the
@@ -243,7 +249,6 @@
return n / d;
}
-
CCLayerSorter::CCLayerSorter()
: m_zRange(0)
{
@@ -251,23 +256,32 @@
CCLayerSorter::ABCompareResult CCLayerSorter::checkOverlap(GraphNode* a, GraphNode* b)
{
- if (!a->boundingBox.intersects(b->boundingBox))
+ if (!a->shape.boundingBox.intersects(b->shape.boundingBox))
return None;
// Make the early exit threshold proportional to the total Z range.
float exitThreshold = m_zRange * 0.01;
+ float zDiff = calculateZDiff(a->shape, b->shape, exitThreshold);
- LayerIntersector intersector(a, b, exitThreshold);
- intersector.go();
-
- if (intersector.zDiff > 0)
+ if (zDiff > 0)
return BBeforeA;
- if (intersector.zDiff < 0)
+ if (zDiff < 0)
return ABeforeB;
return None;
}
+CCLayerSorter::LayerShape::LayerShape(const FloatPoint3D& p1, const FloatPoint3D& p2, const FloatPoint3D& p3, const FloatPoint3D& p4)
+ : normal((p2 - p1).cross(p3 - p1))
+ , c1(FloatPoint(p1.x(), p1.y()))
+ , c2(FloatPoint(p2.x(), p2.y()))
+ , c3(FloatPoint(p3.x(), p3.y()))
+ , c4(FloatPoint(p4.x(), p4.y()))
+ , origin(p1)
+{
+ boundingBox.fitToPoints(c1, c2, c3, c4);
+}
+
void CCLayerSorter::createGraphNodes(LayerList::iterator first, LayerList::iterator last)
{
#if !defined( NDEBUG )
@@ -302,13 +316,7 @@
FloatPoint3D c2 = drawTransform.mapPoint(FloatPoint3D(layerWidth, layerHeight, 0));
FloatPoint3D c3 = drawTransform.mapPoint(FloatPoint3D(layerWidth, -layerHeight, 0));
FloatPoint3D c4 = drawTransform.mapPoint(FloatPoint3D(-layerWidth, -layerHeight, 0));
- node.normal = (c2 - c1).cross(c3 - c1);
- node.c1 = FloatPoint(c1.x(), c1.y());
- node.c2 = FloatPoint(c2.x(), c2.y());
- node.c3 = FloatPoint(c3.x(), c3.y());
- node.c4 = FloatPoint(c4.x(), c4.y());
- node.origin = c1;
- node.boundingBox.fitToPoints(node.c1, node.c2, node.c3, node.c4);
+ node.shape = LayerShape(c1, c2, c3, c4);
maxZ = max(c4.z(), max(c3.z(), max(c2.z(), max(maxZ, c1.z()))));
minZ = min(c4.z(), min(c3.z(), min(c2.z(), min(minZ, c1.z()))));
Modified: trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.h (96336 => 96337)
--- trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.h 2011-09-29 17:04:20 UTC (rev 96336)
+++ trunk/Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.h 2011-09-29 17:05:41 UTC (rev 96337)
@@ -42,16 +42,31 @@
typedef Vector<RefPtr<CCLayerImpl> > LayerList;
void sort(LayerList::iterator first, LayerList::iterator last);
+
+ // Helper methods, public for unit testing.
+ static bool pointInTriangle(const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&);
+
+ // Holds various useful properties derived from a layer's 3D outline.
+ struct LayerShape {
+ LayerShape() { }
+ LayerShape(const FloatPoint3D&, const FloatPoint3D&, const FloatPoint3D&, const FloatPoint3D&);
+
+ FloatPoint3D normal;
+ FloatPoint c1, c2, c3, c4;
+ FloatPoint3D origin;
+ FloatRect boundingBox;
+ };
+
+ static float calculateZDiff(const LayerShape&, const LayerShape&, float earlyExitThreshold);
+
private:
struct GraphEdge;
struct GraphNode {
- GraphNode(CCLayerImpl* cclayer) : layer(cclayer) { };
+ explicit GraphNode(CCLayerImpl* cclayer) : layer(cclayer) { }
+
CCLayerImpl* layer;
- FloatPoint c1, c2, c3, c4;
- FloatPoint3D normal;
- FloatPoint3D origin;
- FloatRect boundingBox;
+ LayerShape shape;
Vector<GraphEdge*> incoming;
Vector<GraphEdge*> outgoing;
};
@@ -64,18 +79,18 @@
};
struct LayerIntersector {
- LayerIntersector(GraphNode*, GraphNode*, float);
+ LayerIntersector(const LayerShape&, const LayerShape&, float);
void go();
- float layerZFromProjectedPoint(GraphNode*, const FloatPoint&);
+ float layerZFromProjectedPoint(const LayerShape&, const FloatPoint&);
bool triangleTriangleTest(const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&);
bool edgeTriangleTest(const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&, const FloatPoint&);
bool checkZDiff(const FloatPoint&);
FloatPoint intersectionPoint;
- GraphNode* nodeA;
- GraphNode* nodeB;
+ const LayerShape& layerA;
+ const LayerShape& layerB;
float zDiff;
float earlyExitThreshold;
};
Added: trunk/Source/WebKit/chromium/tests/CCLayerSorterTest.cpp (0 => 96337)
--- trunk/Source/WebKit/chromium/tests/CCLayerSorterTest.cpp (rev 0)
+++ trunk/Source/WebKit/chromium/tests/CCLayerSorterTest.cpp 2011-09-29 17:05:41 UTC (rev 96337)
@@ -0,0 +1,159 @@
+/*
+ * Copyright (C) 2011 Google Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include "cc/CCLayerSorter.h"
+
+#include <gtest/gtest.h>
+
+using namespace WebCore;
+
+namespace {
+
+TEST(CCLayerSorterTest, PointInTriangle)
+{
+ FloatPoint a(10.0, 10.0);
+ FloatPoint b(30.0, 10.0);
+ FloatPoint c(20.0, 20.0);
+
+ // Point in the center is in the triangle.
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), a, b, c));
+
+ // Permuting the corners doesn't change the result.
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), a, c, b));
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), b, a, c));
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), b, c, a));
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), c, a, b));
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 15.0), c, b, a));
+
+ // Points on the edges are not in the triangle.
+ EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 10.0), a, b, c));
+ EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(15.0, 15.0), a, b, c));
+ EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(25.0, 15.0), a, b, c));
+
+ // Points just inside the edges are in the triangle.
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(20.0, 10.01), a, b, c));
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(15.01, 15.0), a, b, c));
+ EXPECT_TRUE(CCLayerSorter::pointInTriangle(FloatPoint(24.99, 15.0), a, b, c));
+
+ // Zero-area triangle doesn't intersect any point.
+ EXPECT_FALSE(CCLayerSorter::pointInTriangle(FloatPoint(15.0, 10.0), a, b, FloatPoint(20.0, 10.0)));
+}
+
+TEST(CCLayerSorterTest, CalculateZDiff)
+{
+ // This should be bigger than the range of z values used.
+ const float threshold = 10.0;
+
+ // Trivial test, with one layer directly obscuring the other.
+
+ CCLayerSorter::LayerShape front(
+ FloatPoint3D(-1.0, 1.0, 5.0),
+ FloatPoint3D(1.0, 1.0, 5.0),
+ FloatPoint3D(1.0, -1.0, 5.0),
+ FloatPoint3D(-1.0, -1.0, 5.0));
+
+ CCLayerSorter::LayerShape back(
+ FloatPoint3D(-1.0, 1.0, 4.0),
+ FloatPoint3D(1.0, 1.0, 4.0),
+ FloatPoint3D(1.0, -1.0, 4.0),
+ FloatPoint3D(-1.0, -1.0, 4.0));
+
+ EXPECT_GT(CCLayerSorter::calculateZDiff(front, back, threshold), 0.0);
+ EXPECT_LT(CCLayerSorter::calculateZDiff(back, front, threshold), 0.0);
+
+ // When comparing a layer with itself, zDiff is always 0.
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(front, front, threshold), 0.0);
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(back, back, threshold), 0.0);
+
+ // Same again but with two layers that intersect only at one point (0,0).
+ // This *does* count as obscuring, so we should get the same results.
+
+ front = CCLayerSorter::LayerShape(
+ FloatPoint3D(-1.0, 0.0, 5.0),
+ FloatPoint3D(0.0, 0.0, 5.0),
+ FloatPoint3D(0.0, -1.0, 5.0),
+ FloatPoint3D(-1.0, -1.0, 5.0));
+
+ back = CCLayerSorter::LayerShape(
+ FloatPoint3D(0.0, 1.0, 4.0),
+ FloatPoint3D(1.0, 1.0, 4.0),
+ FloatPoint3D(1.0, 0.0, 4.0),
+ FloatPoint3D(0.0, 0.0, 4.0));
+
+ EXPECT_GT(CCLayerSorter::calculateZDiff(front, back, threshold), 0.0);
+ EXPECT_LT(CCLayerSorter::calculateZDiff(back, front, threshold), 0.0);
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(front, front, threshold), 0.0);
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(back, back, threshold), 0.0);
+
+ // Trickier test with layers at an angle.
+ //
+ // -x . . . . 0 . . . . +x
+ // -z /
+ // : /----B----
+ // 0 C
+ // : ----A----/
+ // +z /
+ //
+ // C is in front of A and behind B (not what you'd expect by comparing centers).
+ // A and B don't overlap, so they're incomparable (zDiff = 0).
+
+ const float yHi = 10.0;
+ const float yLo = -10.0;
+ const float zA = 1.0;
+ const float zB = -1.0;
+
+ CCLayerSorter::LayerShape layerA(
+ FloatPoint3D(-10.0, yHi, zA),
+ FloatPoint3D(-2.0, yHi, zA),
+ FloatPoint3D(-2.0, yLo, zA),
+ FloatPoint3D(-10.0, yLo, zA));
+
+ CCLayerSorter::LayerShape layerB(
+ FloatPoint3D(2.0, yHi, zB),
+ FloatPoint3D(10.0, yHi, zB),
+ FloatPoint3D(10.0, yLo, zB),
+ FloatPoint3D(2.0, yLo, zB));
+
+ CCLayerSorter::LayerShape layerC(
+ FloatPoint3D(-5.0, yHi, 5.0),
+ FloatPoint3D(5.0, yHi, -5.0),
+ FloatPoint3D(5.0, yLo, -5.0),
+ FloatPoint3D(-5.0, yLo, 5.0));
+
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(layerA, layerA, threshold), 0.0);
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(layerA, layerB, threshold), 0.0);
+ EXPECT_LT(CCLayerSorter::calculateZDiff(layerA, layerC, threshold), 0.0);
+
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(layerB, layerA, threshold), 0.0);
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(layerB, layerB, threshold), 0.0);
+ EXPECT_GT(CCLayerSorter::calculateZDiff(layerB, layerC, threshold), 0.0);
+
+ EXPECT_GT(CCLayerSorter::calculateZDiff(layerC, layerA, threshold), 0.0);
+ EXPECT_LT(CCLayerSorter::calculateZDiff(layerC, layerB, threshold), 0.0);
+ EXPECT_EQ(CCLayerSorter::calculateZDiff(layerC, layerC, threshold), 0.0);
+}
+
+} // namespace
