summaryrefslogtreecommitdiffstats
path: root/gfx/layers/BSPTree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gfx/layers/BSPTree.cpp')
-rw-r--r--gfx/layers/BSPTree.cpp107
1 files changed, 107 insertions, 0 deletions
diff --git a/gfx/layers/BSPTree.cpp b/gfx/layers/BSPTree.cpp
new file mode 100644
index 000000000..e1ed8621a
--- /dev/null
+++ b/gfx/layers/BSPTree.cpp
@@ -0,0 +1,107 @@
+/* -*- 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/. */
+
+#include "BSPTree.h"
+#include "mozilla/gfx/Polygon.h"
+
+namespace mozilla {
+namespace layers {
+
+LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers)
+{
+ LayerPolygon layer = Move(aLayers.front());
+ aLayers.pop_front();
+ return layer;
+}
+
+void
+BSPTree::BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
+ nsTArray<LayerPolygon>& aLayers) const
+{
+ const gfx::Point3D& normal = aNode->First().GetNormal();
+
+ UniquePtr<BSPTreeNode> *front = &aNode->front;
+ UniquePtr<BSPTreeNode> *back = &aNode->back;
+
+ // Since the goal is to return the draw order from back to front, we reverse
+ // the traversal order if the current polygon is facing towards the camera.
+ const bool reverseOrder = normal.z > 0.0f;
+
+ if (reverseOrder) {
+ std::swap(front, back);
+ }
+
+ if (*front) {
+ BuildDrawOrder(*front, aLayers);
+ }
+
+ for (LayerPolygon& layer : aNode->layers) {
+ MOZ_ASSERT(layer.geometry);
+
+ if (layer.geometry->GetPoints().Length() >= 3) {
+ aLayers.AppendElement(Move(layer));
+ }
+ }
+
+ if (*back) {
+ BuildDrawOrder(*back, aLayers);
+ }
+}
+
+void
+BSPTree::BuildTree(UniquePtr<BSPTreeNode>& aRoot,
+ std::deque<LayerPolygon>& aLayers)
+{
+ if (aLayers.empty()) {
+ return;
+ }
+
+ const gfx::Polygon3D& plane = aRoot->First();
+ std::deque<LayerPolygon> backLayers, frontLayers;
+
+ for (LayerPolygon& layerPolygon : aLayers) {
+ const Maybe<gfx::Polygon3D>& geometry = layerPolygon.geometry;
+
+ size_t pos = 0, neg = 0;
+ nsTArray<float> dots = geometry->CalculateDotProducts(plane, pos, neg);
+
+ // Back polygon
+ if (pos == 0 && neg > 0) {
+ backLayers.push_back(Move(layerPolygon));
+ }
+ // Front polygon
+ else if (pos > 0 && neg == 0) {
+ frontLayers.push_back(Move(layerPolygon));
+ }
+ // Coplanar polygon
+ else if (pos == 0 && neg == 0) {
+ aRoot->layers.push_back(Move(layerPolygon));
+ }
+ // Polygon intersects with the splitting plane.
+ else if (pos > 0 && neg > 0) {
+ nsTArray<gfx::Point3D> backPoints, frontPoints;
+ geometry->SplitPolygon(plane, dots, backPoints, frontPoints);
+
+ const gfx::Point3D& normal = geometry->GetNormal();
+ Layer *layer = layerPolygon.layer;
+
+ backLayers.push_back(LayerPolygon(layer, Move(backPoints), normal));
+ frontLayers.push_back(LayerPolygon(layer, Move(frontPoints), normal));
+ }
+ }
+
+ if (!backLayers.empty()) {
+ aRoot->back.reset(new BSPTreeNode(PopFront(backLayers)));
+ BuildTree(aRoot->back, backLayers);
+ }
+
+ if (!frontLayers.empty()) {
+ aRoot->front.reset(new BSPTreeNode(PopFront(frontLayers)));
+ BuildTree(aRoot->front, frontLayers);
+ }
+}
+
+} // namespace layers
+} // namespace mozilla