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