Bug 1301818 - Prepare BSPTree for integration with the layers code draft
authorMiko Mynttinen <mikokm@gmail.com>
Fri, 16 Sep 2016 16:03:32 -0700
changeset 415241 069fdb40aa4992ab1bbddb7f09a4f3efe9381774
parent 413053 f5d043ce6d36a3c461cbd829d4a4a38394b7c436
child 531577 f4bf3385ea6dd411e091c26688f5cc132e017063
push id29832
push userbmo:mikokm@gmail.com
push dateTue, 20 Sep 2016 00:32:58 +0000
bugs1301818
milestone51.0a1
Bug 1301818 - Prepare BSPTree for integration with the layers code MozReview-Commit-ID: ADJvCZYSk6p
gfx/2d/Polygon.h
gfx/layers/BSPTree.cpp
gfx/layers/BSPTree.h
gfx/tests/gtest/TestBSPTree.cpp
--- a/gfx/2d/Polygon.h
+++ b/gfx/2d/Polygon.h
@@ -2,90 +2,125 @@
  * 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_GFX_POLYGON_H
 #define MOZILLA_GFX_POLYGON_H
 
+#include "Matrix.h"
 #include "mozilla/InitializerList.h"
 #include "nsTArray.h"
 #include "Point.h"
 
 namespace mozilla {
 namespace gfx {
 
-
 // BasePolygon3D stores the points of a convex planar polygon.
 template<class Units>
 class BasePolygon3D {
 public:
-  explicit BasePolygon3D(const std::initializer_list<Point3DTyped<Units>>& aPoints)
-    : mPoints(aPoints)
+  BasePolygon3D() {}
+
+  explicit BasePolygon3D(const std::initializer_list<Point3DTyped<Units>>& aPoints,
+                         Point3DTyped<Units> aNormal =
+                           Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
+    : mNormal(aNormal), mPoints(aPoints)
   {
-    CalculateNormal();
+#ifdef DEBUG
+    EnsurePlanarPolygon();
+#endif
   }
 
-  explicit BasePolygon3D(nsTArray<Point3DTyped<Units>> && aPoints)
-    : mPoints(aPoints)
+  explicit BasePolygon3D(nsTArray<Point3DTyped<Units>>&& aPoints,
+                         Point3DTyped<Units> aNormal =
+                           Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
+    : mNormal(aNormal), mPoints(aPoints)
   {
-    CalculateNormal();
+#ifdef DEBUG
+    EnsurePlanarPolygon();
+#endif
   }
 
   const Point3DTyped<Units>& GetNormal() const
   {
     return mNormal;
   }
 
-  const nsTArray<Point3D>& GetPoints() const
+  const nsTArray<Point3DTyped<Units>>& GetPoints() const
   {
     return mPoints;
   }
 
   const Point3DTyped<Units>& operator[](size_t aIndex) const
   {
     MOZ_ASSERT(mPoints.Length() > aIndex);
     return mPoints[aIndex];
   }
 
+  void TransformToLayerSpace(const Matrix4x4Typed<Units, Units>& aInverseTransform)
+  {
+    TransformPoints(aInverseTransform);
+    mNormal = Point3DTyped<Units>(0.0f, 0.0f, 1.0f);
+  }
+
+  void TransformToScreenSpace(const Matrix4x4Typed<Units, Units>& aTransform)
+  {
+    TransformPoints(aTransform);
+
+    // Normal vectors should be transformed using inverse transpose.
+    mNormal = aTransform.Inverse().Transpose().TransformPoint(mNormal);
+  }
+
 private:
-  // Calculates the polygon surface normal.
-  // The resulting normal vector will point towards the viewer when the polygon
-  // has a counter-clockwise winding order from the perspective of the viewer.
-  void CalculateNormal()
+
+#ifdef DEBUG
+  void EnsurePlanarPolygon() const
   {
     MOZ_ASSERT(mPoints.Length() >= 3);
 
     // This normal calculation method works only for planar polygons.
-    mNormal = (mPoints[1] - mPoints[0]).CrossProduct(mPoints[2] - mPoints[0]);
+    // The resulting normal vector will point towards the viewer when the polygon
+    // has a counter-clockwise winding order from the perspective of the viewer.
+    Point3DTyped<Units> normal;
 
-    const float epsilon = 0.001f;
-    if (mNormal.Length() < epsilon) {
-      // The first three points were too close.
-      // Use more points for better accuracy.
-      for (size_t i = 2; i < mPoints.Length() - 1; ++i) {
-        mNormal += (mPoints[i] - mPoints[0]).CrossProduct(mPoints[i + 1] - mPoints[0]);
-      }
+    for (size_t i = 1; i < mPoints.Length() - 1; ++i) {
+      normal +=
+        (mPoints[i] - mPoints[0]).CrossProduct(mPoints[i + 1] - mPoints[0]);
     }
 
-    mNormal.Normalize();
+    // Ensure that at least one component is greater than zero.
+    // This avoids division by zero when normalizing the vector.
+    bool hasNonZeroComponent = std::abs(normal.x) > 0.0f ||
+                               std::abs(normal.y) > 0.0f ||
+                               std::abs(normal.z) > 0.0f;
+    MOZ_ASSERT(hasNonZeroComponent);
 
-    #ifdef DEBUG
+    normal.Normalize();
+
     // Ensure that the polygon is planar.
     // http://mathworld.wolfram.com/Point-PlaneDistance.html
-    for (const gfx::Point3DTyped<Units>& point : mPoints) {
-      float d = mNormal.DotProduct(point - mPoints[0]);
+    const float epsilon = 0.01f;
+    for (const Point3DTyped<Units>& point : mPoints) {
+      float d = normal.DotProduct(point - mPoints[0]);
       MOZ_ASSERT(std::abs(d) < epsilon);
     }
-    #endif
+  }
+#endif
+
+  void TransformPoints(const Matrix4x4Typed<Units, Units>& aTransform)
+  {
+    for (Point3DTyped<Units>& point : mPoints) {
+      point = aTransform.TransformPoint(point);
+    }
   }
 
+  Point3DTyped<Units> mNormal;
   nsTArray<Point3DTyped<Units>> mPoints;
-  Point3DTyped<Units> mNormal;
 };
 
 typedef BasePolygon3D<UnknownUnits> Polygon3D;
 
 } // namespace gfx
 } // namespace mozilla
 
 #endif /* MOZILLA_GFX_POLYGON_H */
--- a/gfx/layers/BSPTree.cpp
+++ b/gfx/layers/BSPTree.cpp
@@ -4,68 +4,29 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "BSPTree.h"
 #include "mozilla/gfx/Polygon.h"
 
 namespace mozilla {
 namespace layers {
 
-gfx::Polygon3D PopFront(std::deque<gfx::Polygon3D>& aPolygons)
+LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers)
 {
-  gfx::Polygon3D polygon = std::move(aPolygons.front());
-  aPolygons.pop_front();
-  return polygon;
+  LayerPolygon layer = std::move(aLayers.front());
+  aLayers.pop_front();
+  return layer;
 }
 
 namespace {
 
-static int sign(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 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, aPolygons);
-  }
-
-  for (gfx::Polygon3D& polygon : aNode->polygons) {
-    aPolygons.AppendElement(std::move(polygon));
-  }
-
-  if (*back) {
-    BuildDrawOrder(*back, aPolygons);
-  }
-}
-
 nsTArray<float>
-BSPTree::CalculateDotProduct(const gfx::Polygon3D& aFirst,
-                             const gfx::Polygon3D& aSecond,
-                             size_t& aPos, size_t& aNeg) const
+CalculateDotProduct(const gfx::Polygon3D& aFirst,
+                    const gfx::Polygon3D& aSecond,
+                    size_t& aPos, size_t& aNeg)
 {
   // 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];
 
@@ -84,75 +45,35 @@ BSPTree::CalculateDotProduct(const gfx::
     }
 
     dotProducts.AppendElement(dot);
   }
 
   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 (gfx::Polygon3D& polygon : aPolygons) {
-    size_t pos = 0, neg = 0;
-    nsTArray<float> dots = CalculateDotProduct(splittingPlane, polygon,
-                                               pos, neg);
+int Sign(float aValue) {
+  if (aValue > 0) return 1;
+  if (aValue < 0) return -1;
 
-    // Back polygon
-    if (pos == 0 && neg > 0) {
-      backPolygons.push_back(std::move(polygon));
-    }
-    // Front polygon
-    else if (pos > 0 && neg == 0) {
-     frontPolygons.push_back(std::move(polygon));
-    }
-    // Coplanar polygon
-    else if (pos == 0 && neg == 0) {
-      aRoot->polygons.push_back(std::move(polygon));
-    }
-    // Polygon intersects with the splitting plane.
-    else if (pos > 0 && neg > 0) {
-      nsTArray<gfx::Point3D> backPoints, frontPoints;
-      SplitPolygon(splittingPlane, polygon, dots, backPoints, frontPoints);
-
-      backPolygons.push_back(gfx::Polygon3D(std::move(backPoints)));
-      frontPolygons.push_back(gfx::Polygon3D(std::move(frontPoints)));
-    }
-  }
-
-  if (!backPolygons.empty()) {
-    aRoot->back.reset(new BSPTreeNode(PopFront(backPolygons)));
-    BuildTree(aRoot->back, backPolygons);
-  }
-
-  if (!frontPolygons.empty()) {
-    aRoot->front.reset(new BSPTreeNode(PopFront(frontPolygons)));
-    BuildTree(aRoot->front, frontPolygons);
-  }
+  return 0;
 }
 
 void
-BSPTree::SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
-                      const gfx::Polygon3D& aPolygon,
-                      const nsTArray<float>& dots,
-                      nsTArray<gfx::Point3D>& backPoints,
-                      nsTArray<gfx::Point3D>& frontPoints)
+SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
+             const gfx::Polygon3D& aPolygon,
+             const nsTArray<float>& dots,
+             gfx::Polygon3D& back,
+             gfx::Polygon3D& front)
 {
   const gfx::Point3D& normal = aSplittingPlane.GetNormal();
   const size_t pointCount = aPolygon.GetPoints().Length();
 
+  nsTArray<gfx::Point3D> backPoints, frontPoints;
+
   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];
 
@@ -163,25 +84,110 @@ BSPTree::SplitPolygon(const gfx::Polygon
 
     // 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 (sign(dotA) != sign(dotB)) {
+    if (Sign(dotA) != Sign(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);
     }
   }
+
+  back = gfx::Polygon3D(std::move(backPoints), aPolygon.GetNormal());
+  front = gfx::Polygon3D(std::move(frontPoints), aPolygon.GetNormal());
+}
+
+} // namespace
+
+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) {
+    aLayers.AppendElement(std::move(layer));
+  }
+
+  if (*back) {
+    BuildDrawOrder(*back, aLayers);
+  }
+}
+
+void
+BSPTree::BuildTree(UniquePtr<BSPTreeNode>& aRoot,
+                   std::deque<LayerPolygon>& aLayers)
+{
+  if (aLayers.empty()) {
+    return;
+  }
+
+  const gfx::Polygon3D& splittingPlane = aRoot->First();
+  std::deque<LayerPolygon> backLayers, frontLayers;
+
+  for (LayerPolygon& layerPolygon : aLayers) {
+    size_t pos = 0, neg = 0;
+
+    nsTArray<float> dots =
+      CalculateDotProduct(splittingPlane, *layerPolygon.geometry, pos, neg);
+
+    // Back polygon
+    if (pos == 0 && neg > 0) {
+      backLayers.push_back(std::move(layerPolygon));
+    }
+    // Front polygon
+    else if (pos > 0 && neg == 0) {
+      frontLayers.push_back(std::move(layerPolygon));
+    }
+    // Coplanar polygon
+    else if (pos == 0 && neg == 0) {
+      aRoot->layers.push_back(std::move(layerPolygon));
+    }
+    // Polygon intersects with the splitting plane.
+    else if (pos > 0 && neg > 0) {
+      gfx::Polygon3D back, front;
+      SplitPolygon(splittingPlane, *layerPolygon.geometry, dots, back, front);
+
+      backLayers.push_back(LayerPolygon(std::move(back), layerPolygon.layer));
+      frontLayers.push_back(LayerPolygon(std::move(front), layerPolygon.layer));
+    }
+  }
+
+  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
--- a/gfx/layers/BSPTree.h
+++ b/gfx/layers/BSPTree.h
@@ -10,83 +10,91 @@
 #include "mozilla/UniquePtr.h"
 #include "nsTArray.h"
 
 #include <deque>
 
 namespace mozilla {
 namespace layers {
 
-gfx::Polygon3D PopFront(std::deque<gfx::Polygon3D>& aPolygons);
+class Layer;
+
+// Represents a layer that might have a non-rectangular geometry.
+struct LayerPolygon {
+  LayerPolygon(gfx::Polygon3D&& aGeometry, Layer *aLayer)
+    : layer(aLayer), geometry(Some(aGeometry)) {}
+
+  explicit LayerPolygon(Layer *aLayer)
+    : layer(aLayer) {}
 
-// 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.
+  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(gfx::Polygon3D && aPolygon)
+  explicit BSPTreeNode(LayerPolygon&& layer)
   {
-    polygons.push_back(std::move(aPolygon));
+    layers.push_back(std::move(layer));
   }
 
   const gfx::Polygon3D& First() const
   {
-    return polygons[0];
+    MOZ_ASSERT(layers[0].geometry);
+    return *layers[0].geometry;
   }
 
   UniquePtr<BSPTreeNode> front;
   UniquePtr<BSPTreeNode> back;
-  std::deque<gfx::Polygon3D> polygons;
+  std::deque<LayerPolygon> layers;
 };
 
-// BSPTree class takes a list of polygons as an input and uses binary space
+// 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 polygons in the given list.
-  explicit BSPTree(std::deque<gfx::Polygon3D>& aPolygons)
-    : mRoot(new BSPTreeNode(PopFront(aPolygons)))
+  // This constructor takes the ownership of layers in the given list.
+  explicit BSPTree(std::deque<LayerPolygon>& aLayers)
   {
-    BuildTree(mRoot, aPolygons);
+    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<gfx::Polygon3D> GetDrawOrder() const
+  nsTArray<LayerPolygon> GetDrawOrder() const
   {
-    nsTArray<gfx::Polygon3D> polygons;
-    BuildDrawOrder(mRoot, polygons);
-    return polygons;
+    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<gfx::Polygon3D>& aPolygons) const;
-
+                      nsTArray<LayerPolygon>& aLayers) 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;
-
-  void SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
-                    const gfx::Polygon3D& aPolygon,
-                    const nsTArray<float>& dots,
-                    nsTArray<gfx::Point3D>& backPoints,
-                    nsTArray<gfx::Point3D>& frontPoints);
+                 std::deque<LayerPolygon>& aLayers);
 };
 
 } // namespace layers
 } // namespace mozilla
 
 #endif /* MOZILLA_LAYERS_BSPTREE_H */
--- a/gfx/tests/gtest/TestBSPTree.cpp
+++ b/gfx/tests/gtest/TestBSPTree.cpp
@@ -6,29 +6,33 @@
 #include "BSPTree.h"
 #include "Polygon.h"
 
 #include "gtest/gtest.h"
 
 #include <deque>
 
 using mozilla::layers::BSPTree;
+using mozilla::layers::LayerPolygon;
 using mozilla::gfx::Point3D;
 using mozilla::gfx::Polygon3D;
 
-namespace
-{
+namespace {
 
 // Compares two points while allowing some numerical inaccuracy.
-static bool FuzzyCompare(const Point3D& lhs, const Point3D& rhs)
+static bool FuzzyEquals(const Point3D& lhs, const Point3D& rhs)
 {
   const float epsilon = 0.001f;
   const Point3D d = lhs - rhs;
 
-  return (abs(d.x) > epsilon || abs(d.y) > epsilon || abs(d.z) > epsilon);
+  // The absolute difference between the points should be less than
+  // epsilon for every component.
+  return std::abs(d.x) < epsilon &&
+         std::abs(d.y) < epsilon &&
+         std::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();
@@ -39,52 +43,124 @@ static bool operator==(const Polygon3D& 
   }
 
   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])) {
+    if (FuzzyEquals(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])) {
+    if (!FuzzyEquals(left[i], right[j])) {
       return false;
     }
   }
 
   return true;
 }
 
 static void RunTest(std::deque<Polygon3D> aPolygons,
                     std::deque<Polygon3D> aExpected)
 {
-  const BSPTree tree(aPolygons);
-  const nsTArray<Polygon3D> order = tree.GetDrawOrder();
+  std::deque<LayerPolygon> layers;
+  for (Polygon3D& polygon : aPolygons) {
+    layers.push_back(LayerPolygon(std::move(polygon), nullptr));
+  }
 
-  EXPECT_EQ(order.Length(), aExpected.size());
+  const BSPTree tree(layers);
+  const nsTArray<LayerPolygon> order = tree.GetDrawOrder();
+
+  EXPECT_EQ(aExpected.size(), order.Length());
 
   for (size_t i = 0; i < order.Length(); ++i) {
-    EXPECT_TRUE(order[i] == aExpected[i]);
+    EXPECT_TRUE(aExpected[i] == *order[i].geometry);
   }
 }
 
+} // namespace
+
+TEST(BSPTree, TestSanity)
+{
+  EXPECT_TRUE(FuzzyEquals(Point3D(0.0f, 0.0f, 0.0f),
+                          Point3D(0.0f, 0.0f, 0.0f)));
+
+  EXPECT_TRUE(FuzzyEquals(Point3D(0.0f, 0.0f, 0.0f),
+                          Point3D(0.00001f, 0.00001f, 0.00001f)));
+
+  EXPECT_TRUE(FuzzyEquals(Point3D(0.00001f, 0.00001f, 0.00001f),
+                          Point3D(0.0f, 0.0f, 0.0f)));
+
+  EXPECT_FALSE(FuzzyEquals(Point3D(0.0f, 0.0f, 0.0f),
+                           Point3D(0.01f, 0.01f, 0.01f)));
+
+  EXPECT_FALSE(FuzzyEquals(Point3D(0.01f, 0.01f, 0.01f),
+                           Point3D(0.0f, 0.0f, 0.0f)));
+
+  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)
+  };
+
+  // Same points as above shifted forward by one position.
+  Polygon3D shifted {
+    Point3D(0.0f, 1.0f, 1.0f),
+    Point3D(0.0f, 0.0f, 1.0f),
+    Point3D(1.0f, 0.0f, 1.0f),
+    Point3D(1.0f, 1.0f, 1.0f)
+  };
+
+  Polygon3D p2 {
+    Point3D(0.00001f, 0.00001f, 1.00001f),
+    Point3D(1.00001f, 0.00001f, 1.00001f),
+    Point3D(1.00001f, 1.00001f, 1.00001f),
+    Point3D(0.00001f, 1.00001f, 1.00001f)
+  };
+
+  Polygon3D p3 {
+    Point3D(0.01f, 0.01f, 1.01f),
+    Point3D(1.01f, 0.01f, 1.01f),
+    Point3D(1.01f, 1.01f, 1.01f),
+    Point3D(0.01f, 1.01f, 1.01f)
+  };
+
+  // Trivial equals
+  EXPECT_TRUE(p1 == p1);
+  EXPECT_TRUE(p2 == p2);
+  EXPECT_TRUE(p3 == p3);
+  EXPECT_TRUE(shifted == shifted);
+
+  // Polygons with the same point order
+  EXPECT_TRUE(p1 == p2);
+  EXPECT_TRUE(p1 == shifted);
+
+  // Polygons containing different points
+  EXPECT_FALSE(p1 == p3);
+  EXPECT_FALSE(p2 == p3);
+  EXPECT_FALSE(shifted == p3);
+
+  ::RunTest({p1}, {p1});
+  ::RunTest({p2}, {p2});
+  ::RunTest({p1}, {p2});
+  ::RunTest({p1}, {shifted});
 }
 
 TEST(BSPTree, SameNode)
 {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
       Point3D(0.0f, 0.0f, 0.0f),
       Point3D(1.0f, 0.0f, 0.0f),
@@ -113,18 +189,18 @@ TEST(BSPTree, OneChild)
 
   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});
+  ::RunTest({p1, p2}, {p1, p2});
+  ::RunTest({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),
@@ -269,124 +345,16 @@ TEST(BSPTree, NoSplit2) {
       Point3D(-5.00000f, 5.00000f, 0.00000f),
       Point3D(5.00000f, 5.00000f, 0.00000f),
       Point3D(5.00000f, -5.00000f, 0.00000f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
-TEST(BSPTree, SplitComplex1) {
-  const std::deque<Polygon3D> polygons {
-    Polygon3D {
-      Point3D(0.00000f, -5.00000f, -15.00000f),
-      Point3D(0.00000f, 5.00000f, -15.00000f),
-      Point3D(0.00000f, 5.00000f, -10.00000f),
-      Point3D(0.00000f, -5.00000f, -10.00000f)
-    },
-    Polygon3D {
-      Point3D(-5.00000f, -5.00000f, 0.00000f),
-      Point3D(-5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, -5.00000f, 0.00000f)
-    }
-  };
-
-  const std::deque<Polygon3D> expected {
-    Polygon3D {
-      Point3D(0.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, -5.00000f, 0.00000f),
-      Point3D(0.00000f, -5.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -5.00000f, -15.00000f),
-      Point3D(0.00000f, 5.00000f, -15.00000f),
-      Point3D(0.00000f, 5.00000f, -10.00000f),
-      Point3D(0.00000f, -5.00000f, -10.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -5.00000f, 0.00000f),
-      Point3D(-5.00000f, -5.00000f, 0.00000f),
-      Point3D(-5.00000f, 5.00000f, 0.00000f),
-      Point3D(0.00000f, 5.00000f, 0.00000f)
-    }
-  };
-  ::RunTest(polygons, expected);
-}
-
-TEST(BSPTree, SplitComplex2) {
-  const std::deque<Polygon3D> polygons {
-    Polygon3D {
-      Point3D(-5.00000f, -5.00000f, 0.00000f),
-      Point3D(-5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, -5.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -5.00000f, -5.00000f),
-      Point3D(0.00000f, 5.00000f, -5.00000f),
-      Point3D(0.00000f, 5.00000f, 5.00000f),
-      Point3D(0.00000f, -5.00000f, 5.00000f)
-    },
-    Polygon3D {
-      Point3D(-5.00000f, 0.00000f, -5.00000f),
-      Point3D(-5.00000f, 0.00000f, 5.00000f),
-      Point3D(5.00000f, 0.00000f, 5.00000f),
-      Point3D(5.00000f, 0.00000f, -5.00000f)
-    }
-  };
-
-  const std::deque<Polygon3D> expected {
-    Polygon3D {
-      Point3D(0.00000f, 0.00000f, 0.00000f),
-      Point3D(5.00000f, 0.00000f, 0.00000f),
-      Point3D(5.00000f, 0.00000f, -5.00000f),
-      Point3D(0.00000f, 0.00000f, -5.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -5.00000f, 0.00000f),
-      Point3D(0.00000f, -5.00000f, -5.00000f),
-      Point3D(0.00000f, 5.00000f, -5.00000f),
-      Point3D(0.00000f, 5.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, 0.00000f, -5.00000f),
-      Point3D(-5.00000f, 0.00000f, -5.00000f),
-      Point3D(-5.00000f, 0.00000f, 0.00000f),
-      Point3D(0.00000f, 0.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(-5.00000f, -5.00000f, 0.00000f),
-      Point3D(-5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, 5.00000f, 0.00000f),
-      Point3D(5.00000f, -5.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, 0.00000f, 5.00000f),
-      Point3D(5.00000f, 0.00000f, 5.00000f),
-      Point3D(5.00000f, 0.00000f, 0.00000f),
-      Point3D(0.00000f, 0.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, 5.00000f, 0.00000f),
-      Point3D(0.00000f, 5.00000f, 5.00000f),
-      Point3D(0.00000f, -5.00000f, 5.00000f),
-      Point3D(0.00000f, -5.00000f, 0.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, 0.00000f, 0.00000f),
-      Point3D(-5.00000f, 0.00000f, 0.00000f),
-      Point3D(-5.00000f, 0.00000f, 5.00000f),
-      Point3D(0.00000f, 0.00000f, 5.00000f)
-    }
-  };
-  ::RunTest(polygons, expected);
-}
-
 TEST(BSPTree, TwoPlaneIntersectRotate0degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
       Point3D(-0.00000f, 2.00000f, 2.00000f),
       Point3D(-0.00000f, -2.00000f, 2.00000f),
       Point3D(0.00010f, -2.00000f, -2.00000f),
       Point3D(0.00010f, 2.00000f, -2.00000f)
     },
@@ -395,32 +363,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate0de
       Point3D(2.00000f, -0.00000f, -2.00000f),
       Point3D(-2.00000f, 0.00000f, -2.00000f),
       Point3D(-2.00000f, 0.00010f, 2.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 0.00000f, -2.00000f),
+      Point3D(2.00000f, 0.00000f, 2.00000f),
+      Point3D(2.00000f, -0.00000f, -2.00000f),
       Point3D(-2.00000f, 0.00000f, -2.00000f),
-      Point3D(-2.00000f, 0.00010f, 2.00000f),
-      Point3D(0.00000f, 0.00005f, 2.00000f)
+      Point3D(-2.00000f, 0.00010f, 2.00000f)
     },
     Polygon3D {
       Point3D(-0.00000f, 2.00000f, 2.00000f),
       Point3D(-0.00000f, -2.00000f, 2.00000f),
       Point3D(0.00010f, -2.00000f, -2.00000f),
       Point3D(0.00010f, 2.00000f, -2.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, 0.00005f, 2.00000f),
-      Point3D(2.00000f, 0.00000f, 2.00000f),
-      Point3D(2.00000f, -0.00000f, -2.00000f),
-      Point3D(0.00010f, 0.00000f, -2.00000f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate20degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -434,32 +396,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate20d
       Point3D(2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, -0.68400f, 1.87940f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 0.68410f, -1.87930f),
+      Point3D(2.00000f, -0.68400f, 1.87940f),
+      Point3D(2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, 0.68410f, -1.87930f),
-      Point3D(-2.00000f, -0.68400f, 1.87940f),
-      Point3D(0.00000f, -0.68400f, 1.87940f)
+      Point3D(-2.00000f, -0.68400f, 1.87940f)
     },
     Polygon3D {
       Point3D(-0.00000f, 1.19540f, 2.56350f),
       Point3D(-0.00000f, -2.56340f, 1.19540f),
       Point3D(0.00010f, -1.19530f, -2.56340f),
       Point3D(0.00010f, 2.56350f, -1.19530f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -0.68400f, 1.87940f),
-      Point3D(2.00000f, -0.68400f, 1.87940f),
-      Point3D(2.00000f, 0.68410f, -1.87930f),
-      Point3D(0.00010f, 0.68410f, -1.87930f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate40degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -473,32 +429,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate40d
       Point3D(2.00000f, 1.73210f, -0.99990f),
       Point3D(-2.00000f, 1.73210f, -0.99990f),
       Point3D(-2.00000f, -1.73200f, 1.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 1.73210f, -0.99990f),
+      Point3D(2.00000f, -1.73200f, 1.00000f),
+      Point3D(2.00000f, 1.73210f, -0.99990f),
       Point3D(-2.00000f, 1.73210f, -0.99990f),
-      Point3D(-2.00000f, -1.73200f, 1.00000f),
-      Point3D(0.00000f, -1.73200f, 1.00000f)
+      Point3D(-2.00000f, -1.73200f, 1.00000f)
     },
     Polygon3D {
       Point3D(-0.00000f, -0.73200f, 2.73210f),
       Point3D(-0.00000f, -2.73200f, -0.73200f),
       Point3D(0.00010f, 0.73210f, -2.73200f),
       Point3D(0.00010f, 2.73210f, 0.73210f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -1.73200f, 1.00000f),
-      Point3D(2.00000f, -1.73200f, 1.00000f),
-      Point3D(2.00000f, 1.73210f, -0.99990f),
-      Point3D(0.00010f, 1.73210f, -0.99990f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate60degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -512,32 +462,32 @@ TEST(BSPTree, TwoPlaneIntersectRotate60d
       Point3D(2.00000f, 1.73210f, 1.00010f),
       Point3D(-2.00000f, 1.73210f, 1.00010f),
       Point3D(-2.00000f, -1.73200f, -1.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, -1.73200f, -1.00000f),
+      Point3D(-2.00000f, 1.26793f, 0.73210f),
+      Point3D(-2.00000f, -1.73200f, -1.00000f),
       Point3D(2.00000f, -1.73200f, -1.00000f),
-      Point3D(2.00000f, 1.73210f, 1.00010f),
-      Point3D(0.00010f, 1.73210f, 1.00010f)
+      Point3D(2.00000f, 1.26793f, 0.73210f)
     },
     Polygon3D {
       Point3D(-0.00000f, -2.73200f, 0.73210f),
       Point3D(-0.00000f, -0.73200f, -2.73200f),
       Point3D(0.00010f, 2.73210f, -0.73200f),
       Point3D(0.00010f, 0.73210f, 2.73210f)
     },
     Polygon3D {
-      Point3D(0.00010f, 1.73210f, 1.00010f),
+      Point3D(2.00000f, 1.26793f, 0.73210f),
+      Point3D(2.00000f, 1.73210f, 1.00010f),
       Point3D(-2.00000f, 1.73210f, 1.00010f),
-      Point3D(-2.00000f, -1.73200f, -1.00000f),
-      Point3D(0.00000f, -1.73200f, -1.00000f)
+      Point3D(-2.00000f, 1.26793f, 0.73210f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate80degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -551,32 +501,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate80d
       Point3D(2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, 0.68410f, -1.87930f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 0.68410f, -1.87930f),
-      Point3D(2.00000f, 0.68410f, -1.87930f),
-      Point3D(2.00000f, -0.68400f, 1.87940f),
-      Point3D(0.00010f, -0.68400f, 1.87940f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, -1.19530f, -2.56340f),
       Point3D(-0.00000f, 2.56350f, -1.19530f),
       Point3D(0.00010f, 1.19540f, 2.56350f),
       Point3D(0.00010f, -2.56340f, 1.19540f)
     },
     Polygon3D {
-      Point3D(0.00010f, -0.68400f, 1.87940f),
+      Point3D(2.00000f, 0.68410f, -1.87930f),
+      Point3D(2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, -0.68400f, 1.87940f),
-      Point3D(-2.00000f, 0.68410f, -1.87930f),
-      Point3D(0.00000f, 0.68410f, -1.87930f)
+      Point3D(-2.00000f, 0.68410f, -1.87930f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate100degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -590,32 +534,32 @@ TEST(BSPTree, TwoPlaneIntersectRotate100
       Point3D(2.00000f, -1.73200f, -1.00000f),
       Point3D(-2.00000f, -1.73200f, -1.00000f),
       Point3D(-2.00000f, 1.73210f, 1.00010f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, -1.73200f, -1.00000f),
+      Point3D(2.00000f, -1.26783f, -0.73200f),
+      Point3D(2.00000f, -1.73200f, -1.00000f),
       Point3D(-2.00000f, -1.73200f, -1.00000f),
-      Point3D(-2.00000f, 1.73210f, 1.00010f),
-      Point3D(0.00000f, 1.73210f, 1.00010f)
+      Point3D(-2.00000f, -1.26783f, -0.73200f)
     },
     Polygon3D {
       Point3D(-0.00000f, 2.73210f, -0.73200f),
       Point3D(-0.00000f, 0.73210f, 2.73210f),
       Point3D(0.00010f, -2.73200f, 0.73210f),
       Point3D(0.00010f, -0.73200f, -2.73200f)
     },
     Polygon3D {
-      Point3D(0.00000f, 1.73210f, 1.00010f),
+      Point3D(-2.00000f, -1.26783f, -0.73200f),
+      Point3D(-2.00000f, 1.73210f, 1.00010f),
       Point3D(2.00000f, 1.73210f, 1.00010f),
-      Point3D(2.00000f, -1.73200f, -1.00000f),
-      Point3D(0.00010f, -1.73200f, -1.00000f)
+      Point3D(2.00000f, -1.26783f, -0.73200f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate120degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -629,32 +573,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate120
       Point3D(2.00000f, 1.73210f, -0.99990f),
       Point3D(-2.00000f, 1.73210f, -0.99990f),
       Point3D(-2.00000f, -1.73200f, 1.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 1.73210f, -0.99990f),
+      Point3D(2.00000f, -1.73200f, 1.00000f),
+      Point3D(2.00000f, 1.73210f, -0.99990f),
       Point3D(-2.00000f, 1.73210f, -0.99990f),
-      Point3D(-2.00000f, -1.73200f, 1.00000f),
-      Point3D(0.00000f, -1.73200f, 1.00000f)
+      Point3D(-2.00000f, -1.73200f, 1.00000f)
     },
     Polygon3D {
       Point3D(-0.00000f, -0.73200f, 2.73210f),
       Point3D(-0.00000f, -2.73200f, -0.73200f),
       Point3D(0.00010f, 0.73210f, -2.73200f),
       Point3D(0.00010f, 2.73210f, 0.73210f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -1.73200f, 1.00000f),
-      Point3D(2.00000f, -1.73200f, 1.00000f),
-      Point3D(2.00000f, 1.73210f, -0.99990f),
-      Point3D(0.00010f, 1.73210f, -0.99990f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate140degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -668,32 +606,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate140
       Point3D(2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, 0.68410f, -1.87930f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 0.68410f, -1.87930f),
-      Point3D(2.00000f, 0.68410f, -1.87930f),
-      Point3D(2.00000f, -0.68400f, 1.87940f),
-      Point3D(0.00010f, -0.68400f, 1.87940f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, -1.19530f, -2.56340f),
       Point3D(-0.00000f, 2.56350f, -1.19530f),
       Point3D(0.00010f, 1.19540f, 2.56350f),
       Point3D(0.00010f, -2.56340f, 1.19540f)
     },
     Polygon3D {
-      Point3D(0.00010f, -0.68400f, 1.87940f),
+      Point3D(2.00000f, 0.68410f, -1.87930f),
+      Point3D(2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, -0.68400f, 1.87940f),
-      Point3D(-2.00000f, 0.68410f, -1.87930f),
-      Point3D(0.00000f, 0.68410f, -1.87930f)
+      Point3D(-2.00000f, 0.68410f, -1.87930f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate160degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -707,32 +639,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate160
       Point3D(2.00000f, 0.00010f, -2.00000f),
       Point3D(-2.00000f, 0.00010f, -2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 0.00010f, -2.00000f),
+      Point3D(2.00000f, -0.00000f, 2.00000f),
+      Point3D(2.00000f, 0.00010f, -2.00000f),
       Point3D(-2.00000f, 0.00010f, -2.00000f),
-      Point3D(-2.00000f, -0.00000f, 2.00000f),
-      Point3D(0.00000f, 0.00000f, 2.00000f)
+      Point3D(-2.00000f, -0.00000f, 2.00000f)
     },
     Polygon3D {
       Point3D(-0.00000f, 2.00000f, 2.00000f),
       Point3D(-0.00000f, -2.00000f, 2.00000f),
       Point3D(0.00010f, -2.00000f, -2.00000f),
       Point3D(0.00010f, 2.00000f, -2.00000f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, 0.00000f, 2.00000f),
-      Point3D(2.00000f, -0.00000f, 2.00000f),
-      Point3D(2.00000f, 0.00010f, -2.00000f),
-      Point3D(0.00010f, 0.00010f, -2.00000f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate180degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -746,32 +672,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate180
       Point3D(2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, 0.00010f, -2.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 0.00010f, -2.00000f),
-      Point3D(2.00000f, 0.00010f, -2.00000f),
-      Point3D(2.00000f, -0.00000f, 2.00000f),
-      Point3D(0.00010f, 0.00000f, 2.00000f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, -2.00000f, -2.00000f),
       Point3D(-0.00000f, 2.00000f, -2.00000f),
       Point3D(0.00010f, 2.00000f, 2.00000f),
       Point3D(0.00010f, -2.00000f, 2.00000f)
     },
     Polygon3D {
-      Point3D(0.00010f, 0.00000f, 2.00000f),
+      Point3D(2.00000f, 0.00010f, -2.00000f),
+      Point3D(2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f),
-      Point3D(-2.00000f, 0.00010f, -2.00000f),
-      Point3D(0.00000f, 0.00010f, -2.00000f)
+      Point3D(-2.00000f, 0.00010f, -2.00000f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate200degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -785,32 +705,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate200
       Point3D(2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, -0.68400f, 1.87940f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 0.68410f, -1.87930f),
+      Point3D(2.00000f, -0.68400f, 1.87940f),
+      Point3D(2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, 0.68410f, -1.87930f),
-      Point3D(-2.00000f, -0.68400f, 1.87940f),
-      Point3D(0.00000f, -0.68400f, 1.87940f)
+      Point3D(-2.00000f, -0.68400f, 1.87940f)
     },
     Polygon3D {
       Point3D(-0.00000f, 1.19540f, 2.56350f),
       Point3D(-0.00000f, -2.56340f, 1.19540f),
       Point3D(0.00010f, -1.19530f, -2.56340f),
       Point3D(0.00010f, 2.56350f, -1.19530f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -0.68400f, 1.87940f),
-      Point3D(2.00000f, -0.68400f, 1.87940f),
-      Point3D(2.00000f, 0.68410f, -1.87930f),
-      Point3D(0.00010f, 0.68410f, -1.87930f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate220degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -824,32 +738,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate220
       Point3D(2.00000f, -1.73200f, 1.00000f),
       Point3D(-2.00000f, -1.73200f, 1.00000f),
       Point3D(-2.00000f, 1.73210f, -0.99990f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 1.73210f, -0.99990f),
-      Point3D(2.00000f, 1.73210f, -0.99990f),
-      Point3D(2.00000f, -1.73200f, 1.00000f),
-      Point3D(0.00010f, -1.73200f, 1.00000f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, 0.73210f, -2.73200f),
       Point3D(-0.00000f, 2.73210f, 0.73210f),
       Point3D(0.00010f, -0.73200f, 2.73210f),
       Point3D(0.00010f, -2.73200f, -0.73200f)
     },
     Polygon3D {
-      Point3D(0.00010f, -1.73200f, 1.00000f),
+      Point3D(2.00000f, 1.73210f, -0.99990f),
+      Point3D(2.00000f, -1.73200f, 1.00000f),
       Point3D(-2.00000f, -1.73200f, 1.00000f),
-      Point3D(-2.00000f, 1.73210f, -0.99990f),
-      Point3D(0.00000f, 1.73210f, -0.99990f)
+      Point3D(-2.00000f, 1.73210f, -0.99990f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate240degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -863,32 +771,32 @@ TEST(BSPTree, TwoPlaneIntersectRotate240
       Point3D(2.00000f, 1.73210f, 1.00010f),
       Point3D(-2.00000f, 1.73210f, 1.00010f),
       Point3D(-2.00000f, -1.73200f, -1.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, -1.73200f, -1.00000f),
+      Point3D(-2.00000f, 1.26793f, 0.73210f),
+      Point3D(-2.00000f, -1.73200f, -1.00000f),
       Point3D(2.00000f, -1.73200f, -1.00000f),
-      Point3D(2.00000f, 1.73210f, 1.00010f),
-      Point3D(0.00010f, 1.73210f, 1.00010f)
+      Point3D(2.00000f, 1.26793f, 0.73210f)
     },
     Polygon3D {
       Point3D(-0.00000f, -2.73200f, 0.73210f),
       Point3D(-0.00000f, -0.73200f, -2.73200f),
       Point3D(0.00010f, 2.73210f, -0.73200f),
       Point3D(0.00010f, 0.73210f, 2.73210f)
     },
     Polygon3D {
-      Point3D(0.00010f, 1.73210f, 1.00010f),
+      Point3D(2.00000f, 1.26793f, 0.73210f),
+      Point3D(2.00000f, 1.73210f, 1.00010f),
       Point3D(-2.00000f, 1.73210f, 1.00010f),
-      Point3D(-2.00000f, -1.73200f, -1.00000f),
-      Point3D(0.00000f, -1.73200f, -1.00000f)
+      Point3D(-2.00000f, 1.26793f, 0.73210f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate260degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -902,32 +810,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate260
       Point3D(2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, -0.68400f, 1.87940f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, 0.68410f, -1.87930f),
+      Point3D(2.00000f, -0.68400f, 1.87940f),
+      Point3D(2.00000f, 0.68410f, -1.87930f),
       Point3D(-2.00000f, 0.68410f, -1.87930f),
-      Point3D(-2.00000f, -0.68400f, 1.87940f),
-      Point3D(0.00000f, -0.68400f, 1.87940f)
+      Point3D(-2.00000f, -0.68400f, 1.87940f)
     },
     Polygon3D {
       Point3D(-0.00000f, 1.19540f, 2.56350f),
       Point3D(-0.00000f, -2.56340f, 1.19540f),
       Point3D(0.00010f, -1.19530f, -2.56340f),
       Point3D(0.00010f, 2.56350f, -1.19530f)
-    },
-    Polygon3D {
-      Point3D(0.00000f, -0.68400f, 1.87940f),
-      Point3D(2.00000f, -0.68400f, 1.87940f),
-      Point3D(2.00000f, 0.68410f, -1.87930f),
-      Point3D(0.00010f, 0.68410f, -1.87930f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate280degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -941,32 +843,32 @@ TEST(BSPTree, TwoPlaneIntersectRotate280
       Point3D(2.00000f, -1.73200f, -1.00000f),
       Point3D(-2.00000f, -1.73200f, -1.00000f),
       Point3D(-2.00000f, 1.73210f, 1.00010f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00010f, -1.73200f, -1.00000f),
+      Point3D(2.00000f, -1.26783f, -0.73200f),
+      Point3D(2.00000f, -1.73200f, -1.00000f),
       Point3D(-2.00000f, -1.73200f, -1.00000f),
-      Point3D(-2.00000f, 1.73210f, 1.00010f),
-      Point3D(0.00000f, 1.73210f, 1.00010f)
+      Point3D(-2.00000f, -1.26783f, -0.73200f)
     },
     Polygon3D {
       Point3D(-0.00000f, 2.73210f, -0.73200f),
       Point3D(-0.00000f, 0.73210f, 2.73210f),
       Point3D(0.00010f, -2.73200f, 0.73210f),
       Point3D(0.00010f, -0.73200f, -2.73200f)
     },
     Polygon3D {
-      Point3D(0.00000f, 1.73210f, 1.00010f),
+      Point3D(-2.00000f, -1.26783f, -0.73200f),
+      Point3D(-2.00000f, 1.73210f, 1.00010f),
       Point3D(2.00000f, 1.73210f, 1.00010f),
-      Point3D(2.00000f, -1.73200f, -1.00000f),
-      Point3D(0.00010f, -1.73200f, -1.00000f)
+      Point3D(2.00000f, -1.26783f, -0.73200f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate300degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -980,32 +882,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate300
       Point3D(2.00000f, -1.73200f, 1.00000f),
       Point3D(-2.00000f, -1.73200f, 1.00000f),
       Point3D(-2.00000f, 1.73210f, -0.99990f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 1.73210f, -0.99990f),
-      Point3D(2.00000f, 1.73210f, -0.99990f),
-      Point3D(2.00000f, -1.73200f, 1.00000f),
-      Point3D(0.00010f, -1.73200f, 1.00000f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, 0.73210f, -2.73200f),
       Point3D(-0.00000f, 2.73210f, 0.73210f),
       Point3D(0.00010f, -0.73200f, 2.73210f),
       Point3D(0.00010f, -2.73200f, -0.73200f)
     },
     Polygon3D {
-      Point3D(0.00010f, -1.73200f, 1.00000f),
+      Point3D(2.00000f, 1.73210f, -0.99990f),
+      Point3D(2.00000f, -1.73200f, 1.00000f),
       Point3D(-2.00000f, -1.73200f, 1.00000f),
-      Point3D(-2.00000f, 1.73210f, -0.99990f),
-      Point3D(0.00000f, 1.73210f, -0.99990f)
+      Point3D(-2.00000f, 1.73210f, -0.99990f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate320degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -1019,32 +915,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate320
       Point3D(2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, 0.68410f, -1.87930f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 0.68410f, -1.87930f),
-      Point3D(2.00000f, 0.68410f, -1.87930f),
-      Point3D(2.00000f, -0.68400f, 1.87940f),
-      Point3D(0.00010f, -0.68400f, 1.87940f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, -1.19530f, -2.56340f),
       Point3D(-0.00000f, 2.56350f, -1.19530f),
       Point3D(0.00010f, 1.19540f, 2.56350f),
       Point3D(0.00010f, -2.56340f, 1.19540f)
     },
     Polygon3D {
-      Point3D(0.00010f, -0.68400f, 1.87940f),
+      Point3D(2.00000f, 0.68410f, -1.87930f),
+      Point3D(2.00000f, -0.68400f, 1.87940f),
       Point3D(-2.00000f, -0.68400f, 1.87940f),
-      Point3D(-2.00000f, 0.68410f, -1.87930f),
-      Point3D(0.00000f, 0.68410f, -1.87930f)
+      Point3D(-2.00000f, 0.68410f, -1.87930f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate340degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -1058,32 +948,26 @@ TEST(BSPTree, TwoPlaneIntersectRotate340
       Point3D(2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, 0.00010f, -2.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 0.00010f, -2.00000f),
-      Point3D(2.00000f, 0.00010f, -2.00000f),
-      Point3D(2.00000f, -0.00000f, 2.00000f),
-      Point3D(0.00010f, 0.00000f, 2.00000f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, -2.00000f, -2.00000f),
       Point3D(-0.00000f, 2.00000f, -2.00000f),
       Point3D(0.00010f, 2.00000f, 2.00000f),
       Point3D(0.00010f, -2.00000f, 2.00000f)
     },
     Polygon3D {
-      Point3D(0.00010f, 0.00000f, 2.00000f),
+      Point3D(2.00000f, 0.00010f, -2.00000f),
+      Point3D(2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f),
-      Point3D(-2.00000f, 0.00010f, -2.00000f),
-      Point3D(0.00000f, 0.00010f, -2.00000f)
+      Point3D(-2.00000f, 0.00010f, -2.00000f)
     }
   };
   ::RunTest(polygons, expected);
 }
 
 TEST(BSPTree, TwoPlaneIntersectRotate360degrees) {
   const std::deque<Polygon3D> polygons {
     Polygon3D {
@@ -1097,28 +981,22 @@ TEST(BSPTree, TwoPlaneIntersectRotate360
       Point3D(2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, 0.00010f, -2.00000f)
     }
   };
 
   const std::deque<Polygon3D> expected {
     Polygon3D {
-      Point3D(0.00000f, 0.00010f, -2.00000f),
-      Point3D(2.00000f, 0.00010f, -2.00000f),
-      Point3D(2.00000f, -0.00000f, 2.00000f),
-      Point3D(0.00010f, 0.00000f, 2.00000f)
-    },
-    Polygon3D {
       Point3D(-0.00000f, -2.00000f, -2.00000f),
       Point3D(-0.00000f, 2.00000f, -2.00000f),
       Point3D(0.00010f, 2.00000f, 2.00000f),
       Point3D(0.00010f, -2.00000f, 2.00000f)
     },
     Polygon3D {
-      Point3D(0.00010f, 0.00000f, 2.00000f),
+      Point3D(2.00000f, 0.00010f, -2.00000f),
+      Point3D(2.00000f, -0.00000f, 2.00000f),
       Point3D(-2.00000f, -0.00000f, 2.00000f),
-      Point3D(-2.00000f, 0.00010f, -2.00000f),
-      Point3D(0.00000f, 0.00010f, -2.00000f)
+      Point3D(-2.00000f, 0.00010f, -2.00000f)
     }
   };
   ::RunTest(polygons, expected);
 }