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 "cc/dcheck.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 CC_DCHECK(edgeIndex != notFound); |
317 if (list.size() == 1) { | 310 if (list.size() == 1) { |
318 ASSERT(!edgeIndex); | 311 CC_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 CC_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 |