gfx/layers/BSPTree.h

   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 /**
  22  * Represents a layer that might have a non-rectangular geometry.
  23  */
  24 template <typename T>
  25 struct BSPPolygon {
  26   explicit BSPPolygon(T* aData) : data(aData) {}
  27
  28   BSPPolygon(T* aData, gfx::Polygon&& aGeometry)
  29       : data(aData), geometry(Some(std::move(aGeometry))) {}
  30
  31   BSPPolygon(T* aData, nsTArray<gfx::Point4D>&& aPoints,
  32              const gfx::Point4D& aNormal)
  33       : data(aData) {
  34     geometry.emplace(std::move(aPoints), aNormal);
  35   }
  36
  37   T* data;
  38   Maybe<gfx::Polygon> geometry;
  39 };
  40
  41 /**
  42  * Allocate BSPTreeNodes from a memory arena to improve performance with
  43  * complex scenes.
  44  * The arena size of 4096 bytes was selected as an arbitrary power of two.
  45  * Depending on the platform, this size accommodates roughly 100 BSPTreeNodes.
  46  */
  47 typedef mozilla::ArenaAllocator<4096, 8> BSPTreeArena;
  48
  49 /**
  50  * Aliases the container type used to store layers within BSPTreeNodes.
  51  */
  52 template <typename T>
  53 using PolygonList = std::list<BSPPolygon<T>>;
  54
  55 // For tests. Needs to be defined here rather than in TestBSPTree.cpp because we
  56 // need to explicitly instantiate the out-of-line BSPTree methods for it in
  57 // BSPTree.cpp.
  58 class BSPTestData {};
  59 using TestPolygon = BSPPolygon<BSPTestData>;
  60
  61 /**
  62  * Represents a node in a BSP tree. The node contains at least one layer with
  63  * associated geometry that is used as a splitting plane, and at most two child
  64  * nodes that represent the splitting planes that further subdivide the space.
  65  */
  66 template <typename T>
  67 struct BSPTreeNode {
  68   explicit BSPTreeNode(nsTArray<PolygonList<T>*>& aListPointers)
  69       : front(nullptr), back(nullptr) {
  70     // Store the layer list pointer to free memory when BSPTree is destroyed.
  71     aListPointers.AppendElement(&layers);
  72   }
  73
  74   const gfx::Polygon& First() const {
  75     MOZ_ASSERT(!layers.empty());
  76     MOZ_ASSERT(layers.front().geometry);
  77     return *layers.front().geometry;
  78   }
  79
  80   static void* operator new(size_t aSize, BSPTreeArena& mPool) {
  81     return mPool.Allocate(aSize);
  82   }
  83
  84   BSPTreeNode* front;
  85   BSPTreeNode* back;
  86   PolygonList<T> 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 template <typename T>
  99 class BSPTree final {
 100  public:
 101   /**
 102    * The constructor modifies layers in the given list.
 103    */
 104   explicit BSPTree(std::list<BSPPolygon<T>>& aLayers) {
 105     MOZ_ASSERT(!aLayers.empty());
 106
 107     mRoot = new (mPool) BSPTreeNode(mListPointers);
 108     BuildTree(mRoot, aLayers);
 109   }
 110
 111   ~BSPTree() {
 112     for (PolygonList<T>* listPtr : mListPointers) {
 113       listPtr->~list();
 114     }
 115   }
 116
 117   /**
 118    * Builds and returns the back-to-front draw order for the created BSP tree.
 119    */
 120   nsTArray<BSPPolygon<T>> GetDrawOrder() const {
 121     nsTArray<BSPPolygon<T>> layers;
 122     BuildDrawOrder(mRoot, layers);
 123     return layers;
 124   }
 125
 126  private:
 127   BSPTreeArena mPool;
 128   BSPTreeNode<T>* mRoot;
 129   nsTArray<PolygonList<T>*> mListPointers;
 130
 131   /**
 132    * BuildDrawOrder and BuildTree are called recursively. The depth of the
 133    * recursion depends on the amount of polygons and their intersections.
 134    */
 135   void BuildDrawOrder(BSPTreeNode<T>* aNode,
 136                       nsTArray<BSPPolygon<T>>& aLayers) const;
 137
 138   void BuildTree(BSPTreeNode<T>* aRoot, PolygonList<T>& aLayers);
 139 };
 140
 141 }  // namespace layers
 142 }  // namespace mozilla
 143
 144 #endif /* MOZILLA_LAYERS_BSPTREE_H */