[cc] Rename all cc/ filenames to Chromium style

cc/CCLayerSorter.cpp

Index: cc/CCLayerSorter.cpp
diff --git a/cc/CCLayerSorter.cpp b/cc/CCLayerSorter.cpp
deleted file mode 100644
index cf8577797211258877e2df9c020e41952027e814..0000000000000000000000000000000000000000
--- a/cc/CCLayerSorter.cpp
+++ /dev/null
@@ -1,445 +0,0 @@
-// Copyright 2011 The Chromium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#include "config.h"
-
-#include "CCLayerSorter.h"
-
-#include "CCMathUtil.h"
-#include "CCRenderSurface.h"
-#include <limits.h>
-#include <public/WebTransformationMatrix.h>
-#include <wtf/Deque.h>
-
-using namespace std;
-using WebKit::WebTransformationMatrix;
-
-#define LOG_CHANNEL_PREFIX Log
-#define SHOW_DEBUG_LOG 0
-
-#if !defined( NDEBUG )
-#if SHOW_DEBUG_LOG
-static WTFLogChannel LogCCLayerSorter = { 0x00000000, "", WTFLogChannelOn };
-#else
-static WTFLogChannel LogCCLayerSorter = { 0x00000000, "", WTFLogChannelOff };
-#endif
-#endif
-
-namespace cc {
-
-inline static float perpProduct(const FloatSize& u, const FloatSize& v)
-{
-    return u.width() * v.height() - u.height() * v.width();
-}
-
-// Tests if two edges defined by their endpoints (a,b) and (c,d) intersect. Returns true and the
-// point of intersection if they do and false otherwise.
-static bool edgeEdgeTest(const FloatPoint& a, const FloatPoint& b, const FloatPoint& c, const FloatPoint& d, FloatPoint& r)
-{
-    FloatSize u = b - a;
-    FloatSize v = d - c;
-    FloatSize w = a - c;
-
-    float denom = perpProduct(u, v);
-
-    // If denom == 0 then the edges are parallel. While they could be overlapping
-    // we don't bother to check here as the we'll find their intersections from the
-    // corner to quad tests.
-    if (!denom)
-        return false;
-
-    float s = perpProduct(v, w) / denom;
-    if (s < 0 || s > 1)
-        return false;
-
-    float t = perpProduct(u, w) / denom;
-    if (t < 0 || t > 1)
-        return false;
-
-    u.scale(s);
-    r = a + u;
-    return true;
-}
-
-CCLayerSorter::GraphNode::GraphNode(CCLayerImpl* cclayer)
-    : layer(cclayer)
-    , incomingEdgeWeight(0)
-{
-}
-
-CCLayerSorter::GraphNode::~GraphNode()
-{
-}
-
-CCLayerSorter::CCLayerSorter()
-    : m_zRange(0)
-{
-}
-
-CCLayerSorter::~CCLayerSorter()
-{
-}
-
-// Checks whether layer "a" draws on top of layer "b". The weight value returned is an indication of
-// the maximum z-depth difference between the layers or zero if the layers are found to be intesecting
-// (some features are in front and some are behind).
-CCLayerSorter::ABCompareResult CCLayerSorter::checkOverlap(LayerShape* a, LayerShape* b, float zThreshold, float& weight)
-{
-    weight = 0;
-
-    // Early out if the projected bounds don't overlap.
-    if (!a->projectedBounds.intersects(b->projectedBounds))
-        return None;
-
-    FloatPoint aPoints[4] = {a->projectedQuad.p1(), a->projectedQuad.p2(), a->projectedQuad.p3(), a->projectedQuad.p4() };
-    FloatPoint bPoints[4] = {b->projectedQuad.p1(), b->projectedQuad.p2(), b->projectedQuad.p3(), b->projectedQuad.p4() };
-
-    // Make a list of points that inside both layer quad projections.
-    Vector<FloatPoint> overlapPoints;
-
-    // Check all four corners of one layer against the other layer's quad.
-    for (int i = 0; i < 4; ++i) {
-        if (a->projectedQuad.containsPoint(bPoints[i]))
-            overlapPoints.append(bPoints[i]);
-        if (b->projectedQuad.containsPoint(aPoints[i]))
-            overlapPoints.append(aPoints[i]);
-    }
-
-    // Check all the edges of one layer for intersection with the other layer's edges.
-    FloatPoint r;
-    for (int ea = 0; ea < 4; ++ea)
-        for (int eb = 0; eb < 4; ++eb)
-            if (edgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4],
-                             bPoints[eb], bPoints[(eb + 1) % 4],
-                             r))
-                overlapPoints.append(r);
-
-    if (!overlapPoints.size())
-        return None;
-
-    // Check the corresponding layer depth value for all overlap points to determine
-    // which layer is in front.
-    float maxPositive = 0;
-    float maxNegative = 0;
-    for (unsigned o = 0; o < overlapPoints.size(); o++) {
-        float za = a->layerZFromProjectedPoint(overlapPoints[o]);
-        float zb = b->layerZFromProjectedPoint(overlapPoints[o]);
-
-        float diff = za - zb;
-        if (diff > maxPositive)
-            maxPositive = diff;
-        if (diff < maxNegative)
-            maxNegative = diff;
-    }
-
-    float maxDiff = (fabsf(maxPositive) > fabsf(maxNegative) ? maxPositive : maxNegative);
-
-    // If the results are inconsistent (and the z difference substantial to rule out
-    // numerical errors) then the layers are intersecting. We will still return an
-    // order based on the maximum depth difference but with an edge weight of zero
-    // these layers will get priority if a graph cycle is present and needs to be broken.
-    if (maxPositive > zThreshold && maxNegative < -zThreshold)
-        weight = 0;
-    else
-        weight = fabsf(maxDiff);
-
-    // Maintain relative order if the layers have the same depth at all intersection points.
-    if (maxDiff <= 0)
-        return ABeforeB;
-
-    return BBeforeA;
-}
-
-CCLayerSorter::LayerShape::LayerShape()
-{
-}
-
-CCLayerSorter::LayerShape::LayerShape(float width, float height, const WebTransformationMatrix& drawTransform)
-{
-    FloatQuad layerQuad(FloatRect(0, 0, width, height));
-
-    // Compute the projection of the layer quad onto the z = 0 plane.
-
-    FloatPoint clippedQuad[8];
-    int numVerticesInClippedQuad;
-    CCMathUtil::mapClippedQuad(drawTransform, layerQuad, clippedQuad, numVerticesInClippedQuad);
-
-    if (numVerticesInClippedQuad < 3) {
-        projectedBounds = FloatRect();
-        return;
-    }
-
-    projectedBounds = CCMathUtil::computeEnclosingRectOfVertices(clippedQuad, numVerticesInClippedQuad);
-
-    // NOTE: it will require very significant refactoring and overhead to deal with
-    // generalized polygons or multiple quads per layer here. For the sake of layer
-    // sorting it is equally correct to take a subsection of the polygon that can be made
-    // into a quad. This will only be incorrect in the case of intersecting layers, which
-    // are not supported yet anyway.
-    projectedQuad.setP1(clippedQuad[0]);
-    projectedQuad.setP2(clippedQuad[1]);
-    projectedQuad.setP3(clippedQuad[2]);
-    if (numVerticesInClippedQuad >= 4)
-        projectedQuad.setP4(clippedQuad[3]);
-    else
-        projectedQuad.setP4(clippedQuad[2]); // this will be a degenerate quad that is actually a triangle.
-
-    // Compute the normal of the layer's plane.
-    bool clipped = false;
-    FloatPoint3D c1 = CCMathUtil::mapPoint(drawTransform, FloatPoint3D(0, 0, 0), clipped);
-    FloatPoint3D c2 = CCMathUtil::mapPoint(drawTransform, FloatPoint3D(0, 1, 0), clipped);
-    FloatPoint3D c3 = CCMathUtil::mapPoint(drawTransform, FloatPoint3D(1, 0, 0), clipped);
-    // FIXME: Deal with clipping.
-    FloatPoint3D c12 = c2 - c1;
-    FloatPoint3D c13 = c3 - c1;
-    layerNormal = c13.cross(c12);
-
-    transformOrigin = c1;
-}
-
-// Returns the Z coordinate of a point on the layer that projects
-// 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::LayerShape::layerZFromProjectedPoint(const FloatPoint& p) const
-{
-    const FloatPoint3D zAxis(0, 0, 1);
-    FloatPoint3D w = FloatPoint3D(p) - transformOrigin;
-
-    float d = layerNormal.dot(zAxis);
-    float n = -layerNormal.dot(w);
-
-    // Check if layer is parallel to the z = 0 axis which will make it
-    // invisible and hence returning zero is fine.
-    if (!d)
-        return 0;
-
-    // The intersection point would be given by:
-    // p + (n / d) * u  but since we are only interested in the 
-    // z coordinate and p's z coord is zero, all we need is the value of n/d.
-    return n / d;
-}
-
-void CCLayerSorter::createGraphNodes(LayerList::iterator first, LayerList::iterator last)
-{
-#if !defined( NDEBUG )
-    LOG(CCLayerSorter, "Creating graph nodes:\n");
-#endif
-    float minZ = FLT_MAX;
-    float maxZ = -FLT_MAX;
-    for (LayerList::const_iterator it = first; it < last; it++) {
-        m_nodes.append(GraphNode(*it));
-        GraphNode& node = m_nodes.at(m_nodes.size() - 1);
-        CCRenderSurface* renderSurface = node.layer->renderSurface();
-        if (!node.layer->drawsContent() && !renderSurface)
-            continue;
-
-#if !defined( NDEBUG )
-        LOG(CCLayerSorter, "Layer %d (%d x %d)\n", node.layer->id(), node.layer->bounds().width(), node.layer->bounds().height());
-#endif
-
-        WebTransformationMatrix drawTransform;
-        float layerWidth, layerHeight;
-        if (renderSurface) {
-            drawTransform = renderSurface->drawTransform();
-            layerWidth = renderSurface->contentRect().width();
-            layerHeight = renderSurface->contentRect().height();
-        } else {
-            drawTransform = node.layer->drawTransform();
-            layerWidth = node.layer->contentBounds().width();
-            layerHeight = node.layer->contentBounds().height();
-        }
-
-        node.shape = LayerShape(layerWidth, layerHeight, drawTransform);
-
-        maxZ = max(maxZ, node.shape.transformOrigin.z());
-        minZ = min(minZ, node.shape.transformOrigin.z());
-    }
-
-    m_zRange = fabsf(maxZ - minZ);
-}
-
-void CCLayerSorter::createGraphEdges()
-{
-#if !defined( NDEBUG )
-    LOG(CCLayerSorter, "Edges:\n");
-#endif
-    // Fraction of the total zRange below which z differences
-    // are not considered reliable.
-    const float zThresholdFactor = 0.01f;
-    float zThreshold = m_zRange * zThresholdFactor;
-
-    for (unsigned na = 0; na < m_nodes.size(); na++) {
-        GraphNode& nodeA = m_nodes[na];
-        if (!nodeA.layer->drawsContent() && !nodeA.layer->renderSurface())
-            continue;
-        for (unsigned nb = na + 1; nb < m_nodes.size(); nb++) {
-            GraphNode& nodeB = m_nodes[nb];
-            if (!nodeB.layer->drawsContent() && !nodeB.layer->renderSurface())
-                continue;
-            float weight = 0;
-            ABCompareResult overlapResult = checkOverlap(&nodeA.shape, &nodeB.shape, zThreshold, weight);
-            GraphNode* startNode = 0;
-            GraphNode* endNode = 0;
-            if (overlapResult == ABeforeB) {
-                startNode = &nodeA;
-                endNode = &nodeB;
-            } else if (overlapResult == BBeforeA) {
-                startNode = &nodeB;
-                endNode = &nodeA;
-            }
-
-            if (startNode) {
-#if !defined( NDEBUG )
-                LOG(CCLayerSorter, "%d -> %d\n", startNode->layer->id(), endNode->layer->id());
-#endif
-                m_edges.append(GraphEdge(startNode, endNode, weight));
-            }
-        }
-    }
-
-    for (unsigned i = 0; i < m_edges.size(); i++) {
-        GraphEdge& edge = m_edges[i];
-        m_activeEdges.add(&edge, &edge);
-        edge.from->outgoing.append(&edge);
-        edge.to->incoming.append(&edge);
-        edge.to->incomingEdgeWeight += edge.weight;
-    }
-}
-
-// Finds and removes an edge from the list by doing a swap with the
-// last element of the list.
-void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, Vector<GraphEdge*>& list)
-{
-    size_t edgeIndex = list.find(edge);
-    ASSERT(edgeIndex != notFound);
-    if (list.size() == 1) {
-        ASSERT(!edgeIndex);
-        list.clear();
-        return;
-    }
-    if (edgeIndex != list.size() - 1)
-        list[edgeIndex] = list[list.size() - 1];
-
-    list.removeLast();
-}
-
-// Sorts the given list of layers such that they can be painted in a back-to-front
-// order. Sorting produces correct results for non-intersecting layers that don't have
-// cyclical order dependencies. Cycles and intersections are broken (somewhat) aribtrarily.
-// Sorting of layers is done via a topological sort of a directed graph whose nodes are
-// the layers themselves. An edge from node A to node B signifies that layer A needs to
-// be drawn before layer B. If A and B have no dependency between each other, then we
-// preserve the ordering of those layers as they were in the original list.
-//
-// The draw order between two layers is determined by projecting the two triangles making
-// up each layer quad to the Z = 0 plane, finding points of intersection between the triangles
-// and backprojecting those points to the plane of the layer to determine the corresponding Z
-// coordinate. The layer with the lower Z coordinate (farther from the eye) needs to be rendered
-// first.
-//
-// If the layer projections don't intersect, then no edges (dependencies) are created
-// between them in the graph. HOWEVER, in this case we still need to preserve the ordering
-// of the original list of layers, since that list should already have proper z-index
-// ordering of layers.
-//
-void CCLayerSorter::sort(LayerList::iterator first, LayerList::iterator last)
-{
-#if !defined( NDEBUG )
-    LOG(CCLayerSorter, "Sorting start ----\n");
-#endif
-    createGraphNodes(first, last);
-
-    createGraphEdges();
-
-    Vector<GraphNode*> sortedList;
-    Deque<GraphNode*> noIncomingEdgeNodeList;
-
-    // Find all the nodes that don't have incoming edges.
-    for (NodeList::iterator la = m_nodes.begin(); la < m_nodes.end(); la++) {
-        if (!la->incoming.size())
-            noIncomingEdgeNodeList.append(la);
-    }
-
-#if !defined( NDEBUG )
-    LOG(CCLayerSorter, "Sorted list: ");
-#endif
-    while (m_activeEdges.size() || noIncomingEdgeNodeList.size()) {
-        while (noIncomingEdgeNodeList.size()) {
-
-            // It is necessary to preserve the existing ordering of layers, when there are
-            // no explicit dependencies (because this existing ordering has correct
-            // z-index/layout ordering). To preserve this ordering, we process Nodes in
-            // the same order that they were added to the list.
-            GraphNode* fromNode = noIncomingEdgeNodeList.takeFirst();
-
-            // Add it to the final list.
-            sortedList.append(fromNode);
-
-#if !defined( NDEBUG )
-            LOG(CCLayerSorter, "%d, ", fromNode->layer->id());
-#endif
-
-            // Remove all its outgoing edges from the graph.
-            for (unsigned i = 0; i < fromNode->outgoing.size(); i++) {
-                GraphEdge* outgoingEdge = fromNode->outgoing[i];
-
-                m_activeEdges.remove(outgoingEdge);
-                removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming);
-                outgoingEdge->to->incomingEdgeWeight -= outgoingEdge->weight;
-
-                if (!outgoingEdge->to->incoming.size())
-                    noIncomingEdgeNodeList.append(outgoingEdge->to);
-            }
-            fromNode->outgoing.clear();
-        }
-
-        if (!m_activeEdges.size())
-            break;
-
-        // If there are still active edges but the list of nodes without incoming edges
-        // is empty then we have run into a cycle. Break the cycle by finding the node
-        // with the smallest overall incoming edge weight and use it. This will favor
-        // nodes that have zero-weight incoming edges i.e. layers that are being
-        // occluded by a layer that intersects them.
-        float minIncomingEdgeWeight = FLT_MAX;
-        GraphNode* nextNode = 0;
-        for (unsigned i = 0; i < m_nodes.size(); i++) {
-            if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < minIncomingEdgeWeight) {
-                minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight;
-                nextNode = &m_nodes[i];
-            }
-        }
-        ASSERT(nextNode);
-        // Remove all its incoming edges.
-        for (unsigned e = 0; e < nextNode->incoming.size(); e++) {
-            GraphEdge* incomingEdge = nextNode->incoming[e];
-
-            m_activeEdges.remove(incomingEdge);
-            removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing);
-        }
-        nextNode->incoming.clear();
-        nextNode->incomingEdgeWeight = 0;
-        noIncomingEdgeNodeList.append(nextNode);
-#if !defined( NDEBUG )
-        LOG(CCLayerSorter, "Breaking cycle by cleaning up incoming edges from %d (weight = %f)\n", nextNode->layer->id(), minIncomingEdgeWeight);
-#endif
-    }
-
-    // Note: The original elements of the list are in no danger of having their ref count go to zero
-    // here as they are all nodes of the layer hierarchy and are kept alive by their parent nodes.
-    int count = 0;
-    for (LayerList::iterator it = first; it < last; it++)
-        *it = sortedList[count++]->layer;
-
-#if !defined( NDEBUG )
-    LOG(CCLayerSorter, "Sorting end ----\n");
-#endif
-
-    m_nodes.clear();
-    m_edges.clear();
-    m_activeEdges.clear();
-}
-
-}