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 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:
  88  * https://en.wikipedia.org/wiki/Binary_space_partitioning
  89  * ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
  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 */