Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       5             : 
       6             : #ifndef MOZILLA_LAYERS_BSPTREE_H
       7             : #define MOZILLA_LAYERS_BSPTREE_H
       8             : 
       9             : #include "mozilla/ArenaAllocator.h"
      10             : #include "mozilla/gfx/Polygon.h"
      11             : #include "mozilla/Move.h"
      12             : #include "mozilla/UniquePtr.h"
      13             : #include "nsTArray.h"
      14             : 
      15             : #include <list>
      16             : 
      17             : namespace mozilla {
      18             : namespace layers {
      19             : 
      20             : class Layer;
      21             : 
      22             : /**
      23             :  * Represents a layer that might have a non-rectangular geometry.
      24             :  */
      25        1101 : struct LayerPolygon {
      26         367 :   explicit LayerPolygon(Layer* aLayer)
      27         367 :     : layer(aLayer) {}
      28             : 
      29           0 :   LayerPolygon(Layer* aLayer,
      30             :                gfx::Polygon&& aGeometry)
      31           0 :     : layer(aLayer), geometry(Some(Move(aGeometry))) {}
      32             : 
      33           0 :   LayerPolygon(Layer* aLayer,
      34             :                nsTArray<gfx::Point4D>&& aPoints,
      35             :                const gfx::Point4D& aNormal)
      36           0 :     : layer(aLayer)
      37             :   {
      38           0 :     geometry.emplace(Move(aPoints), aNormal);
      39           0 :   }
      40             : 
      41             :   Layer* layer;
      42             :   Maybe<gfx::Polygon> geometry;
      43             : };
      44             : 
      45             : /**
      46             :  * Allocate BSPTreeNodes from a memory arena to improve performance with
      47             :  * complex scenes.
      48             :  * The arena size of 4096 bytes was selected as an arbitrary power of two.
      49             :  * Depending on the platform, this size accommodates roughly 100 BSPTreeNodes.
      50             :  */
      51             : typedef mozilla::ArenaAllocator<4096, 8> BSPTreeArena;
      52             : 
      53             : /**
      54             :  * Aliases the container type used to store layers within BSPTreeNodes.
      55             :  */
      56             : typedef std::list<LayerPolygon> LayerList;
      57             : 
      58             : /**
      59             :  * Represents a node in a BSP tree. The node contains at least one layer with
      60             :  * associated geometry that is used as a splitting plane, and at most two child
      61             :  * nodes that represent the splitting planes that further subdivide the space.
      62             :  */
      63             : struct BSPTreeNode {
      64           0 :   explicit BSPTreeNode(nsTArray<LayerList*>& aListPointers)
      65           0 :     : front(nullptr), back(nullptr)
      66             :   {
      67             :     // Store the layer list pointer to free memory when BSPTree is destroyed.
      68           0 :     aListPointers.AppendElement(&layers);
      69           0 :   }
      70             : 
      71           0 :   const gfx::Polygon& First() const
      72             :   {
      73           0 :     MOZ_ASSERT(!layers.empty());
      74           0 :     MOZ_ASSERT(layers.front().geometry);
      75           0 :     return *layers.front().geometry;
      76             :   }
      77             : 
      78           0 :   static void* operator new(size_t aSize, BSPTreeArena& mPool)
      79             :   {
      80           0 :     return mPool.Allocate(aSize);
      81             :   }
      82             : 
      83             :   BSPTreeNode* front;
      84             :   BSPTreeNode* back;
      85             :   LayerList 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             : class BSPTree {
      98             : public:
      99             :   /**
     100             :    * The constructor modifies layers in the given list.
     101             :    */
     102           0 :   explicit BSPTree(std::list<LayerPolygon>& aLayers)
     103           0 :   {
     104           0 :     MOZ_ASSERT(!aLayers.empty());
     105             : 
     106           0 :     mRoot = new (mPool) BSPTreeNode(mListPointers);
     107           0 :     BuildTree(mRoot, aLayers);
     108           0 :   }
     109             : 
     110             : 
     111           0 :   ~BSPTree()
     112           0 :   {
     113           0 :     for (LayerList* listPtr : mListPointers) {
     114           0 :       listPtr->~LayerList();
     115             :     }
     116           0 :   }
     117             : 
     118             :   /**
     119             :    * Builds and returns the back-to-front draw order for the created BSP tree.
     120             :    */
     121           0 :   nsTArray<LayerPolygon> GetDrawOrder() const
     122             :   {
     123           0 :     nsTArray<LayerPolygon> layers;
     124           0 :     BuildDrawOrder(mRoot, layers);
     125           0 :     return layers;
     126             :   }
     127             : 
     128             : private:
     129             :   BSPTreeArena mPool;
     130             :   BSPTreeNode* mRoot;
     131             :   nsTArray<LayerList*> mListPointers;
     132             : 
     133             :   /**
     134             :    * BuildDrawOrder and BuildTree are called recursively. The depth of the
     135             :    * recursion depends on the amount of polygons and their intersections.
     136             :    */
     137             :   void BuildDrawOrder(BSPTreeNode* aNode,
     138             :                       nsTArray<LayerPolygon>& aLayers) const;
     139             : 
     140             :   void BuildTree(BSPTreeNode* aRoot,
     141             :                  std::list<LayerPolygon>& aLayers);
     142             : };
     143             : 
     144             : } // namespace layers
     145             : } // namespace mozilla
     146             : 
     147             : #endif /* MOZILLA_LAYERS_BSPTREE_H */