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 {
LayerPolygonLayerPolygon27   explicit LayerPolygon(Layer* aLayer) : layer(aLayer) {}
28 
LayerPolygonLayerPolygon29   LayerPolygon(Layer* aLayer, gfx::Polygon&& aGeometry)
30       : layer(aLayer), geometry(Some(Move(aGeometry))) {}
31 
LayerPolygonLayerPolygon32   LayerPolygon(Layer* aLayer, nsTArray<gfx::Point4D>&& aPoints,
33                const gfx::Point4D& aNormal)
34       : layer(aLayer) {
35     geometry.emplace(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 {
BSPTreeNodeBSPTreeNode61   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 
FirstBSPTreeNode67   const gfx::Polygon& First() const {
68     MOZ_ASSERT(!layers.empty());
69     MOZ_ASSERT(layers.front().geometry);
70     return *layers.front().geometry;
71   }
72 
newBSPTreeNode73   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:
88  * https://en.wikipedia.org/wiki/Binary_space_partitioning
89  * ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
90  */
91 class BSPTree {
92  public:
93   /**
94    * The constructor modifies layers in the given list.
95    */
BSPTree(std::list<LayerPolygon> & aLayers)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 
~BSPTree()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    */
GetDrawOrder()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 */
137