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. 4 5#include "cc/trees/layer_sorter.h" 6 7#include <algorithm> 8#include <deque> 9#include <limits> 10#include <vector> 11 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" 16 17namespace cc { 18 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. 24const float k_layer_epsilon = 1e-4f; 25 26inline static float PerpProduct(gfx::Vector2dF u, gfx::Vector2dF v) { 27 return u.x() * v.y() - u.y() * v.x(); 28} 29 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. 32static bool EdgeEdgeTest(gfx::PointF a, 33 gfx::PointF b, 34 gfx::PointF c, 35 gfx::PointF d, 36 gfx::PointF* r) { 37 gfx::Vector2dF u = b - a; 38 gfx::Vector2dF v = d - c; 39 gfx::Vector2dF w = a - c; 40 41 float denom = PerpProduct(u, v); 42 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. 46 if (!denom) 47 return false; 48 49 float s = PerpProduct(v, w) / denom; 50 if (s < 0.f || s > 1.f) 51 return false; 52 53 float t = PerpProduct(u, w) / denom; 54 if (t < 0.f || t > 1.f) 55 return false; 56 57 u.Scale(s); 58 *r = a + u; 59 return true; 60} 61 62GraphNode::GraphNode(LayerImpl* layer_impl) 63 : layer(layer_impl), 64 incoming_edge_weight(0.f) {} 65 66GraphNode::~GraphNode() {} 67 68LayerSorter::LayerSorter() 69 : z_range_(0.f) {} 70 71LayerSorter::~LayerSorter() {} 72 73static 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; 78} 79 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 83// some are behind). 84LayerSorter::ABCompareResult LayerSorter::CheckOverlap(LayerShape* a, 85 LayerShape* b, 86 float z_threshold, 87 float* weight) { 88 *weight = 0.f; 89 90 // Early out if the projected bounds don't overlap. 91 if (!a->projected_bounds.Intersects(b->projected_bounds)) 92 return None; 93 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() }; 102 103 // Make a list of points that inside both layer quad projections. 104 std::vector<gfx::PointF> overlap_points; 105 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]); 112 } 113 114 // Check all the edges of one layer for intersection with the other layer's 115 // edges. 116 gfx::PointF r; 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], 121 &r)) 122 overlap_points.push_back(r); 123 124 if (overlap_points.empty()) 125 return None; 126 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; 131 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; 136 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]); 140 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) 148 accurate = true; 149 150 float diff = za - zb; 151 if (diff > max_positive) 152 max_positive = diff; 153 if (diff < max_negative) 154 max_negative = diff; 155 } 156 157 // If we can't tell which should come first, we use document order. 158 if (!accurate) 159 return ABeforeB; 160 161 float max_diff = 162 std::abs(max_positive) > std::abs(max_negative) ? 163 max_positive : max_negative; 164 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) 171 *weight = 0.f; 172 else 173 *weight = std::abs(max_diff); 174 175 // Maintain relative order if the layers have the same depth at all 176 // intersection points. 177 if (max_diff <= 0.f) 178 return ABeforeB; 179 180 return BBeforeA; 181} 182 183LayerShape::LayerShape() {} 184 185LayerShape::LayerShape(float width, 186 float height, 187 const gfx::Transform& draw_transform) { 188 gfx::QuadF layer_quad(gfx::RectF(0.f, 0.f, width, height)); 189 190 // Compute the projection of the layer quad onto the z = 0 plane. 191 192 gfx::PointF clipped_quad[8]; 193 int num_vertices_in_clipped_quad; 194 MathUtil::MapClippedQuad(draw_transform, 195 layer_quad, 196 clipped_quad, 197 &num_vertices_in_clipped_quad); 198 199 if (num_vertices_in_clipped_quad < 3) { 200 projected_bounds = gfx::RectF(); 201 return; 202 } 203 204 projected_bounds = 205 MathUtil::ComputeEnclosingRectOfVertices(clipped_quad, 206 num_vertices_in_clipped_quad); 207 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]); 218 } else { 219 // This will be a degenerate quad that is actually a triangle. 220 projected_quad.set_p4(clipped_quad[2]); 221 } 222 223 // Compute the normal of the layer's plane. 224 bool clipped = false; 225 gfx::Point3F c1 = 226 MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 0.f, 0.f), &clipped); 227 gfx::Point3F c2 = 228 MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 1.f, 0.f), &clipped); 229 gfx::Point3F c3 = 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); 235 236 transform_origin = c1; 237} 238 239LayerShape::~LayerShape() {} 240 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 244// of the layer. 245float 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; 248 249 float d = gfx::DotProduct(layer_normal, z_axis); 250 float n = -gfx::DotProduct(layer_normal, w); 251 252 // Check if layer is parallel to the z = 0 axis which will make it 253 // invisible and hence returning zero is fine. 254 if (!d) 255 return 0.f; 256 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. 260 return n / d; 261} 262 263void 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) 273 continue; 274 275 DVLOG(2) << "Layer " << node.layer->id() << 276 " (" << node.layer->bounds().width() << 277 " x " << node.layer->bounds().height() << ")"; 278 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(); 285 } else { 286 draw_transform = node.layer->draw_transform(); 287 layer_width = node.layer->content_bounds().width(); 288 layer_height = node.layer->content_bounds().height(); 289 } 290 291 node.shape = LayerShape(layer_width, layer_height, draw_transform); 292 293 max_z = std::max(max_z, node.shape.transform_origin.z()); 294 min_z = std::min(min_z, node.shape.transform_origin.z()); 295 } 296 297 z_range_ = std::abs(max_z - min_z); 298} 299 300void 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; 306 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()) 310 continue; 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()) 314 continue; 315 float weight = 0.f; 316 ABCompareResult overlap_result = CheckOverlap(&node_a.shape, 317 &node_b.shape, 318 z_threshold, 319 &weight); 320 GraphNode* start_node = NULL; 321 GraphNode* end_node = NULL; 322 if (overlap_result == ABeforeB) { 323 start_node = &node_a; 324 end_node = &node_b; 325 } else if (overlap_result == BBeforeA) { 326 start_node = &node_b; 327 end_node = &node_a; 328 } 329 330 if (start_node) { 331 DVLOG(2) << start_node->layer->id() << " -> " << end_node->layer->id(); 332 edges_.push_back(GraphEdge(start_node, end_node, weight)); 333 } 334 } 335 } 336 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; 343 } 344} 345 346// Finds and removes an edge from the list by doing a swap with the 347// last element of the list. 348void 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()); 353 list->erase(iter); 354} 355 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. 364// 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 370// first. 371// 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. 376// 377void LayerSorter::Sort(LayerImplList::iterator first, 378 LayerImplList::iterator last) { 379 DVLOG(2) << "Sorting start ----"; 380 CreateGraphNodes(first, last); 381 382 CreateGraphEdges(); 383 384 std::vector<GraphNode*> sorted_list; 385 std::deque<GraphNode*> no_incoming_edge_node_list; 386 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)); 391 } 392 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(); 402 403 // Add it to the final list. 404 sorted_list.push_back(from_node); 405 406 DVLOG(2) << from_node->layer->id() << ", "; 407 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]; 411 412 active_edges_.erase(outgoing_edge); 413 RemoveEdgeFromList(outgoing_edge, &outgoing_edge->to->incoming); 414 outgoing_edge->to->incoming_edge_weight -= outgoing_edge->weight; 415 416 if (!outgoing_edge->to->incoming.size()) 417 no_incoming_edge_node_list.push_back(outgoing_edge->to); 418 } 419 from_node->outgoing.clear(); 420 } 421 422 if (!active_edges_.size()) 423 break; 424 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]; 437 } 438 } 439 DCHECK(next_node); 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]; 443 444 active_edges_.erase(incoming_edge); 445 RemoveEdgeFromList(incoming_edge, &incoming_edge->from->outgoing); 446 } 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 << ")"; 453 } 454 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. 458 int count = 0; 459 for (LayerImplList::iterator it = first; it < last; it++) 460 *it = sorted_list[count++]->layer; 461 462 DVLOG(2) << "Sorting end ----"; 463 464 nodes_.clear(); 465 edges_.clear(); 466 active_edges_.clear(); 467} 468 469} // namespace cc 470