gfx/layers/LayerSorter.cpp

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