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 |