| OLD | NEW |
| 1 // Copyright 2011 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "config.h" | 5 #include "config.h" |
| 6 | 6 |
| 7 #include "CCLayerSorter.h" | 7 #include "CCLayerSorter.h" |
| 8 | 8 |
| 9 #include <limits> | |
| 10 | |
| 11 #include "base/logging.h" | |
| 12 #include "CCMathUtil.h" | 9 #include "CCMathUtil.h" |
| 13 #include "CCRenderSurface.h" | 10 #include "CCRenderSurface.h" |
| 11 #include <limits.h> |
| 14 #include <public/WebTransformationMatrix.h> | 12 #include <public/WebTransformationMatrix.h> |
| 15 #include <wtf/Deque.h> | 13 #include <wtf/Deque.h> |
| 16 | 14 |
| 17 using namespace std; | 15 using namespace std; |
| 18 using WebKit::WebTransformationMatrix; | 16 using WebKit::WebTransformationMatrix; |
| 19 | 17 |
| 20 #define SHOW_DEBUG_LOG 0 && !defined(NDEBUG) | 18 #define LOG_CHANNEL_PREFIX Log |
| 19 #define SHOW_DEBUG_LOG 0 |
| 20 |
| 21 #if !defined( NDEBUG ) |
| 22 #if SHOW_DEBUG_LOG |
| 23 static WTFLogChannel LogCCLayerSorter = { 0x00000000, "", WTFLogChannelOn }; |
| 24 #else |
| 25 static WTFLogChannel LogCCLayerSorter = { 0x00000000, "", WTFLogChannelOff }; |
| 26 #endif |
| 27 #endif |
| 21 | 28 |
| 22 namespace cc { | 29 namespace cc { |
| 23 | 30 |
| 24 inline static float perpProduct(const FloatSize& u, const FloatSize& v) | 31 inline static float perpProduct(const FloatSize& u, const FloatSize& v) |
| 25 { | 32 { |
| 26 return u.width() * v.height() - u.height() * v.width(); | 33 return u.width() * v.height() - u.height() * v.width(); |
| 27 } | 34 } |
| 28 | 35 |
| 29 // Tests if two edges defined by their endpoints (a,b) and (c,d) intersect. Retu
rns true and the | 36 // Tests if two edges defined by their endpoints (a,b) and (c,d) intersect. Retu
rns true and the |
| 30 // point of intersection if they do and false otherwise. | 37 // point of intersection if they do and false otherwise. |
| (...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 209 return 0; | 216 return 0; |
| 210 | 217 |
| 211 // The intersection point would be given by: | 218 // The intersection point would be given by: |
| 212 // p + (n / d) * u but since we are only interested in the | 219 // p + (n / d) * u but since we are only interested in the |
| 213 // z coordinate and p's z coord is zero, all we need is the value of n/d. | 220 // z coordinate and p's z coord is zero, all we need is the value of n/d. |
| 214 return n / d; | 221 return n / d; |
| 215 } | 222 } |
| 216 | 223 |
| 217 void CCLayerSorter::createGraphNodes(LayerList::iterator first, LayerList::itera
tor last) | 224 void CCLayerSorter::createGraphNodes(LayerList::iterator first, LayerList::itera
tor last) |
| 218 { | 225 { |
| 219 #if SHOW_DEBUG_LOG | 226 #if !defined( NDEBUG ) |
| 220 DLOG(INFO) << "CCLayerSorter: Creating graph nodes:\n"; | 227 LOG(CCLayerSorter, "Creating graph nodes:\n"); |
| 221 #endif | 228 #endif |
| 222 float minZ = FLT_MAX; | 229 float minZ = FLT_MAX; |
| 223 float maxZ = -FLT_MAX; | 230 float maxZ = -FLT_MAX; |
| 224 for (LayerList::const_iterator it = first; it < last; it++) { | 231 for (LayerList::const_iterator it = first; it < last; it++) { |
| 225 m_nodes.append(GraphNode(*it)); | 232 m_nodes.append(GraphNode(*it)); |
| 226 GraphNode& node = m_nodes.at(m_nodes.size() - 1); | 233 GraphNode& node = m_nodes.at(m_nodes.size() - 1); |
| 227 CCRenderSurface* renderSurface = node.layer->renderSurface(); | 234 CCRenderSurface* renderSurface = node.layer->renderSurface(); |
| 228 if (!node.layer->drawsContent() && !renderSurface) | 235 if (!node.layer->drawsContent() && !renderSurface) |
| 229 continue; | 236 continue; |
| 230 | 237 |
| 231 #if SHOW_DEBUG_LOG | 238 #if !defined( NDEBUG ) |
| 232 DLOG(INFO) << "CCLayerSorter: Layer " << node.layer->id() << " (" << nod
e.layer->bounds().width() << " x " << node.layer->bounds().height() << ")\n"; | 239 LOG(CCLayerSorter, "Layer %d (%d x %d)\n", node.layer->id(), node.layer-
>bounds().width(), node.layer->bounds().height()); |
| 233 #endif | 240 #endif |
| 234 | 241 |
| 235 WebTransformationMatrix drawTransform; | 242 WebTransformationMatrix drawTransform; |
| 236 float layerWidth, layerHeight; | 243 float layerWidth, layerHeight; |
| 237 if (renderSurface) { | 244 if (renderSurface) { |
| 238 drawTransform = renderSurface->drawTransform(); | 245 drawTransform = renderSurface->drawTransform(); |
| 239 layerWidth = renderSurface->contentRect().width(); | 246 layerWidth = renderSurface->contentRect().width(); |
| 240 layerHeight = renderSurface->contentRect().height(); | 247 layerHeight = renderSurface->contentRect().height(); |
| 241 } else { | 248 } else { |
| 242 drawTransform = node.layer->drawTransform(); | 249 drawTransform = node.layer->drawTransform(); |
| 243 layerWidth = node.layer->contentBounds().width(); | 250 layerWidth = node.layer->contentBounds().width(); |
| 244 layerHeight = node.layer->contentBounds().height(); | 251 layerHeight = node.layer->contentBounds().height(); |
| 245 } | 252 } |
| 246 | 253 |
| 247 node.shape = LayerShape(layerWidth, layerHeight, drawTransform); | 254 node.shape = LayerShape(layerWidth, layerHeight, drawTransform); |
| 248 | 255 |
| 249 maxZ = max(maxZ, node.shape.transformOrigin.z()); | 256 maxZ = max(maxZ, node.shape.transformOrigin.z()); |
| 250 minZ = min(minZ, node.shape.transformOrigin.z()); | 257 minZ = min(minZ, node.shape.transformOrigin.z()); |
| 251 } | 258 } |
| 252 | 259 |
| 253 m_zRange = fabsf(maxZ - minZ); | 260 m_zRange = fabsf(maxZ - minZ); |
| 254 } | 261 } |
| 255 | 262 |
| 256 void CCLayerSorter::createGraphEdges() | 263 void CCLayerSorter::createGraphEdges() |
| 257 { | 264 { |
| 258 #if SHOW_DEBUG_LOG | 265 #if !defined( NDEBUG ) |
| 259 DLOG(INFO) << "CCLayerSorter: Edges:\n"; | 266 LOG(CCLayerSorter, "Edges:\n"); |
| 260 #endif | 267 #endif |
| 261 // Fraction of the total zRange below which z differences | 268 // Fraction of the total zRange below which z differences |
| 262 // are not considered reliable. | 269 // are not considered reliable. |
| 263 const float zThresholdFactor = 0.01f; | 270 const float zThresholdFactor = 0.01f; |
| 264 float zThreshold = m_zRange * zThresholdFactor; | 271 float zThreshold = m_zRange * zThresholdFactor; |
| 265 | 272 |
| 266 for (unsigned na = 0; na < m_nodes.size(); na++) { | 273 for (unsigned na = 0; na < m_nodes.size(); na++) { |
| 267 GraphNode& nodeA = m_nodes[na]; | 274 GraphNode& nodeA = m_nodes[na]; |
| 268 if (!nodeA.layer->drawsContent() && !nodeA.layer->renderSurface()) | 275 if (!nodeA.layer->drawsContent() && !nodeA.layer->renderSurface()) |
| 269 continue; | 276 continue; |
| 270 for (unsigned nb = na + 1; nb < m_nodes.size(); nb++) { | 277 for (unsigned nb = na + 1; nb < m_nodes.size(); nb++) { |
| 271 GraphNode& nodeB = m_nodes[nb]; | 278 GraphNode& nodeB = m_nodes[nb]; |
| 272 if (!nodeB.layer->drawsContent() && !nodeB.layer->renderSurface()) | 279 if (!nodeB.layer->drawsContent() && !nodeB.layer->renderSurface()) |
| 273 continue; | 280 continue; |
| 274 float weight = 0; | 281 float weight = 0; |
| 275 ABCompareResult overlapResult = checkOverlap(&nodeA.shape, &nodeB.sh
ape, zThreshold, weight); | 282 ABCompareResult overlapResult = checkOverlap(&nodeA.shape, &nodeB.sh
ape, zThreshold, weight); |
| 276 GraphNode* startNode = 0; | 283 GraphNode* startNode = 0; |
| 277 GraphNode* endNode = 0; | 284 GraphNode* endNode = 0; |
| 278 if (overlapResult == ABeforeB) { | 285 if (overlapResult == ABeforeB) { |
| 279 startNode = &nodeA; | 286 startNode = &nodeA; |
| 280 endNode = &nodeB; | 287 endNode = &nodeB; |
| 281 } else if (overlapResult == BBeforeA) { | 288 } else if (overlapResult == BBeforeA) { |
| 282 startNode = &nodeB; | 289 startNode = &nodeB; |
| 283 endNode = &nodeA; | 290 endNode = &nodeA; |
| 284 } | 291 } |
| 285 | 292 |
| 286 if (startNode) { | 293 if (startNode) { |
| 287 #if SHOW_DEBUG_LOG | 294 #if !defined( NDEBUG ) |
| 288 DLOG(INFO) << "CCLayerSorter: " << startNode->layer->id() << " -
> " << endNode->layer->id() << "\n"; | 295 LOG(CCLayerSorter, "%d -> %d\n", startNode->layer->id(), endNode
->layer->id()); |
| 289 #endif | 296 #endif |
| 290 m_edges.append(GraphEdge(startNode, endNode, weight)); | 297 m_edges.append(GraphEdge(startNode, endNode, weight)); |
| 291 } | 298 } |
| 292 } | 299 } |
| 293 } | 300 } |
| 294 | 301 |
| 295 for (unsigned i = 0; i < m_edges.size(); i++) { | 302 for (unsigned i = 0; i < m_edges.size(); i++) { |
| 296 GraphEdge& edge = m_edges[i]; | 303 GraphEdge& edge = m_edges[i]; |
| 297 m_activeEdges.add(&edge, &edge); | 304 m_activeEdges.add(&edge, &edge); |
| 298 edge.from->outgoing.append(&edge); | 305 edge.from->outgoing.append(&edge); |
| 299 edge.to->incoming.append(&edge); | 306 edge.to->incoming.append(&edge); |
| 300 edge.to->incomingEdgeWeight += edge.weight; | 307 edge.to->incomingEdgeWeight += edge.weight; |
| 301 } | 308 } |
| 302 } | 309 } |
| 303 | 310 |
| 304 // Finds and removes an edge from the list by doing a swap with the | 311 // Finds and removes an edge from the list by doing a swap with the |
| 305 // last element of the list. | 312 // last element of the list. |
| 306 void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, Vector<GraphEdge*>& list
) | 313 void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, Vector<GraphEdge*>& list
) |
| 307 { | 314 { |
| 308 size_t edgeIndex = list.find(edge); | 315 size_t edgeIndex = list.find(edge); |
| 309 DCHECK(edgeIndex != notFound); | 316 ASSERT(edgeIndex != notFound); |
| 310 if (list.size() == 1) { | 317 if (list.size() == 1) { |
| 311 DCHECK(!edgeIndex); | 318 ASSERT(!edgeIndex); |
| 312 list.clear(); | 319 list.clear(); |
| 313 return; | 320 return; |
| 314 } | 321 } |
| 315 if (edgeIndex != list.size() - 1) | 322 if (edgeIndex != list.size() - 1) |
| 316 list[edgeIndex] = list[list.size() - 1]; | 323 list[edgeIndex] = list[list.size() - 1]; |
| 317 | 324 |
| 318 list.removeLast(); | 325 list.removeLast(); |
| 319 } | 326 } |
| 320 | 327 |
| 321 // Sorts the given list of layers such that they can be painted in a back-to-fro
nt | 328 // Sorts the given list of layers such that they can be painted in a back-to-fro
nt |
| (...skipping 10 matching lines...) Expand all Loading... |
| 332 // coordinate. The layer with the lower Z coordinate (farther from the eye) need
s to be rendered | 339 // coordinate. The layer with the lower Z coordinate (farther from the eye) need
s to be rendered |
| 333 // first. | 340 // first. |
| 334 // | 341 // |
| 335 // If the layer projections don't intersect, then no edges (dependencies) are cr
eated | 342 // If the layer projections don't intersect, then no edges (dependencies) are cr
eated |
| 336 // between them in the graph. HOWEVER, in this case we still need to preserve th
e ordering | 343 // between them in the graph. HOWEVER, in this case we still need to preserve th
e ordering |
| 337 // of the original list of layers, since that list should already have proper z-
index | 344 // of the original list of layers, since that list should already have proper z-
index |
| 338 // ordering of layers. | 345 // ordering of layers. |
| 339 // | 346 // |
| 340 void CCLayerSorter::sort(LayerList::iterator first, LayerList::iterator last) | 347 void CCLayerSorter::sort(LayerList::iterator first, LayerList::iterator last) |
| 341 { | 348 { |
| 342 #if SHOW_DEBUG_LOG | 349 #if !defined( NDEBUG ) |
| 343 DLOG(INFO) << "CCLayerSorter: Sorting start ----\n"; | 350 LOG(CCLayerSorter, "Sorting start ----\n"); |
| 344 #endif | 351 #endif |
| 345 createGraphNodes(first, last); | 352 createGraphNodes(first, last); |
| 346 | 353 |
| 347 createGraphEdges(); | 354 createGraphEdges(); |
| 348 | 355 |
| 349 Vector<GraphNode*> sortedList; | 356 Vector<GraphNode*> sortedList; |
| 350 Deque<GraphNode*> noIncomingEdgeNodeList; | 357 Deque<GraphNode*> noIncomingEdgeNodeList; |
| 351 | 358 |
| 352 // Find all the nodes that don't have incoming edges. | 359 // Find all the nodes that don't have incoming edges. |
| 353 for (NodeList::iterator la = m_nodes.begin(); la < m_nodes.end(); la++) { | 360 for (NodeList::iterator la = m_nodes.begin(); la < m_nodes.end(); la++) { |
| 354 if (!la->incoming.size()) | 361 if (!la->incoming.size()) |
| 355 noIncomingEdgeNodeList.append(la); | 362 noIncomingEdgeNodeList.append(la); |
| 356 } | 363 } |
| 357 | 364 |
| 358 #if SHOW_DEBUG_LOG | 365 #if !defined( NDEBUG ) |
| 359 DLOG(INFO) << "CCLayerSorter: Sorted list: "; | 366 LOG(CCLayerSorter, "Sorted list: "); |
| 360 #endif | 367 #endif |
| 361 while (m_activeEdges.size() || noIncomingEdgeNodeList.size()) { | 368 while (m_activeEdges.size() || noIncomingEdgeNodeList.size()) { |
| 362 while (noIncomingEdgeNodeList.size()) { | 369 while (noIncomingEdgeNodeList.size()) { |
| 363 | 370 |
| 364 // It is necessary to preserve the existing ordering of layers, when
there are | 371 // It is necessary to preserve the existing ordering of layers, when
there are |
| 365 // no explicit dependencies (because this existing ordering has corr
ect | 372 // no explicit dependencies (because this existing ordering has corr
ect |
| 366 // z-index/layout ordering). To preserve this ordering, we process N
odes in | 373 // z-index/layout ordering). To preserve this ordering, we process N
odes in |
| 367 // the same order that they were added to the list. | 374 // the same order that they were added to the list. |
| 368 GraphNode* fromNode = noIncomingEdgeNodeList.takeFirst(); | 375 GraphNode* fromNode = noIncomingEdgeNodeList.takeFirst(); |
| 369 | 376 |
| 370 // Add it to the final list. | 377 // Add it to the final list. |
| 371 sortedList.append(fromNode); | 378 sortedList.append(fromNode); |
| 372 | 379 |
| 373 #if SHOW_DEBUG_LOG | 380 #if !defined( NDEBUG ) |
| 374 DLOG(INFO) << fromNode->layer->id() << ", "; | 381 LOG(CCLayerSorter, "%d, ", fromNode->layer->id()); |
| 375 #endif | 382 #endif |
| 376 | 383 |
| 377 // Remove all its outgoing edges from the graph. | 384 // Remove all its outgoing edges from the graph. |
| 378 for (unsigned i = 0; i < fromNode->outgoing.size(); i++) { | 385 for (unsigned i = 0; i < fromNode->outgoing.size(); i++) { |
| 379 GraphEdge* outgoingEdge = fromNode->outgoing[i]; | 386 GraphEdge* outgoingEdge = fromNode->outgoing[i]; |
| 380 | 387 |
| 381 m_activeEdges.remove(outgoingEdge); | 388 m_activeEdges.remove(outgoingEdge); |
| 382 removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming); | 389 removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming); |
| 383 outgoingEdge->to->incomingEdgeWeight -= outgoingEdge->weight; | 390 outgoingEdge->to->incomingEdgeWeight -= outgoingEdge->weight; |
| 384 | 391 |
| (...skipping 12 matching lines...) Expand all Loading... |
| 397 // nodes that have zero-weight incoming edges i.e. layers that are being | 404 // nodes that have zero-weight incoming edges i.e. layers that are being |
| 398 // occluded by a layer that intersects them. | 405 // occluded by a layer that intersects them. |
| 399 float minIncomingEdgeWeight = FLT_MAX; | 406 float minIncomingEdgeWeight = FLT_MAX; |
| 400 GraphNode* nextNode = 0; | 407 GraphNode* nextNode = 0; |
| 401 for (unsigned i = 0; i < m_nodes.size(); i++) { | 408 for (unsigned i = 0; i < m_nodes.size(); i++) { |
| 402 if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < mi
nIncomingEdgeWeight) { | 409 if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < mi
nIncomingEdgeWeight) { |
| 403 minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight; | 410 minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight; |
| 404 nextNode = &m_nodes[i]; | 411 nextNode = &m_nodes[i]; |
| 405 } | 412 } |
| 406 } | 413 } |
| 407 DCHECK(nextNode); | 414 ASSERT(nextNode); |
| 408 // Remove all its incoming edges. | 415 // Remove all its incoming edges. |
| 409 for (unsigned e = 0; e < nextNode->incoming.size(); e++) { | 416 for (unsigned e = 0; e < nextNode->incoming.size(); e++) { |
| 410 GraphEdge* incomingEdge = nextNode->incoming[e]; | 417 GraphEdge* incomingEdge = nextNode->incoming[e]; |
| 411 | 418 |
| 412 m_activeEdges.remove(incomingEdge); | 419 m_activeEdges.remove(incomingEdge); |
| 413 removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing); | 420 removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing); |
| 414 } | 421 } |
| 415 nextNode->incoming.clear(); | 422 nextNode->incoming.clear(); |
| 416 nextNode->incomingEdgeWeight = 0; | 423 nextNode->incomingEdgeWeight = 0; |
| 417 noIncomingEdgeNodeList.append(nextNode); | 424 noIncomingEdgeNodeList.append(nextNode); |
| 418 #if SHOW_DEBUG_LOG | 425 #if !defined( NDEBUG ) |
| 419 DLOG(INFO) << "Breaking cycle by cleaning up incoming edges from " << ne
xtNode->layer->id() << " (weight = " << minIncomingEdgeWeight<< ")\n"; | 426 LOG(CCLayerSorter, "Breaking cycle by cleaning up incoming edges from %d
(weight = %f)\n", nextNode->layer->id(), minIncomingEdgeWeight); |
| 420 #endif | 427 #endif |
| 421 } | 428 } |
| 422 | 429 |
| 423 // Note: The original elements of the list are in no danger of having their
ref count go to zero | 430 // Note: The original elements of the list are in no danger of having their
ref count go to zero |
| 424 // here as they are all nodes of the layer hierarchy and are kept alive by t
heir parent nodes. | 431 // here as they are all nodes of the layer hierarchy and are kept alive by t
heir parent nodes. |
| 425 int count = 0; | 432 int count = 0; |
| 426 for (LayerList::iterator it = first; it < last; it++) | 433 for (LayerList::iterator it = first; it < last; it++) |
| 427 *it = sortedList[count++]->layer; | 434 *it = sortedList[count++]->layer; |
| 428 | 435 |
| 429 #if SHOW_DEBUG_LOG | 436 #if !defined( NDEBUG ) |
| 430 DLOG(INFO) << "CCLayerSorter: Sorting end ----\n"; | 437 LOG(CCLayerSorter, "Sorting end ----\n"); |
| 431 #endif | 438 #endif |
| 432 | 439 |
| 433 m_nodes.clear(); | 440 m_nodes.clear(); |
| 434 m_edges.clear(); | 441 m_edges.clear(); |
| 435 m_activeEdges.clear(); | 442 m_activeEdges.clear(); |
| 436 } | 443 } |
| 437 | 444 |
| 438 } | 445 } |
| OLD | NEW |