summaryrefslogtreecommitdiffstats
path: root/gfx/layers/BSPTree.h
diff options
context:
space:
mode:
Diffstat (limited to 'gfx/layers/BSPTree.h')
-rw-r--r--gfx/layers/BSPTree.h106
1 files changed, 106 insertions, 0 deletions
diff --git a/gfx/layers/BSPTree.h b/gfx/layers/BSPTree.h
new file mode 100644
index 000000000..24a82f2ac
--- /dev/null
+++ b/gfx/layers/BSPTree.h
@@ -0,0 +1,106 @@
+/* -*- 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/gfx/Polygon.h"
+#include "mozilla/Move.h"
+#include "mozilla/UniquePtr.h"
+#include "nsTArray.h"
+
+#include <deque>
+
+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::Polygon3D&& aGeometry)
+ : layer(aLayer), geometry(Some(aGeometry)) {}
+
+ LayerPolygon(Layer *aLayer,
+ nsTArray<gfx::Point3D>&& aPoints, const gfx::Point3D& aNormal)
+ : layer(aLayer), geometry(Some(gfx::Polygon3D(Move(aPoints), aNormal))) {}
+
+ Layer *layer;
+ Maybe<gfx::Polygon3D> geometry;
+};
+
+LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers);
+
+// 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 {
+ explicit BSPTreeNode(LayerPolygon&& layer)
+ {
+ layers.push_back(Move(layer));
+ }
+
+ const gfx::Polygon3D& First() const
+ {
+ MOZ_ASSERT(layers[0].geometry);
+ return *layers[0].geometry;
+ }
+
+ UniquePtr<BSPTreeNode> front;
+ UniquePtr<BSPTreeNode> back;
+ std::deque<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:
+ // This constructor takes the ownership of layers in the given list.
+ explicit BSPTree(std::deque<LayerPolygon>& aLayers)
+ {
+ MOZ_ASSERT(!aLayers.empty());
+ mRoot.reset(new BSPTreeNode(PopFront(aLayers)));
+
+ BuildTree(mRoot, aLayers);
+ }
+
+ // Returns the root node of the BSP tree.
+ const UniquePtr<BSPTreeNode>& GetRoot() const
+ {
+ return mRoot;
+ }
+
+ // 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:
+ UniquePtr<BSPTreeNode> mRoot;
+
+ // BuildDrawOrder and BuildTree are called recursively. The depth of the
+ // recursion depends on the amount of polygons and their intersections.
+ void BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
+ nsTArray<LayerPolygon>& aLayers) const;
+ void BuildTree(UniquePtr<BSPTreeNode>& aRoot,
+ std::deque<LayerPolygon>& aLayers);
+};
+
+} // namespace layers
+} // namespace mozilla
+
+#endif /* MOZILLA_LAYERS_BSPTREE_H */