gfx/layers/LayerSorter.cpp

   1 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include "LayerSorter.h"
   7 #include "DirectedGraph.h"
   8 #include "limits.h"
   9 #include "gfxLineSegment.h"
  10 #include "Layers.h"
  11 #include "mozilla/Assertions.h"
  12
  13 namespace mozilla {
  14 namespace layers {
  15
  16 enum LayerSortOrder {
  17   Undefined,
  18   ABeforeB,
  19   BBeforeA,
  20 };
  21
  22 /**
  23  * Recover the z component from a 2d transformed point by finding the intersection
  24  * of a line through the point in the z direction and the transformed plane.
  25  *
  26  * We want to solve:
  27  *
  28  * point = normal . (p0 - l0) / normal . l
  29  */
  30 static gfxFloat RecoverZDepth(const gfx3DMatrix& aTransform, const gfxPoint& aPoint)
  31 {
  32     const gfxPoint3D l(0, 0, 1);
  33     gfxPoint3D l0 = gfxPoint3D(aPoint.x, aPoint.y, 0);
  34     gfxPoint3D p0 = aTransform.Transform3D(gfxPoint3D(0, 0, 0));
  35     gfxPoint3D normal = aTransform.GetNormalVector();
  36
  37     gfxFloat n = normal.DotProduct(p0 - l0);
  38     gfxFloat d = normal.DotProduct(l);
  39
  40     if (!d) {
  41         return 0;
  42     }
  43
  44     return n/d;
  45 }
  46
  47 /**
  48  * Determine if this transform layer should be drawn before another when they
  49  * are both preserve-3d children.
  50  *
  51  * We want to find the relative z depths of the 2 layers at points where they
  52  * intersect when projected onto the 2d screen plane. Intersections are defined
  53  * as corners that are positioned within the other quad, as well as intersections
  54  * of the lines.
  55  *
  56  * We then choose the intersection point with the greatest difference in Z
  57  * depths and use this point to determine an ordering for the two layers.
  58  * For layers that are intersecting in 3d space, this essentially guesses an
  59  * order. In a lot of cases we only intersect right at the edge point (3d cubes
  60  * in particular) and this generates the 'correct' looking ordering. For planes
  61  * that truely intersect, then there is no correct ordering and this remains
  62  * unsolved without changing our rendering code.
  63  */
  64 static LayerSortOrder CompareDepth(Layer* aOne, Layer* aTwo) {
  65   gfxRect ourRect = aOne->GetEffectiveVisibleRegion().GetBounds();
  66   gfxRect otherRect = aTwo->GetEffectiveVisibleRegion().GetBounds();
  67
  68   gfx3DMatrix ourTransform = aOne->GetTransform();
  69   gfx3DMatrix otherTransform = aTwo->GetTransform();
  70
  71   // Transform both rectangles and project into 2d space.
  72   gfxQuad ourTransformedRect = ourTransform.TransformRect(ourRect);
  73   gfxQuad otherTransformedRect = otherTransform.TransformRect(otherRect);
  74
  75   gfxRect ourBounds = ourTransformedRect.GetBounds();
  76   gfxRect otherBounds = otherTransformedRect.GetBounds();
  77
  78   if (!ourBounds.Intersects(otherBounds)) {
  79     return Undefined;
  80   }
  81
  82   // Make a list of all points that are within the other rect.
  83   // Could we just check Contains() on the bounds rects. ie, is it possible
  84   // for layers to overlap without intersections (in 2d space) and yet still
  85   // have their bounds rects not completely enclose each other?
  86   nsTArray<gfxPoint> points;
  87   for (uint32_t i = 0; i < 4; i++) {
  88     if (ourTransformedRect.Contains(otherTransformedRect.mPoints[i])) {
  89       points.AppendElement(otherTransformedRect.mPoints[i]);
  90     }
  91     if (otherTransformedRect.Contains(ourTransformedRect.mPoints[i])) {
  92       points.AppendElement(ourTransformedRect.mPoints[i]);
  93     }
  94   }
  95
  96   // Look for intersections between lines (in 2d space) and use these as
  97   // depth testing points.
  98   for (uint32_t i = 0; i < 4; i++) {
  99     for (uint32_t j = 0; j < 4; j++) {
 100       gfxPoint intersection;
 101       gfxLineSegment one(ourTransformedRect.mPoints[i],
 102                          ourTransformedRect.mPoints[(i + 1) % 4]);
 103       gfxLineSegment two(otherTransformedRect.mPoints[j],
 104                          otherTransformedRect.mPoints[(j + 1) % 4]);
 105       if (one.Intersects(two, intersection)) {
 106         points.AppendElement(intersection);
 107       }
 108     }
 109   }
 110
 111   // No intersections, no defined order between these layers.
 112   if (points.IsEmpty()) {
 113     return Undefined;
 114   }
 115
 116   // Find the relative Z depths of each intersection point and check that the layers are in the same order.
 117   gfxFloat highest = 0;
 118   for (uint32_t i = 0; i < points.Length(); i++) {
 119     gfxFloat ourDepth = RecoverZDepth(ourTransform, points.ElementAt(i));
 120     gfxFloat otherDepth = RecoverZDepth(otherTransform, points.ElementAt(i));
 121
 122     gfxFloat difference = otherDepth - ourDepth;
 123
 124     if (fabs(difference) > fabs(highest)) {
 125       highest = difference;
 126     }
 127   }
 128   // If layers have the same depth keep the original order
 129   if (fabs(highest) < 0.1 || highest >= 0) {
 130     return ABeforeB;
 131   } else {
 132     return BBeforeA;
 133   }
 134 }
 135
 136 #ifdef DEBUG
 137 static bool gDumpLayerSortList = getenv("MOZ_DUMP_LAYER_SORT_LIST") != 0;
 138
 139 #define BLACK       0
 140 #define RED         1
 141 #define GREEN       2
 142 #define YELLOW      3
 143 #define BLUE        4
 144 #define MAGENTA     5
 145 #define CYAN        6
 146 #define WHITE       7
 147
 148 //#define USE_XTERM_COLORING
 149 #ifdef USE_XTERM_COLORING
 150
 151 #define RESET       0
 152 #define BRIGHT      1
 153 #define DIM         2
 154 #define UNDERLINE   3
 155 #define BLINK       4
 156 #define REVERSE     7
 157 #define HIDDEN      8
 158
 159 static void SetTextColor(uint32_t aColor)
 160 {
 161   char command[13];
 162
 163   /* Command is the control command to the terminal */
 164   sprintf(command, "%c[%d;%d;%dm", 0x1B, RESET, aColor + 30, BLACK + 40);
 165   printf("%s", command);
 166 }
 167
 168 static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
 169 {
 170   SetTextColor(aColor);
 171   fprintf(aFile, "%p", aLayer);
 172   SetTextColor(GREEN);
 173 }
 174 #else
 175
 176 const char *colors[] = { "Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White" };
 177
 178 static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
 179 {
 180   fprintf(aFile, "%p(%s)", aLayer, colors[aColor]);
 181 }
 182 #endif
 183
 184 static void print_layer(FILE* aFile, Layer* aLayer)
 185 {
 186   print_layer_internal(aFile, aLayer, aLayer->GetDebugColorIndex());
 187 }
 188
 189 static void DumpLayerList(nsTArray<Layer*>& aLayers)
 190 {
 191   for (uint32_t i = 0; i < aLayers.Length(); i++) {
 192     print_layer(stderr, aLayers.ElementAt(i));
 193     fprintf(stderr, " ");
 194   }
 195   fprintf(stderr, "\n");
 196 }
 197
 198 static void DumpEdgeList(DirectedGraph<Layer*>& aGraph)
 199 {
 200   const nsTArray<DirectedGraph<Layer*>::Edge>& edges = aGraph.GetEdgeList();
 201
 202   for (uint32_t i = 0; i < edges.Length(); i++) {
 203     fprintf(stderr, "From: ");
 204     print_layer(stderr, edges.ElementAt(i).mFrom);
 205     fprintf(stderr, ", To: ");
 206     print_layer(stderr, edges.ElementAt(i).mTo);
 207     fprintf(stderr, "\n");
 208   }
 209 }
 210 #endif
 211
 212 // The maximum number of layers that we will attempt to sort. Anything
 213 // greater than this will be left unsorted. We should consider enabling
 214 // depth buffering for the scene in this case.
 215 #define MAX_SORTABLE_LAYERS 100
 216
 217
 218 uint32_t gColorIndex = 1;
 219
 220 void SortLayersBy3DZOrder(nsTArray<Layer*>& aLayers)
 221 {
 222   uint32_t nodeCount = aLayers.Length();
 223   if (nodeCount > MAX_SORTABLE_LAYERS) {
 224     return;
 225   }
 226   DirectedGraph<Layer*> graph;
 227
 228 #ifdef DEBUG
 229   if (gDumpLayerSortList) {
 230     for (uint32_t i = 0; i < nodeCount; i++) {
 231       if (aLayers.ElementAt(i)->GetDebugColorIndex() == 0) {
 232         aLayers.ElementAt(i)->SetDebugColorIndex(gColorIndex++);
 233         if (gColorIndex > 7) {
 234           gColorIndex = 1;
 235         }
 236       }
 237     }
 238     fprintf(stderr, " --- Layers before sorting: --- \n");
 239     DumpLayerList(aLayers);
 240   }
 241 #endif
 242
 243   // Iterate layers and determine edges.
 244   for (uint32_t i = 0; i < nodeCount; i++) {
 245     for (uint32_t j = i + 1; j < nodeCount; j++) {
 246       Layer* a = aLayers.ElementAt(i);
 247       Layer* b = aLayers.ElementAt(j);
 248       LayerSortOrder order = CompareDepth(a, b);
 249       if (order == ABeforeB) {
 250         graph.AddEdge(a, b);
 251       } else if (order == BBeforeA) {
 252         graph.AddEdge(b, a);
 253       }
 254     }
 255   }
 256
 257 #ifdef DEBUG
 258   if (gDumpLayerSortList) {
 259     fprintf(stderr, " --- Edge List: --- \n");
 260     DumpEdgeList(graph);
 261   }
 262 #endif
 263
 264   // Build a new array using the graph.
 265   nsTArray<Layer*> noIncoming;
 266   nsTArray<Layer*> sortedList;
 267
 268   // Make a list of all layers with no incoming edges.
 269   noIncoming.AppendElements(aLayers);
 270   const nsTArray<DirectedGraph<Layer*>::Edge>& edges = graph.GetEdgeList();
 271   for (uint32_t i = 0; i < edges.Length(); i++) {
 272     noIncoming.RemoveElement(edges.ElementAt(i).mTo);
 273   }
 274
 275   // Move each item without incoming edges into the sorted list,
 276   // and remove edges from it.
 277   do {
 278     if (!noIncoming.IsEmpty()) {
 279       uint32_t last = noIncoming.Length() - 1;
 280
 281       Layer* layer = noIncoming.ElementAt(last);
 282       MOZ_ASSERT(layer); // don't let null layer pointers sneak into sortedList
 283
 284       noIncoming.RemoveElementAt(last);
 285       sortedList.AppendElement(layer);
 286
 287       nsTArray<DirectedGraph<Layer*>::Edge> outgoing;
 288       graph.GetEdgesFrom(layer, outgoing);
 289       for (uint32_t i = 0; i < outgoing.Length(); i++) {
 290         DirectedGraph<Layer*>::Edge edge = outgoing.ElementAt(i);
 291         graph.RemoveEdge(edge);
 292         if (!graph.NumEdgesTo(edge.mTo)) {
 293           // If this node also has no edges now, add it to the list
 294           noIncoming.AppendElement(edge.mTo);
 295         }
 296       }
 297     }
 298
 299     // If there are no nodes without incoming edges, but there
 300     // are still edges, then we have a cycle.
 301     if (noIncoming.IsEmpty() && graph.GetEdgeCount()) {
 302       // Find the node with the least incoming edges.
 303       uint32_t minEdges = UINT_MAX;
 304       Layer* minNode = nullptr;
 305       for (uint32_t i = 0; i < aLayers.Length(); i++) {
 306         uint32_t edgeCount = graph.NumEdgesTo(aLayers.ElementAt(i));
 307         if (edgeCount && edgeCount < minEdges) {
 308           minEdges = edgeCount;
 309           minNode = aLayers.ElementAt(i);
 310           if (minEdges == 1) {
 311             break;
 312           }
 313         }
 314       }
 315
 316       if (minNode) {
 317         // Remove all of them!
 318         graph.RemoveEdgesTo(minNode);
 319         noIncoming.AppendElement(minNode);
 320       }
 321     }
 322   } while (!noIncoming.IsEmpty());
 323   NS_ASSERTION(!graph.GetEdgeCount(), "Cycles detected!");
 324 #ifdef DEBUG
 325   if (gDumpLayerSortList) {
 326     fprintf(stderr, " --- Layers after sorting: --- \n");
 327     DumpLayerList(sortedList);
 328   }
 329 #endif
 330
 331   aLayers.Clear();
 332   aLayers.AppendElements(sortedList);
 333 }
 334
 335 }
 336 }