Revert of Splitting of layers for correct intersections (patchset #20 id:370001 of https://codereview.chromium.org/595593002/)

Reason for revert:
Appears to be adding new static initializers and is breaking Mac/Linux builders, e.g.: http://build.chromium.org/p/chromium/buildstatus?builder=Mac&number=34562

Original issue's description:
> Splitting of layers for correct intersections
>
> Sorting 3d-sorted layers and rendering them in that order causes issues
> when layers intersect. Instead place 3d-sorted layers in a bsp tree and
> fragment any intersecting layers into non-rectangular quads. We can then
> render the fragments in the correct sorted order regardless of
> intersections.
>
> BUG=455918,159225,132122,230833
>
> Committed: https://crrev.com/7e2af77dcd3b5df086be3421fad40b719779381c
> Cr-Commit-Position: refs/heads/master@{#320096}

TBR=enne@chromium.org,danakj@chromium.org,eroman@chromium.org,thakis@chromium.org,awoloszyn@chromium.org
NOPRESUBMIT=true
NOTREECHECKS=true
NOTRY=true
BUG=455918,159225,132122,230833

Review URL: https://codereview.chromium.org/998023002

Cr-Commit-Position: refs/heads/master@{#320122}

10 files changed, 1216 insertions, 17 deletions

diff --git a/cc/trees/layer_sorter.cc b/cc/trees/layer_sorter.cc
new file mode 100644
index 0000000..bde4920
--- /dev/null
+++ b/cc/trees/layer_sorter.cc
@@ -0,0 +1,470 @@
+// 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
diff --git a/cc/trees/layer_sorter.h b/cc/trees/layer_sorter.h
new file mode 100644
index 0000000..4cfa8fe
--- /dev/null
+++ b/cc/trees/layer_sorter.h
@@ -0,0 +1,97 @@
+// 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.
+
+#ifndef CC_TREES_LAYER_SORTER_H_
+#define CC_TREES_LAYER_SORTER_H_
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/containers/hash_tables.h"
+#include "cc/base/cc_export.h"
+#include "cc/layers/layer_impl.h"
+#include "ui/gfx/geometry/point3_f.h"
+#include "ui/gfx/geometry/quad_f.h"
+#include "ui/gfx/geometry/rect_f.h"
+#include "ui/gfx/geometry/vector3d_f.h"
+
+namespace gfx {
+class Transform;
+}
+
+namespace cc {
+struct GraphEdge;
+
+// Holds various useful properties derived from a layer's 3D outline.
+struct CC_EXPORT LayerShape {
+  LayerShape();
+  LayerShape(float width, float height, const gfx::Transform& draw_transform);
+  ~LayerShape();
+
+  float LayerZFromProjectedPoint(const gfx::PointF& p) const;
+
+  gfx::Vector3dF layer_normal;
+  gfx::Point3F transform_origin;
+  gfx::QuadF projected_quad;
+  gfx::RectF projected_bounds;
+};
+
+struct GraphNode {
+  explicit GraphNode(LayerImpl* layer_impl);
+  ~GraphNode();
+
+  LayerImpl* layer;
+  LayerShape shape;
+  std::vector<GraphEdge*> incoming;
+  std::vector<GraphEdge*> outgoing;
+  float incoming_edge_weight;
+};
+
+struct GraphEdge {
+  GraphEdge(GraphNode* from_node, GraphNode* to_node, float weight)
+      : from(from_node),
+        to(to_node),
+        weight(weight) {}
+
+  GraphNode* from;
+  GraphNode* to;
+  float weight;
+};
+
+
+
+class CC_EXPORT LayerSorter {
+ public:
+  LayerSorter();
+  ~LayerSorter();
+
+  void Sort(LayerImplList::iterator first, LayerImplList::iterator last);
+
+  enum ABCompareResult { A_BEFORE_B, B_BEFORE_A, NONE };
+
+  static ABCompareResult CheckOverlap(LayerShape* a,
+                                      LayerShape* b,
+                                      float z_threshold,
+                                      float* weight);
+
+ private:
+  typedef std::vector<GraphNode> NodeList;
+  typedef std::vector<GraphEdge> EdgeList;
+  NodeList nodes_;
+  EdgeList edges_;
+  float z_range_;
+
+  typedef base::hash_map<GraphEdge*, GraphEdge*> EdgeMap;
+  EdgeMap active_edges_;
+
+  void CreateGraphNodes(LayerImplList::iterator first,
+                        LayerImplList::iterator last);
+  void CreateGraphEdges();
+  void RemoveEdgeFromList(GraphEdge* graph, std::vector<GraphEdge*>* list);
+
+  DISALLOW_COPY_AND_ASSIGN(LayerSorter);
+};
+
+}  // namespace cc
+#endif  // CC_TREES_LAYER_SORTER_H_
diff --git a/cc/trees/layer_sorter_unittest.cc b/cc/trees/layer_sorter_unittest.cc
new file mode 100644
index 0000000..74d3cf5
--- /dev/null
+++ b/cc/trees/layer_sorter_unittest.cc
@@ -0,0 +1,329 @@
+// 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 "cc/base/math_util.h"
+#include "cc/layers/layer_impl.h"
+#include "cc/test/fake_impl_proxy.h"
+#include "cc/test/fake_layer_tree_host_impl.h"
+#include "cc/test/test_shared_bitmap_manager.h"
+#include "cc/trees/single_thread_proxy.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "ui/gfx/transform.h"
+
+namespace cc {
+namespace {
+
+// Note: In the following overlap tests, the "camera" is looking down the
+// negative Z axis, meaning that layers with smaller z values (more negative)
+// are further from the camera and therefore must be drawn before layers with
+// higher z values.
+
+TEST(LayerSorterTest, BasicOverlap) {
+  LayerSorter::ABCompareResult overlap_result;
+  const float z_threshold = 0.1f;
+  float weight = 0.f;
+
+  // Trivial test, with one layer directly obscuring the other.
+  gfx::Transform neg4_translate;
+  neg4_translate.Translate3d(0.0, 0.0, -4.0);
+  LayerShape front(2.f, 2.f, neg4_translate);
+
+  gfx::Transform neg5_translate;
+  neg5_translate.Translate3d(0.0, 0.0, -5.0);
+  LayerShape back(2.f, 2.f, neg5_translate);
+
+  overlap_result =
+      LayerSorter::CheckOverlap(&front, &back, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::B_BEFORE_A, overlap_result);
+  EXPECT_EQ(1.f, weight);
+
+  overlap_result =
+      LayerSorter::CheckOverlap(&back, &front, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::A_BEFORE_B, overlap_result);
+  EXPECT_EQ(1.f, weight);
+
+  // One layer translated off to the right. No overlap should be detected.
+  gfx::Transform right_translate;
+  right_translate.Translate3d(10.0, 0.0, -5.0);
+  LayerShape back_right(2.f, 2.f, right_translate);
+  overlap_result =
+      LayerSorter::CheckOverlap(&front, &back_right, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::NONE, overlap_result);
+
+  // When comparing a layer with itself, z difference is always 0.
+  overlap_result =
+      LayerSorter::CheckOverlap(&front, &front, z_threshold, &weight);
+  EXPECT_EQ(0.f, weight);
+}
+
+TEST(LayerSorterTest, RightAngleOverlap) {
+  LayerSorter::ABCompareResult overlap_result;
+  const float z_threshold = 0.1f;
+  float weight = 0.f;
+
+  gfx::Transform perspective_matrix;
+  perspective_matrix.ApplyPerspectiveDepth(1000.0);
+
+  // Two layers forming a right angle with a perspective viewing transform.
+  gfx::Transform left_face_matrix;
+  left_face_matrix.Translate3d(-1.0, 0.0, -5.0);
+  left_face_matrix.RotateAboutYAxis(-90.0);
+  left_face_matrix.Translate(-1.0, -1.0);
+  LayerShape left_face(2.f, 2.f, perspective_matrix * left_face_matrix);
+  gfx::Transform front_face_matrix;
+  front_face_matrix.Translate3d(0.0, 0.0, -4.0);
+  front_face_matrix.Translate(-1.0, -1.0);
+  LayerShape front_face(2.f, 2.f, perspective_matrix * front_face_matrix);
+
+  overlap_result =
+      LayerSorter::CheckOverlap(&front_face, &left_face, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::B_BEFORE_A, overlap_result);
+}
+
+TEST(LayerSorterTest, IntersectingLayerOverlap) {
+  LayerSorter::ABCompareResult overlap_result;
+  const float z_threshold = 0.1f;
+  float weight = 0.f;
+
+  gfx::Transform perspective_matrix;
+  perspective_matrix.ApplyPerspectiveDepth(1000.0);
+
+  // Intersecting layers. An explicit order will be returned based on relative z
+  // values at the overlapping features but the weight returned should be zero.
+  gfx::Transform front_face_matrix;
+  front_face_matrix.Translate3d(0.0, 0.0, -4.0);
+  front_face_matrix.Translate(-1.0, -1.0);
+  LayerShape front_face(2.f, 2.f, perspective_matrix * front_face_matrix);
+
+  gfx::Transform through_matrix;
+  through_matrix.Translate3d(0.0, 0.0, -4.0);
+  through_matrix.RotateAboutYAxis(45.0);
+  through_matrix.Translate(-1.0, -1.0);
+  LayerShape rotated_face(2.f, 2.f, perspective_matrix * through_matrix);
+  overlap_result = LayerSorter::CheckOverlap(&front_face,
+                                             &rotated_face,
+                                             z_threshold,
+                                             &weight);
+  EXPECT_NE(LayerSorter::NONE, overlap_result);
+  EXPECT_EQ(0.f, weight);
+}
+
+TEST(LayerSorterTest, LayersAtAngleOverlap) {
+  LayerSorter::ABCompareResult overlap_result;
+  const float z_threshold = 0.1f;
+  float weight = 0.f;
+
+  // 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.
+
+  gfx::Transform transform_a;
+  transform_a.Translate3d(-6.0, 0.0, 1.0);
+  transform_a.Translate(-4.0, -10.0);
+  LayerShape layer_a(8.f, 20.f, transform_a);
+
+  gfx::Transform transform_b;
+  transform_b.Translate3d(6.0, 0.0, -1.0);
+  transform_b.Translate(-4.0, -10.0);
+  LayerShape layer_b(8.f, 20.f, transform_b);
+
+  gfx::Transform transform_c;
+  transform_c.RotateAboutYAxis(40.0);
+  transform_c.Translate(-4.0, -10.0);
+  LayerShape layer_c(8.f, 20.f, transform_c);
+
+  overlap_result =
+      LayerSorter::CheckOverlap(&layer_a, &layer_c, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::A_BEFORE_B, overlap_result);
+  overlap_result =
+      LayerSorter::CheckOverlap(&layer_c, &layer_b, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::A_BEFORE_B, overlap_result);
+  overlap_result =
+      LayerSorter::CheckOverlap(&layer_a, &layer_b, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::NONE, overlap_result);
+}
+
+TEST(LayerSorterTest, LayersUnderPathologicalPerspectiveTransform) {
+  LayerSorter::ABCompareResult overlap_result;
+  const float z_threshold = 0.1f;
+  float weight = 0.f;
+
+  // On perspective projection, if w becomes negative, the re-projected point
+  // will be invalid and un-usable. Correct code needs to clip away portions of
+  // the geometry where w < 0. If the code uses the invalid value, it will think
+  // that a layer has different bounds than it really does, which can cause
+  // things to sort incorrectly.
+
+  gfx::Transform perspective_matrix;
+  perspective_matrix.ApplyPerspectiveDepth(1);
+
+  gfx::Transform transform_a;
+  transform_a.Translate3d(-15.0, 0.0, -2.0);
+  transform_a.Translate(-5.0, -5.0);
+  LayerShape layer_a(10.f, 10.f, perspective_matrix * transform_a);
+
+  // With this sequence of transforms, when layer B is correctly clipped, it
+  // will be visible on the left half of the projection plane, in front of
+  // layer_a. When it is not clipped, its bounds will actually incorrectly
+  // appear much smaller and the correct sorting dependency will not be found.
+  gfx::Transform transform_b;
+  transform_b.Translate3d(0.f, 0.f, 0.7f);
+  transform_b.RotateAboutYAxis(45.0);
+  transform_b.Translate(-5.0, -5.0);
+  LayerShape layer_b(10.f, 10.f, perspective_matrix * transform_b);
+
+  // Sanity check that the test case actually covers the intended scenario,
+  // where part of layer B go behind the w = 0 plane.
+  gfx::QuadF test_quad = gfx::QuadF(gfx::RectF(-0.5f, -0.5f, 1.f, 1.f));
+  bool clipped = false;
+  MathUtil::MapQuad(perspective_matrix * transform_b, test_quad, &clipped);
+  ASSERT_TRUE(clipped);
+
+  overlap_result =
+      LayerSorter::CheckOverlap(&layer_a, &layer_b, z_threshold, &weight);
+  EXPECT_EQ(LayerSorter::A_BEFORE_B, overlap_result);
+}
+
+TEST(LayerSorterTest, VerifyExistingOrderingPreservedWhenNoZDiff) {
+  // If there is no reason to re-sort the layers (i.e. no 3d z difference), then
+  // the existing ordering provided on input should be retained. This test
+  // covers the fix in https://bugs.webkit.org/show_bug.cgi?id=75046. Before
+  // this fix, ordering was accidentally reversed, causing bugs in z-index
+  // ordering on websites when preserves3D triggered the LayerSorter.
+
+  // Input list of layers: [1, 2, 3, 4, 5].
+  // Expected output: [3, 4, 1, 2, 5].
+  //    - 1, 2, and 5 do not have a 3d z difference, and therefore their
+  //      relative ordering should be retained.
+  //    - 3 and 4 do not have a 3d z difference, and therefore their relative
+  //      ordering should be retained.
+  //    - 3 and 4 should be re-sorted so they are in front of 1, 2, and 5.
+
+  FakeImplProxy proxy;
+  TestSharedBitmapManager shared_bitmap_manager;
+  FakeLayerTreeHostImpl host_impl(&proxy, &shared_bitmap_manager);
+
+  scoped_ptr<LayerImpl> layer1 = LayerImpl::Create(host_impl.active_tree(), 1);
+  scoped_ptr<LayerImpl> layer2 = LayerImpl::Create(host_impl.active_tree(), 2);
+  scoped_ptr<LayerImpl> layer3 = LayerImpl::Create(host_impl.active_tree(), 3);
+  scoped_ptr<LayerImpl> layer4 = LayerImpl::Create(host_impl.active_tree(), 4);
+  scoped_ptr<LayerImpl> layer5 = LayerImpl::Create(host_impl.active_tree(), 5);
+
+  gfx::Transform BehindMatrix;
+  BehindMatrix.Translate3d(0.0, 0.0, 2.0);
+  gfx::Transform FrontMatrix;
+  FrontMatrix.Translate3d(0.0, 0.0, 1.0);
+
+  layer1->SetBounds(gfx::Size(10, 10));
+  layer1->SetContentBounds(gfx::Size(10, 10));
+  layer1->draw_properties().target_space_transform = BehindMatrix;
+  layer1->SetDrawsContent(true);
+
+  layer2->SetBounds(gfx::Size(20, 20));
+  layer2->SetContentBounds(gfx::Size(20, 20));
+  layer2->draw_properties().target_space_transform = BehindMatrix;
+  layer2->SetDrawsContent(true);
+
+  layer3->SetBounds(gfx::Size(30, 30));
+  layer3->SetContentBounds(gfx::Size(30, 30));
+  layer3->draw_properties().target_space_transform = FrontMatrix;
+  layer3->SetDrawsContent(true);
+
+  layer4->SetBounds(gfx::Size(40, 40));
+  layer4->SetContentBounds(gfx::Size(40, 40));
+  layer4->draw_properties().target_space_transform = FrontMatrix;
+  layer4->SetDrawsContent(true);
+
+  layer5->SetBounds(gfx::Size(50, 50));
+  layer5->SetContentBounds(gfx::Size(50, 50));
+  layer5->draw_properties().target_space_transform = BehindMatrix;
+  layer5->SetDrawsContent(true);
+
+  LayerImplList layer_list;
+  layer_list.push_back(layer1.get());
+  layer_list.push_back(layer2.get());
+  layer_list.push_back(layer3.get());
+  layer_list.push_back(layer4.get());
+  layer_list.push_back(layer5.get());
+
+  ASSERT_EQ(5u, layer_list.size());
+  EXPECT_EQ(1, layer_list[0]->id());
+  EXPECT_EQ(2, layer_list[1]->id());
+  EXPECT_EQ(3, layer_list[2]->id());
+  EXPECT_EQ(4, layer_list[3]->id());
+  EXPECT_EQ(5, layer_list[4]->id());
+
+  LayerSorter layer_sorter;
+  layer_sorter.Sort(layer_list.begin(), layer_list.end());
+
+  ASSERT_EQ(5u, layer_list.size());
+  EXPECT_EQ(3, layer_list[0]->id());
+  EXPECT_EQ(4, layer_list[1]->id());
+  EXPECT_EQ(1, layer_list[2]->id());
+  EXPECT_EQ(2, layer_list[3]->id());
+  EXPECT_EQ(5, layer_list[4]->id());
+}
+
+TEST(LayerSorterTest, VerifyConcidentLayerPrecisionLossResultsInDocumentOrder) {
+  FakeImplProxy proxy;
+  TestSharedBitmapManager shared_bitmap_manager;
+  FakeLayerTreeHostImpl host_impl(&proxy, &shared_bitmap_manager);
+
+  scoped_ptr<LayerImpl> layer1 = LayerImpl::Create(host_impl.active_tree(), 1);
+  scoped_ptr<LayerImpl> layer2 = LayerImpl::Create(host_impl.active_tree(), 2);
+
+  // Layer 1 should occur before layer 2 in paint.  However, due to numeric
+  // issues in the sorter, it will put the layers in the wrong order
+  // in some situations.  Here we test a patch that results in  document
+  // order rather than calculated order when numeric percision is suspect
+  // in calculated order.
+
+  gfx::Transform BehindMatrix;
+  BehindMatrix.Translate3d(0.f, 0.f, 0.999999f);
+  BehindMatrix.RotateAboutXAxis(38.5);
+  BehindMatrix.RotateAboutYAxis(77.0);
+  gfx::Transform FrontMatrix;
+  FrontMatrix.Translate3d(0, 0, 1.0);
+  FrontMatrix.RotateAboutXAxis(38.5);
+  FrontMatrix.RotateAboutYAxis(77.0);
+
+  layer1->SetBounds(gfx::Size(10, 10));
+  layer1->SetContentBounds(gfx::Size(10, 10));
+  layer1->draw_properties().target_space_transform = BehindMatrix;
+  layer1->SetDrawsContent(true);
+
+  layer2->SetBounds(gfx::Size(10, 10));
+  layer2->SetContentBounds(gfx::Size(10, 10));
+  layer2->draw_properties().target_space_transform = FrontMatrix;
+  layer2->SetDrawsContent(true);
+
+  LayerImplList layer_list;
+  layer_list.push_back(layer1.get());
+  layer_list.push_back(layer2.get());
+
+  ASSERT_EQ(2u, layer_list.size());
+  EXPECT_EQ(1, layer_list[0]->id());
+  EXPECT_EQ(2, layer_list[1]->id());
+
+  LayerSorter layer_sorter;
+  layer_sorter.Sort(layer_list.begin(), layer_list.end());
+
+  ASSERT_EQ(2u, layer_list.size());
+  EXPECT_EQ(1, layer_list[0]->id());
+  EXPECT_EQ(2, layer_list[1]->id());
+}
+
+}  // namespace
+}  // namespace cc
+
diff --git a/cc/trees/layer_tree_host_common.cc b/cc/trees/layer_tree_host_common.cc
index e47ef0d..f4c2029 100644
--- a/cc/trees/layer_tree_host_common.cc
+++ b/cc/trees/layer_tree_host_common.cc
@@ -15,6 +15,7 @@
 #include "cc/layers/render_surface.h"
 #include "cc/layers/render_surface_impl.h"
 #include "cc/trees/draw_property_utils.h"
+#include "cc/trees/layer_sorter.h"
 #include "cc/trees/layer_tree_host.h"
 #include "cc/trees/layer_tree_impl.h"
 #include "ui/gfx/geometry/rect_conversions.h"
@@ -30,6 +31,20 @@ ScrollAndScaleSet::ScrollAndScaleSet()
 
 ScrollAndScaleSet::~ScrollAndScaleSet() {}
 
+static void SortLayers(LayerList::iterator first,
+                       LayerList::iterator end,
+                       void* layer_sorter) {
+  NOTREACHED();
+}
+
+static void SortLayers(LayerImplList::iterator first,
+                       LayerImplList::iterator end,
+                       LayerSorter* layer_sorter) {
+  DCHECK(layer_sorter);
+  TRACE_EVENT0("cc", "LayerTreeHostCommon::SortLayers");
+  layer_sorter->Sort(first, end);
+}
+
 template <typename LayerType>
 static gfx::Vector2dF GetEffectiveScrollDelta(LayerType* layer) {
   // Layer's scroll offset can have an integer part and fractional part.
@@ -1266,6 +1281,7 @@ static void PreCalculateMetaInformation(
 
 template <typename LayerType>
 struct SubtreeGlobals {
+  LayerSorter* layer_sorter;
   int max_texture_size;
   float device_scale_factor;
   float page_scale_factor;
@@ -2353,6 +2369,17 @@ static void CalculateDrawPropertiesInternal(
     return;
   }
 
+  // If preserves-3d then sort all the descendants in 3D so that they can be
+  // drawn from back to front. If the preserves-3d property is also set on the
+  // parent then skip the sorting as the parent will sort all the descendants
+  // anyway.
+  if (globals.layer_sorter && descendants.size() && layer->Is3dSorted() &&
+      !LayerIsInExisting3DRenderingContext(layer)) {
+    SortLayers(descendants.begin() + sorting_start_index,
+               descendants.end(),
+               globals.layer_sorter);
+  }
+
   UpdateAccumulatedSurfaceState<LayerType>(
       layer, local_drawable_content_rect_of_subtree, accumulated_surface_state);
 
@@ -2390,6 +2417,7 @@ static void ProcessCalcDrawPropsInputs(
   scaled_device_transform.Scale(inputs.device_scale_factor,
                                 inputs.device_scale_factor);
 
+  globals->layer_sorter = NULL;
   globals->max_texture_size = inputs.max_texture_size;
   globals->device_scale_factor =
       inputs.device_scale_factor * device_transform_scale;
@@ -2553,6 +2581,9 @@ void LayerTreeHostCommon::CalculateDrawProperties(
   DataForRecursion<LayerImpl> data_for_recursion;
   ProcessCalcDrawPropsInputs(*inputs, &globals, &data_for_recursion);
 
+  LayerSorter layer_sorter;
+  globals.layer_sorter = &layer_sorter;
+
   PreCalculateMetaInformationRecursiveData recursive_data;
   PreCalculateMetaInformation(inputs->root_layer, &recursive_data);
   std::vector<AccumulatedSurfaceState<LayerImpl>> accumulated_surface_state;
diff --git a/cc/trees/layer_tree_host_common_perftest.cc b/cc/trees/layer_tree_host_common_perftest.cc
index 1732e5588..73d5c1d 100644
--- a/cc/trees/layer_tree_host_common_perftest.cc
+++ b/cc/trees/layer_tree_host_common_perftest.cc
@@ -25,6 +25,7 @@
 #include "cc/test/layer_tree_json_parser.h"
 #include "cc/test/layer_tree_test.h"
 #include "cc/test/paths.h"
+#include "cc/trees/layer_sorter.h"
 #include "cc/trees/layer_tree_impl.h"
 #include "testing/perf/perf_test.h"
 
@@ -161,7 +162,55 @@ class CalcDrawPropsImplTest : public LayerTreeHostCommonPerfTest {
   }
 };
 
-class BspTreePerfTest : public CalcDrawPropsImplTest {
+class LayerSorterMainTest : public CalcDrawPropsImplTest {
+ public:
+  void RunSortLayers() { RunTest(false, false, false); }
+
+  void BeginTest() override { PostSetNeedsCommitToMainThread(); }
+
+  void DrawLayersOnThread(LayerTreeHostImpl* host_impl) override {
+    LayerTreeImpl* active_tree = host_impl->active_tree();
+    // First build the tree and then we'll start running tests on layersorter
+    // itself
+    bool can_render_to_separate_surface = true;
+    int max_texture_size = 8096;
+    DoCalcDrawPropertiesImpl(can_render_to_separate_surface,
+                             max_texture_size,
+                             active_tree,
+                             host_impl);
+
+    // Behaviour of this test is different from that of sorting in practice.
+    // In this case, all layers that exist in any 3D context are put into a list
+    // and are sorted as one big 3D context instead of several smaller ones.
+    BuildLayerImplList(active_tree->root_layer(), &base_list_);
+    timer_.Reset();
+    do {
+      // Here we'll move the layers into a LayerImpl list of their own to be
+      // sorted so we don't have a sorted list for every run after the first
+      LayerImplList test_list = base_list_;
+      layer_sorter_.Sort(test_list.begin(), test_list.end());
+      timer_.NextLap();
+    } while (!timer_.HasTimeLimitExpired());
+
+    EndTest();
+  }
+
+  void BuildLayerImplList(LayerImpl* layer, LayerImplList* list) {
+    if (layer->Is3dSorted()) {
+      list->push_back(layer);
+    }
+
+    for (size_t i = 0; i < layer->children().size(); i++) {
+      BuildLayerImplList(layer->children()[i], list);
+    }
+  }
+
+ private:
+  LayerImplList base_list_;
+  LayerSorter layer_sorter_;
+};
+
+class BspTreePerfTest : public LayerSorterMainTest {
  public:
   void RunSortLayers() { RunTest(false, false, false); }
 
@@ -212,18 +261,7 @@ class BspTreePerfTest : public CalcDrawPropsImplTest {
     EndTest();
   }
 
-  void BuildLayerImplList(LayerImpl* layer, LayerImplList* list) {
-    if (layer->Is3dSorted()) {
-      list->push_back(layer);
-    }
-
-    for (size_t i = 0; i < layer->children().size(); i++) {
-      BuildLayerImplList(layer->children()[i], list);
-    }
-  }
-
  private:
-  LayerImplList base_list_;
   int num_duplicates_;
 };
 
@@ -275,13 +313,13 @@ TEST_F(CalcDrawPropsImplTest, TouchRegionHeavy) {
   RunCalcDrawProps();
 }
 
-TEST_F(BspTreePerfTest, LayerSorterCubes) {
+TEST_F(LayerSorterMainTest, LayerSorterCubes) {
   SetTestName("layer_sort_cubes");
   ReadTestFile("layer_sort_cubes");
   RunSortLayers();
 }
 
-TEST_F(BspTreePerfTest, LayerSorterRubik) {
+TEST_F(LayerSorterMainTest, LayerSorterRubik) {
   SetTestName("layer_sort_rubik");
   ReadTestFile("layer_sort_rubik");
   // TODO(vollick): Remove verify_property_trees setting after
diff --git a/cc/trees/layer_tree_host_common_unittest.cc b/cc/trees/layer_tree_host_common_unittest.cc
index 7bd0634..0a51ccc 100644
--- a/cc/trees/layer_tree_host_common_unittest.cc
+++ b/cc/trees/layer_tree_host_common_unittest.cc
@@ -2975,6 +2975,78 @@ TEST_F(LayerTreeHostCommonTest,
   EXPECT_FALSE(child->draw_properties().sorted_for_recursion);
 }
 
+TEST_F(LayerTreeHostCommonTest, WillSortAtContextBoundary) {
+  // Creates a layer tree that looks as follows:
+  // * root (sorting-context-id1)
+  //   * parent (sorting-context-id2)
+  //     * child1 (sorting-context-id2)
+  //     * child2 (sorting-context-id2)
+  //
+  // This test ensures that we sort at |parent| even though both it and root are
+  // set to be 3d sorted.
+  FakeImplProxy proxy;
+  TestSharedBitmapManager shared_bitmap_manager;
+  FakeLayerTreeHostImpl host_impl(&proxy, &shared_bitmap_manager);
+
+  scoped_ptr<LayerImpl> root_ptr(LayerImpl::Create(host_impl.active_tree(), 1));
+  LayerImpl* root = root_ptr.get();
+  scoped_ptr<LayerImpl> parent_ptr(
+      LayerImpl::Create(host_impl.active_tree(), 2));
+  LayerImpl* parent = parent_ptr.get();
+  scoped_ptr<LayerImpl> child1_ptr(
+      LayerImpl::Create(host_impl.active_tree(), 3));
+  LayerImpl* child1 = child1_ptr.get();
+  scoped_ptr<LayerImpl> child2_ptr(
+      LayerImpl::Create(host_impl.active_tree(), 4));
+  LayerImpl* child2 = child2_ptr.get();
+
+  gfx::Transform identity_matrix;
+  gfx::Transform below_matrix;
+  below_matrix.Translate3d(0.f, 0.f, -10.f);
+  gfx::Transform above_matrix;
+  above_matrix.Translate3d(0.f, 0.f, 10.f);
+
+  SetLayerPropertiesForTesting(root, identity_matrix, gfx::Point3F(),
+                               gfx::PointF(), gfx::Size(100, 100), true, true,
+                               true);
+  SetLayerPropertiesForTesting(parent, identity_matrix, gfx::Point3F(),
+                               gfx::PointF(), gfx::Size(50, 50), true, true,
+                               true);
+  SetLayerPropertiesForTesting(child1, above_matrix, gfx::Point3F(),
+                               gfx::PointF(), gfx::Size(50, 50), true, true,
+                               false);
+  SetLayerPropertiesForTesting(child2, below_matrix, gfx::Point3F(),
+                               gfx::PointF(), gfx::Size(50, 50), true, true,
+                               false);
+
+  root->Set3dSortingContextId(3);
+  root->SetDrawsContent(true);
+  parent->Set3dSortingContextId(7);
+  parent->SetDrawsContent(true);
+  child1->Set3dSortingContextId(7);
+  child1->SetDrawsContent(true);
+  child2->Set3dSortingContextId(7);
+  child2->SetDrawsContent(true);
+
+  parent->AddChild(child1_ptr.Pass());
+  parent->AddChild(child2_ptr.Pass());
+  root->AddChild(parent_ptr.Pass());
+
+  LayerImplList render_surface_layer_list;
+  LayerTreeHostCommon::CalcDrawPropsImplInputsForTesting inputs(
+      root_ptr.get(), root->bounds(), &render_surface_layer_list);
+  inputs.can_adjust_raster_scales = true;
+  LayerTreeHostCommon::CalculateDrawProperties(&inputs);
+
+  EXPECT_TRUE(root->render_surface());
+  EXPECT_EQ(2u, render_surface_layer_list.size());
+
+  EXPECT_EQ(3u, parent->render_surface()->layer_list().size());
+  EXPECT_EQ(child2->id(), parent->render_surface()->layer_list().at(0)->id());
+  EXPECT_EQ(parent->id(), parent->render_surface()->layer_list().at(1)->id());
+  EXPECT_EQ(child1->id(), parent->render_surface()->layer_list().at(2)->id());
+}
+
 TEST_F(LayerTreeHostCommonTest,
        SingularNonAnimatingTransformDoesNotPreventClearingDrawProperties) {
   scoped_refptr<Layer> root = Layer::Create();
@@ -7520,6 +7592,110 @@ TEST_F(LayerTreeHostCommonTest, OutOfOrderClippingRequiresRSLLSorting) {
   EXPECT_TRUE(render_surface_layer_list.at(2)->render_surface());
 }
 
+TEST_F(LayerTreeHostCommonTest, DoNotClobberSorting) {
+  // We rearrange layer list contributions if we have to visit children out of
+  // order, but it should be a 'stable' rearrangement. That is, the layer list
+  // additions for a single layer should not be reordered, though their position
+  // wrt to the contributions due to a sibling may vary.
+  //
+  // + root
+  //   + scroll_child
+  //     + top_content
+  //     + bottom_content
+  //   + scroll_parent_border
+  //     + scroll_parent_clip
+  //       + scroll_parent
+  //
+  FakeImplProxy proxy;
+  TestSharedBitmapManager shared_bitmap_manager;
+  FakeLayerTreeHostImpl host_impl(&proxy, &shared_bitmap_manager);
+  host_impl.CreatePendingTree();
+  scoped_ptr<LayerImpl> root = LayerImpl::Create(host_impl.active_tree(), 1);
+  scoped_ptr<LayerImpl> scroll_parent_border =
+      LayerImpl::Create(host_impl.active_tree(), 2);
+  scoped_ptr<LayerImpl> scroll_parent_clip =
+      LayerImpl::Create(host_impl.active_tree(), 3);
+  scoped_ptr<LayerImpl> scroll_parent =
+      LayerImpl::Create(host_impl.active_tree(), 4);
+  scoped_ptr<LayerImpl> scroll_child =
+      LayerImpl::Create(host_impl.active_tree(), 5);
+  scoped_ptr<LayerImpl> bottom_content =
+      LayerImpl::Create(host_impl.active_tree(), 6);
+  scoped_ptr<LayerImpl> top_content =
+      LayerImpl::Create(host_impl.active_tree(), 7);
+
+  scroll_parent_clip->SetMasksToBounds(true);
+
+  scroll_child->SetScrollParent(scroll_parent.get());
+  scoped_ptr<std::set<LayerImpl*>> scroll_children(new std::set<LayerImpl*>);
+  scroll_children->insert(scroll_child.get());
+  scroll_parent->SetScrollChildren(scroll_children.release());
+
+  scroll_child->SetDrawsContent(true);
+  scroll_parent->SetDrawsContent(true);
+  top_content->SetDrawsContent(true);
+  bottom_content->SetDrawsContent(true);
+
+  gfx::Transform identity_transform;
+  gfx::Transform top_transform;
+  top_transform.Translate3d(0.0, 0.0, 5.0);
+  gfx::Transform bottom_transform;
+  bottom_transform.Translate3d(0.0, 0.0, 3.0);
+
+  SetLayerPropertiesForTesting(root.get(), identity_transform, gfx::Point3F(),
+                               gfx::PointF(), gfx::Size(50, 50), true, false,
+                               true);
+  SetLayerPropertiesForTesting(scroll_parent_border.get(), identity_transform,
+                               gfx::Point3F(), gfx::PointF(), gfx::Size(40, 40),
+                               true, false, false);
+  SetLayerPropertiesForTesting(scroll_parent_clip.get(), identity_transform,
+                               gfx::Point3F(), gfx::PointF(), gfx::Size(30, 30),
+                               true, false, false);
+  SetLayerPropertiesForTesting(scroll_parent.get(), identity_transform,
+                               gfx::Point3F(), gfx::PointF(), gfx::Size(50, 50),
+                               true, false, false);
+  SetLayerPropertiesForTesting(scroll_child.get(), identity_transform,
+                               gfx::Point3F(), gfx::PointF(), gfx::Size(50, 50),
+                               true, false, false);
+  SetLayerPropertiesForTesting(top_content.get(), top_transform, gfx::Point3F(),
+                               gfx::PointF(), gfx::Size(50, 50), false, true,
+                               true);
+  SetLayerPropertiesForTesting(bottom_content.get(), bottom_transform,
+                               gfx::Point3F(), gfx::PointF(), gfx::Size(50, 50),
+                               false, true, true);
+
+  scroll_child->SetShouldFlattenTransform(false);
+  scroll_child->Set3dSortingContextId(1);
+
+  scroll_child->AddChild(top_content.Pass());
+  scroll_child->AddChild(bottom_content.Pass());
+  root->AddChild(scroll_child.Pass());
+
+  scroll_parent_clip->AddChild(scroll_parent.Pass());
+  scroll_parent_border->AddChild(scroll_parent_clip.Pass());
+  root->AddChild(scroll_parent_border.Pass());
+
+  LayerImplList render_surface_layer_list;
+  LayerTreeHostCommon::CalcDrawPropsImplInputsForTesting inputs(
+      root.get(), root->bounds(), &render_surface_layer_list);
+
+  LayerTreeHostCommon::CalculateDrawProperties(&inputs);
+
+  EXPECT_TRUE(root->render_surface());
+
+  // If we don't sort by depth and let the layers get added in the order they
+  // would normally be visited in, then layers 6 and 7 will be out of order. In
+  // other words, although we've had to shift 5, 6, and 7 to appear before 4
+  // in the list (because of the scroll parent relationship), this should not
+  // have an effect on the the order of 5, 6, and 7 (which had been reordered
+  // due to layer sorting).
+  EXPECT_EQ(4u, root->render_surface()->layer_list().size());
+  EXPECT_EQ(5, root->render_surface()->layer_list().at(0)->id());
+  EXPECT_EQ(6, root->render_surface()->layer_list().at(1)->id());
+  EXPECT_EQ(7, root->render_surface()->layer_list().at(2)->id());
+  EXPECT_EQ(4, root->render_surface()->layer_list().at(3)->id());
+}
+
 TEST_F(LayerTreeHostCommonTest, ScrollCompensationWithRounding) {
   // This test verifies that a scrolling layer that gets snapped to
   // integer coordinates doesn't move a fixed position child.
diff --git a/cc/trees/layer_tree_host_pixeltest_filters.cc b/cc/trees/layer_tree_host_pixeltest_filters.cc
index dd3cf73..76acaa8 100644
--- a/cc/trees/layer_tree_host_pixeltest_filters.cc
+++ b/cc/trees/layer_tree_host_pixeltest_filters.cc
@@ -97,8 +97,8 @@ TEST_F(LayerTreeHostFiltersPixelTest, BackgroundFilterBlurOutsets) {
 }
 
 TEST_F(LayerTreeHostFiltersPixelTest, BackgroundFilterBlurOffAxis) {
-  scoped_refptr<SolidColorLayer> background =
-      CreateSolidColorLayer(gfx::Rect(200, 200), SK_ColorTRANSPARENT);
+  scoped_refptr<SolidColorLayer> background = CreateSolidColorLayer(
+      gfx::Rect(200, 200), SK_ColorWHITE);
 
   // This verifies that the perspective of the clear layer (with black border)
   // does not influence the blending of the green box behind it. Also verifies
diff --git a/cc/trees/layer_tree_impl_unittest.cc b/cc/trees/layer_tree_impl_unittest.cc
index 06df3c2..67f98e65 100644
--- a/cc/trees/layer_tree_impl_unittest.cc
+++ b/cc/trees/layer_tree_impl_unittest.cc
@@ -920,6 +920,14 @@ TEST_F(LayerTreeImplTest, HitTestingForMultipleLayersAtVaryingDepths) {
   ASSERT_TRUE(grand_child1);
   ASSERT_EQ(1u, RenderSurfaceLayerList().size());
 
+  RenderSurfaceImpl* root_render_surface =
+      host_impl().active_tree()->root_layer()->render_surface();
+  ASSERT_EQ(4u, root_render_surface->layer_list().size());
+  ASSERT_EQ(3, root_render_surface->layer_list().at(0)->id());
+  ASSERT_EQ(1, root_render_surface->layer_list().at(1)->id());
+  ASSERT_EQ(2, root_render_surface->layer_list().at(2)->id());
+  ASSERT_EQ(4, root_render_surface->layer_list().at(3)->id());
+
   // Nothing overlaps the root_layer at (1, 1), so hit testing there should find
   // the root layer.
   gfx::Point test_point = gfx::Point(1, 1);
diff --git a/cc/trees/occlusion_tracker.cc b/cc/trees/occlusion_tracker.cc
index 0f0ce15..388eb6e 100644
--- a/cc/trees/occlusion_tracker.cc
+++ b/cc/trees/occlusion_tracker.cc
@@ -155,7 +155,7 @@ static inline bool LayerIsInUnsorted3dRenderingContext(const Layer* layer) {
   return layer->Is3dSorted();
 }
 static inline bool LayerIsInUnsorted3dRenderingContext(const LayerImpl* layer) {
-  return layer->Is3dSorted();
+  return false;
 }
 
 template <typename LayerType>
diff --git a/cc/trees/occlusion_tracker_unittest.cc b/cc/trees/occlusion_tracker_unittest.cc
index f3f2185..e3639ad 100644
--- a/cc/trees/occlusion_tracker_unittest.cc
+++ b/cc/trees/occlusion_tracker_unittest.cc
@@ -1540,6 +1540,56 @@ class OcclusionTrackerTestLayerBehindCameraDoesNotOcclude
   }
 };
 
+// This test requires accumulating occlusion of 3d layers, which are skipped by
+// the occlusion tracker on the main thread. So this test should run on the impl
+// thread.
+IMPL_THREAD_TEST(OcclusionTrackerTestLayerBehindCameraDoesNotOcclude);
+
+template <class Types>
+class OcclusionTrackerTestLargePixelsOccludeInsideClipRect
+    : public OcclusionTrackerTest<Types> {
+ protected:
+  explicit OcclusionTrackerTestLargePixelsOccludeInsideClipRect(
+      bool opaque_layers)
+      : OcclusionTrackerTest<Types>(opaque_layers) {}
+  void RunMyTest() override {
+    gfx::Transform transform;
+    transform.Translate(50.0, 50.0);
+    transform.ApplyPerspectiveDepth(100.0);
+    transform.Translate3d(0.0, 0.0, 99.0);
+    transform.Translate(-50.0, -50.0);
+
+    typename Types::ContentLayerType* parent = this->CreateRoot(
+        this->identity_matrix, gfx::PointF(), gfx::Size(100, 100));
+    parent->SetMasksToBounds(true);
+    typename Types::ContentLayerType* layer = this->CreateDrawingLayer(
+        parent, transform, gfx::PointF(), gfx::Size(100, 100), true);
+    parent->SetShouldFlattenTransform(false);
+    parent->Set3dSortingContextId(1);
+    layer->SetShouldFlattenTransform(false);
+    layer->Set3dSortingContextId(1);
+    this->CalcDrawEtc(parent);
+
+    TestOcclusionTrackerWithClip<typename Types::LayerType> occlusion(
+        gfx::Rect(0, 0, 1000, 1000));
+
+    // This is very close to the camera, so pixels in its visible_content_rect()
+    // will actually go outside of the layer's clip rect.  Ensure that those
+    // pixels don't occlude things outside the clip rect.
+    this->VisitLayer(layer, &occlusion);
+    this->EnterLayer(parent, &occlusion);
+    EXPECT_EQ(gfx::Rect(0, 0, 100, 100).ToString(),
+              occlusion.occlusion_from_inside_target().ToString());
+    EXPECT_EQ(gfx::Rect().ToString(),
+              occlusion.occlusion_from_outside_target().ToString());
+  }
+};
+
+// This test requires accumulating occlusion of 3d layers, which are skipped by
+// the occlusion tracker on the main thread. So this test should run on the impl
+// thread.
+IMPL_THREAD_TEST(OcclusionTrackerTestLargePixelsOccludeInsideClipRect);
+
 template <class Types>
 class OcclusionTrackerTestAnimationOpacity1OnMainThread
     : public OcclusionTrackerTest<Types> {