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
#ifndef MOZILLA_LAYERS_BSPTREE_H
8
#define MOZILLA_LAYERS_BSPTREE_H
9
10
#include <list>
11
#include <utility>
12
13
#include "mozilla/ArenaAllocator.h"
14
#include "mozilla/UniquePtr.h"
15
#include "mozilla/gfx/Polygon.h"
16
#include "nsTArray.h"
17
18
namespace mozilla {
19
namespace layers {
20
21
class Layer;
22
23
/**
24
* Represents a layer that might have a non-rectangular geometry.
25
*/
26
struct LayerPolygon {
27
explicit LayerPolygon(Layer* aLayer) : layer(aLayer) {}
28
29
LayerPolygon(Layer* aLayer, gfx::Polygon&& aGeometry)
30
: layer(aLayer), geometry(Some(std::move(aGeometry))) {}
31
32
LayerPolygon(Layer* aLayer, nsTArray<gfx::Point4D>&& aPoints,
33
const gfx::Point4D& aNormal)
34
: layer(aLayer) {
35
geometry.emplace(std::move(aPoints), aNormal);
36
}
37
38
Layer* layer;
39
Maybe<gfx::Polygon> geometry;
40
};
41
42
/**
43
* Allocate BSPTreeNodes from a memory arena to improve performance with
44
* complex scenes.
45
* The arena size of 4096 bytes was selected as an arbitrary power of two.
46
* Depending on the platform, this size accommodates roughly 100 BSPTreeNodes.
47
*/
48
typedef mozilla::ArenaAllocator<4096, 8> BSPTreeArena;
49
50
/**
51
* Aliases the container type used to store layers within BSPTreeNodes.
52
*/
53
typedef std::list<LayerPolygon> LayerList;
54
55
/**
56
* Represents a node in a BSP tree. The node contains at least one layer with
57
* associated geometry that is used as a splitting plane, and at most two child
58
* nodes that represent the splitting planes that further subdivide the space.
59
*/
60
struct BSPTreeNode {
61
explicit BSPTreeNode(nsTArray<LayerList*>& aListPointers)
62
: front(nullptr), back(nullptr) {
63
// Store the layer list pointer to free memory when BSPTree is destroyed.
64
aListPointers.AppendElement(&layers);
65
}
66
67
const gfx::Polygon& First() const {
68
MOZ_ASSERT(!layers.empty());
69
MOZ_ASSERT(layers.front().geometry);
70
return *layers.front().geometry;
71
}
72
73
static void* operator new(size_t aSize, BSPTreeArena& mPool) {
74
return mPool.Allocate(aSize);
75
}
76
77
BSPTreeNode* front;
78
BSPTreeNode* back;
79
LayerList layers;
80
};
81
82
/**
83
* BSPTree class takes a list of layers as an input and uses binary space
84
* partitioning algorithm to create a tree structure that can be used for
85
* depth sorting.
86
87
* Sources for more information:
90
*/
91
class BSPTree final {
92
public:
93
/**
94
* The constructor modifies layers in the given list.
95
*/
96
explicit BSPTree(std::list<LayerPolygon>& aLayers) {
97
MOZ_ASSERT(!aLayers.empty());
98
99
mRoot = new (mPool) BSPTreeNode(mListPointers);
100
BuildTree(mRoot, aLayers);
101
}
102
103
~BSPTree() {
104
for (LayerList* listPtr : mListPointers) {
105
listPtr->~LayerList();
106
}
107
}
108
109
/**
110
* Builds and returns the back-to-front draw order for the created BSP tree.
111
*/
112
nsTArray<LayerPolygon> GetDrawOrder() const {
113
nsTArray<LayerPolygon> layers;
114
BuildDrawOrder(mRoot, layers);
115
return layers;
116
}
117
118
private:
119
BSPTreeArena mPool;
120
BSPTreeNode* mRoot;
121
nsTArray<LayerList*> mListPointers;
122
123
/**
124
* BuildDrawOrder and BuildTree are called recursively. The depth of the
125
* recursion depends on the amount of polygons and their intersections.
126
*/
127
void BuildDrawOrder(BSPTreeNode* aNode,
128
nsTArray<LayerPolygon>& aLayers) const;
129
130
void BuildTree(BSPTreeNode* aRoot, std::list<LayerPolygon>& aLayers);
131
};
132
133
} // namespace layers
134
} // namespace mozilla
135
136
#endif /* MOZILLA_LAYERS_BSPTREE_H */