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/. */
6 #include "LayerSorter.h"
7 #include "DirectedGraph.h"
9 #include "gfxLineSegment.h"
11 #include "mozilla/Assertions.h"
23 * Recover the z component from a 2d transformed point by finding the intersection
24 * of a line through the point in the z direction and the transformed plane.
28 * point = normal . (p0 - l0) / normal . l
30 static gfxFloat
RecoverZDepth(const gfx3DMatrix
& aTransform
, const gfxPoint
& aPoint
)
32 const gfxPoint3D
l(0, 0, 1);
33 gfxPoint3D l0
= gfxPoint3D(aPoint
.x
, aPoint
.y
, 0);
34 gfxPoint3D p0
= aTransform
.Transform3D(gfxPoint3D(0, 0, 0));
35 gfxPoint3D normal
= aTransform
.GetNormalVector();
37 gfxFloat n
= normal
.DotProduct(p0
- l0
);
38 gfxFloat d
= normal
.DotProduct(l
);
48 * Determine if this transform layer should be drawn before another when they
49 * are both preserve-3d children.
51 * We want to find the relative z depths of the 2 layers at points where they
52 * intersect when projected onto the 2d screen plane. Intersections are defined
53 * as corners that are positioned within the other quad, as well as intersections
56 * We then choose the intersection point with the greatest difference in Z
57 * depths and use this point to determine an ordering for the two layers.
58 * For layers that are intersecting in 3d space, this essentially guesses an
59 * order. In a lot of cases we only intersect right at the edge point (3d cubes
60 * in particular) and this generates the 'correct' looking ordering. For planes
61 * that truely intersect, then there is no correct ordering and this remains
62 * unsolved without changing our rendering code.
64 static LayerSortOrder
CompareDepth(Layer
* aOne
, Layer
* aTwo
) {
65 gfxRect ourRect
= aOne
->GetEffectiveVisibleRegion().GetBounds();
66 gfxRect otherRect
= aTwo
->GetEffectiveVisibleRegion().GetBounds();
68 gfx3DMatrix ourTransform
= aOne
->GetTransform();
69 gfx3DMatrix otherTransform
= aTwo
->GetTransform();
71 // Transform both rectangles and project into 2d space.
72 gfxQuad ourTransformedRect
= ourTransform
.TransformRect(ourRect
);
73 gfxQuad otherTransformedRect
= otherTransform
.TransformRect(otherRect
);
75 gfxRect ourBounds
= ourTransformedRect
.GetBounds();
76 gfxRect otherBounds
= otherTransformedRect
.GetBounds();
78 if (!ourBounds
.Intersects(otherBounds
)) {
82 // Make a list of all points that are within the other rect.
83 // Could we just check Contains() on the bounds rects. ie, is it possible
84 // for layers to overlap without intersections (in 2d space) and yet still
85 // have their bounds rects not completely enclose each other?
86 nsTArray
<gfxPoint
> points
;
87 for (uint32_t i
= 0; i
< 4; i
++) {
88 if (ourTransformedRect
.Contains(otherTransformedRect
.mPoints
[i
])) {
89 points
.AppendElement(otherTransformedRect
.mPoints
[i
]);
91 if (otherTransformedRect
.Contains(ourTransformedRect
.mPoints
[i
])) {
92 points
.AppendElement(ourTransformedRect
.mPoints
[i
]);
96 // Look for intersections between lines (in 2d space) and use these as
97 // depth testing points.
98 for (uint32_t i
= 0; i
< 4; i
++) {
99 for (uint32_t j
= 0; j
< 4; j
++) {
100 gfxPoint intersection
;
101 gfxLineSegment
one(ourTransformedRect
.mPoints
[i
],
102 ourTransformedRect
.mPoints
[(i
+ 1) % 4]);
103 gfxLineSegment
two(otherTransformedRect
.mPoints
[j
],
104 otherTransformedRect
.mPoints
[(j
+ 1) % 4]);
105 if (one
.Intersects(two
, intersection
)) {
106 points
.AppendElement(intersection
);
111 // No intersections, no defined order between these layers.
112 if (points
.IsEmpty()) {
116 // Find the relative Z depths of each intersection point and check that the layers are in the same order.
117 gfxFloat highest
= 0;
118 for (uint32_t i
= 0; i
< points
.Length(); i
++) {
119 gfxFloat ourDepth
= RecoverZDepth(ourTransform
, points
.ElementAt(i
));
120 gfxFloat otherDepth
= RecoverZDepth(otherTransform
, points
.ElementAt(i
));
122 gfxFloat difference
= otherDepth
- ourDepth
;
124 if (fabs(difference
) > fabs(highest
)) {
125 highest
= difference
;
128 // If layers have the same depth keep the original order
129 if (fabs(highest
) < 0.1 || highest
>= 0) {
137 static bool gDumpLayerSortList
= getenv("MOZ_DUMP_LAYER_SORT_LIST") != 0;
148 //#define USE_XTERM_COLORING
149 #ifdef USE_XTERM_COLORING
159 static void SetTextColor(uint32_t aColor
)
163 /* Command is the control command to the terminal */
164 sprintf(command
, "%c[%d;%d;%dm", 0x1B, RESET
, aColor
+ 30, BLACK
+ 40);
165 printf("%s", command
);
168 static void print_layer_internal(FILE* aFile
, Layer
* aLayer
, uint32_t aColor
)
170 SetTextColor(aColor
);
171 fprintf(aFile
, "%p", aLayer
);
176 const char *colors
[] = { "Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White" };
178 static void print_layer_internal(FILE* aFile
, Layer
* aLayer
, uint32_t aColor
)
180 fprintf(aFile
, "%p(%s)", aLayer
, colors
[aColor
]);
184 static void print_layer(FILE* aFile
, Layer
* aLayer
)
186 print_layer_internal(aFile
, aLayer
, aLayer
->GetDebugColorIndex());
189 static void DumpLayerList(nsTArray
<Layer
*>& aLayers
)
191 for (uint32_t i
= 0; i
< aLayers
.Length(); i
++) {
192 print_layer(stderr
, aLayers
.ElementAt(i
));
193 fprintf(stderr
, " ");
195 fprintf(stderr
, "\n");
198 static void DumpEdgeList(DirectedGraph
<Layer
*>& aGraph
)
200 const nsTArray
<DirectedGraph
<Layer
*>::Edge
>& edges
= aGraph
.GetEdgeList();
202 for (uint32_t i
= 0; i
< edges
.Length(); i
++) {
203 fprintf(stderr
, "From: ");
204 print_layer(stderr
, edges
.ElementAt(i
).mFrom
);
205 fprintf(stderr
, ", To: ");
206 print_layer(stderr
, edges
.ElementAt(i
).mTo
);
207 fprintf(stderr
, "\n");
212 // The maximum number of layers that we will attempt to sort. Anything
213 // greater than this will be left unsorted. We should consider enabling
214 // depth buffering for the scene in this case.
215 #define MAX_SORTABLE_LAYERS 100
218 uint32_t gColorIndex
= 1;
220 void SortLayersBy3DZOrder(nsTArray
<Layer
*>& aLayers
)
222 uint32_t nodeCount
= aLayers
.Length();
223 if (nodeCount
> MAX_SORTABLE_LAYERS
) {
226 DirectedGraph
<Layer
*> graph
;
229 if (gDumpLayerSortList
) {
230 for (uint32_t i
= 0; i
< nodeCount
; i
++) {
231 if (aLayers
.ElementAt(i
)->GetDebugColorIndex() == 0) {
232 aLayers
.ElementAt(i
)->SetDebugColorIndex(gColorIndex
++);
233 if (gColorIndex
> 7) {
238 fprintf(stderr
, " --- Layers before sorting: --- \n");
239 DumpLayerList(aLayers
);
243 // Iterate layers and determine edges.
244 for (uint32_t i
= 0; i
< nodeCount
; i
++) {
245 for (uint32_t j
= i
+ 1; j
< nodeCount
; j
++) {
246 Layer
* a
= aLayers
.ElementAt(i
);
247 Layer
* b
= aLayers
.ElementAt(j
);
248 LayerSortOrder order
= CompareDepth(a
, b
);
249 if (order
== ABeforeB
) {
251 } else if (order
== BBeforeA
) {
258 if (gDumpLayerSortList
) {
259 fprintf(stderr
, " --- Edge List: --- \n");
264 // Build a new array using the graph.
265 nsTArray
<Layer
*> noIncoming
;
266 nsTArray
<Layer
*> sortedList
;
268 // Make a list of all layers with no incoming edges.
269 noIncoming
.AppendElements(aLayers
);
270 const nsTArray
<DirectedGraph
<Layer
*>::Edge
>& edges
= graph
.GetEdgeList();
271 for (uint32_t i
= 0; i
< edges
.Length(); i
++) {
272 noIncoming
.RemoveElement(edges
.ElementAt(i
).mTo
);
275 // Move each item without incoming edges into the sorted list,
276 // and remove edges from it.
278 if (!noIncoming
.IsEmpty()) {
279 uint32_t last
= noIncoming
.Length() - 1;
281 Layer
* layer
= noIncoming
.ElementAt(last
);
282 MOZ_ASSERT(layer
); // don't let null layer pointers sneak into sortedList
284 noIncoming
.RemoveElementAt(last
);
285 sortedList
.AppendElement(layer
);
287 nsTArray
<DirectedGraph
<Layer
*>::Edge
> outgoing
;
288 graph
.GetEdgesFrom(layer
, outgoing
);
289 for (uint32_t i
= 0; i
< outgoing
.Length(); i
++) {
290 DirectedGraph
<Layer
*>::Edge edge
= outgoing
.ElementAt(i
);
291 graph
.RemoveEdge(edge
);
292 if (!graph
.NumEdgesTo(edge
.mTo
)) {
293 // If this node also has no edges now, add it to the list
294 noIncoming
.AppendElement(edge
.mTo
);
299 // If there are no nodes without incoming edges, but there
300 // are still edges, then we have a cycle.
301 if (noIncoming
.IsEmpty() && graph
.GetEdgeCount()) {
302 // Find the node with the least incoming edges.
303 uint32_t minEdges
= UINT_MAX
;
304 Layer
* minNode
= nullptr;
305 for (uint32_t i
= 0; i
< aLayers
.Length(); i
++) {
306 uint32_t edgeCount
= graph
.NumEdgesTo(aLayers
.ElementAt(i
));
307 if (edgeCount
&& edgeCount
< minEdges
) {
308 minEdges
= edgeCount
;
309 minNode
= aLayers
.ElementAt(i
);
317 // Remove all of them!
318 graph
.RemoveEdgesTo(minNode
);
319 noIncoming
.AppendElement(minNode
);
322 } while (!noIncoming
.IsEmpty());
323 NS_ASSERTION(!graph
.GetEdgeCount(), "Cycles detected!");
325 if (gDumpLayerSortList
) {
326 fprintf(stderr
, " --- Layers after sorting: --- \n");
327 DumpLayerList(sortedList
);
332 aLayers
.AppendElements(sortedList
);