tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

BSPTree.h (4092B)

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