gfx/layers/BSPTree.h
author Miko Mynttinen <mikokm@gmail.com>
Wed, 05 Apr 2017 20:12:35 +0200
changeset 400323 a6c0e4789330b9a37956bcb123449db35e27e6f0
parent 370798 29b6c0a80512eaf0359c90cc398bcc1722533fe6
child 400325 efdb4e01ad4e4ee99f5b8c3718873530b63e2c17
permissions -rw-r--r--
Bug 1351426 - Part 3: Refactor BSPTree to use list instead of deque r=kip MozReview-Commit-ID: F4ezRzbGihI

/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef MOZILLA_LAYERS_BSPTREE_H
#define MOZILLA_LAYERS_BSPTREE_H

#include "mozilla/ArenaAllocator.h"
#include "mozilla/gfx/Polygon.h"
#include "mozilla/Move.h"
#include "mozilla/UniquePtr.h"
#include "nsTArray.h"

#include <list>

namespace mozilla {
namespace layers {

class Layer;

// Represents a layer that might have a non-rectangular geometry.
struct LayerPolygon {
  explicit LayerPolygon(Layer *aLayer)
    : layer(aLayer) {}

  LayerPolygon(Layer *aLayer,
               gfx::Polygon&& aGeometry)
    : layer(aLayer), geometry(Some(Move(aGeometry))) {}

  LayerPolygon(Layer *aLayer,
               nsTArray<gfx::Point4D>&& aPoints,
               const gfx::Point4D& aNormal)
    : layer(aLayer)
  {
    geometry.emplace(Move(aPoints), aNormal);
  }

  Layer *layer;
  Maybe<gfx::Polygon> geometry;
};

/**
 * Allocate BSPTreeNodes from a memory arena to improve performance with
 * complex scenes.
 * The arena size of 4096 bytes was selected as an arbitrary power of two.
 * Depending on the platform, this size accommodates roughly 100 BSPTreeNodes.
 */
typedef mozilla::ArenaAllocator<4096, 8> BSPTreeArena;

// Represents a node in a BSP tree. The node contains at least one layer with
// associated geometry that is used as a splitting plane, and at most two child
// nodes that represent the splitting planes that further subdivide the space.
struct BSPTreeNode {
  BSPTreeNode()
    : front(nullptr), back(nullptr) {}

  const gfx::Polygon& First() const
  {
    MOZ_ASSERT(!layers.empty());
    MOZ_ASSERT(layers.front().geometry);
    return *layers.front().geometry;
  }

  static void* operator new(size_t aSize, BSPTreeArena& mPool)
  {
    return mPool.Allocate(aSize);
  }

  BSPTreeNode* front;
  BSPTreeNode* back;
  std::list<LayerPolygon> layers;
};

// BSPTree class takes a list of layers as an input and uses binary space
// partitioning algorithm to create a tree structure that can be used for
// depth sorting.
//
// Sources for more information:
// https://en.wikipedia.org/wiki/Binary_space_partitioning
// ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
class BSPTree {
public:
  /**
   * The constructor modifies layers in the given list.
   */
  explicit BSPTree(std::list<LayerPolygon>& aLayers)
  {
    MOZ_ASSERT(!aLayers.empty());

    mRoot = new (mPool) BSPTreeNode();
    BuildTree(mRoot, aLayers);
  }

  // Builds and returns the back-to-front draw order for the created BSP tree.
  nsTArray<LayerPolygon> GetDrawOrder() const
  {
    nsTArray<LayerPolygon> layers;
    BuildDrawOrder(mRoot, layers);
    return layers;
  }

private:
  BSPTreeArena mPool;
  BSPTreeNode* mRoot;

  // BuildDrawOrder and BuildTree are called recursively. The depth of the
  // recursion depends on the amount of polygons and their intersections.
  void BuildDrawOrder(BSPTreeNode* aNode,
                      nsTArray<LayerPolygon>& aLayers) const;

  void BuildTree(BSPTreeNode* aRoot,
                 std::list<LayerPolygon>& aLayers);
};

} // namespace layers
} // namespace mozilla

#endif /* MOZILLA_LAYERS_BSPTREE_H */