Source code

Revision control

Other Tools

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