Splitting of layers for correct intersections

cc/trees/layer_sorter.cc

Index: cc/trees/layer_sorter.cc
diff --git a/cc/trees/layer_sorter.cc b/cc/trees/layer_sorter.cc
deleted file mode 100644
index bde49201f4e717c74e01808b677c37b005cafc4c..0000000000000000000000000000000000000000
--- a/cc/trees/layer_sorter.cc
+++ /dev/null
@@ -1,470 +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 "cc/trees/layer_sorter.h"
-
-#include <algorithm>
-#include <deque>
-#include <limits>
-#include <vector>
-
-#include "base/logging.h"
-#include "cc/base/math_util.h"
-#include "cc/layers/render_surface_impl.h"
-#include "ui/gfx/transform.h"
-
-namespace cc {
-
-// This epsilon is used to determine if two layers are too close to each other
-// to be able to tell which is in front of the other.  It's a relative epsilon
-// so it is robust to changes in scene scale.  This value was chosen by picking
-// a value near machine epsilon and then increasing it until the flickering on
-// the test scene went away.
-const float k_layer_epsilon = 1e-4f;
-
-inline static float PerpProduct(const gfx::Vector2dF& u,
-                                const gfx::Vector2dF& v) {
-  return u.x() * v.y() - u.y() * v.x();
-}
-
-// 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 gfx::PointF& a,
-                         const gfx::PointF& b,
-                         const gfx::PointF& c,
-                         const gfx::PointF& d,
-                         gfx::PointF* r) {
-  gfx::Vector2dF u = b - a;
-  gfx::Vector2dF v = d - c;
-  gfx::Vector2dF 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.f || s > 1.f)
-    return false;
-
-  float t = PerpProduct(u, w) / denom;
-  if (t < 0.f || t > 1.f)
-    return false;
-
-  u.Scale(s);
-  *r = a + u;
-  return true;
-}
-
-GraphNode::GraphNode(LayerImpl* layer_impl)
-    : layer(layer_impl),
-      incoming_edge_weight(0.f) {}
-
-GraphNode::~GraphNode() {}
-
-LayerSorter::LayerSorter()
-    : z_range_(0.f) {}
-
-LayerSorter::~LayerSorter() {}
-
-static float CheckFloatingPointNumericAccuracy(float a, float b) {
-  float abs_dif = std::abs(b - a);
-  float abs_max = std::max(std::abs(b), std::abs(a));
-  // Check to see if we've got a result with a reasonable amount of error.
-  return abs_dif / abs_max;
-}
-
-// 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).
-LayerSorter::ABCompareResult LayerSorter::CheckOverlap(LayerShape* a,
-                                                       LayerShape* b,
-                                                       float z_threshold,
-                                                       float* weight) {
-  *weight = 0.f;
-
-  // Early out if the projected bounds don't overlap.
-  if (!a->projected_bounds.Intersects(b->projected_bounds))
-    return NONE;
-
-  gfx::PointF aPoints[4] = { a->projected_quad.p1(),
-                             a->projected_quad.p2(),
-                             a->projected_quad.p3(),
-                             a->projected_quad.p4() };
-  gfx::PointF bPoints[4] = { b->projected_quad.p1(),
-                             b->projected_quad.p2(),
-                             b->projected_quad.p3(),
-                             b->projected_quad.p4() };
-
-  // Make a list of points that inside both layer quad projections.
-  std::vector<gfx::PointF> overlap_points;
-
-  // Check all four corners of one layer against the other layer's quad.
-  for (int i = 0; i < 4; ++i) {
-    if (a->projected_quad.Contains(bPoints[i]))
-      overlap_points.push_back(bPoints[i]);
-    if (b->projected_quad.Contains(aPoints[i]))
-      overlap_points.push_back(aPoints[i]);
-  }
-
-  // Check all the edges of one layer for intersection with the other layer's
-  // edges.
-  gfx::PointF 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))
-        overlap_points.push_back(r);
-
-  if (overlap_points.empty())
-    return NONE;
-
-  // Check the corresponding layer depth value for all overlap points to
-  // determine which layer is in front.
-  float max_positive = 0.f;
-  float max_negative = 0.f;
-
-  // This flag tracks the existance of a numerically accurate seperation
-  // between two layers.  If there is no accurate seperation, the layers
-  // cannot be effectively sorted.
-  bool accurate = false;
-
-  for (size_t o = 0; o < overlap_points.size(); o++) {
-    float za = a->LayerZFromProjectedPoint(overlap_points[o]);
-    float zb = b->LayerZFromProjectedPoint(overlap_points[o]);
-
-    // Here we attempt to avoid numeric issues with layers that are too
-    // close together.  If we have 2-sided quads that are very close
-    // together then we will draw them in document order to avoid
-    // flickering.  The correct solution is for the content maker to turn
-    // on back-face culling or move the quads apart (if they're not two
-    // sides of one object).
-    if (CheckFloatingPointNumericAccuracy(za, zb) > k_layer_epsilon)
-      accurate = true;
-
-    float diff = za - zb;
-    if (diff > max_positive)
-      max_positive = diff;
-    if (diff < max_negative)
-      max_negative = diff;
-  }
-
-  // If we can't tell which should come first, we use document order.
-  if (!accurate)
-    return A_BEFORE_B;
-
-  float max_diff =
-      std::abs(max_positive) > std::abs(max_negative) ?
-          max_positive : max_negative;
-
-  // 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 (max_positive > z_threshold && max_negative < -z_threshold)
-    *weight = 0.f;
-  else
-    *weight = std::abs(max_diff);
-
-  // Maintain relative order if the layers have the same depth at all
-  // intersection points.
-  if (max_diff <= 0.f)
-    return A_BEFORE_B;
-
-  return B_BEFORE_A;
-}
-
-LayerShape::LayerShape() {}
-
-LayerShape::LayerShape(float width,
-                       float height,
-                       const gfx::Transform& draw_transform) {
-  gfx::QuadF layer_quad(gfx::RectF(0.f, 0.f, width, height));
-
-  // Compute the projection of the layer quad onto the z = 0 plane.
-
-  gfx::PointF clipped_quad[8];
-  int num_vertices_in_clipped_quad;
-  MathUtil::MapClippedQuad(draw_transform,
-                           layer_quad,
-                           clipped_quad,
-                           &num_vertices_in_clipped_quad);
-
-  if (num_vertices_in_clipped_quad < 3) {
-    projected_bounds = gfx::RectF();
-    return;
-  }
-
-  projected_bounds =
-      MathUtil::ComputeEnclosingRectOfVertices(clipped_quad,
-                                               num_vertices_in_clipped_quad);
-
-  // 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.
-  projected_quad.set_p1(clipped_quad[0]);
-  projected_quad.set_p2(clipped_quad[1]);
-  projected_quad.set_p3(clipped_quad[2]);
-  if (num_vertices_in_clipped_quad >= 4) {
-    projected_quad.set_p4(clipped_quad[3]);
-  } else {
-    // This will be a degenerate quad that is actually a triangle.
-    projected_quad.set_p4(clipped_quad[2]);
-  }
-
-  // Compute the normal of the layer's plane.
-  bool clipped = false;
-  gfx::Point3F c1 =
-      MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 0.f, 0.f), &clipped);
-  gfx::Point3F c2 =
-      MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 1.f, 0.f), &clipped);
-  gfx::Point3F c3 =
-      MathUtil::MapPoint(draw_transform, gfx::Point3F(1.f, 0.f, 0.f), &clipped);
-  // TODO(shawnsingh): Deal with clipping.
-  gfx::Vector3dF c12 = c2 - c1;
-  gfx::Vector3dF c13 = c3 - c1;
-  layer_normal = gfx::CrossProduct(c13, c12);
-
-  transform_origin = c1;
-}
-
-LayerShape::~LayerShape() {}
-
-// 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 LayerShape::LayerZFromProjectedPoint(const gfx::PointF& p) const {
-  gfx::Vector3dF z_axis(0.f, 0.f, 1.f);
-  gfx::Vector3dF w = gfx::Point3F(p) - transform_origin;
-
-  float d = gfx::DotProduct(layer_normal, z_axis);
-  float n = -gfx::DotProduct(layer_normal, 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.f;
-
-  // 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 LayerSorter::CreateGraphNodes(LayerImplList::iterator first,
-                                   LayerImplList::iterator last) {
-  DVLOG(2) << "Creating graph nodes:";
-  float min_z = FLT_MAX;
-  float max_z = -FLT_MAX;
-  for (LayerImplList::const_iterator it = first; it < last; it++) {
-    nodes_.push_back(GraphNode(*it));
-    GraphNode& node = nodes_.at(nodes_.size() - 1);
-    RenderSurfaceImpl* render_surface = node.layer->render_surface();
-    if (!node.layer->DrawsContent() && !render_surface)
-      continue;
-
-    DVLOG(2) << "Layer " << node.layer->id() <<
-        " (" << node.layer->bounds().width() <<
-        " x " << node.layer->bounds().height() << ")";
-
-    gfx::Transform draw_transform;
-    float layer_width, layer_height;
-    if (render_surface) {
-      draw_transform = render_surface->draw_transform();
-      layer_width = render_surface->content_rect().width();
-      layer_height = render_surface->content_rect().height();
-    } else {
-      draw_transform = node.layer->draw_transform();
-      layer_width = node.layer->content_bounds().width();
-      layer_height = node.layer->content_bounds().height();
-    }
-
-    node.shape = LayerShape(layer_width, layer_height, draw_transform);
-
-    max_z = std::max(max_z, node.shape.transform_origin.z());
-    min_z = std::min(min_z, node.shape.transform_origin.z());
-  }
-
-  z_range_ = std::abs(max_z - min_z);
-}
-
-void LayerSorter::CreateGraphEdges() {
-  DVLOG(2) << "Edges:";
-  // Fraction of the total z_range below which z differences
-  // are not considered reliable.
-  const float z_threshold_factor = 0.01f;
-  float z_threshold = z_range_ * z_threshold_factor;
-
-  for (size_t na = 0; na < nodes_.size(); na++) {
-    GraphNode& node_a = nodes_[na];
-    if (!node_a.layer->DrawsContent() && !node_a.layer->render_surface())
-      continue;
-    for (size_t nb = na + 1; nb < nodes_.size(); nb++) {
-      GraphNode& node_b = nodes_[nb];
-      if (!node_b.layer->DrawsContent() && !node_b.layer->render_surface())
-        continue;
-      float weight = 0.f;
-      ABCompareResult overlap_result = CheckOverlap(&node_a.shape,
-                                                    &node_b.shape,
-                                                    z_threshold,
-                                                    &weight);
-      GraphNode* start_node = NULL;
-      GraphNode* end_node = NULL;
-      if (overlap_result == A_BEFORE_B) {
-        start_node = &node_a;
-        end_node = &node_b;
-      } else if (overlap_result == B_BEFORE_A) {
-        start_node = &node_b;
-        end_node = &node_a;
-      }
-
-      if (start_node) {
-        DVLOG(2) << start_node->layer->id() << " -> " << end_node->layer->id();
-        edges_.push_back(GraphEdge(start_node, end_node, weight));
-      }
-    }
-  }
-
-  for (size_t i = 0; i < edges_.size(); i++) {
-    GraphEdge& edge = edges_[i];
-    active_edges_[&edge] = &edge;
-    edge.from->outgoing.push_back(&edge);
-    edge.to->incoming.push_back(&edge);
-    edge.to->incoming_edge_weight += edge.weight;
-  }
-}
-
-// Finds and removes an edge from the list by doing a swap with the
-// last element of the list.
-void LayerSorter::RemoveEdgeFromList(GraphEdge* edge,
-                                     std::vector<GraphEdge*>* list) {
-  std::vector<GraphEdge*>::iterator iter =
-      std::find(list->begin(), list->end(), edge);
-  DCHECK(iter != list->end());
-  list->erase(iter);
-}
-
-// 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 LayerSorter::Sort(LayerImplList::iterator first,
-                       LayerImplList::iterator last) {
-  DVLOG(2) << "Sorting start ----";
-  CreateGraphNodes(first, last);
-
-  CreateGraphEdges();
-
-  std::vector<GraphNode*> sorted_list;
-  std::deque<GraphNode*> no_incoming_edge_node_list;
-
-  // Find all the nodes that don't have incoming edges.
-  for (NodeList::iterator la = nodes_.begin(); la < nodes_.end(); la++) {
-    if (!la->incoming.size())
-      no_incoming_edge_node_list.push_back(&(*la));
-  }
-
-  DVLOG(2) << "Sorted list: ";
-  while (active_edges_.size() || no_incoming_edge_node_list.size()) {
-    while (no_incoming_edge_node_list.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* from_node = no_incoming_edge_node_list.front();
-      no_incoming_edge_node_list.pop_front();
-
-      // Add it to the final list.
-      sorted_list.push_back(from_node);
-
-      DVLOG(2) << from_node->layer->id() << ", ";
-
-      // Remove all its outgoing edges from the graph.
-      for (size_t i = 0; i < from_node->outgoing.size(); i++) {
-        GraphEdge* outgoing_edge = from_node->outgoing[i];
-
-        active_edges_.erase(outgoing_edge);
-        RemoveEdgeFromList(outgoing_edge, &outgoing_edge->to->incoming);
-        outgoing_edge->to->incoming_edge_weight -= outgoing_edge->weight;
-
-        if (!outgoing_edge->to->incoming.size())
-          no_incoming_edge_node_list.push_back(outgoing_edge->to);
-      }
-      from_node->outgoing.clear();
-    }
-
-    if (!active_edges_.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 min_incoming_edge_weight = FLT_MAX;
-    GraphNode* next_node = NULL;
-    for (size_t i = 0; i < nodes_.size(); i++) {
-      if (nodes_[i].incoming.size() &&
-          nodes_[i].incoming_edge_weight < min_incoming_edge_weight) {
-        min_incoming_edge_weight = nodes_[i].incoming_edge_weight;
-        next_node = &nodes_[i];
-      }
-    }
-    DCHECK(next_node);
-    // Remove all its incoming edges.
-    for (size_t e = 0; e < next_node->incoming.size(); e++) {
-      GraphEdge* incoming_edge = next_node->incoming[e];
-
-      active_edges_.erase(incoming_edge);
-      RemoveEdgeFromList(incoming_edge, &incoming_edge->from->outgoing);
-    }
-    next_node->incoming.clear();
-    next_node->incoming_edge_weight = 0.f;
-    no_incoming_edge_node_list.push_back(next_node);
-    DVLOG(2) << "Breaking cycle by cleaning up incoming edges from " <<
-        next_node->layer->id() <<
-        " (weight = " << min_incoming_edge_weight << ")";
-  }
-
-  // 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 (LayerImplList::iterator it = first; it < last; it++)
-    *it = sorted_list[count++]->layer;
-
-  DVLOG(2) << "Sorting end ----";
-
-  nodes_.clear();
-  edges_.clear();
-  active_edges_.clear();
-}
-
-}  // namespace cc