1 // Copyright 2011 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "cc/trees/layer_sorter.h"
12 #include "base/logging.h"
13 #include "cc/base/math_util.h"
14 #include "cc/layers/render_surface_impl.h"
15 #include "ui/gfx/transform.h"
19 // This epsilon is used to determine if two layers are too close to each other
20 // to be able to tell which is in front of the other. It's a relative epsilon
21 // so it is robust to changes in scene scale. This value was chosen by picking
22 // a value near machine epsilon and then increasing it until the flickering on
23 // the test scene went away.
24 const float k_layer_epsilon = 1e-4f;
26 inline static float PerpProduct(gfx::Vector2dF u, gfx::Vector2dF v) {
27 return u.x() * v.y() - u.y() * v.x();
30 // Tests if two edges defined by their endpoints (a,b) and (c,d) intersect.
31 // Returns true and the point of intersection if they do and false otherwise.
32 static bool EdgeEdgeTest(gfx::PointF a,
37 gfx::Vector2dF u = b - a;
38 gfx::Vector2dF v = d - c;
39 gfx::Vector2dF w = a - c;
41 float denom = PerpProduct(u, v);
43 // If denom == 0 then the edges are parallel. While they could be overlapping
44 // we don't bother to check here as the we'll find their intersections from
45 // the corner to quad tests.
49 float s = PerpProduct(v, w) / denom;
50 if (s < 0.f || s > 1.f)
53 float t = PerpProduct(u, w) / denom;
54 if (t < 0.f || t > 1.f)
62 GraphNode::GraphNode(LayerImpl* layer_impl)
64 incoming_edge_weight(0.f) {}
66 GraphNode::~GraphNode() {}
68 LayerSorter::LayerSorter()
71 LayerSorter::~LayerSorter() {}
73 static float CheckFloatingPointNumericAccuracy(float a, float b) {
74 float abs_dif = std::abs(b - a);
75 float abs_max = std::max(std::abs(b), std::abs(a));
76 // Check to see if we've got a result with a reasonable amount of error.
77 return abs_dif / abs_max;
80 // Checks whether layer "a" draws on top of layer "b". The weight value returned
81 // is an indication of the maximum z-depth difference between the layers or zero
82 // if the layers are found to be intesecting (some features are in front and
84 LayerSorter::ABCompareResult LayerSorter::CheckOverlap(LayerShape* a,
90 // Early out if the projected bounds don't overlap.
91 if (!a->projected_bounds.Intersects(b->projected_bounds))
94 gfx::PointF aPoints[4] = { a->projected_quad.p1(),
95 a->projected_quad.p2(),
96 a->projected_quad.p3(),
97 a->projected_quad.p4() };
98 gfx::PointF bPoints[4] = { b->projected_quad.p1(),
99 b->projected_quad.p2(),
100 b->projected_quad.p3(),
101 b->projected_quad.p4() };
103 // Make a list of points that inside both layer quad projections.
104 std::vector<gfx::PointF> overlap_points;
106 // Check all four corners of one layer against the other layer's quad.
107 for (int i = 0; i < 4; ++i) {
108 if (a->projected_quad.Contains(bPoints[i]))
109 overlap_points.push_back(bPoints[i]);
110 if (b->projected_quad.Contains(aPoints[i]))
111 overlap_points.push_back(aPoints[i]);
114 // Check all the edges of one layer for intersection with the other layer's
117 for (int ea = 0; ea < 4; ++ea)
118 for (int eb = 0; eb < 4; ++eb)
119 if (EdgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4],
120 bPoints[eb], bPoints[(eb + 1) % 4],
122 overlap_points.push_back(r);
124 if (overlap_points.empty())
127 // Check the corresponding layer depth value for all overlap points to
128 // determine which layer is in front.
129 float max_positive = 0.f;
130 float max_negative = 0.f;
132 // This flag tracks the existance of a numerically accurate seperation
133 // between two layers. If there is no accurate seperation, the layers
134 // cannot be effectively sorted.
135 bool accurate = false;
137 for (size_t o = 0; o < overlap_points.size(); o++) {
138 float za = a->LayerZFromProjectedPoint(overlap_points[o]);
139 float zb = b->LayerZFromProjectedPoint(overlap_points[o]);
141 // Here we attempt to avoid numeric issues with layers that are too
142 // close together. If we have 2-sided quads that are very close
143 // together then we will draw them in document order to avoid
144 // flickering. The correct solution is for the content maker to turn
145 // on back-face culling or move the quads apart (if they're not two
146 // sides of one object).
147 if (CheckFloatingPointNumericAccuracy(za, zb) > k_layer_epsilon)
150 float diff = za - zb;
151 if (diff > max_positive)
153 if (diff < max_negative)
157 // If we can't tell which should come first, we use document order.
162 std::abs(max_positive) > std::abs(max_negative) ?
163 max_positive : max_negative;
165 // If the results are inconsistent (and the z difference substantial to rule
166 // out numerical errors) then the layers are intersecting. We will still
167 // return an order based on the maximum depth difference but with an edge
168 // weight of zero these layers will get priority if a graph cycle is present
169 // and needs to be broken.
170 if (max_positive > z_threshold && max_negative < -z_threshold)
173 *weight = std::abs(max_diff);
175 // Maintain relative order if the layers have the same depth at all
176 // intersection points.
183 LayerShape::LayerShape() {}
185 LayerShape::LayerShape(float width,
187 const gfx::Transform& draw_transform) {
188 gfx::QuadF layer_quad(gfx::RectF(0.f, 0.f, width, height));
190 // Compute the projection of the layer quad onto the z = 0 plane.
192 gfx::PointF clipped_quad[8];
193 int num_vertices_in_clipped_quad;
194 MathUtil::MapClippedQuad(draw_transform,
197 &num_vertices_in_clipped_quad);
199 if (num_vertices_in_clipped_quad < 3) {
200 projected_bounds = gfx::RectF();
205 MathUtil::ComputeEnclosingRectOfVertices(clipped_quad,
206 num_vertices_in_clipped_quad);
208 // NOTE: it will require very significant refactoring and overhead to deal
209 // with generalized polygons or multiple quads per layer here. For the sake of
210 // layer sorting it is equally correct to take a subsection of the polygon
211 // that can be made into a quad. This will only be incorrect in the case of
212 // intersecting layers, which are not supported yet anyway.
213 projected_quad.set_p1(clipped_quad[0]);
214 projected_quad.set_p2(clipped_quad[1]);
215 projected_quad.set_p3(clipped_quad[2]);
216 if (num_vertices_in_clipped_quad >= 4) {
217 projected_quad.set_p4(clipped_quad[3]);
219 // This will be a degenerate quad that is actually a triangle.
220 projected_quad.set_p4(clipped_quad[2]);
223 // Compute the normal of the layer's plane.
224 bool clipped = false;
226 MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 0.f, 0.f), &clipped);
228 MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 1.f, 0.f), &clipped);
230 MathUtil::MapPoint(draw_transform, gfx::Point3F(1.f, 0.f, 0.f), &clipped);
231 // TODO(shawnsingh): Deal with clipping.
232 gfx::Vector3dF c12 = c2 - c1;
233 gfx::Vector3dF c13 = c3 - c1;
234 layer_normal = gfx::CrossProduct(c13, c12);
236 transform_origin = c1;
239 LayerShape::~LayerShape() {}
241 // Returns the Z coordinate of a point on the layer that projects
242 // to point p which lies on the z = 0 plane. It does it by computing the
243 // intersection of a line starting from p along the Z axis and the plane
245 float LayerShape::LayerZFromProjectedPoint(gfx::PointF p) const {
246 gfx::Vector3dF z_axis(0.f, 0.f, 1.f);
247 gfx::Vector3dF w = gfx::Point3F(p) - transform_origin;
249 float d = gfx::DotProduct(layer_normal, z_axis);
250 float n = -gfx::DotProduct(layer_normal, w);
252 // Check if layer is parallel to the z = 0 axis which will make it
253 // invisible and hence returning zero is fine.
257 // The intersection point would be given by:
258 // p + (n / d) * u but since we are only interested in the
259 // z coordinate and p's z coord is zero, all we need is the value of n/d.
263 void LayerSorter::CreateGraphNodes(LayerImplList::iterator first,
264 LayerImplList::iterator last) {
265 DVLOG(2) << "Creating graph nodes:";
266 float min_z = FLT_MAX;
267 float max_z = -FLT_MAX;
268 for (LayerImplList::const_iterator it = first; it < last; it++) {
269 nodes_.push_back(GraphNode(*it));
270 GraphNode& node = nodes_.at(nodes_.size() - 1);
271 RenderSurfaceImpl* render_surface = node.layer->render_surface();
272 if (!node.layer->DrawsContent() && !render_surface)
275 DVLOG(2) << "Layer " << node.layer->id() <<
276 " (" << node.layer->bounds().width() <<
277 " x " << node.layer->bounds().height() << ")";
279 gfx::Transform draw_transform;
280 float layer_width, layer_height;
281 if (render_surface) {
282 draw_transform = render_surface->draw_transform();
283 layer_width = render_surface->content_rect().width();
284 layer_height = render_surface->content_rect().height();
286 draw_transform = node.layer->draw_transform();
287 layer_width = node.layer->content_bounds().width();
288 layer_height = node.layer->content_bounds().height();
291 node.shape = LayerShape(layer_width, layer_height, draw_transform);
293 max_z = std::max(max_z, node.shape.transform_origin.z());
294 min_z = std::min(min_z, node.shape.transform_origin.z());
297 z_range_ = std::abs(max_z - min_z);
300 void LayerSorter::CreateGraphEdges() {
301 DVLOG(2) << "Edges:";
302 // Fraction of the total z_range below which z differences
303 // are not considered reliable.
304 const float z_threshold_factor = 0.01f;
305 float z_threshold = z_range_ * z_threshold_factor;
307 for (size_t na = 0; na < nodes_.size(); na++) {
308 GraphNode& node_a = nodes_[na];
309 if (!node_a.layer->DrawsContent() && !node_a.layer->render_surface())
311 for (size_t nb = na + 1; nb < nodes_.size(); nb++) {
312 GraphNode& node_b = nodes_[nb];
313 if (!node_b.layer->DrawsContent() && !node_b.layer->render_surface())
316 ABCompareResult overlap_result = CheckOverlap(&node_a.shape,
320 GraphNode* start_node = NULL;
321 GraphNode* end_node = NULL;
322 if (overlap_result == ABeforeB) {
323 start_node = &node_a;
325 } else if (overlap_result == BBeforeA) {
326 start_node = &node_b;
331 DVLOG(2) << start_node->layer->id() << " -> " << end_node->layer->id();
332 edges_.push_back(GraphEdge(start_node, end_node, weight));
337 for (size_t i = 0; i < edges_.size(); i++) {
338 GraphEdge& edge = edges_[i];
339 active_edges_[&edge] = &edge;
340 edge.from->outgoing.push_back(&edge);
341 edge.to->incoming.push_back(&edge);
342 edge.to->incoming_edge_weight += edge.weight;
346 // Finds and removes an edge from the list by doing a swap with the
347 // last element of the list.
348 void LayerSorter::RemoveEdgeFromList(GraphEdge* edge,
349 std::vector<GraphEdge*>* list) {
350 std::vector<GraphEdge*>::iterator iter =
351 std::find(list->begin(), list->end(), edge);
352 DCHECK(iter != list->end());
356 // Sorts the given list of layers such that they can be painted in a
357 // back-to-front order. Sorting produces correct results for non-intersecting
358 // layers that don't have cyclical order dependencies. Cycles and intersections
359 // are broken (somewhat) aribtrarily. Sorting of layers is done via a
360 // topological sort of a directed graph whose nodes are the layers themselves.
361 // An edge from node A to node B signifies that layer A needs to be drawn before
362 // layer B. If A and B have no dependency between each other, then we preserve
363 // the ordering of those layers as they were in the original list.
365 // The draw order between two layers is determined by projecting the two
366 // triangles making up each layer quad to the Z = 0 plane, finding points of
367 // intersection between the triangles and backprojecting those points to the
368 // plane of the layer to determine the corresponding Z coordinate. The layer
369 // with the lower Z coordinate (farther from the eye) needs to be rendered
372 // If the layer projections don't intersect, then no edges (dependencies) are
373 // created between them in the graph. HOWEVER, in this case we still need to
374 // preserve the ordering of the original list of layers, since that list should
375 // already have proper z-index ordering of layers.
377 void LayerSorter::Sort(LayerImplList::iterator first,
378 LayerImplList::iterator last) {
379 DVLOG(2) << "Sorting start ----";
380 CreateGraphNodes(first, last);
384 std::vector<GraphNode*> sorted_list;
385 std::deque<GraphNode*> no_incoming_edge_node_list;
387 // Find all the nodes that don't have incoming edges.
388 for (NodeList::iterator la = nodes_.begin(); la < nodes_.end(); la++) {
389 if (!la->incoming.size())
390 no_incoming_edge_node_list.push_back(&(*la));
393 DVLOG(2) << "Sorted list: ";
394 while (active_edges_.size() || no_incoming_edge_node_list.size()) {
395 while (no_incoming_edge_node_list.size()) {
396 // It is necessary to preserve the existing ordering of layers, when there
397 // are no explicit dependencies (because this existing ordering has
398 // correct z-index/layout ordering). To preserve this ordering, we process
399 // Nodes in the same order that they were added to the list.
400 GraphNode* from_node = no_incoming_edge_node_list.front();
401 no_incoming_edge_node_list.pop_front();
403 // Add it to the final list.
404 sorted_list.push_back(from_node);
406 DVLOG(2) << from_node->layer->id() << ", ";
408 // Remove all its outgoing edges from the graph.
409 for (size_t i = 0; i < from_node->outgoing.size(); i++) {
410 GraphEdge* outgoing_edge = from_node->outgoing[i];
412 active_edges_.erase(outgoing_edge);
413 RemoveEdgeFromList(outgoing_edge, &outgoing_edge->to->incoming);
414 outgoing_edge->to->incoming_edge_weight -= outgoing_edge->weight;
416 if (!outgoing_edge->to->incoming.size())
417 no_incoming_edge_node_list.push_back(outgoing_edge->to);
419 from_node->outgoing.clear();
422 if (!active_edges_.size())
425 // If there are still active edges but the list of nodes without incoming
426 // edges is empty then we have run into a cycle. Break the cycle by finding
427 // the node with the smallest overall incoming edge weight and use it. This
428 // will favor nodes that have zero-weight incoming edges i.e. layers that
429 // are being occluded by a layer that intersects them.
430 float min_incoming_edge_weight = FLT_MAX;
431 GraphNode* next_node = NULL;
432 for (size_t i = 0; i < nodes_.size(); i++) {
433 if (nodes_[i].incoming.size() &&
434 nodes_[i].incoming_edge_weight < min_incoming_edge_weight) {
435 min_incoming_edge_weight = nodes_[i].incoming_edge_weight;
436 next_node = &nodes_[i];
440 // Remove all its incoming edges.
441 for (size_t e = 0; e < next_node->incoming.size(); e++) {
442 GraphEdge* incoming_edge = next_node->incoming[e];
444 active_edges_.erase(incoming_edge);
445 RemoveEdgeFromList(incoming_edge, &incoming_edge->from->outgoing);
447 next_node->incoming.clear();
448 next_node->incoming_edge_weight = 0.f;
449 no_incoming_edge_node_list.push_back(next_node);
450 DVLOG(2) << "Breaking cycle by cleaning up incoming edges from " <<
451 next_node->layer->id() <<
452 " (weight = " << min_incoming_edge_weight << ")";
455 // Note: The original elements of the list are in no danger of having their
456 // ref count go to zero here as they are all nodes of the layer hierarchy and
457 // are kept alive by their parent nodes.
459 for (LayerImplList::iterator it = first; it < last; it++)
460 *it = sorted_list[count++]->layer;
462 DVLOG(2) << "Sorting end ----";
466 active_edges_.clear();