Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(434)

Side by Side Diff: cc/layer_sorter.cc

Issue 11048044: cc: Switch to Chromium DCHECKs and LOGs (Closed) Base URL: http://git.chromium.org/chromium/src.git@master
Patch Set: Created 8 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « cc/layer_quad.cc ('k') | cc/layer_texture_sub_image.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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 }
OLDNEW
« no previous file with comments | « cc/layer_quad.cc ('k') | cc/layer_texture_sub_image.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698