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