Bug 1292390 - Add BSP tree implementation draft
authorMiko Mynttinen <mikokm@gmail.com>
Thu, 04 Aug 2016 17:52:44 -0700
changeset 398864 43c9715476c789daf6b6df4c9c7a7394bcb1d5c0
parent 398863 362714d0b5d53fa7e3ff40e5fabebc38863dfd57
child 398865 20d9bbd7b73f3ced6bb8cee9e5b22142e2d743a7
push id25661
push userbmo:mikokm@gmail.com
push dateTue, 09 Aug 2016 22:06:19 +0000
bugs1292390
milestone51.0a1
Bug 1292390 - Add BSP tree implementation MozReview-Commit-ID: 81MYa4qBNUL
gfx/layers/BSPTree.cpp
gfx/layers/BSPTree.h
gfx/layers/moz.build
gfx/tests/gtest/TestBSPTree.cpp
gfx/tests/gtest/moz.build
new file mode 100644
--- /dev/null
+++ b/gfx/layers/BSPTree.cpp
@@ -0,0 +1,185 @@
+/* -*- 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 {
+
+namespace {
+
+static int signum(float d) {
+  if (d > 0) return 1;
+  if (d < 0) return -1;
+
+  return 0;
+}
+
+}
+
+void
+BSPTree::BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
+                        nsTArray<gfx::Polygon3D>& aPolygons) 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 iteration 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, aPolygons);
+  }
+
+  aPolygons.AppendElements(aNode->polygons);
+
+  if (*back) {
+    BuildDrawOrder(*back, aPolygons);
+  }
+}
+
+nsTArray<float>
+BSPTree::CalculateDotProduct(const gfx::Polygon3D& aFirst,
+                             const gfx::Polygon3D& aSecond,
+                             size_t& aPos, size_t& aNeg) const
+{
+  // Point classification might produce incorrect results due to numerical
+  // inaccuracies. Using an epsilon value makes the splitting plane "thicker".
+  const float epsilon = 0.05f;
+
+  const gfx::Point3D& normal = aFirst.GetNormal();
+  const gfx::Point3D& planePoint = aFirst[0];
+
+  nsTArray<float> dotProducts;
+
+  for (const gfx::Point3D& point : aSecond.GetPoints()) {
+    const float dot = (point - planePoint).DotProduct(normal);
+    dotProducts.AppendElement(dot);
+
+    if (dot > epsilon) {
+      aPos++;
+    } else if (dot < -epsilon) {
+      aNeg++;
+    } else {
+      // The point is within the thick plane.
+      dotProducts[dotProducts.Length() - 1] = 0.0f;
+    }
+  }
+
+  return dotProducts;
+}
+
+void
+BSPTree::BuildTree(UniquePtr<BSPTreeNode>& aRoot,
+                   std::deque<gfx::Polygon3D>& aPolygons)
+{
+  if (aPolygons.empty()) {
+    return;
+  }
+
+  const gfx::Polygon3D& splittingPlane = aRoot->First();
+  std::deque<gfx::Polygon3D> backPolygons, frontPolygons;
+
+  for (const gfx::Polygon3D& polygon : aPolygons) {
+    size_t pos = 0, neg = 0;
+    nsTArray<float> dots = CalculateDotProduct(splittingPlane, polygon,
+                                               pos, neg);
+
+    // Back polygon
+    if (pos == 0 && neg > 0) {
+      backPolygons.push_back(polygon);
+    }
+
+    // Front polygon
+    if (pos > 0 && neg == 0) {
+     frontPolygons.push_back(polygon);
+    }
+
+    // Coplanar polygon
+    if (pos == 0 && neg == 0) {
+      aRoot->AddPolygon(polygon);
+    }
+
+    // Polygon intersects with the splitting plane.
+    if (pos > 0 && neg > 0) {
+      std::pair<gfx::Polygon3D, gfx::Polygon3D> split =
+        SplitPolygon(splittingPlane, polygon, dots);
+
+      backPolygons.push_back(split.first);
+      frontPolygons.push_back(split.second);
+    }
+  }
+
+  if (!backPolygons.empty()) {
+    aRoot->back.reset(new BSPTreeNode(backPolygons.front()));
+    backPolygons.pop_front();
+    BuildTree(aRoot->back, backPolygons);
+  }
+
+  if (!frontPolygons.empty()) {
+    aRoot->front.reset(new BSPTreeNode(frontPolygons.front()));
+    frontPolygons.pop_front();
+    BuildTree(aRoot->front, frontPolygons);
+  }
+}
+
+std::pair<gfx::Polygon3D, gfx::Polygon3D>
+BSPTree::SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
+                      const gfx::Polygon3D& aPolygon,
+                      const nsTArray<float>& dots)
+{
+  const gfx::Point3D& normal = aSplittingPlane.GetNormal();
+  nsTArray<gfx::Point3D> frontPoints, backPoints;
+
+  const size_t pointCount = aPolygon.GetPoints().Length();
+
+  for (size_t i = 0; i < pointCount; ++i) {
+    size_t j = (i + 1) % pointCount;
+
+    const gfx::Point3D& a = aPolygon[i];
+    const gfx::Point3D& b = aPolygon[j];
+    const float dotA = dots[i];
+    const float dotB = dots[j];
+
+    // The point is in front of the plane.
+    if (dotA >= 0) {
+      frontPoints.AppendElement(a);
+    }
+
+    // The point is behind the plane.
+    if (dotA <= 0) {
+      backPoints.AppendElement(a);
+    }
+
+    // If the sign of the dot product changes between two consecutive vertices,
+    // the splitting plane intersects the corresponding polygon edge.
+    if (signum(dotA) != signum(dotB)) {
+
+      // Calculate the line segment and plane intersection point.
+      const gfx::Point3D ab = b - a;
+      const float dotAB = ab.DotProduct(normal);
+      const float t = -dotA / dotAB;
+      const gfx::Point3D p = a + (ab * t);
+
+      // Add the intersection point to both polygons.
+      backPoints.AppendElement(p);
+      frontPoints.AppendElement(p);
+    }
+  }
+
+  return std::make_pair(gfx::Polygon3D(backPoints),
+                        gfx::Polygon3D(frontPoints));
+}
+
+} // namespace layers
+} // namespace mozilla
new file mode 100644
--- /dev/null
+++ b/gfx/layers/BSPTree.h
@@ -0,0 +1,95 @@
+/* -*- 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/UniquePtr.h"
+#include "nsTArray.h"
+
+#include <deque>
+#include <utility>
+
+namespace mozilla {
+namespace layers {
+
+// Represents a node in a BSP tree. The node contains at least one polygon 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(const gfx::Polygon3D& aPolygon)
+  {
+    AddPolygon(aPolygon);
+  }
+
+  void AddPolygon(const gfx::Polygon3D& aPolygon)
+  {
+    polygons.AppendElement(aPolygon);
+  }
+
+  const gfx::Polygon3D& First() const
+  {
+    return polygons[0];
+  }
+
+  UniquePtr<BSPTreeNode> front;
+  UniquePtr<BSPTreeNode> back;
+  nsTArray<gfx::Polygon3D> polygons;
+};
+
+// BSPTree class takes a list of polygons 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:
+  explicit BSPTree(std::deque<gfx::Polygon3D> aPolygons)
+    : mRoot(new BSPTreeNode(aPolygons.front()))
+  {
+    aPolygons.pop_front();
+    BuildTree(mRoot, aPolygons);
+  }
+
+  // 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<gfx::Polygon3D> GetDrawOrder() const
+  {
+    nsTArray<gfx::Polygon3D> polygons;
+    BuildDrawOrder(mRoot, polygons);
+    return polygons;
+  }
+
+private:
+  UniquePtr<BSPTreeNode> mRoot;
+
+  void BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
+                      nsTArray<gfx::Polygon3D>& aPolygons) const;
+
+  void BuildTree(UniquePtr<BSPTreeNode>& aRoot,
+                 std::deque<gfx::Polygon3D>& aPolygons);
+
+  nsTArray<float> CalculateDotProduct(const gfx::Polygon3D& aFirst,
+                                      const gfx::Polygon3D& aSecond,
+                                      size_t& aPos, size_t& aNeg) const;
+
+  std::pair<gfx::Polygon3D, gfx::Polygon3D>
+  SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
+               const gfx::Polygon3D& aPolygon,
+               const nsTArray<float>& dots);
+};
+
+} // namespace layers
+} // namespace mozilla
+
+#endif /* MOZILLA_LAYERS_BSPTREE_H */
\ No newline at end of file
--- a/gfx/layers/moz.build
+++ b/gfx/layers/moz.build
@@ -119,16 +119,17 @@ EXPORTS.mozilla.layers += [
     'apz/util/TouchActionHelper.h',
     'AsyncCanvasRenderer.h',
     'AtomicRefCountedWithFinalize.h',
     'AxisPhysicsModel.h',
     'AxisPhysicsMSDModel.h',
     'basic/BasicCompositor.h',
     'basic/MacIOSurfaceTextureHostBasic.h',
     'basic/TextureHostBasic.h',
+    'BSPTree.h',
     'BufferTexture.h',
     'client/CanvasClient.h',
     'client/CompositableClient.h',
     'client/ContentClient.h',
     'client/ImageClient.h',
     'client/SingleTiledContentClient.h',
     'client/TextureClient.h',
     'client/TextureClientPool.h',
@@ -297,16 +298,17 @@ UNIFIED_SOURCES += [
     'basic/BasicColorLayer.cpp',
     'basic/BasicCompositor.cpp',
     'basic/BasicContainerLayer.cpp',
     'basic/BasicImages.cpp',
     'basic/BasicLayerManager.cpp',
     'basic/BasicLayersImpl.cpp',
     'basic/BasicPaintedLayer.cpp',
     'basic/TextureHostBasic.cpp',
+    'BSPTree.cpp',
     'BufferTexture.cpp',
     'BufferUnrotate.cpp',
     'client/CanvasClient.cpp',
     'client/ClientCanvasLayer.cpp',
     'client/ClientColorLayer.cpp',
     'client/ClientContainerLayer.cpp',
     'client/ClientImageLayer.cpp',
     'client/ClientLayerManager.cpp',
new file mode 100644
--- /dev/null
+++ b/gfx/tests/gtest/TestBSPTree.cpp
@@ -0,0 +1,1124 @@
+/* -*- 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 "Polygon.h"
+
+#include "gtest/gtest.h"
+
+#include <deque>
+
+using mozilla::layers::BSPTree;
+using mozilla::gfx::Point3D;
+using mozilla::gfx::Polygon3D;
+
+namespace
+{
+
+// Compares two points while allowing some numerical inaccuracy.
+static bool FuzzyCompare(const Point3D& lhs, const Point3D& rhs)
+{
+  const float epsilon = 0.001;
+  const Point3D d = lhs - rhs;
+
+  return (abs(d.x) > epsilon || abs(d.y) > epsilon || abs(d.z) > epsilon);
+}
+
+// Compares the points of two polygons and ensures
+// that the points are in the same winding order.
+static bool operator==(const Polygon3D& lhs, const Polygon3D& rhs)
+{
+  const nsTArray<Point3D>& left = lhs.GetPoints();
+  const nsTArray<Point3D>& right = rhs.GetPoints();
+
+  // Polygons do not have the same amount of points.
+  if (left.Length() != right.Length()) {
+    return false;
+  }
+
+  const size_t pointCount = left.Length();
+
+  // Find the first vertex of the first polygon from the second polygon.
+  // This assumes that the polygons do not contain duplicate vertices.
+  int start = -1;
+  for (size_t i = 0; i < pointCount; ++i) {
+    if (FuzzyCompare(left[0], right[i])) {
+      start = i;
+      break;
+    }
+  }
+
+  // Found at least one different vertex.
+  if (start == -1) {
+    return false;
+  }
+
+  // Verify that the polygons have the same points.
+  for (size_t i = 0; i < pointCount; ++i) {
+    size_t j = (start + i) % pointCount;
+
+    if (!FuzzyCompare(left[i], right[j])) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+static void RunTest(const std::deque<Polygon3D>& aPolygons,
+                    const std::deque<Polygon3D>& aExpected)
+{
+  const BSPTree tree(aPolygons);
+  const nsTArray<Polygon3D> order = tree.GetDrawOrder();
+
+  EXPECT_EQ(order.Length(), aExpected.size());
+
+  for (size_t i = 0; i < order.Length(); ++i) {
+    EXPECT_TRUE(order[i] == aExpected[i]);
+  }
+}
+
+}
+
+TEST(BSPTree, SameNode)
+{
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(0.0f, 0.0f, 0.0f),
+      Point3D(1.0f, 0.0f, 0.0f),
+      Point3D(1.0f, 1.0f, 0.0f),
+      Point3D(0.0f, 1.0f, 0.0f)
+    },
+    Polygon3D {
+      Point3D(0.0f, 0.0f, 0.0f),
+      Point3D(1.0f, 0.0f, 0.0f),
+      Point3D(1.0f, 1.0f, 0.0f),
+      Point3D(0.0f, 1.0f, 0.0f)
+    }
+  };
+
+  ::RunTest(polygons, polygons);
+}
+
+TEST(BSPTree, OneChild)
+{
+  const Polygon3D p1 {
+    Point3D(0.0f, 0.0f, 0.0f),
+    Point3D(1.0f, 0.0f, 0.0f),
+    Point3D(1.0f, 1.0f, 0.0f),
+    Point3D(0.0f, 1.0f, 0.0f)
+  };
+
+  const Polygon3D p2 {
+    Point3D(0.0f, 0.0f, 1.0f),
+    Point3D(1.0f, 0.0f, 1.0f),
+    Point3D(1.0f, 1.0f, 1.0f),
+    Point3D(0.0f, 1.0f, 1.0f)
+  };
+
+  ::RunTest(std::deque<Polygon3D> {p1, p2}, {p1, p2});
+  ::RunTest(std::deque<Polygon3D> {p2, p1}, {p1, p2});
+}
+
+TEST(BSPTree, SplitSimple1)
+{
+  Polygon3D p1 {
+    Point3D(0.0f, 0.0f, 1.0f),
+    Point3D(1.0f, 0.0f, 1.0f),
+    Point3D(1.0f, 1.0f, 1.0f),
+    Point3D(0.0f, 1.0f, 1.0f)
+  };
+
+  Polygon3D p2 {
+    Point3D(0.0f, 0.0f, 2.0f),
+    Point3D(1.0f, 0.0f, 2.0f),
+    Point3D(1.0f, 1.0f, 0.0f),
+    Point3D(0.0f, 1.0f, 0.0f)
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.0f, 1.0f, 0.0f),
+      Point3D(0.0f, 0.5f, 1.0f),
+      Point3D(1.0f, 0.5f, 1.0f),
+      Point3D(1.0f, 1.0f, 0.0f)
+    },
+    p1,
+    Polygon3D {
+      Point3D(0.0f, 0.0f, 2.0f),
+      Point3D(1.0f, 0.0f, 2.0f),
+      Point3D(1.0f, 0.5f, 1.0f),
+      Point3D(0.0f, 0.5f, 1.0f)
+    }
+  };
+
+  ::RunTest({p1, p2}, expected);
+}
+
+TEST(BSPTree, SplitSimple2) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, -5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, 5.00000),
+      Point3D(0.00000, -5.00000, 5.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, -5.00000, 0.00000),
+      Point3D(0.00000, -5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 5.00000, 0.00000),
+      Point3D(0.00000, 5.00000, 5.00000),
+      Point3D(0.00000, -5.00000, 5.00000),
+      Point3D(0.00000, -5.00000, 0.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, NoSplit1) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(0.00000, 10.00000, 0.00000),
+      Point3D(0.00000, 0.00000, 0.00000),
+      Point3D(10.00000, 0.00000, 0.00000),
+      Point3D(10.00000, 10.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 10.00000, -5.00000),
+      Point3D(0.00000, 0.00000, -5.00000),
+      Point3D(10.00000, 0.00000, -5.00000),
+      Point3D(10.00000, 10.00000, -5.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 10.00000, 5.00000),
+      Point3D(0.00000, 0.00000, 5.00000),
+      Point3D(10.00000, 0.00000, 5.00000),
+      Point3D(10.00000, 10.00000, 5.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 10.00000, -5.00000),
+      Point3D(0.00000, 0.00000, -5.00000),
+      Point3D(10.00000, 0.00000, -5.00000),
+      Point3D(10.00000, 10.00000, -5.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 10.00000, 0.00000),
+      Point3D(0.00000, 0.00000, 0.00000),
+      Point3D(10.00000, 0.00000, 0.00000),
+      Point3D(10.00000, 10.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 10.00000, 5.00000),
+      Point3D(0.00000, 0.00000, 5.00000),
+      Point3D(10.00000, 0.00000, 5.00000),
+      Point3D(10.00000, 10.00000, 5.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, NoSplit2) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 5.00000, -15.00000),
+      Point3D(0.00000, -5.00000, -15.00000),
+      Point3D(0.00000, -5.00000, -10.00000),
+      Point3D(0.00000, 5.00000, -10.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 5.00000, -15.00000),
+      Point3D(0.00000, -5.00000, -15.00000),
+      Point3D(0.00000, -5.00000, -10.00000),
+      Point3D(0.00000, 5.00000, -10.00000)
+    },
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, SplitComplex1) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(0.00000, -5.00000, -15.00000),
+      Point3D(0.00000, 5.00000, -15.00000),
+      Point3D(0.00000, 5.00000, -10.00000),
+      Point3D(0.00000, -5.00000, -10.00000)
+    },
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000),
+      Point3D(0.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, -5.00000, -15.00000),
+      Point3D(0.00000, 5.00000, -15.00000),
+      Point3D(0.00000, 5.00000, -10.00000),
+      Point3D(0.00000, -5.00000, -10.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(0.00000, 5.00000, 0.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, SplitComplex2) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, -5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, 5.00000),
+      Point3D(0.00000, -5.00000, 5.00000)
+    },
+    Polygon3D {
+      Point3D(-5.00000, 0.00000, -5.00000),
+      Point3D(-5.00000, 0.00000, 5.00000),
+      Point3D(5.00000, 0.00000, 5.00000),
+      Point3D(5.00000, 0.00000, -5.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.00000, 0.00000),
+      Point3D(5.00000, 0.00000, 0.00000),
+      Point3D(5.00000, 0.00000, -5.00000),
+      Point3D(0.00000, 0.00000, -5.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, -5.00000, 0.00000),
+      Point3D(0.00000, -5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, -5.00000),
+      Point3D(0.00000, 5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 0.00000, -5.00000),
+      Point3D(-5.00000, 0.00000, -5.00000),
+      Point3D(-5.00000, 0.00000, 0.00000),
+      Point3D(0.00000, 0.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(-5.00000, -5.00000, 0.00000),
+      Point3D(-5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, 5.00000, 0.00000),
+      Point3D(5.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 0.00000, 5.00000),
+      Point3D(5.00000, 0.00000, 5.00000),
+      Point3D(5.00000, 0.00000, 0.00000),
+      Point3D(0.00000, 0.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 5.00000, 0.00000),
+      Point3D(0.00000, 5.00000, 5.00000),
+      Point3D(0.00000, -5.00000, 5.00000),
+      Point3D(0.00000, -5.00000, 0.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 0.00000, 0.00000),
+      Point3D(-5.00000, 0.00000, 0.00000),
+      Point3D(-5.00000, 0.00000, 5.00000),
+      Point3D(0.00000, 0.00000, 5.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate0) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 2.00000, 2.00000),
+      Point3D(-0.00000, -2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, -2.00000)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.00000, 2.00000),
+      Point3D(2.00000, -0.00000, -2.00000),
+      Point3D(-2.00000, 0.00000, -2.00000),
+      Point3D(-2.00000, 0.00010, 2.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 0.00000, -2.00000),
+      Point3D(-2.00000, 0.00000, -2.00000),
+      Point3D(-2.00000, 0.00010, 2.00000),
+      Point3D(0.00000, 0.00005, 2.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 2.00000, 2.00000),
+      Point3D(-0.00000, -2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, -2.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 0.00005, 2.00000),
+      Point3D(2.00000, 0.00000, 2.00000),
+      Point3D(2.00000, -0.00000, -2.00000),
+      Point3D(0.00010, 0.00000, -2.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate20) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 1.19540, 2.56350),
+      Point3D(-0.00000, -2.56340, 1.19540),
+      Point3D(0.00010, -1.19530, -2.56340),
+      Point3D(0.00010, 2.56350, -1.19530)
+    },
+    Polygon3D {
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, -0.68400, 1.87940)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 0.68410, -1.87930),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(0.00000, -0.68400, 1.87940)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 1.19540, 2.56350),
+      Point3D(-0.00000, -2.56340, 1.19540),
+      Point3D(0.00010, -1.19530, -2.56340),
+      Point3D(0.00010, 2.56350, -1.19530)
+    },
+    Polygon3D {
+      Point3D(0.00000, -0.68400, 1.87940),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(0.00010, 0.68410, -1.87930)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate40) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -0.73200, 2.73210),
+      Point3D(-0.00000, -2.73200, -0.73200),
+      Point3D(0.00010, 0.73210, -2.73200),
+      Point3D(0.00010, 2.73210, 0.73210)
+    },
+    Polygon3D {
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(-2.00000, 1.73210, -0.99990),
+      Point3D(-2.00000, -1.73200, 1.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 1.73210, -0.99990),
+      Point3D(-2.00000, 1.73210, -0.99990),
+      Point3D(-2.00000, -1.73200, 1.00000),
+      Point3D(0.00000, -1.73200, 1.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -0.73200, 2.73210),
+      Point3D(-0.00000, -2.73200, -0.73200),
+      Point3D(0.00010, 0.73210, -2.73200),
+      Point3D(0.00010, 2.73210, 0.73210)
+    },
+    Polygon3D {
+      Point3D(0.00000, -1.73200, 1.00000),
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(0.00010, 1.73210, -0.99990)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate60) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -2.73200, 0.73210),
+      Point3D(-0.00000, -0.73200, -2.73200),
+      Point3D(0.00010, 2.73210, -0.73200),
+      Point3D(0.00010, 0.73210, 2.73210)
+    },
+    Polygon3D {
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(-2.00000, 1.73210, 1.00010),
+      Point3D(-2.00000, -1.73200, -1.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, -1.73200, -1.00000),
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(0.00010, 1.73210, 1.00010)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -2.73200, 0.73210),
+      Point3D(-0.00000, -0.73200, -2.73200),
+      Point3D(0.00010, 2.73210, -0.73200),
+      Point3D(0.00010, 0.73210, 2.73210)
+    },
+    Polygon3D {
+      Point3D(0.00010, 1.73210, 1.00010),
+      Point3D(-2.00000, 1.73210, 1.00010),
+      Point3D(-2.00000, -1.73200, -1.00000),
+      Point3D(0.00000, -1.73200, -1.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate80) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -1.19530, -2.56340),
+      Point3D(-0.00000, 2.56350, -1.19530),
+      Point3D(0.00010, 1.19540, 2.56350),
+      Point3D(0.00010, -2.56340, 1.19540)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, 0.68410, -1.87930)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.68410, -1.87930),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(0.00010, -0.68400, 1.87940)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -1.19530, -2.56340),
+      Point3D(-0.00000, 2.56350, -1.19530),
+      Point3D(0.00010, 1.19540, 2.56350),
+      Point3D(0.00010, -2.56340, 1.19540)
+    },
+    Polygon3D {
+      Point3D(0.00010, -0.68400, 1.87940),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(0.00000, 0.68410, -1.87930)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate100) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 2.73210, -0.73200),
+      Point3D(-0.00000, 0.73210, 2.73210),
+      Point3D(0.00010, -2.73200, 0.73210),
+      Point3D(0.00010, -0.73200, -2.73200)
+    },
+    Polygon3D {
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(-2.00000, -1.73200, -1.00000),
+      Point3D(-2.00000, 1.73210, 1.00010)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, -1.73200, -1.00000),
+      Point3D(-2.00000, -1.73200, -1.00000),
+      Point3D(-2.00000, 1.73210, 1.00010),
+      Point3D(0.00000, 1.73210, 1.00010)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 2.73210, -0.73200),
+      Point3D(-0.00000, 0.73210, 2.73210),
+      Point3D(0.00010, -2.73200, 0.73210),
+      Point3D(0.00010, -0.73200, -2.73200)
+    },
+    Polygon3D {
+      Point3D(0.00000, 1.73210, 1.00010),
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(0.00010, -1.73200, -1.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate120) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -0.73200, 2.73210),
+      Point3D(-0.00000, -2.73200, -0.73200),
+      Point3D(0.00010, 0.73210, -2.73200),
+      Point3D(0.00010, 2.73210, 0.73210)
+    },
+    Polygon3D {
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(-2.00000, 1.73210, -0.99990),
+      Point3D(-2.00000, -1.73200, 1.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 1.73210, -0.99990),
+      Point3D(-2.00000, 1.73210, -0.99990),
+      Point3D(-2.00000, -1.73200, 1.00000),
+      Point3D(0.00000, -1.73200, 1.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -0.73200, 2.73210),
+      Point3D(-0.00000, -2.73200, -0.73200),
+      Point3D(0.00010, 0.73210, -2.73200),
+      Point3D(0.00010, 2.73210, 0.73210)
+    },
+    Polygon3D {
+      Point3D(0.00000, -1.73200, 1.00000),
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(0.00010, 1.73210, -0.99990)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate140) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -1.19530, -2.56340),
+      Point3D(-0.00000, 2.56350, -1.19530),
+      Point3D(0.00010, 1.19540, 2.56350),
+      Point3D(0.00010, -2.56340, 1.19540)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, 0.68410, -1.87930)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.68410, -1.87930),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(0.00010, -0.68400, 1.87940)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -1.19530, -2.56340),
+      Point3D(-0.00000, 2.56350, -1.19530),
+      Point3D(0.00010, 1.19540, 2.56350),
+      Point3D(0.00010, -2.56340, 1.19540)
+    },
+    Polygon3D {
+      Point3D(0.00010, -0.68400, 1.87940),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(0.00000, 0.68410, -1.87930)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate160) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 2.00000, 2.00000),
+      Point3D(-0.00000, -2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, -2.00000)
+    },
+    Polygon3D {
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 0.00010, -2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(0.00000, 0.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 2.00000, 2.00000),
+      Point3D(-0.00000, -2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, -2.00000)
+    },
+    Polygon3D {
+      Point3D(0.00000, 0.00000, 2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(0.00010, 0.00010, -2.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate180) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -2.00000, -2.00000),
+      Point3D(-0.00000, 2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.00010, -2.00000),
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(0.00010, 0.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -2.00000, -2.00000),
+      Point3D(-0.00000, 2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(0.00010, 0.00000, 2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000),
+      Point3D(0.00000, 0.00010, -2.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate200) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 1.19540, 2.56350),
+      Point3D(-0.00000, -2.56340, 1.19540),
+      Point3D(0.00010, -1.19530, -2.56340),
+      Point3D(0.00010, 2.56350, -1.19530)
+    },
+    Polygon3D {
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, -0.68400, 1.87940)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 0.68410, -1.87930),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(0.00000, -0.68400, 1.87940)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 1.19540, 2.56350),
+      Point3D(-0.00000, -2.56340, 1.19540),
+      Point3D(0.00010, -1.19530, -2.56340),
+      Point3D(0.00010, 2.56350, -1.19530)
+    },
+    Polygon3D {
+      Point3D(0.00000, -0.68400, 1.87940),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(0.00010, 0.68410, -1.87930)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate220) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 0.73210, -2.73200),
+      Point3D(-0.00000, 2.73210, 0.73210),
+      Point3D(0.00010, -0.73200, 2.73210),
+      Point3D(0.00010, -2.73200, -0.73200)
+    },
+    Polygon3D {
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(-2.00000, -1.73200, 1.00000),
+      Point3D(-2.00000, 1.73210, -0.99990)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 1.73210, -0.99990),
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(0.00010, -1.73200, 1.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 0.73210, -2.73200),
+      Point3D(-0.00000, 2.73210, 0.73210),
+      Point3D(0.00010, -0.73200, 2.73210),
+      Point3D(0.00010, -2.73200, -0.73200)
+    },
+    Polygon3D {
+      Point3D(0.00010, -1.73200, 1.00000),
+      Point3D(-2.00000, -1.73200, 1.00000),
+      Point3D(-2.00000, 1.73210, -0.99990),
+      Point3D(0.00000, 1.73210, -0.99990)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate240) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -2.73200, 0.73210),
+      Point3D(-0.00000, -0.73200, -2.73200),
+      Point3D(0.00010, 2.73210, -0.73200),
+      Point3D(0.00010, 0.73210, 2.73210)
+    },
+    Polygon3D {
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(-2.00000, 1.73210, 1.00010),
+      Point3D(-2.00000, -1.73200, -1.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, -1.73200, -1.00000),
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(0.00010, 1.73210, 1.00010)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -2.73200, 0.73210),
+      Point3D(-0.00000, -0.73200, -2.73200),
+      Point3D(0.00010, 2.73210, -0.73200),
+      Point3D(0.00010, 0.73210, 2.73210)
+    },
+    Polygon3D {
+      Point3D(0.00010, 1.73210, 1.00010),
+      Point3D(-2.00000, 1.73210, 1.00010),
+      Point3D(-2.00000, -1.73200, -1.00000),
+      Point3D(0.00000, -1.73200, -1.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate260) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 1.19540, 2.56350),
+      Point3D(-0.00000, -2.56340, 1.19540),
+      Point3D(0.00010, -1.19530, -2.56340),
+      Point3D(0.00010, 2.56350, -1.19530)
+    },
+    Polygon3D {
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, -0.68400, 1.87940)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, 0.68410, -1.87930),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(0.00000, -0.68400, 1.87940)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 1.19540, 2.56350),
+      Point3D(-0.00000, -2.56340, 1.19540),
+      Point3D(0.00010, -1.19530, -2.56340),
+      Point3D(0.00010, 2.56350, -1.19530)
+    },
+    Polygon3D {
+      Point3D(0.00000, -0.68400, 1.87940),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(0.00010, 0.68410, -1.87930)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate280) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 2.73210, -0.73200),
+      Point3D(-0.00000, 0.73210, 2.73210),
+      Point3D(0.00010, -2.73200, 0.73210),
+      Point3D(0.00010, -0.73200, -2.73200)
+    },
+    Polygon3D {
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(-2.00000, -1.73200, -1.00000),
+      Point3D(-2.00000, 1.73210, 1.00010)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00010, -1.73200, -1.00000),
+      Point3D(-2.00000, -1.73200, -1.00000),
+      Point3D(-2.00000, 1.73210, 1.00010),
+      Point3D(0.00000, 1.73210, 1.00010)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 2.73210, -0.73200),
+      Point3D(-0.00000, 0.73210, 2.73210),
+      Point3D(0.00010, -2.73200, 0.73210),
+      Point3D(0.00010, -0.73200, -2.73200)
+    },
+    Polygon3D {
+      Point3D(0.00000, 1.73210, 1.00010),
+      Point3D(2.00000, 1.73210, 1.00010),
+      Point3D(2.00000, -1.73200, -1.00000),
+      Point3D(0.00010, -1.73200, -1.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate300) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, 0.73210, -2.73200),
+      Point3D(-0.00000, 2.73210, 0.73210),
+      Point3D(0.00010, -0.73200, 2.73210),
+      Point3D(0.00010, -2.73200, -0.73200)
+    },
+    Polygon3D {
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(-2.00000, -1.73200, 1.00000),
+      Point3D(-2.00000, 1.73210, -0.99990)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 1.73210, -0.99990),
+      Point3D(2.00000, 1.73210, -0.99990),
+      Point3D(2.00000, -1.73200, 1.00000),
+      Point3D(0.00010, -1.73200, 1.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, 0.73210, -2.73200),
+      Point3D(-0.00000, 2.73210, 0.73210),
+      Point3D(0.00010, -0.73200, 2.73210),
+      Point3D(0.00010, -2.73200, -0.73200)
+    },
+    Polygon3D {
+      Point3D(0.00010, -1.73200, 1.00000),
+      Point3D(-2.00000, -1.73200, 1.00000),
+      Point3D(-2.00000, 1.73210, -0.99990),
+      Point3D(0.00000, 1.73210, -0.99990)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate320) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -1.19530, -2.56340),
+      Point3D(-0.00000, 2.56350, -1.19530),
+      Point3D(0.00010, 1.19540, 2.56350),
+      Point3D(0.00010, -2.56340, 1.19540)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, 0.68410, -1.87930)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.68410, -1.87930),
+      Point3D(2.00000, 0.68410, -1.87930),
+      Point3D(2.00000, -0.68400, 1.87940),
+      Point3D(0.00010, -0.68400, 1.87940)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -1.19530, -2.56340),
+      Point3D(-0.00000, 2.56350, -1.19530),
+      Point3D(0.00010, 1.19540, 2.56350),
+      Point3D(0.00010, -2.56340, 1.19540)
+    },
+    Polygon3D {
+      Point3D(0.00010, -0.68400, 1.87940),
+      Point3D(-2.00000, -0.68400, 1.87940),
+      Point3D(-2.00000, 0.68410, -1.87930),
+      Point3D(0.00000, 0.68410, -1.87930)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate340) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -2.00000, -2.00000),
+      Point3D(-0.00000, 2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.00010, -2.00000),
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(0.00010, 0.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -2.00000, -2.00000),
+      Point3D(-0.00000, 2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(0.00010, 0.00000, 2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000),
+      Point3D(0.00000, 0.00010, -2.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
+
+TEST(BSPTree, TwoPlaneIntersectRotate360) {
+  const std::deque<Polygon3D> polygons {
+    Polygon3D {
+      Point3D(-0.00000, -2.00000, -2.00000),
+      Point3D(-0.00000, 2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000)
+    }
+  };
+
+  const std::deque<Polygon3D> expected {
+    Polygon3D {
+      Point3D(0.00000, 0.00010, -2.00000),
+      Point3D(2.00000, 0.00010, -2.00000),
+      Point3D(2.00000, -0.00000, 2.00000),
+      Point3D(0.00010, 0.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(-0.00000, -2.00000, -2.00000),
+      Point3D(-0.00000, 2.00000, -2.00000),
+      Point3D(0.00010, 2.00000, 2.00000),
+      Point3D(0.00010, -2.00000, 2.00000)
+    },
+    Polygon3D {
+      Point3D(0.00010, 0.00000, 2.00000),
+      Point3D(-2.00000, -0.00000, 2.00000),
+      Point3D(-2.00000, 0.00010, -2.00000),
+      Point3D(0.00000, 0.00010, -2.00000)
+    }
+  };
+  ::RunTest(polygons, expected);
+}
\ No newline at end of file
--- a/gfx/tests/gtest/moz.build
+++ b/gfx/tests/gtest/moz.build
@@ -3,16 +3,17 @@
 # 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/.
 
 UNIFIED_SOURCES += [
     'gfxSurfaceRefCountTest.cpp',
     'TestArena.cpp',
     'TestArrayView.cpp',
+    'TestBSPTree.cpp',
     'TestBufferRotation.cpp',
     'TestColorNames.cpp',
     'TestCompositor.cpp',
     'TestGfxPrefs.cpp',
     'TestGfxWidgets.cpp',
     'TestJobScheduler.cpp',
     'TestLayers.cpp',
     'TestMoz2D.cpp',