| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 17 namespace 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. | |
| 24 const float k_layer_epsilon = 1e-4f; | |
| 25 | |
| 26 inline static float PerpProduct(const gfx::Vector2dF& u, | |
| 27 const gfx::Vector2dF& v) { | |
| 28 return u.x() * v.y() - u.y() * v.x(); | |
| 29 } | |
| 30 | |
| 31 // Tests if two edges defined by their endpoints (a,b) and (c,d) intersect. | |
| 32 // Returns true and the point of intersection if they do and false otherwise. | |
| 33 static bool EdgeEdgeTest(const gfx::PointF& a, | |
| 34 const gfx::PointF& b, | |
| 35 const gfx::PointF& c, | |
| 36 const gfx::PointF& d, | |
| 37 gfx::PointF* r) { | |
| 38 gfx::Vector2dF u = b - a; | |
| 39 gfx::Vector2dF v = d - c; | |
| 40 gfx::Vector2dF w = a - c; | |
| 41 | |
| 42 float denom = PerpProduct(u, v); | |
| 43 | |
| 44 // If denom == 0 then the edges are parallel. While they could be overlapping | |
| 45 // we don't bother to check here as the we'll find their intersections from | |
| 46 // the corner to quad tests. | |
| 47 if (!denom) | |
| 48 return false; | |
| 49 | |
| 50 float s = PerpProduct(v, w) / denom; | |
| 51 if (s < 0.f || s > 1.f) | |
| 52 return false; | |
| 53 | |
| 54 float t = PerpProduct(u, w) / denom; | |
| 55 if (t < 0.f || t > 1.f) | |
| 56 return false; | |
| 57 | |
| 58 u.Scale(s); | |
| 59 *r = a + u; | |
| 60 return true; | |
| 61 } | |
| 62 | |
| 63 GraphNode::GraphNode(LayerImpl* layer_impl) | |
| 64 : layer(layer_impl), | |
| 65 incoming_edge_weight(0.f) {} | |
| 66 | |
| 67 GraphNode::~GraphNode() {} | |
| 68 | |
| 69 LayerSorter::LayerSorter() | |
| 70 : z_range_(0.f) {} | |
| 71 | |
| 72 LayerSorter::~LayerSorter() {} | |
| 73 | |
| 74 static float CheckFloatingPointNumericAccuracy(float a, float b) { | |
| 75 float abs_dif = std::abs(b - a); | |
| 76 float abs_max = std::max(std::abs(b), std::abs(a)); | |
| 77 // Check to see if we've got a result with a reasonable amount of error. | |
| 78 return abs_dif / abs_max; | |
| 79 } | |
| 80 | |
| 81 // Checks whether layer "a" draws on top of layer "b". The weight value returned | |
| 82 // is an indication of the maximum z-depth difference between the layers or zero | |
| 83 // if the layers are found to be intesecting (some features are in front and | |
| 84 // some are behind). | |
| 85 LayerSorter::ABCompareResult LayerSorter::CheckOverlap(LayerShape* a, | |
| 86 LayerShape* b, | |
| 87 float z_threshold, | |
| 88 float* weight) { | |
| 89 *weight = 0.f; | |
| 90 | |
| 91 // Early out if the projected bounds don't overlap. | |
| 92 if (!a->projected_bounds.Intersects(b->projected_bounds)) | |
| 93 return NONE; | |
| 94 | |
| 95 gfx::PointF aPoints[4] = { a->projected_quad.p1(), | |
| 96 a->projected_quad.p2(), | |
| 97 a->projected_quad.p3(), | |
| 98 a->projected_quad.p4() }; | |
| 99 gfx::PointF bPoints[4] = { b->projected_quad.p1(), | |
| 100 b->projected_quad.p2(), | |
| 101 b->projected_quad.p3(), | |
| 102 b->projected_quad.p4() }; | |
| 103 | |
| 104 // Make a list of points that inside both layer quad projections. | |
| 105 std::vector<gfx::PointF> overlap_points; | |
| 106 | |
| 107 // Check all four corners of one layer against the other layer's quad. | |
| 108 for (int i = 0; i < 4; ++i) { | |
| 109 if (a->projected_quad.Contains(bPoints[i])) | |
| 110 overlap_points.push_back(bPoints[i]); | |
| 111 if (b->projected_quad.Contains(aPoints[i])) | |
| 112 overlap_points.push_back(aPoints[i]); | |
| 113 } | |
| 114 | |
| 115 // Check all the edges of one layer for intersection with the other layer's | |
| 116 // edges. | |
| 117 gfx::PointF r; | |
| 118 for (int ea = 0; ea < 4; ++ea) | |
| 119 for (int eb = 0; eb < 4; ++eb) | |
| 120 if (EdgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4], | |
| 121 bPoints[eb], bPoints[(eb + 1) % 4], | |
| 122 &r)) | |
| 123 overlap_points.push_back(r); | |
| 124 | |
| 125 if (overlap_points.empty()) | |
| 126 return NONE; | |
| 127 | |
| 128 // Check the corresponding layer depth value for all overlap points to | |
| 129 // determine which layer is in front. | |
| 130 float max_positive = 0.f; | |
| 131 float max_negative = 0.f; | |
| 132 | |
| 133 // This flag tracks the existance of a numerically accurate seperation | |
| 134 // between two layers. If there is no accurate seperation, the layers | |
| 135 // cannot be effectively sorted. | |
| 136 bool accurate = false; | |
| 137 | |
| 138 for (size_t o = 0; o < overlap_points.size(); o++) { | |
| 139 float za = a->LayerZFromProjectedPoint(overlap_points[o]); | |
| 140 float zb = b->LayerZFromProjectedPoint(overlap_points[o]); | |
| 141 | |
| 142 // Here we attempt to avoid numeric issues with layers that are too | |
| 143 // close together. If we have 2-sided quads that are very close | |
| 144 // together then we will draw them in document order to avoid | |
| 145 // flickering. The correct solution is for the content maker to turn | |
| 146 // on back-face culling or move the quads apart (if they're not two | |
| 147 // sides of one object). | |
| 148 if (CheckFloatingPointNumericAccuracy(za, zb) > k_layer_epsilon) | |
| 149 accurate = true; | |
| 150 | |
| 151 float diff = za - zb; | |
| 152 if (diff > max_positive) | |
| 153 max_positive = diff; | |
| 154 if (diff < max_negative) | |
| 155 max_negative = diff; | |
| 156 } | |
| 157 | |
| 158 // If we can't tell which should come first, we use document order. | |
| 159 if (!accurate) | |
| 160 return A_BEFORE_B; | |
| 161 | |
| 162 float max_diff = | |
| 163 std::abs(max_positive) > std::abs(max_negative) ? | |
| 164 max_positive : max_negative; | |
| 165 | |
| 166 // If the results are inconsistent (and the z difference substantial to rule | |
| 167 // out numerical errors) then the layers are intersecting. We will still | |
| 168 // return an order based on the maximum depth difference but with an edge | |
| 169 // weight of zero these layers will get priority if a graph cycle is present | |
| 170 // and needs to be broken. | |
| 171 if (max_positive > z_threshold && max_negative < -z_threshold) | |
| 172 *weight = 0.f; | |
| 173 else | |
| 174 *weight = std::abs(max_diff); | |
| 175 | |
| 176 // Maintain relative order if the layers have the same depth at all | |
| 177 // intersection points. | |
| 178 if (max_diff <= 0.f) | |
| 179 return A_BEFORE_B; | |
| 180 | |
| 181 return B_BEFORE_A; | |
| 182 } | |
| 183 | |
| 184 LayerShape::LayerShape() {} | |
| 185 | |
| 186 LayerShape::LayerShape(float width, | |
| 187 float height, | |
| 188 const gfx::Transform& draw_transform) { | |
| 189 gfx::QuadF layer_quad(gfx::RectF(0.f, 0.f, width, height)); | |
| 190 | |
| 191 // Compute the projection of the layer quad onto the z = 0 plane. | |
| 192 | |
| 193 gfx::PointF clipped_quad[8]; | |
| 194 int num_vertices_in_clipped_quad; | |
| 195 MathUtil::MapClippedQuad(draw_transform, | |
| 196 layer_quad, | |
| 197 clipped_quad, | |
| 198 &num_vertices_in_clipped_quad); | |
| 199 | |
| 200 if (num_vertices_in_clipped_quad < 3) { | |
| 201 projected_bounds = gfx::RectF(); | |
| 202 return; | |
| 203 } | |
| 204 | |
| 205 projected_bounds = | |
| 206 MathUtil::ComputeEnclosingRectOfVertices(clipped_quad, | |
| 207 num_vertices_in_clipped_quad); | |
| 208 | |
| 209 // NOTE: it will require very significant refactoring and overhead to deal | |
| 210 // with generalized polygons or multiple quads per layer here. For the sake of | |
| 211 // layer sorting it is equally correct to take a subsection of the polygon | |
| 212 // that can be made into a quad. This will only be incorrect in the case of | |
| 213 // intersecting layers, which are not supported yet anyway. | |
| 214 projected_quad.set_p1(clipped_quad[0]); | |
| 215 projected_quad.set_p2(clipped_quad[1]); | |
| 216 projected_quad.set_p3(clipped_quad[2]); | |
| 217 if (num_vertices_in_clipped_quad >= 4) { | |
| 218 projected_quad.set_p4(clipped_quad[3]); | |
| 219 } else { | |
| 220 // This will be a degenerate quad that is actually a triangle. | |
| 221 projected_quad.set_p4(clipped_quad[2]); | |
| 222 } | |
| 223 | |
| 224 // Compute the normal of the layer's plane. | |
| 225 bool clipped = false; | |
| 226 gfx::Point3F c1 = | |
| 227 MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 0.f, 0.f), &clipped); | |
| 228 gfx::Point3F c2 = | |
| 229 MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 1.f, 0.f), &clipped); | |
| 230 gfx::Point3F c3 = | |
| 231 MathUtil::MapPoint(draw_transform, gfx::Point3F(1.f, 0.f, 0.f), &clipped); | |
| 232 // TODO(shawnsingh): Deal with clipping. | |
| 233 gfx::Vector3dF c12 = c2 - c1; | |
| 234 gfx::Vector3dF c13 = c3 - c1; | |
| 235 layer_normal = gfx::CrossProduct(c13, c12); | |
| 236 | |
| 237 transform_origin = c1; | |
| 238 } | |
| 239 | |
| 240 LayerShape::~LayerShape() {} | |
| 241 | |
| 242 // Returns the Z coordinate of a point on the layer that projects | |
| 243 // to point p which lies on the z = 0 plane. It does it by computing the | |
| 244 // intersection of a line starting from p along the Z axis and the plane | |
| 245 // of the layer. | |
| 246 float LayerShape::LayerZFromProjectedPoint(const gfx::PointF& p) const { | |
| 247 gfx::Vector3dF z_axis(0.f, 0.f, 1.f); | |
| 248 gfx::Vector3dF w = gfx::Point3F(p) - transform_origin; | |
| 249 | |
| 250 float d = gfx::DotProduct(layer_normal, z_axis); | |
| 251 float n = -gfx::DotProduct(layer_normal, w); | |
| 252 | |
| 253 // Check if layer is parallel to the z = 0 axis which will make it | |
| 254 // invisible and hence returning zero is fine. | |
| 255 if (!d) | |
| 256 return 0.f; | |
| 257 | |
| 258 // The intersection point would be given by: | |
| 259 // p + (n / d) * u but since we are only interested in the | |
| 260 // z coordinate and p's z coord is zero, all we need is the value of n/d. | |
| 261 return n / d; | |
| 262 } | |
| 263 | |
| 264 void LayerSorter::CreateGraphNodes(LayerImplList::iterator first, | |
| 265 LayerImplList::iterator last) { | |
| 266 DVLOG(2) << "Creating graph nodes:"; | |
| 267 float min_z = FLT_MAX; | |
| 268 float max_z = -FLT_MAX; | |
| 269 for (LayerImplList::const_iterator it = first; it < last; it++) { | |
| 270 nodes_.push_back(GraphNode(*it)); | |
| 271 GraphNode& node = nodes_.at(nodes_.size() - 1); | |
| 272 RenderSurfaceImpl* render_surface = node.layer->render_surface(); | |
| 273 if (!node.layer->DrawsContent() && !render_surface) | |
| 274 continue; | |
| 275 | |
| 276 DVLOG(2) << "Layer " << node.layer->id() << | |
| 277 " (" << node.layer->bounds().width() << | |
| 278 " x " << node.layer->bounds().height() << ")"; | |
| 279 | |
| 280 gfx::Transform draw_transform; | |
| 281 float layer_width, layer_height; | |
| 282 if (render_surface) { | |
| 283 draw_transform = render_surface->draw_transform(); | |
| 284 layer_width = render_surface->content_rect().width(); | |
| 285 layer_height = render_surface->content_rect().height(); | |
| 286 } else { | |
| 287 draw_transform = node.layer->draw_transform(); | |
| 288 layer_width = node.layer->content_bounds().width(); | |
| 289 layer_height = node.layer->content_bounds().height(); | |
| 290 } | |
| 291 | |
| 292 node.shape = LayerShape(layer_width, layer_height, draw_transform); | |
| 293 | |
| 294 max_z = std::max(max_z, node.shape.transform_origin.z()); | |
| 295 min_z = std::min(min_z, node.shape.transform_origin.z()); | |
| 296 } | |
| 297 | |
| 298 z_range_ = std::abs(max_z - min_z); | |
| 299 } | |
| 300 | |
| 301 void LayerSorter::CreateGraphEdges() { | |
| 302 DVLOG(2) << "Edges:"; | |
| 303 // Fraction of the total z_range below which z differences | |
| 304 // are not considered reliable. | |
| 305 const float z_threshold_factor = 0.01f; | |
| 306 float z_threshold = z_range_ * z_threshold_factor; | |
| 307 | |
| 308 for (size_t na = 0; na < nodes_.size(); na++) { | |
| 309 GraphNode& node_a = nodes_[na]; | |
| 310 if (!node_a.layer->DrawsContent() && !node_a.layer->render_surface()) | |
| 311 continue; | |
| 312 for (size_t nb = na + 1; nb < nodes_.size(); nb++) { | |
| 313 GraphNode& node_b = nodes_[nb]; | |
| 314 if (!node_b.layer->DrawsContent() && !node_b.layer->render_surface()) | |
| 315 continue; | |
| 316 float weight = 0.f; | |
| 317 ABCompareResult overlap_result = CheckOverlap(&node_a.shape, | |
| 318 &node_b.shape, | |
| 319 z_threshold, | |
| 320 &weight); | |
| 321 GraphNode* start_node = NULL; | |
| 322 GraphNode* end_node = NULL; | |
| 323 if (overlap_result == A_BEFORE_B) { | |
| 324 start_node = &node_a; | |
| 325 end_node = &node_b; | |
| 326 } else if (overlap_result == B_BEFORE_A) { | |
| 327 start_node = &node_b; | |
| 328 end_node = &node_a; | |
| 329 } | |
| 330 | |
| 331 if (start_node) { | |
| 332 DVLOG(2) << start_node->layer->id() << " -> " << end_node->layer->id(); | |
| 333 edges_.push_back(GraphEdge(start_node, end_node, weight)); | |
| 334 } | |
| 335 } | |
| 336 } | |
| 337 | |
| 338 for (size_t i = 0; i < edges_.size(); i++) { | |
| 339 GraphEdge& edge = edges_[i]; | |
| 340 active_edges_[&edge] = &edge; | |
| 341 edge.from->outgoing.push_back(&edge); | |
| 342 edge.to->incoming.push_back(&edge); | |
| 343 edge.to->incoming_edge_weight += edge.weight; | |
| 344 } | |
| 345 } | |
| 346 | |
| 347 // Finds and removes an edge from the list by doing a swap with the | |
| 348 // last element of the list. | |
| 349 void LayerSorter::RemoveEdgeFromList(GraphEdge* edge, | |
| 350 std::vector<GraphEdge*>* list) { | |
| 351 std::vector<GraphEdge*>::iterator iter = | |
| 352 std::find(list->begin(), list->end(), edge); | |
| 353 DCHECK(iter != list->end()); | |
| 354 list->erase(iter); | |
| 355 } | |
| 356 | |
| 357 // Sorts the given list of layers such that they can be painted in a | |
| 358 // back-to-front order. Sorting produces correct results for non-intersecting | |
| 359 // layers that don't have cyclical order dependencies. Cycles and intersections | |
| 360 // are broken (somewhat) aribtrarily. Sorting of layers is done via a | |
| 361 // topological sort of a directed graph whose nodes are the layers themselves. | |
| 362 // An edge from node A to node B signifies that layer A needs to be drawn before | |
| 363 // layer B. If A and B have no dependency between each other, then we preserve | |
| 364 // the ordering of those layers as they were in the original list. | |
| 365 // | |
| 366 // The draw order between two layers is determined by projecting the two | |
| 367 // triangles making up each layer quad to the Z = 0 plane, finding points of | |
| 368 // intersection between the triangles and backprojecting those points to the | |
| 369 // plane of the layer to determine the corresponding Z coordinate. The layer | |
| 370 // with the lower Z coordinate (farther from the eye) needs to be rendered | |
| 371 // first. | |
| 372 // | |
| 373 // If the layer projections don't intersect, then no edges (dependencies) are | |
| 374 // created between them in the graph. HOWEVER, in this case we still need to | |
| 375 // preserve the ordering of the original list of layers, since that list should | |
| 376 // already have proper z-index ordering of layers. | |
| 377 // | |
| 378 void LayerSorter::Sort(LayerImplList::iterator first, | |
| 379 LayerImplList::iterator last) { | |
| 380 DVLOG(2) << "Sorting start ----"; | |
| 381 CreateGraphNodes(first, last); | |
| 382 | |
| 383 CreateGraphEdges(); | |
| 384 | |
| 385 std::vector<GraphNode*> sorted_list; | |
| 386 std::deque<GraphNode*> no_incoming_edge_node_list; | |
| 387 | |
| 388 // Find all the nodes that don't have incoming edges. | |
| 389 for (NodeList::iterator la = nodes_.begin(); la < nodes_.end(); la++) { | |
| 390 if (!la->incoming.size()) | |
| 391 no_incoming_edge_node_list.push_back(&(*la)); | |
| 392 } | |
| 393 | |
| 394 DVLOG(2) << "Sorted list: "; | |
| 395 while (active_edges_.size() || no_incoming_edge_node_list.size()) { | |
| 396 while (no_incoming_edge_node_list.size()) { | |
| 397 // It is necessary to preserve the existing ordering of layers, when there | |
| 398 // are no explicit dependencies (because this existing ordering has | |
| 399 // correct z-index/layout ordering). To preserve this ordering, we process | |
| 400 // Nodes in the same order that they were added to the list. | |
| 401 GraphNode* from_node = no_incoming_edge_node_list.front(); | |
| 402 no_incoming_edge_node_list.pop_front(); | |
| 403 | |
| 404 // Add it to the final list. | |
| 405 sorted_list.push_back(from_node); | |
| 406 | |
| 407 DVLOG(2) << from_node->layer->id() << ", "; | |
| 408 | |
| 409 // Remove all its outgoing edges from the graph. | |
| 410 for (size_t i = 0; i < from_node->outgoing.size(); i++) { | |
| 411 GraphEdge* outgoing_edge = from_node->outgoing[i]; | |
| 412 | |
| 413 active_edges_.erase(outgoing_edge); | |
| 414 RemoveEdgeFromList(outgoing_edge, &outgoing_edge->to->incoming); | |
| 415 outgoing_edge->to->incoming_edge_weight -= outgoing_edge->weight; | |
| 416 | |
| 417 if (!outgoing_edge->to->incoming.size()) | |
| 418 no_incoming_edge_node_list.push_back(outgoing_edge->to); | |
| 419 } | |
| 420 from_node->outgoing.clear(); | |
| 421 } | |
| 422 | |
| 423 if (!active_edges_.size()) | |
| 424 break; | |
| 425 | |
| 426 // If there are still active edges but the list of nodes without incoming | |
| 427 // edges is empty then we have run into a cycle. Break the cycle by finding | |
| 428 // the node with the smallest overall incoming edge weight and use it. This | |
| 429 // will favor nodes that have zero-weight incoming edges i.e. layers that | |
| 430 // are being occluded by a layer that intersects them. | |
| 431 float min_incoming_edge_weight = FLT_MAX; | |
| 432 GraphNode* next_node = NULL; | |
| 433 for (size_t i = 0; i < nodes_.size(); i++) { | |
| 434 if (nodes_[i].incoming.size() && | |
| 435 nodes_[i].incoming_edge_weight < min_incoming_edge_weight) { | |
| 436 min_incoming_edge_weight = nodes_[i].incoming_edge_weight; | |
| 437 next_node = &nodes_[i]; | |
| 438 } | |
| 439 } | |
| 440 DCHECK(next_node); | |
| 441 // Remove all its incoming edges. | |
| 442 for (size_t e = 0; e < next_node->incoming.size(); e++) { | |
| 443 GraphEdge* incoming_edge = next_node->incoming[e]; | |
| 444 | |
| 445 active_edges_.erase(incoming_edge); | |
| 446 RemoveEdgeFromList(incoming_edge, &incoming_edge->from->outgoing); | |
| 447 } | |
| 448 next_node->incoming.clear(); | |
| 449 next_node->incoming_edge_weight = 0.f; | |
| 450 no_incoming_edge_node_list.push_back(next_node); | |
| 451 DVLOG(2) << "Breaking cycle by cleaning up incoming edges from " << | |
| 452 next_node->layer->id() << | |
| 453 " (weight = " << min_incoming_edge_weight << ")"; | |
| 454 } | |
| 455 | |
| 456 // Note: The original elements of the list are in no danger of having their | |
| 457 // ref count go to zero here as they are all nodes of the layer hierarchy and | |
| 458 // are kept alive by their parent nodes. | |
| 459 int count = 0; | |
| 460 for (LayerImplList::iterator it = first; it < last; it++) | |
| 461 *it = sorted_list[count++]->layer; | |
| 462 | |
| 463 DVLOG(2) << "Sorting end ----"; | |
| 464 | |
| 465 nodes_.clear(); | |
| 466 edges_.clear(); | |
| 467 active_edges_.clear(); | |
| 468 } | |
| 469 | |
| 470 } // namespace cc | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1001833005:
Update from https://crrev.com/320343 (Closed)
Base URL: git@github.com:domokit/mojo.git@master