1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/layers/LayerSorter.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,353 @@
1.4 +/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
1.5 + * This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "LayerSorter.h"
1.10 +#include <math.h> // for fabs
1.11 +#include <stdint.h> // for uint32_t
1.12 +#include <stdio.h> // for fprintf, stderr, FILE
1.13 +#include <stdlib.h> // for getenv
1.14 +#include "DirectedGraph.h" // for DirectedGraph
1.15 +#include "Layers.h" // for Layer
1.16 +#include "gfx3DMatrix.h" // for gfx3DMatrix
1.17 +#include "gfxLineSegment.h" // for gfxLineSegment
1.18 +#include "gfxPoint.h" // for gfxPoint
1.19 +#include "gfxPoint3D.h" // for gfxPoint3D
1.20 +#include "gfxQuad.h" // for gfxQuad
1.21 +#include "gfxRect.h" // for gfxRect
1.22 +#include "gfxTypes.h" // for gfxFloat
1.23 +#include "mozilla/gfx/BasePoint3D.h" // for BasePoint3D
1.24 +#include "nsRegion.h" // for nsIntRegion
1.25 +#include "nsTArray.h" // for nsTArray, etc
1.26 +#include "limits.h"
1.27 +#include "mozilla/Assertions.h"
1.28 +
1.29 +using namespace mozilla::gfx;
1.30 +
1.31 +namespace mozilla {
1.32 +namespace layers {
1.33 +
1.34 +enum LayerSortOrder {
1.35 + Undefined,
1.36 + ABeforeB,
1.37 + BBeforeA,
1.38 +};
1.39 +
1.40 +/**
1.41 + * Recover the z component from a 2d transformed point by finding the intersection
1.42 + * of a line through the point in the z direction and the transformed plane.
1.43 + *
1.44 + * We want to solve:
1.45 + *
1.46 + * point = normal . (p0 - l0) / normal . l
1.47 + */
1.48 +static gfxFloat RecoverZDepth(const gfx3DMatrix& aTransform, const gfxPoint& aPoint)
1.49 +{
1.50 + const gfxPoint3D l(0, 0, 1);
1.51 + gfxPoint3D l0 = gfxPoint3D(aPoint.x, aPoint.y, 0);
1.52 + gfxPoint3D p0 = aTransform.Transform3D(gfxPoint3D(0, 0, 0));
1.53 + gfxPoint3D normal = aTransform.GetNormalVector();
1.54 +
1.55 + gfxFloat n = normal.DotProduct(p0 - l0);
1.56 + gfxFloat d = normal.DotProduct(l);
1.57 +
1.58 + if (!d) {
1.59 + return 0;
1.60 + }
1.61 +
1.62 + return n/d;
1.63 +}
1.64 +
1.65 +/**
1.66 + * Determine if this transform layer should be drawn before another when they
1.67 + * are both preserve-3d children.
1.68 + *
1.69 + * We want to find the relative z depths of the 2 layers at points where they
1.70 + * intersect when projected onto the 2d screen plane. Intersections are defined
1.71 + * as corners that are positioned within the other quad, as well as intersections
1.72 + * of the lines.
1.73 + *
1.74 + * We then choose the intersection point with the greatest difference in Z
1.75 + * depths and use this point to determine an ordering for the two layers.
1.76 + * For layers that are intersecting in 3d space, this essentially guesses an
1.77 + * order. In a lot of cases we only intersect right at the edge point (3d cubes
1.78 + * in particular) and this generates the 'correct' looking ordering. For planes
1.79 + * that truely intersect, then there is no correct ordering and this remains
1.80 + * unsolved without changing our rendering code.
1.81 + */
1.82 +static LayerSortOrder CompareDepth(Layer* aOne, Layer* aTwo) {
1.83 + gfxRect ourRect = aOne->GetEffectiveVisibleRegion().GetBounds();
1.84 + gfxRect otherRect = aTwo->GetEffectiveVisibleRegion().GetBounds();
1.85 +
1.86 + gfx3DMatrix ourTransform;
1.87 + To3DMatrix(aOne->GetTransform(), ourTransform);
1.88 + gfx3DMatrix otherTransform;
1.89 + To3DMatrix(aTwo->GetTransform(), otherTransform);
1.90 +
1.91 + // Transform both rectangles and project into 2d space.
1.92 + gfxQuad ourTransformedRect = ourTransform.TransformRect(ourRect);
1.93 + gfxQuad otherTransformedRect = otherTransform.TransformRect(otherRect);
1.94 +
1.95 + gfxRect ourBounds = ourTransformedRect.GetBounds();
1.96 + gfxRect otherBounds = otherTransformedRect.GetBounds();
1.97 +
1.98 + if (!ourBounds.Intersects(otherBounds)) {
1.99 + return Undefined;
1.100 + }
1.101 +
1.102 + // Make a list of all points that are within the other rect.
1.103 + // Could we just check Contains() on the bounds rects. ie, is it possible
1.104 + // for layers to overlap without intersections (in 2d space) and yet still
1.105 + // have their bounds rects not completely enclose each other?
1.106 + nsTArray<gfxPoint> points;
1.107 + for (uint32_t i = 0; i < 4; i++) {
1.108 + if (ourTransformedRect.Contains(otherTransformedRect.mPoints[i])) {
1.109 + points.AppendElement(otherTransformedRect.mPoints[i]);
1.110 + }
1.111 + if (otherTransformedRect.Contains(ourTransformedRect.mPoints[i])) {
1.112 + points.AppendElement(ourTransformedRect.mPoints[i]);
1.113 + }
1.114 + }
1.115 +
1.116 + // Look for intersections between lines (in 2d space) and use these as
1.117 + // depth testing points.
1.118 + for (uint32_t i = 0; i < 4; i++) {
1.119 + for (uint32_t j = 0; j < 4; j++) {
1.120 + gfxPoint intersection;
1.121 + gfxLineSegment one(ourTransformedRect.mPoints[i],
1.122 + ourTransformedRect.mPoints[(i + 1) % 4]);
1.123 + gfxLineSegment two(otherTransformedRect.mPoints[j],
1.124 + otherTransformedRect.mPoints[(j + 1) % 4]);
1.125 + if (one.Intersects(two, intersection)) {
1.126 + points.AppendElement(intersection);
1.127 + }
1.128 + }
1.129 + }
1.130 +
1.131 + // No intersections, no defined order between these layers.
1.132 + if (points.IsEmpty()) {
1.133 + return Undefined;
1.134 + }
1.135 +
1.136 + // Find the relative Z depths of each intersection point and check that the layers are in the same order.
1.137 + gfxFloat highest = 0;
1.138 + for (uint32_t i = 0; i < points.Length(); i++) {
1.139 + gfxFloat ourDepth = RecoverZDepth(ourTransform, points.ElementAt(i));
1.140 + gfxFloat otherDepth = RecoverZDepth(otherTransform, points.ElementAt(i));
1.141 +
1.142 + gfxFloat difference = otherDepth - ourDepth;
1.143 +
1.144 + if (fabs(difference) > fabs(highest)) {
1.145 + highest = difference;
1.146 + }
1.147 + }
1.148 + // If layers have the same depth keep the original order
1.149 + if (fabs(highest) < 0.1 || highest >= 0) {
1.150 + return ABeforeB;
1.151 + } else {
1.152 + return BBeforeA;
1.153 + }
1.154 +}
1.155 +
1.156 +#ifdef DEBUG
1.157 +static bool gDumpLayerSortList = getenv("MOZ_DUMP_LAYER_SORT_LIST") != 0;
1.158 +
1.159 +static const int BLACK = 0;
1.160 +static const int RED = 1;
1.161 +static const int GREEN = 2;
1.162 +static const int YELLOW = 3;
1.163 +static const int BLUE = 4;
1.164 +static const int MAGENTA = 5;
1.165 +static const int CYAN = 6;
1.166 +static const int WHITE = 7;
1.167 +
1.168 +//#define USE_XTERM_COLORING
1.169 +#ifdef USE_XTERM_COLORING
1.170 +
1.171 +static const int RESET = 0;
1.172 +static const int BRIGHT = 1;
1.173 +static const int DIM = 2;
1.174 +static const int UNDERLINE = 3;
1.175 +static const int BLINK = 4;
1.176 +static const int REVERSE = 7;
1.177 +static const int HIDDEN = 8;
1.178 +
1.179 +static void SetTextColor(uint32_t aColor)
1.180 +{
1.181 + char command[13];
1.182 +
1.183 + /* Command is the control command to the terminal */
1.184 + sprintf(command, "%c[%d;%d;%dm", 0x1B, RESET, aColor + 30, BLACK + 40);
1.185 + printf("%s", command);
1.186 +}
1.187 +
1.188 +static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
1.189 +{
1.190 + SetTextColor(aColor);
1.191 + fprintf(aFile, "%p", aLayer);
1.192 + SetTextColor(GREEN);
1.193 +}
1.194 +#else
1.195 +
1.196 +const char *colors[] = { "Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White" };
1.197 +
1.198 +static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
1.199 +{
1.200 + fprintf(aFile, "%p(%s)", aLayer, colors[aColor]);
1.201 +}
1.202 +#endif
1.203 +
1.204 +static void print_layer(FILE* aFile, Layer* aLayer)
1.205 +{
1.206 + print_layer_internal(aFile, aLayer, aLayer->GetDebugColorIndex());
1.207 +}
1.208 +
1.209 +static void DumpLayerList(nsTArray<Layer*>& aLayers)
1.210 +{
1.211 + for (uint32_t i = 0; i < aLayers.Length(); i++) {
1.212 + print_layer(stderr, aLayers.ElementAt(i));
1.213 + fprintf(stderr, " ");
1.214 + }
1.215 + fprintf(stderr, "\n");
1.216 +}
1.217 +
1.218 +static void DumpEdgeList(DirectedGraph<Layer*>& aGraph)
1.219 +{
1.220 + const nsTArray<DirectedGraph<Layer*>::Edge>& edges = aGraph.GetEdgeList();
1.221 +
1.222 + for (uint32_t i = 0; i < edges.Length(); i++) {
1.223 + fprintf(stderr, "From: ");
1.224 + print_layer(stderr, edges.ElementAt(i).mFrom);
1.225 + fprintf(stderr, ", To: ");
1.226 + print_layer(stderr, edges.ElementAt(i).mTo);
1.227 + fprintf(stderr, "\n");
1.228 + }
1.229 +}
1.230 +#endif
1.231 +
1.232 +// The maximum number of layers that we will attempt to sort. Anything
1.233 +// greater than this will be left unsorted. We should consider enabling
1.234 +// depth buffering for the scene in this case.
1.235 +#define MAX_SORTABLE_LAYERS 100
1.236 +
1.237 +
1.238 +uint32_t gColorIndex = 1;
1.239 +
1.240 +void SortLayersBy3DZOrder(nsTArray<Layer*>& aLayers)
1.241 +{
1.242 + uint32_t nodeCount = aLayers.Length();
1.243 + if (nodeCount > MAX_SORTABLE_LAYERS) {
1.244 + return;
1.245 + }
1.246 + DirectedGraph<Layer*> graph;
1.247 +
1.248 +#ifdef DEBUG
1.249 + if (gDumpLayerSortList) {
1.250 + for (uint32_t i = 0; i < nodeCount; i++) {
1.251 + if (aLayers.ElementAt(i)->GetDebugColorIndex() == 0) {
1.252 + aLayers.ElementAt(i)->SetDebugColorIndex(gColorIndex++);
1.253 + if (gColorIndex > 7) {
1.254 + gColorIndex = 1;
1.255 + }
1.256 + }
1.257 + }
1.258 + fprintf(stderr, " --- Layers before sorting: --- \n");
1.259 + DumpLayerList(aLayers);
1.260 + }
1.261 +#endif
1.262 +
1.263 + // Iterate layers and determine edges.
1.264 + for (uint32_t i = 0; i < nodeCount; i++) {
1.265 + for (uint32_t j = i + 1; j < nodeCount; j++) {
1.266 + Layer* a = aLayers.ElementAt(i);
1.267 + Layer* b = aLayers.ElementAt(j);
1.268 + LayerSortOrder order = CompareDepth(a, b);
1.269 + if (order == ABeforeB) {
1.270 + graph.AddEdge(a, b);
1.271 + } else if (order == BBeforeA) {
1.272 + graph.AddEdge(b, a);
1.273 + }
1.274 + }
1.275 + }
1.276 +
1.277 +#ifdef DEBUG
1.278 + if (gDumpLayerSortList) {
1.279 + fprintf(stderr, " --- Edge List: --- \n");
1.280 + DumpEdgeList(graph);
1.281 + }
1.282 +#endif
1.283 +
1.284 + // Build a new array using the graph.
1.285 + nsTArray<Layer*> noIncoming;
1.286 + nsTArray<Layer*> sortedList;
1.287 +
1.288 + // Make a list of all layers with no incoming edges.
1.289 + noIncoming.AppendElements(aLayers);
1.290 + const nsTArray<DirectedGraph<Layer*>::Edge>& edges = graph.GetEdgeList();
1.291 + for (uint32_t i = 0; i < edges.Length(); i++) {
1.292 + noIncoming.RemoveElement(edges.ElementAt(i).mTo);
1.293 + }
1.294 +
1.295 + // Move each item without incoming edges into the sorted list,
1.296 + // and remove edges from it.
1.297 + do {
1.298 + if (!noIncoming.IsEmpty()) {
1.299 + uint32_t last = noIncoming.Length() - 1;
1.300 +
1.301 + Layer* layer = noIncoming.ElementAt(last);
1.302 + MOZ_ASSERT(layer); // don't let null layer pointers sneak into sortedList
1.303 +
1.304 + noIncoming.RemoveElementAt(last);
1.305 + sortedList.AppendElement(layer);
1.306 +
1.307 + nsTArray<DirectedGraph<Layer*>::Edge> outgoing;
1.308 + graph.GetEdgesFrom(layer, outgoing);
1.309 + for (uint32_t i = 0; i < outgoing.Length(); i++) {
1.310 + DirectedGraph<Layer*>::Edge edge = outgoing.ElementAt(i);
1.311 + graph.RemoveEdge(edge);
1.312 + if (!graph.NumEdgesTo(edge.mTo)) {
1.313 + // If this node also has no edges now, add it to the list
1.314 + noIncoming.AppendElement(edge.mTo);
1.315 + }
1.316 + }
1.317 + }
1.318 +
1.319 + // If there are no nodes without incoming edges, but there
1.320 + // are still edges, then we have a cycle.
1.321 + if (noIncoming.IsEmpty() && graph.GetEdgeCount()) {
1.322 + // Find the node with the least incoming edges.
1.323 + uint32_t minEdges = UINT_MAX;
1.324 + Layer* minNode = nullptr;
1.325 + for (uint32_t i = 0; i < aLayers.Length(); i++) {
1.326 + uint32_t edgeCount = graph.NumEdgesTo(aLayers.ElementAt(i));
1.327 + if (edgeCount && edgeCount < minEdges) {
1.328 + minEdges = edgeCount;
1.329 + minNode = aLayers.ElementAt(i);
1.330 + if (minEdges == 1) {
1.331 + break;
1.332 + }
1.333 + }
1.334 + }
1.335 +
1.336 + if (minNode) {
1.337 + // Remove all of them!
1.338 + graph.RemoveEdgesTo(minNode);
1.339 + noIncoming.AppendElement(minNode);
1.340 + }
1.341 + }
1.342 + } while (!noIncoming.IsEmpty());
1.343 + NS_ASSERTION(!graph.GetEdgeCount(), "Cycles detected!");
1.344 +#ifdef DEBUG
1.345 + if (gDumpLayerSortList) {
1.346 + fprintf(stderr, " --- Layers after sorting: --- \n");
1.347 + DumpLayerList(sortedList);
1.348 + }
1.349 +#endif
1.350 +
1.351 + aLayers.Clear();
1.352 + aLayers.AppendElements(sortedList);
1.353 +}
1.354 +
1.355 +}
1.356 +}
