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