Line data Source code
1 : /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 : * This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #include "LayerSorter.h"
7 : #include <math.h> // for fabs
8 : #include <stdint.h> // for uint32_t
9 : #include <stdio.h> // for fprintf, stderr, FILE
10 : #include <stdlib.h> // for getenv
11 : #include "DirectedGraph.h" // for DirectedGraph
12 : #include "Layers.h" // for Layer
13 : #include "gfxEnv.h" // for gfxEnv
14 : #include "gfxLineSegment.h" // for gfxLineSegment
15 : #include "gfxPoint.h" // for gfxPoint
16 : #include "gfxQuad.h" // for gfxQuad
17 : #include "gfxRect.h" // for gfxRect
18 : #include "gfxTypes.h" // for gfxFloat
19 : #include "gfxUtils.h" // for TransformToQuad
20 : #include "mozilla/gfx/BasePoint3D.h" // for BasePoint3D
21 : #include "mozilla/Sprintf.h" // for SprintfLiteral
22 : #include "nsRegion.h" // for nsIntRegion
23 : #include "nsTArray.h" // for nsTArray, etc
24 : #include "limits.h"
25 : #include "mozilla/Assertions.h"
26 :
27 : namespace mozilla {
28 : namespace layers {
29 :
30 : using namespace mozilla::gfx;
31 :
32 : enum LayerSortOrder {
33 : Undefined,
34 : ABeforeB,
35 : BBeforeA,
36 : };
37 :
38 : /**
39 : * Recover the z component from a 2d transformed point by finding the intersection
40 : * of a line through the point in the z direction and the transformed plane.
41 : *
42 : * We want to solve:
43 : *
44 : * point = normal . (p0 - l0) / normal . l
45 : */
46 0 : static gfxFloat RecoverZDepth(const Matrix4x4& aTransform, const gfxPoint& aPoint)
47 : {
48 0 : const Point3D l(0, 0, 1);
49 0 : Point3D l0 = Point3D(aPoint.x, aPoint.y, 0);
50 0 : Point3D p0 = aTransform.TransformPoint(Point3D(0, 0, 0));
51 0 : Point3D normal = aTransform.GetNormalVector();
52 :
53 0 : gfxFloat n = normal.DotProduct(p0 - l0);
54 0 : gfxFloat d = normal.DotProduct(l);
55 :
56 0 : if (!d) {
57 0 : return 0;
58 : }
59 :
60 0 : return n/d;
61 : }
62 :
63 : /**
64 : * Determine if this transform layer should be drawn before another when they
65 : * are both preserve-3d children.
66 : *
67 : * We want to find the relative z depths of the 2 layers at points where they
68 : * intersect when projected onto the 2d screen plane. Intersections are defined
69 : * as corners that are positioned within the other quad, as well as intersections
70 : * of the lines.
71 : *
72 : * We then choose the intersection point with the greatest difference in Z
73 : * depths and use this point to determine an ordering for the two layers.
74 : * For layers that are intersecting in 3d space, this essentially guesses an
75 : * order. In a lot of cases we only intersect right at the edge point (3d cubes
76 : * in particular) and this generates the 'correct' looking ordering. For planes
77 : * that truely intersect, then there is no correct ordering and this remains
78 : * unsolved without changing our rendering code.
79 : */
80 0 : static LayerSortOrder CompareDepth(Layer* aOne, Layer* aTwo) {
81 0 : gfxRect ourRect = ThebesRect(aOne->GetLocalVisibleRegion().ToUnknownRegion().GetBounds());
82 0 : gfxRect otherRect = ThebesRect(aTwo->GetLocalVisibleRegion().ToUnknownRegion().GetBounds());
83 :
84 0 : MOZ_ASSERT(aOne->GetParent() && aOne->GetParent()->Extend3DContext() &&
85 : aTwo->GetParent() && aTwo->GetParent()->Extend3DContext());
86 : // Effective transform of leaves may had been projected to 2D.
87 : Matrix4x4 ourTransform =
88 0 : aOne->GetLocalTransform() * aOne->GetParent()->GetEffectiveTransform();
89 : Matrix4x4 otherTransform =
90 0 : aTwo->GetLocalTransform() * aTwo->GetParent()->GetEffectiveTransform();
91 :
92 : // Transform both rectangles and project into 2d space.
93 0 : gfxQuad ourTransformedRect = gfxUtils::TransformToQuad(ourRect, ourTransform);
94 0 : gfxQuad otherTransformedRect = gfxUtils::TransformToQuad(otherRect, otherTransform);
95 :
96 0 : gfxRect ourBounds = ourTransformedRect.GetBounds();
97 0 : gfxRect otherBounds = otherTransformedRect.GetBounds();
98 :
99 0 : if (!ourBounds.Intersects(otherBounds)) {
100 0 : return Undefined;
101 : }
102 :
103 : // Make a list of all points that are within the other rect.
104 : // Could we just check Contains() on the bounds rects. ie, is it possible
105 : // for layers to overlap without intersections (in 2d space) and yet still
106 : // have their bounds rects not completely enclose each other?
107 0 : nsTArray<gfxPoint> points;
108 0 : for (uint32_t i = 0; i < 4; i++) {
109 0 : if (ourTransformedRect.Contains(otherTransformedRect.mPoints[i])) {
110 0 : points.AppendElement(otherTransformedRect.mPoints[i]);
111 : }
112 0 : if (otherTransformedRect.Contains(ourTransformedRect.mPoints[i])) {
113 0 : points.AppendElement(ourTransformedRect.mPoints[i]);
114 : }
115 : }
116 :
117 : // Look for intersections between lines (in 2d space) and use these as
118 : // depth testing points.
119 0 : for (uint32_t i = 0; i < 4; i++) {
120 0 : for (uint32_t j = 0; j < 4; j++) {
121 0 : gfxPoint intersection;
122 : gfxLineSegment one(ourTransformedRect.mPoints[i],
123 0 : ourTransformedRect.mPoints[(i + 1) % 4]);
124 : gfxLineSegment two(otherTransformedRect.mPoints[j],
125 0 : otherTransformedRect.mPoints[(j + 1) % 4]);
126 0 : if (one.Intersects(two, intersection)) {
127 0 : points.AppendElement(intersection);
128 : }
129 : }
130 : }
131 :
132 : // No intersections, no defined order between these layers.
133 0 : if (points.IsEmpty()) {
134 0 : return Undefined;
135 : }
136 :
137 : // Find the relative Z depths of each intersection point and check that the layers are in the same order.
138 0 : gfxFloat highest = 0;
139 0 : for (uint32_t i = 0; i < points.Length(); i++) {
140 0 : gfxFloat ourDepth = RecoverZDepth(ourTransform, points.ElementAt(i));
141 0 : gfxFloat otherDepth = RecoverZDepth(otherTransform, points.ElementAt(i));
142 :
143 0 : gfxFloat difference = otherDepth - ourDepth;
144 :
145 0 : if (fabs(difference) > fabs(highest)) {
146 0 : highest = difference;
147 : }
148 : }
149 : // If layers have the same depth keep the original order
150 0 : if (fabs(highest) < 0.1 || highest >= 0) {
151 0 : return ABeforeB;
152 : } else {
153 0 : return BBeforeA;
154 : }
155 : }
156 :
157 : #ifdef DEBUG
158 : // #define USE_XTERM_COLORING
159 : #ifdef USE_XTERM_COLORING
160 : // List of color values, which can be added to the xterm foreground offset or
161 : // background offset to generate a xterm color code.
162 : // NOTE: The colors that we don't explicitly use (by name) are commented out,
163 : // to avoid triggering Wunused-const-variable build warnings.
164 : static const int XTERM_FOREGROUND_COLOR_OFFSET = 30;
165 : static const int XTERM_BACKGROUND_COLOR_OFFSET = 40;
166 : static const int BLACK = 0;
167 : //static const int RED = 1;
168 : static const int GREEN = 2;
169 : //static const int YELLOW = 3;
170 : //static const int BLUE = 4;
171 : //static const int MAGENTA = 5;
172 : //static const int CYAN = 6;
173 : //static const int WHITE = 7;
174 :
175 : static const int RESET = 0;
176 : // static const int BRIGHT = 1;
177 : // static const int DIM = 2;
178 : // static const int UNDERLINE = 3;
179 : // static const int BLINK = 4;
180 : // static const int REVERSE = 7;
181 : // static const int HIDDEN = 8;
182 :
183 : static void SetTextColor(uint32_t aColor)
184 : {
185 : char command[13];
186 :
187 : /* Command is the control command to the terminal */
188 : SprintfLiteral(command, "%c[%d;%d;%dm", 0x1B, RESET,
189 : aColor + XTERM_FOREGROUND_COLOR_OFFSET,
190 : BLACK + XTERM_BACKGROUND_COLOR_OFFSET);
191 : printf("%s", command);
192 : }
193 :
194 : static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
195 : {
196 : SetTextColor(aColor);
197 : fprintf(aFile, "%p", aLayer);
198 : SetTextColor(GREEN);
199 : }
200 : #else
201 :
202 : const char *colors[] = { "Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White" };
203 :
204 0 : static void print_layer_internal(FILE* aFile, Layer* aLayer, uint32_t aColor)
205 : {
206 0 : fprintf(aFile, "%p(%s)", aLayer, colors[aColor]);
207 0 : }
208 : #endif
209 :
210 0 : static void print_layer(FILE* aFile, Layer* aLayer)
211 : {
212 0 : print_layer_internal(aFile, aLayer, aLayer->GetDebugColorIndex());
213 0 : }
214 :
215 0 : static void DumpLayerList(nsTArray<Layer*>& aLayers)
216 : {
217 0 : for (uint32_t i = 0; i < aLayers.Length(); i++) {
218 0 : print_layer(stderr, aLayers.ElementAt(i));
219 0 : fprintf(stderr, " ");
220 : }
221 0 : fprintf(stderr, "\n");
222 0 : }
223 :
224 0 : static void DumpEdgeList(DirectedGraph<Layer*>& aGraph)
225 : {
226 0 : const nsTArray<DirectedGraph<Layer*>::Edge>& edges = aGraph.GetEdgeList();
227 :
228 0 : for (uint32_t i = 0; i < edges.Length(); i++) {
229 0 : fprintf(stderr, "From: ");
230 0 : print_layer(stderr, edges.ElementAt(i).mFrom);
231 0 : fprintf(stderr, ", To: ");
232 0 : print_layer(stderr, edges.ElementAt(i).mTo);
233 0 : fprintf(stderr, "\n");
234 : }
235 0 : }
236 : #endif
237 :
238 : // The maximum number of layers that we will attempt to sort. Anything
239 : // greater than this will be left unsorted. We should consider enabling
240 : // depth buffering for the scene in this case.
241 : #define MAX_SORTABLE_LAYERS 100
242 :
243 :
244 : uint32_t gColorIndex = 1;
245 :
246 0 : void SortLayersBy3DZOrder(nsTArray<Layer*>& aLayers)
247 : {
248 0 : uint32_t nodeCount = aLayers.Length();
249 0 : if (nodeCount > MAX_SORTABLE_LAYERS) {
250 0 : return;
251 : }
252 0 : DirectedGraph<Layer*> graph;
253 :
254 : #ifdef DEBUG
255 0 : if (gfxEnv::DumpLayerSortList()) {
256 0 : for (uint32_t i = 0; i < nodeCount; i++) {
257 0 : if (aLayers.ElementAt(i)->GetDebugColorIndex() == 0) {
258 0 : aLayers.ElementAt(i)->SetDebugColorIndex(gColorIndex++);
259 0 : if (gColorIndex > 7) {
260 0 : gColorIndex = 1;
261 : }
262 : }
263 : }
264 0 : fprintf(stderr, " --- Layers before sorting: --- \n");
265 0 : DumpLayerList(aLayers);
266 : }
267 : #endif
268 :
269 : // Iterate layers and determine edges.
270 0 : for (uint32_t i = 0; i < nodeCount; i++) {
271 0 : for (uint32_t j = i + 1; j < nodeCount; j++) {
272 0 : Layer* a = aLayers.ElementAt(i);
273 0 : Layer* b = aLayers.ElementAt(j);
274 0 : LayerSortOrder order = CompareDepth(a, b);
275 0 : if (order == ABeforeB) {
276 0 : graph.AddEdge(a, b);
277 0 : } else if (order == BBeforeA) {
278 0 : graph.AddEdge(b, a);
279 : }
280 : }
281 : }
282 :
283 : #ifdef DEBUG
284 0 : if (gfxEnv::DumpLayerSortList()) {
285 0 : fprintf(stderr, " --- Edge List: --- \n");
286 0 : DumpEdgeList(graph);
287 : }
288 : #endif
289 :
290 : // Build a new array using the graph.
291 0 : nsTArray<Layer*> noIncoming;
292 0 : nsTArray<Layer*> sortedList;
293 :
294 : // Make a list of all layers with no incoming edges.
295 0 : noIncoming.AppendElements(aLayers);
296 0 : const nsTArray<DirectedGraph<Layer*>::Edge>& edges = graph.GetEdgeList();
297 0 : for (uint32_t i = 0; i < edges.Length(); i++) {
298 0 : noIncoming.RemoveElement(edges.ElementAt(i).mTo);
299 : }
300 :
301 : // Move each item without incoming edges into the sorted list,
302 : // and remove edges from it.
303 0 : do {
304 0 : if (!noIncoming.IsEmpty()) {
305 0 : uint32_t last = noIncoming.Length() - 1;
306 :
307 0 : Layer* layer = noIncoming.ElementAt(last);
308 0 : MOZ_ASSERT(layer); // don't let null layer pointers sneak into sortedList
309 :
310 0 : noIncoming.RemoveElementAt(last);
311 0 : sortedList.AppendElement(layer);
312 :
313 0 : nsTArray<DirectedGraph<Layer*>::Edge> outgoing;
314 0 : graph.GetEdgesFrom(layer, outgoing);
315 0 : for (uint32_t i = 0; i < outgoing.Length(); i++) {
316 0 : DirectedGraph<Layer*>::Edge edge = outgoing.ElementAt(i);
317 0 : graph.RemoveEdge(edge);
318 0 : if (!graph.NumEdgesTo(edge.mTo)) {
319 : // If this node also has no edges now, add it to the list
320 0 : noIncoming.AppendElement(edge.mTo);
321 : }
322 : }
323 : }
324 :
325 : // If there are no nodes without incoming edges, but there
326 : // are still edges, then we have a cycle.
327 0 : if (noIncoming.IsEmpty() && graph.GetEdgeCount()) {
328 : // Find the node with the least incoming edges.
329 0 : uint32_t minEdges = UINT_MAX;
330 0 : Layer* minNode = nullptr;
331 0 : for (uint32_t i = 0; i < aLayers.Length(); i++) {
332 0 : uint32_t edgeCount = graph.NumEdgesTo(aLayers.ElementAt(i));
333 0 : if (edgeCount && edgeCount < minEdges) {
334 0 : minEdges = edgeCount;
335 0 : minNode = aLayers.ElementAt(i);
336 0 : if (minEdges == 1) {
337 0 : break;
338 : }
339 : }
340 : }
341 :
342 0 : if (minNode) {
343 : // Remove all of them!
344 0 : graph.RemoveEdgesTo(minNode);
345 0 : noIncoming.AppendElement(minNode);
346 : }
347 : }
348 0 : } while (!noIncoming.IsEmpty());
349 0 : NS_ASSERTION(!graph.GetEdgeCount(), "Cycles detected!");
350 : #ifdef DEBUG
351 0 : if (gfxEnv::DumpLayerSortList()) {
352 0 : fprintf(stderr, " --- Layers after sorting: --- \n");
353 0 : DumpLayerList(sortedList);
354 : }
355 : #endif
356 :
357 0 : aLayers.Clear();
358 0 : aLayers.AppendElements(sortedList);
359 : }
360 :
361 : } // namespace layers
362 9 : } // namespace mozilla
|
