| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "config.h" | |
| 6 | |
| 7 #include "CCLayerSorter.h" | |
| 8 | |
| 9 #include "CCMathUtil.h" | |
| 10 #include "CCRenderSurface.h" | |
| 11 #include <limits.h> | |
| 12 #include <public/WebTransformationMatrix.h> | |
| 13 #include <wtf/Deque.h> | |
| 14 | |
| 15 using namespace std; | |
| 16 using WebKit::WebTransformationMatrix; | |
| 17 | |
| 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 | |
| 28 | |
| 29 namespace cc { | |
| 30 | |
| 31 inline static float perpProduct(const FloatSize& u, const FloatSize& v) | |
| 32 { | |
| 33 return u.width() * v.height() - u.height() * v.width(); | |
| 34 } | |
| 35 | |
| 36 // 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. | |
| 38 static bool edgeEdgeTest(const FloatPoint& a, const FloatPoint& b, const FloatPo
int& c, const FloatPoint& d, FloatPoint& r) | |
| 39 { | |
| 40 FloatSize u = b - a; | |
| 41 FloatSize v = d - c; | |
| 42 FloatSize w = a - c; | |
| 43 | |
| 44 float denom = perpProduct(u, v); | |
| 45 | |
| 46 // If denom == 0 then the edges are parallel. While they could be overlappin
g | |
| 47 // we don't bother to check here as the we'll find their intersections from
the | |
| 48 // corner to quad tests. | |
| 49 if (!denom) | |
| 50 return false; | |
| 51 | |
| 52 float s = perpProduct(v, w) / denom; | |
| 53 if (s < 0 || s > 1) | |
| 54 return false; | |
| 55 | |
| 56 float t = perpProduct(u, w) / denom; | |
| 57 if (t < 0 || t > 1) | |
| 58 return false; | |
| 59 | |
| 60 u.scale(s); | |
| 61 r = a + u; | |
| 62 return true; | |
| 63 } | |
| 64 | |
| 65 CCLayerSorter::GraphNode::GraphNode(CCLayerImpl* cclayer) | |
| 66 : layer(cclayer) | |
| 67 , incomingEdgeWeight(0) | |
| 68 { | |
| 69 } | |
| 70 | |
| 71 CCLayerSorter::GraphNode::~GraphNode() | |
| 72 { | |
| 73 } | |
| 74 | |
| 75 CCLayerSorter::CCLayerSorter() | |
| 76 : m_zRange(0) | |
| 77 { | |
| 78 } | |
| 79 | |
| 80 CCLayerSorter::~CCLayerSorter() | |
| 81 { | |
| 82 } | |
| 83 | |
| 84 // Checks whether layer "a" draws on top of layer "b". The weight value returned
is an indication of | |
| 85 // the maximum z-depth difference between the layers or zero if the layers are f
ound to be intesecting | |
| 86 // (some features are in front and some are behind). | |
| 87 CCLayerSorter::ABCompareResult CCLayerSorter::checkOverlap(LayerShape* a, LayerS
hape* b, float zThreshold, float& weight) | |
| 88 { | |
| 89 weight = 0; | |
| 90 | |
| 91 // Early out if the projected bounds don't overlap. | |
| 92 if (!a->projectedBounds.intersects(b->projectedBounds)) | |
| 93 return None; | |
| 94 | |
| 95 FloatPoint aPoints[4] = {a->projectedQuad.p1(), a->projectedQuad.p2(), a->pr
ojectedQuad.p3(), a->projectedQuad.p4() }; | |
| 96 FloatPoint bPoints[4] = {b->projectedQuad.p1(), b->projectedQuad.p2(), b->pr
ojectedQuad.p3(), b->projectedQuad.p4() }; | |
| 97 | |
| 98 // Make a list of points that inside both layer quad projections. | |
| 99 Vector<FloatPoint> overlapPoints; | |
| 100 | |
| 101 // Check all four corners of one layer against the other layer's quad. | |
| 102 for (int i = 0; i < 4; ++i) { | |
| 103 if (a->projectedQuad.containsPoint(bPoints[i])) | |
| 104 overlapPoints.append(bPoints[i]); | |
| 105 if (b->projectedQuad.containsPoint(aPoints[i])) | |
| 106 overlapPoints.append(aPoints[i]); | |
| 107 } | |
| 108 | |
| 109 // Check all the edges of one layer for intersection with the other layer's
edges. | |
| 110 FloatPoint r; | |
| 111 for (int ea = 0; ea < 4; ++ea) | |
| 112 for (int eb = 0; eb < 4; ++eb) | |
| 113 if (edgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4], | |
| 114 bPoints[eb], bPoints[(eb + 1) % 4], | |
| 115 r)) | |
| 116 overlapPoints.append(r); | |
| 117 | |
| 118 if (!overlapPoints.size()) | |
| 119 return None; | |
| 120 | |
| 121 // Check the corresponding layer depth value for all overlap points to deter
mine | |
| 122 // which layer is in front. | |
| 123 float maxPositive = 0; | |
| 124 float maxNegative = 0; | |
| 125 for (unsigned o = 0; o < overlapPoints.size(); o++) { | |
| 126 float za = a->layerZFromProjectedPoint(overlapPoints[o]); | |
| 127 float zb = b->layerZFromProjectedPoint(overlapPoints[o]); | |
| 128 | |
| 129 float diff = za - zb; | |
| 130 if (diff > maxPositive) | |
| 131 maxPositive = diff; | |
| 132 if (diff < maxNegative) | |
| 133 maxNegative = diff; | |
| 134 } | |
| 135 | |
| 136 float maxDiff = (fabsf(maxPositive) > fabsf(maxNegative) ? maxPositive : max
Negative); | |
| 137 | |
| 138 // If the results are inconsistent (and the z difference substantial to rule
out | |
| 139 // numerical errors) then the layers are intersecting. We will still return
an | |
| 140 // order based on the maximum depth difference but with an edge weight of ze
ro | |
| 141 // these layers will get priority if a graph cycle is present and needs to b
e broken. | |
| 142 if (maxPositive > zThreshold && maxNegative < -zThreshold) | |
| 143 weight = 0; | |
| 144 else | |
| 145 weight = fabsf(maxDiff); | |
| 146 | |
| 147 // Maintain relative order if the layers have the same depth at all intersec
tion points. | |
| 148 if (maxDiff <= 0) | |
| 149 return ABeforeB; | |
| 150 | |
| 151 return BBeforeA; | |
| 152 } | |
| 153 | |
| 154 CCLayerSorter::LayerShape::LayerShape() | |
| 155 { | |
| 156 } | |
| 157 | |
| 158 CCLayerSorter::LayerShape::LayerShape(float width, float height, const WebTransf
ormationMatrix& drawTransform) | |
| 159 { | |
| 160 FloatQuad layerQuad(FloatRect(0, 0, width, height)); | |
| 161 | |
| 162 // Compute the projection of the layer quad onto the z = 0 plane. | |
| 163 | |
| 164 FloatPoint clippedQuad[8]; | |
| 165 int numVerticesInClippedQuad; | |
| 166 CCMathUtil::mapClippedQuad(drawTransform, layerQuad, clippedQuad, numVertice
sInClippedQuad); | |
| 167 | |
| 168 if (numVerticesInClippedQuad < 3) { | |
| 169 projectedBounds = FloatRect(); | |
| 170 return; | |
| 171 } | |
| 172 | |
| 173 projectedBounds = CCMathUtil::computeEnclosingRectOfVertices(clippedQuad, nu
mVerticesInClippedQuad); | |
| 174 | |
| 175 // NOTE: it will require very significant refactoring and overhead to deal w
ith | |
| 176 // generalized polygons or multiple quads per layer here. For the sake of la
yer | |
| 177 // sorting it is equally correct to take a subsection of the polygon that ca
n be made | |
| 178 // into a quad. This will only be incorrect in the case of intersecting laye
rs, which | |
| 179 // are not supported yet anyway. | |
| 180 projectedQuad.setP1(clippedQuad[0]); | |
| 181 projectedQuad.setP2(clippedQuad[1]); | |
| 182 projectedQuad.setP3(clippedQuad[2]); | |
| 183 if (numVerticesInClippedQuad >= 4) | |
| 184 projectedQuad.setP4(clippedQuad[3]); | |
| 185 else | |
| 186 projectedQuad.setP4(clippedQuad[2]); // this will be a degenerate quad t
hat is actually a triangle. | |
| 187 | |
| 188 // Compute the normal of the layer's plane. | |
| 189 bool clipped = false; | |
| 190 FloatPoint3D c1 = CCMathUtil::mapPoint(drawTransform, FloatPoint3D(0, 0, 0),
clipped); | |
| 191 FloatPoint3D c2 = CCMathUtil::mapPoint(drawTransform, FloatPoint3D(0, 1, 0),
clipped); | |
| 192 FloatPoint3D c3 = CCMathUtil::mapPoint(drawTransform, FloatPoint3D(1, 0, 0),
clipped); | |
| 193 // FIXME: Deal with clipping. | |
| 194 FloatPoint3D c12 = c2 - c1; | |
| 195 FloatPoint3D c13 = c3 - c1; | |
| 196 layerNormal = c13.cross(c12); | |
| 197 | |
| 198 transformOrigin = c1; | |
| 199 } | |
| 200 | |
| 201 // Returns the Z coordinate of a point on the layer that projects | |
| 202 // to point p which lies on the z = 0 plane. It does it by computing the | |
| 203 // intersection of a line starting from p along the Z axis and the plane | |
| 204 // of the layer. | |
| 205 float CCLayerSorter::LayerShape::layerZFromProjectedPoint(const FloatPoint& p) c
onst | |
| 206 { | |
| 207 const FloatPoint3D zAxis(0, 0, 1); | |
| 208 FloatPoint3D w = FloatPoint3D(p) - transformOrigin; | |
| 209 | |
| 210 float d = layerNormal.dot(zAxis); | |
| 211 float n = -layerNormal.dot(w); | |
| 212 | |
| 213 // Check if layer is parallel to the z = 0 axis which will make it | |
| 214 // invisible and hence returning zero is fine. | |
| 215 if (!d) | |
| 216 return 0; | |
| 217 | |
| 218 // The intersection point would be given by: | |
| 219 // 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. | |
| 221 return n / d; | |
| 222 } | |
| 223 | |
| 224 void CCLayerSorter::createGraphNodes(LayerList::iterator first, LayerList::itera
tor last) | |
| 225 { | |
| 226 #if !defined( NDEBUG ) | |
| 227 LOG(CCLayerSorter, "Creating graph nodes:\n"); | |
| 228 #endif | |
| 229 float minZ = FLT_MAX; | |
| 230 float maxZ = -FLT_MAX; | |
| 231 for (LayerList::const_iterator it = first; it < last; it++) { | |
| 232 m_nodes.append(GraphNode(*it)); | |
| 233 GraphNode& node = m_nodes.at(m_nodes.size() - 1); | |
| 234 CCRenderSurface* renderSurface = node.layer->renderSurface(); | |
| 235 if (!node.layer->drawsContent() && !renderSurface) | |
| 236 continue; | |
| 237 | |
| 238 #if !defined( NDEBUG ) | |
| 239 LOG(CCLayerSorter, "Layer %d (%d x %d)\n", node.layer->id(), node.layer-
>bounds().width(), node.layer->bounds().height()); | |
| 240 #endif | |
| 241 | |
| 242 WebTransformationMatrix drawTransform; | |
| 243 float layerWidth, layerHeight; | |
| 244 if (renderSurface) { | |
| 245 drawTransform = renderSurface->drawTransform(); | |
| 246 layerWidth = renderSurface->contentRect().width(); | |
| 247 layerHeight = renderSurface->contentRect().height(); | |
| 248 } else { | |
| 249 drawTransform = node.layer->drawTransform(); | |
| 250 layerWidth = node.layer->contentBounds().width(); | |
| 251 layerHeight = node.layer->contentBounds().height(); | |
| 252 } | |
| 253 | |
| 254 node.shape = LayerShape(layerWidth, layerHeight, drawTransform); | |
| 255 | |
| 256 maxZ = max(maxZ, node.shape.transformOrigin.z()); | |
| 257 minZ = min(minZ, node.shape.transformOrigin.z()); | |
| 258 } | |
| 259 | |
| 260 m_zRange = fabsf(maxZ - minZ); | |
| 261 } | |
| 262 | |
| 263 void CCLayerSorter::createGraphEdges() | |
| 264 { | |
| 265 #if !defined( NDEBUG ) | |
| 266 LOG(CCLayerSorter, "Edges:\n"); | |
| 267 #endif | |
| 268 // Fraction of the total zRange below which z differences | |
| 269 // are not considered reliable. | |
| 270 const float zThresholdFactor = 0.01f; | |
| 271 float zThreshold = m_zRange * zThresholdFactor; | |
| 272 | |
| 273 for (unsigned na = 0; na < m_nodes.size(); na++) { | |
| 274 GraphNode& nodeA = m_nodes[na]; | |
| 275 if (!nodeA.layer->drawsContent() && !nodeA.layer->renderSurface()) | |
| 276 continue; | |
| 277 for (unsigned nb = na + 1; nb < m_nodes.size(); nb++) { | |
| 278 GraphNode& nodeB = m_nodes[nb]; | |
| 279 if (!nodeB.layer->drawsContent() && !nodeB.layer->renderSurface()) | |
| 280 continue; | |
| 281 float weight = 0; | |
| 282 ABCompareResult overlapResult = checkOverlap(&nodeA.shape, &nodeB.sh
ape, zThreshold, weight); | |
| 283 GraphNode* startNode = 0; | |
| 284 GraphNode* endNode = 0; | |
| 285 if (overlapResult == ABeforeB) { | |
| 286 startNode = &nodeA; | |
| 287 endNode = &nodeB; | |
| 288 } else if (overlapResult == BBeforeA) { | |
| 289 startNode = &nodeB; | |
| 290 endNode = &nodeA; | |
| 291 } | |
| 292 | |
| 293 if (startNode) { | |
| 294 #if !defined( NDEBUG ) | |
| 295 LOG(CCLayerSorter, "%d -> %d\n", startNode->layer->id(), endNode
->layer->id()); | |
| 296 #endif | |
| 297 m_edges.append(GraphEdge(startNode, endNode, weight)); | |
| 298 } | |
| 299 } | |
| 300 } | |
| 301 | |
| 302 for (unsigned i = 0; i < m_edges.size(); i++) { | |
| 303 GraphEdge& edge = m_edges[i]; | |
| 304 m_activeEdges.add(&edge, &edge); | |
| 305 edge.from->outgoing.append(&edge); | |
| 306 edge.to->incoming.append(&edge); | |
| 307 edge.to->incomingEdgeWeight += edge.weight; | |
| 308 } | |
| 309 } | |
| 310 | |
| 311 // Finds and removes an edge from the list by doing a swap with the | |
| 312 // last element of the list. | |
| 313 void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, Vector<GraphEdge*>& list
) | |
| 314 { | |
| 315 size_t edgeIndex = list.find(edge); | |
| 316 ASSERT(edgeIndex != notFound); | |
| 317 if (list.size() == 1) { | |
| 318 ASSERT(!edgeIndex); | |
| 319 list.clear(); | |
| 320 return; | |
| 321 } | |
| 322 if (edgeIndex != list.size() - 1) | |
| 323 list[edgeIndex] = list[list.size() - 1]; | |
| 324 | |
| 325 list.removeLast(); | |
| 326 } | |
| 327 | |
| 328 // Sorts the given list of layers such that they can be painted in a back-to-fro
nt | |
| 329 // order. Sorting produces correct results for non-intersecting layers that don'
t have | |
| 330 // cyclical order dependencies. Cycles and intersections are broken (somewhat) a
ribtrarily. | |
| 331 // Sorting of layers is done via a topological sort of a directed graph whose no
des are | |
| 332 // the layers themselves. An edge from node A to node B signifies that layer A n
eeds to | |
| 333 // be drawn before layer B. If A and B have no dependency between each other, th
en we | |
| 334 // preserve the ordering of those layers as they were in the original list. | |
| 335 // | |
| 336 // The draw order between two layers is determined by projecting the two triangl
es making | |
| 337 // up each layer quad to the Z = 0 plane, finding points of intersection between
the triangles | |
| 338 // and backprojecting those points to the plane of the layer to determine the co
rresponding Z | |
| 339 // coordinate. The layer with the lower Z coordinate (farther from the eye) need
s to be rendered | |
| 340 // first. | |
| 341 // | |
| 342 // 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 | |
| 344 // of the original list of layers, since that list should already have proper z-
index | |
| 345 // ordering of layers. | |
| 346 // | |
| 347 void CCLayerSorter::sort(LayerList::iterator first, LayerList::iterator last) | |
| 348 { | |
| 349 #if !defined( NDEBUG ) | |
| 350 LOG(CCLayerSorter, "Sorting start ----\n"); | |
| 351 #endif | |
| 352 createGraphNodes(first, last); | |
| 353 | |
| 354 createGraphEdges(); | |
| 355 | |
| 356 Vector<GraphNode*> sortedList; | |
| 357 Deque<GraphNode*> noIncomingEdgeNodeList; | |
| 358 | |
| 359 // Find all the nodes that don't have incoming edges. | |
| 360 for (NodeList::iterator la = m_nodes.begin(); la < m_nodes.end(); la++) { | |
| 361 if (!la->incoming.size()) | |
| 362 noIncomingEdgeNodeList.append(la); | |
| 363 } | |
| 364 | |
| 365 #if !defined( NDEBUG ) | |
| 366 LOG(CCLayerSorter, "Sorted list: "); | |
| 367 #endif | |
| 368 while (m_activeEdges.size() || noIncomingEdgeNodeList.size()) { | |
| 369 while (noIncomingEdgeNodeList.size()) { | |
| 370 | |
| 371 // It is necessary to preserve the existing ordering of layers, when
there are | |
| 372 // no explicit dependencies (because this existing ordering has corr
ect | |
| 373 // z-index/layout ordering). To preserve this ordering, we process N
odes in | |
| 374 // the same order that they were added to the list. | |
| 375 GraphNode* fromNode = noIncomingEdgeNodeList.takeFirst(); | |
| 376 | |
| 377 // Add it to the final list. | |
| 378 sortedList.append(fromNode); | |
| 379 | |
| 380 #if !defined( NDEBUG ) | |
| 381 LOG(CCLayerSorter, "%d, ", fromNode->layer->id()); | |
| 382 #endif | |
| 383 | |
| 384 // Remove all its outgoing edges from the graph. | |
| 385 for (unsigned i = 0; i < fromNode->outgoing.size(); i++) { | |
| 386 GraphEdge* outgoingEdge = fromNode->outgoing[i]; | |
| 387 | |
| 388 m_activeEdges.remove(outgoingEdge); | |
| 389 removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming); | |
| 390 outgoingEdge->to->incomingEdgeWeight -= outgoingEdge->weight; | |
| 391 | |
| 392 if (!outgoingEdge->to->incoming.size()) | |
| 393 noIncomingEdgeNodeList.append(outgoingEdge->to); | |
| 394 } | |
| 395 fromNode->outgoing.clear(); | |
| 396 } | |
| 397 | |
| 398 if (!m_activeEdges.size()) | |
| 399 break; | |
| 400 | |
| 401 // If there are still active edges but the list of nodes without incomin
g edges | |
| 402 // is empty then we have run into a cycle. Break the cycle by finding th
e node | |
| 403 // with the smallest overall incoming edge weight and use it. This will
favor | |
| 404 // nodes that have zero-weight incoming edges i.e. layers that are being | |
| 405 // occluded by a layer that intersects them. | |
| 406 float minIncomingEdgeWeight = FLT_MAX; | |
| 407 GraphNode* nextNode = 0; | |
| 408 for (unsigned i = 0; i < m_nodes.size(); i++) { | |
| 409 if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < mi
nIncomingEdgeWeight) { | |
| 410 minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight; | |
| 411 nextNode = &m_nodes[i]; | |
| 412 } | |
| 413 } | |
| 414 ASSERT(nextNode); | |
| 415 // Remove all its incoming edges. | |
| 416 for (unsigned e = 0; e < nextNode->incoming.size(); e++) { | |
| 417 GraphEdge* incomingEdge = nextNode->incoming[e]; | |
| 418 | |
| 419 m_activeEdges.remove(incomingEdge); | |
| 420 removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing); | |
| 421 } | |
| 422 nextNode->incoming.clear(); | |
| 423 nextNode->incomingEdgeWeight = 0; | |
| 424 noIncomingEdgeNodeList.append(nextNode); | |
| 425 #if !defined( NDEBUG ) | |
| 426 LOG(CCLayerSorter, "Breaking cycle by cleaning up incoming edges from %d
(weight = %f)\n", nextNode->layer->id(), minIncomingEdgeWeight); | |
| 427 #endif | |
| 428 } | |
| 429 | |
| 430 // 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. | |
| 432 int count = 0; | |
| 433 for (LayerList::iterator it = first; it < last; it++) | |
| 434 *it = sortedList[count++]->layer; | |
| 435 | |
| 436 #if !defined( NDEBUG ) | |
| 437 LOG(CCLayerSorter, "Sorting end ----\n"); | |
| 438 #endif | |
| 439 | |
| 440 m_nodes.clear(); | |
| 441 m_edges.clear(); | |
| 442 m_activeEdges.clear(); | |
| 443 } | |
| 444 | |
| 445 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 11122003:
[cc] Rename all cc/ filenames to Chromium style (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src