The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-

  * This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #include "LayerSorter.h"

 #include <math.h>                       // for fabs

 #include <stdint.h>                     // for uint32_t

 #include <stdio.h>                      // for fprintf, stderr, FILE

 #include <stdlib.h>                     // for getenv

 #include "DirectedGraph.h"              // for DirectedGraph

 #include "Layers.h"                     // for Layer

 #include "gfx3DMatrix.h"                // for gfx3DMatrix

 #include "gfxLineSegment.h"             // for gfxLineSegment

 #include "gfxPoint.h"                   // for gfxPoint

 #include "gfxPoint3D.h"                 // for gfxPoint3D

 #include "gfxQuad.h"                    // for gfxQuad

 #include "gfxRect.h"                    // for gfxRect

 #include "gfxTypes.h"                   // for gfxFloat

 #include "mozilla/gfx/BasePoint3D.h"    // for BasePoint3D

 #include "nsRegion.h"                   // for nsIntRegion

 #include "nsTArray.h"                   // for nsTArray, etc

 #include "limits.h"

 #include "mozilla/Assertions.h"

 using namespace mozilla::gfx;

 namespace mozilla {

 namespace layers {

 enum LayerSortOrder {

   Undefined,

   ABeforeB,

   BBeforeA,

 };

 /**

  * Recover the z component from a 2d transformed point by finding the intersection

  * of a line through the point in the z direction and the transformed plane.

  *

  * We want to solve:

  *

  * point = normal . (p0 - l0) / normal . l

  */

 static gfxFloat RecoverZDepth(const gfx3DMatrix& aTransform, const gfxPoint& aPoint)

 {

     const gfxPoint3D l(0, 0, 1);

     gfxPoint3D l0 = gfxPoint3D(aPoint.x, aPoint.y, 0);

     gfxPoint3D p0 = aTransform.Transform3D(gfxPoint3D(0, 0, 0));

     gfxPoint3D normal = aTransform.GetNormalVector();

     gfxFloat n = normal.DotProduct(p0 - l0); 

     gfxFloat d = normal.DotProduct(l);

     if (!d) {

         return 0;

     }

     return n/d;

 }

 /**

  * Determine if this transform layer should be drawn before another when they 

  * are both preserve-3d children.

  *

  * We want to find the relative z depths of the 2 layers at points where they

  * intersect when projected onto the 2d screen plane. Intersections are defined

  * as corners that are positioned within the other quad, as well as intersections

  * of the lines.

  *

  * We then choose the intersection point with the greatest difference in Z

  * depths and use this point to determine an ordering for the two layers.

  * For layers that are intersecting in 3d space, this essentially guesses an 

  * order. In a lot of cases we only intersect right at the edge point (3d cubes

  * in particular) and this generates the 'correct' looking ordering. For planes

  * that truely intersect, then there is no correct ordering and this remains

  * unsolved without changing our rendering code.

  */

 static LayerSortOrder CompareDepth(Layer* aOne, Layer* aTwo) {

   gfxRect ourRect = aOne->GetEffectiveVisibleRegion().GetBounds();

   gfxRect otherRect = aTwo->GetEffectiveVisibleRegion().GetBounds();

   gfx3DMatrix ourTransform;

   To3DMatrix(aOne->GetTransform(), ourTransform);

   gfx3DMatrix otherTransform;

   To3DMatrix(aTwo->GetTransform(), otherTransform);

   // Transform both rectangles and project into 2d space.

   gfxQuad ourTransformedRect = ourTransform.TransformRect(ourRect);

   gfxQuad otherTransformedRect = otherTransform.TransformRect(otherRect);

   gfxRect ourBounds = ourTransformedRect.GetBounds();

   gfxRect otherBounds = otherTransformedRect.GetBounds();

   if (!ourBounds.Intersects(otherBounds)) {

     return Undefined;

   }

   // Make a list of all points that are within the other rect.

   // Could we just check Contains() on the bounds rects. ie, is it possible

   // for layers to overlap without intersections (in 2d space) and yet still

   // have their bounds rects not completely enclose each other?

   nsTArray<gfxPoint> points;

   for (uint32_t i = 0; i < 4; i++) {

     if (ourTransformedRect.Contains(otherTransformedRect.mPoints[i])) {

       points.AppendElement(otherTransformedRect.mPoints[i]);

     }

     if (otherTransformedRect.Contains(ourTransformedRect.mPoints[i])) {

       points.AppendElement(ourTransformedRect.mPoints[i]);

     }

   }

   // Look for intersections between lines (in 2d space) and use these as

   // depth testing points.

   for (uint32_t i = 0; i < 4; i++) {

     for (uint32_t j = 0; j < 4; j++) {

       gfxPoint intersection;

       gfxLineSegment one(ourTransformedRect.mPoints[i],

                          ourTransformedRect.mPoints[(i + 1) % 4]);

       gfxLineSegment two(otherTransformedRect.mPoints[j],

                          otherTransformedRect.mPoints[(j + 1) % 4]);

       if (one.Intersects(two, intersection)) {

         points.AppendElement(intersection);

       }

     }

   }

   // No intersections, no defined order between these layers.

   if (points.IsEmpty()) {

     return Undefined;

   }

   // Find the relative Z depths of each intersection point and check that the layers are in the same order.

   gfxFloat highest = 0;

   for (uint32_t i = 0; i < points.Length(); i++) {

     gfxFloat ourDepth = RecoverZDepth(ourTransform, points.ElementAt(i));

     gfxFloat otherDepth = RecoverZDepth(otherTransform, points.ElementAt(i));

     gfxFloat difference = otherDepth - ourDepth;

     if (fabs(difference) > fabs(highest)) {

       highest = difference;

     }

   }

   // If layers have the same depth keep the original order

   if (fabs(highest) < 0.1 || highest >= 0) {

     return ABeforeB;

   } else {

     return BBeforeA;

   }

 }

 #ifdef DEBUG

 static bool gDumpLayerSortList = getenv("MOZ_DUMP_LAYER_SORT_LIST") != 0;

 static const int BLACK = 0;

 static const int RED = 1;

 static const int GREEN = 2;

 static const int YELLOW = 3;

 static const int BLUE = 4;

 static const int MAGENTA = 5;

 static const int CYAN = 6;

 static const int WHITE = 7;

 //#define USE_XTERM_COLORING

 #ifdef USE_XTERM_COLORING

 static const int RESET = 0;

 static const int BRIGHT = 1;

 static const int DIM = 2;

 static const int UNDERLINE = 3;

 static const int BLINK = 4;

 static const int REVERSE = 7;

 static const int HIDDEN = 8;

 static void SetTextColor(uint32_t aColor)

 {

   char command[13];

   /* Command is the control command to the terminal */

   sprintf(command, "%c[%d;%d;%dm", 0x1B, RESET, aColor + 30, BLACK + 40);

   printf("%s", command);

 }

 static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)

 {

   SetTextColor(aColor);

   fprintf(aFile, "%p", aLayer);

   SetTextColor(GREEN);

 }

 #else

 const char *colors[] = { "Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White" };

 static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)

 {

   fprintf(aFile, "%p(%s)", aLayer, colors[aColor]);

 }

 #endif

 static void print_layer(FILE* aFile, Layer* aLayer)

 {

   print_layer_internal(aFile, aLayer, aLayer->GetDebugColorIndex());

 }

 static void DumpLayerList(nsTArray<Layer*>& aLayers)

 {

   for (uint32_t i = 0; i < aLayers.Length(); i++) {

     print_layer(stderr, aLayers.ElementAt(i));

     fprintf(stderr, " ");

   }

   fprintf(stderr, "\n");

 }

 static void DumpEdgeList(DirectedGraph<Layer*>& aGraph)

 {

   const nsTArray<DirectedGraph<Layer*>::Edge>& edges = aGraph.GetEdgeList();

   for (uint32_t i = 0; i < edges.Length(); i++) {

     fprintf(stderr, "From: ");

     print_layer(stderr, edges.ElementAt(i).mFrom);

     fprintf(stderr, ", To: ");

     print_layer(stderr, edges.ElementAt(i).mTo);

     fprintf(stderr, "\n");

   }

 }

 #endif

 // The maximum number of layers that we will attempt to sort. Anything

 // greater than this will be left unsorted. We should consider enabling

 // depth buffering for the scene in this case.

 #define MAX_SORTABLE_LAYERS 100

 uint32_t gColorIndex = 1;

 void SortLayersBy3DZOrder(nsTArray<Layer*>& aLayers)

 {

   uint32_t nodeCount = aLayers.Length();

   if (nodeCount > MAX_SORTABLE_LAYERS) {

     return;

   }

   DirectedGraph<Layer*> graph;

 #ifdef DEBUG

   if (gDumpLayerSortList) {

     for (uint32_t i = 0; i < nodeCount; i++) {

       if (aLayers.ElementAt(i)->GetDebugColorIndex() == 0) {

         aLayers.ElementAt(i)->SetDebugColorIndex(gColorIndex++);

         if (gColorIndex > 7) {

           gColorIndex = 1;

         }

       }

     }

     fprintf(stderr, " --- Layers before sorting: --- \n");

     DumpLayerList(aLayers);

   }

 #endif

   // Iterate layers and determine edges.

   for (uint32_t i = 0; i < nodeCount; i++) {

     for (uint32_t j = i + 1; j < nodeCount; j++) {

       Layer* a = aLayers.ElementAt(i);

       Layer* b = aLayers.ElementAt(j);

       LayerSortOrder order = CompareDepth(a, b);

       if (order == ABeforeB) {

         graph.AddEdge(a, b);

       } else if (order == BBeforeA) {

         graph.AddEdge(b, a);

       }

     }

   }

 #ifdef DEBUG

   if (gDumpLayerSortList) {

     fprintf(stderr, " --- Edge List: --- \n");

     DumpEdgeList(graph);

   }

 #endif

   // Build a new array using the graph.

   nsTArray<Layer*> noIncoming;

   nsTArray<Layer*> sortedList;

   // Make a list of all layers with no incoming edges.

   noIncoming.AppendElements(aLayers);

   const nsTArray<DirectedGraph<Layer*>::Edge>& edges = graph.GetEdgeList();

   for (uint32_t i = 0; i < edges.Length(); i++) {

     noIncoming.RemoveElement(edges.ElementAt(i).mTo);

   }

   // Move each item without incoming edges into the sorted list,

   // and remove edges from it.

   do {

     if (!noIncoming.IsEmpty()) {

       uint32_t last = noIncoming.Length() - 1;

       Layer* layer = noIncoming.ElementAt(last);

       MOZ_ASSERT(layer); // don't let null layer pointers sneak into sortedList

       noIncoming.RemoveElementAt(last);

       sortedList.AppendElement(layer);

       nsTArray<DirectedGraph<Layer*>::Edge> outgoing;

       graph.GetEdgesFrom(layer, outgoing);

       for (uint32_t i = 0; i < outgoing.Length(); i++) {

         DirectedGraph<Layer*>::Edge edge = outgoing.ElementAt(i);

         graph.RemoveEdge(edge);

         if (!graph.NumEdgesTo(edge.mTo)) {

           // If this node also has no edges now, add it to the list

           noIncoming.AppendElement(edge.mTo);

         }

       }

     }

     // If there are no nodes without incoming edges, but there

     // are still edges, then we have a cycle.

     if (noIncoming.IsEmpty() && graph.GetEdgeCount()) {

       // Find the node with the least incoming edges.

       uint32_t minEdges = UINT_MAX;

       Layer* minNode = nullptr;

       for (uint32_t i = 0; i < aLayers.Length(); i++) {

         uint32_t edgeCount = graph.NumEdgesTo(aLayers.ElementAt(i));

         if (edgeCount && edgeCount < minEdges) {

           minEdges = edgeCount;

           minNode = aLayers.ElementAt(i);

           if (minEdges == 1) {

             break;

           }

         }

       }

       if (minNode) {

         // Remove all of them!

         graph.RemoveEdgesTo(minNode);

         noIncoming.AppendElement(minNode);

       }

     }

   } while (!noIncoming.IsEmpty());

   NS_ASSERTION(!graph.GetEdgeCount(), "Cycles detected!");

 #ifdef DEBUG

   if (gDumpLayerSortList) {

     fprintf(stderr, " --- Layers after sorting: --- \n");

     DumpLayerList(sortedList);

   }

 #endif

   aLayers.Clear();

   aLayers.AppendElements(sortedList);

 }

 }

 }