diff -r 000000000000 -r 6474c204b198 gfx/layers/LayerSorter.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gfx/layers/LayerSorter.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,353 @@ +/* -*- 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 // for fabs +#include // for uint32_t +#include // for fprintf, stderr, FILE +#include // 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 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& 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& aGraph) +{ + const nsTArray::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& aLayers) +{ + uint32_t nodeCount = aLayers.Length(); + if (nodeCount > MAX_SORTABLE_LAYERS) { + return; + } + DirectedGraph 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 noIncoming; + nsTArray sortedList; + + // Make a list of all layers with no incoming edges. + noIncoming.AppendElements(aLayers); + const nsTArray::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::Edge> outgoing; + graph.GetEdgesFrom(layer, outgoing); + for (uint32_t i = 0; i < outgoing.Length(); i++) { + DirectedGraph::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); +} + +} +}