michael@0: /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "LayerSorter.h"
michael@0: #include <math.h>                       // for fabs
michael@0: #include <stdint.h>                     // for uint32_t
michael@0: #include <stdio.h>                      // for fprintf, stderr, FILE
michael@0: #include <stdlib.h>                     // for getenv
michael@0: #include "DirectedGraph.h"              // for DirectedGraph
michael@0: #include "Layers.h"                     // for Layer
michael@0: #include "gfx3DMatrix.h"                // for gfx3DMatrix
michael@0: #include "gfxLineSegment.h"             // for gfxLineSegment
michael@0: #include "gfxPoint.h"                   // for gfxPoint
michael@0: #include "gfxPoint3D.h"                 // for gfxPoint3D
michael@0: #include "gfxQuad.h"                    // for gfxQuad
michael@0: #include "gfxRect.h"                    // for gfxRect
michael@0: #include "gfxTypes.h"                   // for gfxFloat
michael@0: #include "mozilla/gfx/BasePoint3D.h"    // for BasePoint3D
michael@0: #include "nsRegion.h"                   // for nsIntRegion
michael@0: #include "nsTArray.h"                   // for nsTArray, etc
michael@0: #include "limits.h"
michael@0: #include "mozilla/Assertions.h"
michael@0: 
michael@0: using namespace mozilla::gfx;
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace layers {
michael@0: 
michael@0: enum LayerSortOrder {
michael@0:   Undefined,
michael@0:   ABeforeB,
michael@0:   BBeforeA,
michael@0: };
michael@0: 
michael@0: /**
michael@0:  * Recover the z component from a 2d transformed point by finding the intersection
michael@0:  * of a line through the point in the z direction and the transformed plane.
michael@0:  *
michael@0:  * We want to solve:
michael@0:  *
michael@0:  * point = normal . (p0 - l0) / normal . l
michael@0:  */
michael@0: static gfxFloat RecoverZDepth(const gfx3DMatrix& aTransform, const gfxPoint& aPoint)
michael@0: {
michael@0:     const gfxPoint3D l(0, 0, 1);
michael@0:     gfxPoint3D l0 = gfxPoint3D(aPoint.x, aPoint.y, 0);
michael@0:     gfxPoint3D p0 = aTransform.Transform3D(gfxPoint3D(0, 0, 0));
michael@0:     gfxPoint3D normal = aTransform.GetNormalVector();
michael@0: 
michael@0:     gfxFloat n = normal.DotProduct(p0 - l0); 
michael@0:     gfxFloat d = normal.DotProduct(l);
michael@0: 
michael@0:     if (!d) {
michael@0:         return 0;
michael@0:     }
michael@0: 
michael@0:     return n/d;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Determine if this transform layer should be drawn before another when they 
michael@0:  * are both preserve-3d children.
michael@0:  *
michael@0:  * We want to find the relative z depths of the 2 layers at points where they
michael@0:  * intersect when projected onto the 2d screen plane. Intersections are defined
michael@0:  * as corners that are positioned within the other quad, as well as intersections
michael@0:  * of the lines.
michael@0:  *
michael@0:  * We then choose the intersection point with the greatest difference in Z
michael@0:  * depths and use this point to determine an ordering for the two layers.
michael@0:  * For layers that are intersecting in 3d space, this essentially guesses an 
michael@0:  * order. In a lot of cases we only intersect right at the edge point (3d cubes
michael@0:  * in particular) and this generates the 'correct' looking ordering. For planes
michael@0:  * that truely intersect, then there is no correct ordering and this remains
michael@0:  * unsolved without changing our rendering code.
michael@0:  */
michael@0: static LayerSortOrder CompareDepth(Layer* aOne, Layer* aTwo) {
michael@0:   gfxRect ourRect = aOne->GetEffectiveVisibleRegion().GetBounds();
michael@0:   gfxRect otherRect = aTwo->GetEffectiveVisibleRegion().GetBounds();
michael@0: 
michael@0:   gfx3DMatrix ourTransform;
michael@0:   To3DMatrix(aOne->GetTransform(), ourTransform);
michael@0:   gfx3DMatrix otherTransform;
michael@0:   To3DMatrix(aTwo->GetTransform(), otherTransform);
michael@0: 
michael@0:   // Transform both rectangles and project into 2d space.
michael@0:   gfxQuad ourTransformedRect = ourTransform.TransformRect(ourRect);
michael@0:   gfxQuad otherTransformedRect = otherTransform.TransformRect(otherRect);
michael@0: 
michael@0:   gfxRect ourBounds = ourTransformedRect.GetBounds();
michael@0:   gfxRect otherBounds = otherTransformedRect.GetBounds();
michael@0: 
michael@0:   if (!ourBounds.Intersects(otherBounds)) {
michael@0:     return Undefined;
michael@0:   }
michael@0: 
michael@0:   // Make a list of all points that are within the other rect.
michael@0:   // Could we just check Contains() on the bounds rects. ie, is it possible
michael@0:   // for layers to overlap without intersections (in 2d space) and yet still
michael@0:   // have their bounds rects not completely enclose each other?
michael@0:   nsTArray<gfxPoint> points;
michael@0:   for (uint32_t i = 0; i < 4; i++) {
michael@0:     if (ourTransformedRect.Contains(otherTransformedRect.mPoints[i])) {
michael@0:       points.AppendElement(otherTransformedRect.mPoints[i]);
michael@0:     }
michael@0:     if (otherTransformedRect.Contains(ourTransformedRect.mPoints[i])) {
michael@0:       points.AppendElement(ourTransformedRect.mPoints[i]);
michael@0:     }
michael@0:   }
michael@0:   
michael@0:   // Look for intersections between lines (in 2d space) and use these as
michael@0:   // depth testing points.
michael@0:   for (uint32_t i = 0; i < 4; i++) {
michael@0:     for (uint32_t j = 0; j < 4; j++) {
michael@0:       gfxPoint intersection;
michael@0:       gfxLineSegment one(ourTransformedRect.mPoints[i],
michael@0:                          ourTransformedRect.mPoints[(i + 1) % 4]);
michael@0:       gfxLineSegment two(otherTransformedRect.mPoints[j],
michael@0:                          otherTransformedRect.mPoints[(j + 1) % 4]);
michael@0:       if (one.Intersects(two, intersection)) {
michael@0:         points.AppendElement(intersection);
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // No intersections, no defined order between these layers.
michael@0:   if (points.IsEmpty()) {
michael@0:     return Undefined;
michael@0:   }
michael@0: 
michael@0:   // Find the relative Z depths of each intersection point and check that the layers are in the same order.
michael@0:   gfxFloat highest = 0;
michael@0:   for (uint32_t i = 0; i < points.Length(); i++) {
michael@0:     gfxFloat ourDepth = RecoverZDepth(ourTransform, points.ElementAt(i));
michael@0:     gfxFloat otherDepth = RecoverZDepth(otherTransform, points.ElementAt(i));
michael@0: 
michael@0:     gfxFloat difference = otherDepth - ourDepth;
michael@0: 
michael@0:     if (fabs(difference) > fabs(highest)) {
michael@0:       highest = difference;
michael@0:     }
michael@0:   }
michael@0:   // If layers have the same depth keep the original order
michael@0:   if (fabs(highest) < 0.1 || highest >= 0) {
michael@0:     return ABeforeB;
michael@0:   } else {
michael@0:     return BBeforeA;
michael@0:   }
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: static bool gDumpLayerSortList = getenv("MOZ_DUMP_LAYER_SORT_LIST") != 0;
michael@0: 
michael@0: static const int BLACK = 0;
michael@0: static const int RED = 1;
michael@0: static const int GREEN = 2;
michael@0: static const int YELLOW = 3;
michael@0: static const int BLUE = 4;
michael@0: static const int MAGENTA = 5;
michael@0: static const int CYAN = 6;
michael@0: static const int WHITE = 7;
michael@0: 
michael@0: //#define USE_XTERM_COLORING
michael@0: #ifdef USE_XTERM_COLORING
michael@0: 
michael@0: static const int RESET = 0;
michael@0: static const int BRIGHT = 1;
michael@0: static const int DIM = 2;
michael@0: static const int UNDERLINE = 3;
michael@0: static const int BLINK = 4;
michael@0: static const int REVERSE = 7;
michael@0: static const int HIDDEN = 8;
michael@0: 
michael@0: static void SetTextColor(uint32_t aColor)
michael@0: {
michael@0:   char command[13];
michael@0: 
michael@0:   /* Command is the control command to the terminal */
michael@0:   sprintf(command, "%c[%d;%d;%dm", 0x1B, RESET, aColor + 30, BLACK + 40);
michael@0:   printf("%s", command);
michael@0: }
michael@0: 
michael@0: static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
michael@0: {
michael@0:   SetTextColor(aColor);
michael@0:   fprintf(aFile, "%p", aLayer);
michael@0:   SetTextColor(GREEN);
michael@0: }
michael@0: #else
michael@0: 
michael@0: const char *colors[] = { "Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White" };
michael@0: 
michael@0: static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
michael@0: {
michael@0:   fprintf(aFile, "%p(%s)", aLayer, colors[aColor]);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: static void print_layer(FILE* aFile, Layer* aLayer)
michael@0: {
michael@0:   print_layer_internal(aFile, aLayer, aLayer->GetDebugColorIndex());
michael@0: }
michael@0: 
michael@0: static void DumpLayerList(nsTArray<Layer*>& aLayers)
michael@0: {
michael@0:   for (uint32_t i = 0; i < aLayers.Length(); i++) {
michael@0:     print_layer(stderr, aLayers.ElementAt(i));
michael@0:     fprintf(stderr, " ");
michael@0:   }
michael@0:   fprintf(stderr, "\n");
michael@0: }
michael@0: 
michael@0: static void DumpEdgeList(DirectedGraph<Layer*>& aGraph)
michael@0: {
michael@0:   const nsTArray<DirectedGraph<Layer*>::Edge>& edges = aGraph.GetEdgeList();
michael@0:   
michael@0:   for (uint32_t i = 0; i < edges.Length(); i++) {
michael@0:     fprintf(stderr, "From: ");
michael@0:     print_layer(stderr, edges.ElementAt(i).mFrom);
michael@0:     fprintf(stderr, ", To: ");
michael@0:     print_layer(stderr, edges.ElementAt(i).mTo);
michael@0:     fprintf(stderr, "\n");
michael@0:   }
michael@0: }
michael@0: #endif
michael@0: 
michael@0: // The maximum number of layers that we will attempt to sort. Anything
michael@0: // greater than this will be left unsorted. We should consider enabling
michael@0: // depth buffering for the scene in this case.
michael@0: #define MAX_SORTABLE_LAYERS 100
michael@0: 
michael@0: 
michael@0: uint32_t gColorIndex = 1;
michael@0: 
michael@0: void SortLayersBy3DZOrder(nsTArray<Layer*>& aLayers)
michael@0: {
michael@0:   uint32_t nodeCount = aLayers.Length();
michael@0:   if (nodeCount > MAX_SORTABLE_LAYERS) {
michael@0:     return;
michael@0:   }
michael@0:   DirectedGraph<Layer*> graph;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   if (gDumpLayerSortList) {
michael@0:     for (uint32_t i = 0; i < nodeCount; i++) {
michael@0:       if (aLayers.ElementAt(i)->GetDebugColorIndex() == 0) {
michael@0:         aLayers.ElementAt(i)->SetDebugColorIndex(gColorIndex++);
michael@0:         if (gColorIndex > 7) {
michael@0:           gColorIndex = 1;
michael@0:         }
michael@0:       }
michael@0:     }
michael@0:     fprintf(stderr, " --- Layers before sorting: --- \n");
michael@0:     DumpLayerList(aLayers);
michael@0:   }
michael@0: #endif
michael@0: 
michael@0:   // Iterate layers and determine edges.
michael@0:   for (uint32_t i = 0; i < nodeCount; i++) {
michael@0:     for (uint32_t j = i + 1; j < nodeCount; j++) {
michael@0:       Layer* a = aLayers.ElementAt(i);
michael@0:       Layer* b = aLayers.ElementAt(j);
michael@0:       LayerSortOrder order = CompareDepth(a, b);
michael@0:       if (order == ABeforeB) {
michael@0:         graph.AddEdge(a, b);
michael@0:       } else if (order == BBeforeA) {
michael@0:         graph.AddEdge(b, a);
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   if (gDumpLayerSortList) {
michael@0:     fprintf(stderr, " --- Edge List: --- \n");
michael@0:     DumpEdgeList(graph);
michael@0:   }
michael@0: #endif
michael@0: 
michael@0:   // Build a new array using the graph.
michael@0:   nsTArray<Layer*> noIncoming;
michael@0:   nsTArray<Layer*> sortedList;
michael@0: 
michael@0:   // Make a list of all layers with no incoming edges.
michael@0:   noIncoming.AppendElements(aLayers);
michael@0:   const nsTArray<DirectedGraph<Layer*>::Edge>& edges = graph.GetEdgeList();
michael@0:   for (uint32_t i = 0; i < edges.Length(); i++) {
michael@0:     noIncoming.RemoveElement(edges.ElementAt(i).mTo);
michael@0:   }
michael@0: 
michael@0:   // Move each item without incoming edges into the sorted list,
michael@0:   // and remove edges from it.
michael@0:   do {
michael@0:     if (!noIncoming.IsEmpty()) {
michael@0:       uint32_t last = noIncoming.Length() - 1;
michael@0: 
michael@0:       Layer* layer = noIncoming.ElementAt(last);
michael@0:       MOZ_ASSERT(layer); // don't let null layer pointers sneak into sortedList
michael@0: 
michael@0:       noIncoming.RemoveElementAt(last);
michael@0:       sortedList.AppendElement(layer);
michael@0: 
michael@0:       nsTArray<DirectedGraph<Layer*>::Edge> outgoing;
michael@0:       graph.GetEdgesFrom(layer, outgoing);
michael@0:       for (uint32_t i = 0; i < outgoing.Length(); i++) {
michael@0:         DirectedGraph<Layer*>::Edge edge = outgoing.ElementAt(i);
michael@0:         graph.RemoveEdge(edge);
michael@0:         if (!graph.NumEdgesTo(edge.mTo)) {
michael@0:           // If this node also has no edges now, add it to the list
michael@0:           noIncoming.AppendElement(edge.mTo);
michael@0:         }
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     // If there are no nodes without incoming edges, but there
michael@0:     // are still edges, then we have a cycle.
michael@0:     if (noIncoming.IsEmpty() && graph.GetEdgeCount()) {
michael@0:       // Find the node with the least incoming edges.
michael@0:       uint32_t minEdges = UINT_MAX;
michael@0:       Layer* minNode = nullptr;
michael@0:       for (uint32_t i = 0; i < aLayers.Length(); i++) {
michael@0:         uint32_t edgeCount = graph.NumEdgesTo(aLayers.ElementAt(i));
michael@0:         if (edgeCount && edgeCount < minEdges) {
michael@0:           minEdges = edgeCount;
michael@0:           minNode = aLayers.ElementAt(i);
michael@0:           if (minEdges == 1) {
michael@0:             break;
michael@0:           }
michael@0:         }
michael@0:       }
michael@0: 
michael@0:       if (minNode) {
michael@0:         // Remove all of them!
michael@0:         graph.RemoveEdgesTo(minNode);
michael@0:         noIncoming.AppendElement(minNode);
michael@0:       }
michael@0:     }
michael@0:   } while (!noIncoming.IsEmpty());
michael@0:   NS_ASSERTION(!graph.GetEdgeCount(), "Cycles detected!");
michael@0: #ifdef DEBUG
michael@0:   if (gDumpLayerSortList) {
michael@0:     fprintf(stderr, " --- Layers after sorting: --- \n");
michael@0:     DumpLayerList(sortedList);
michael@0:   }
michael@0: #endif
michael@0: 
michael@0:   aLayers.Clear();
michael@0:   aLayers.AppendElements(sortedList);
michael@0: }
michael@0: 
michael@0: }
michael@0: }