Use move semantics in BSPTree draft
authorMiko Mynttinen <mikokm@gmail.com>
Tue, 09 Aug 2016 10:27:24 -0700
changeset 398871 cd22f3c92fb30c27c6a006494fbb3b46c6483cf1
parent 398870 70c06030d2b50c36f9fd4de96043c86db669b925
child 398872 300b3f5e1cdc6ae43e0abd539fc5c529a2c0828a
child 398879 d0a92000a50be6021ddc45dfda7fd5f80ef8eef3
push id25661
push userbmo:mikokm@gmail.com
push dateTue, 09 Aug 2016 22:06:19 +0000
milestone51.0a1
Use move semantics in BSPTree MozReview-Commit-ID: 49jA37KDeqB
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
@@ -20,17 +20,17 @@ template<class Units>
 class BasePolygon3D {
 public:
   explicit BasePolygon3D(const std::initializer_list<Point3DTyped<Units>>& aPoints)
     : mPoints(aPoints)
   {
     CalculateNormal();
   }
 
-  explicit BasePolygon3D(nsTArray<Point3DTyped<Units>>&& aPoints)
+  explicit BasePolygon3D(nsTArray<Point3DTyped<Units>> && aPoints)
     : mPoints(aPoints)
   {
     CalculateNormal();
   }
 
   const Point3DTyped<Units>& GetNormal() const
   {
     return mNormal;
--- a/gfx/layers/BSPTree.cpp
+++ b/gfx/layers/BSPTree.cpp
@@ -4,16 +4,23 @@
  * 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)
+{
+  gfx::Polygon3D polygon = std::move(aPolygons.front());
+  aPolygons.pop_front();
+  return polygon;
+}
+
 namespace {
 
 static int sign(float d) {
   if (d > 0) return 1;
   if (d < 0) return -1;
 
   return 0;
 }
@@ -25,28 +32,30 @@ BSPTree::BuildDrawOrder(const UniquePtr<
                         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.
+  // 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);
   }
 
-  aPolygons.AppendElements(aNode->polygons);
+  for (gfx::Polygon3D& polygon : aNode->polygons) {
+    aPolygons.AppendElement(std::move(polygon));
+  }
 
   if (*back) {
     BuildDrawOrder(*back, aPolygons);
   }
 }
 
 nsTArray<float>
 BSPTree::CalculateDotProduct(const gfx::Polygon3D& aFirst,
@@ -86,67 +95,62 @@ BSPTree::BuildTree(UniquePtr<BSPTreeNode
 {
   if (aPolygons.empty()) {
     return;
   }
 
   const gfx::Polygon3D& splittingPlane = aRoot->First();
   std::deque<gfx::Polygon3D> backPolygons, frontPolygons;
 
-  for (const gfx::Polygon3D& polygon : aPolygons) {
+  for (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);
+      backPolygons.push_back(std::move(polygon));
     }
-
     // Front polygon
-    if (pos > 0 && neg == 0) {
-     frontPolygons.push_back(polygon);
+    else if (pos > 0 && neg == 0) {
+     frontPolygons.push_back(std::move(polygon));
     }
-
     // Coplanar polygon
-    if (pos == 0 && neg == 0) {
-      aRoot->AddPolygon(polygon);
+    else if (pos == 0 && neg == 0) {
+      aRoot->polygons.push_back(std::move(polygon));
     }
-
     // Polygon intersects with the splitting plane.
-    if (pos > 0 && neg > 0) {
-      std::pair<gfx::Polygon3D, gfx::Polygon3D> split =
-        SplitPolygon(splittingPlane, polygon, dots);
+    else if (pos > 0 && neg > 0) {
+      nsTArray<gfx::Point3D> backPoints, frontPoints;
+      SplitPolygon(splittingPlane, polygon, dots, backPoints, frontPoints);
 
-      backPolygons.push_back(split.first);
-      frontPolygons.push_back(split.second);
+      backPolygons.push_back(gfx::Polygon3D(std::move(backPoints)));
+      frontPolygons.push_back(gfx::Polygon3D(std::move(frontPoints)));
     }
   }
 
   if (!backPolygons.empty()) {
-    aRoot->back.reset(new BSPTreeNode(backPolygons.front()));
-    backPolygons.pop_front();
+    aRoot->back.reset(new BSPTreeNode(PopFront(backPolygons)));
     BuildTree(aRoot->back, backPolygons);
   }
 
   if (!frontPolygons.empty()) {
-    aRoot->front.reset(new BSPTreeNode(frontPolygons.front()));
-    frontPolygons.pop_front();
+    aRoot->front.reset(new BSPTreeNode(PopFront(frontPolygons)));
     BuildTree(aRoot->front, frontPolygons);
   }
 }
 
-std::pair<gfx::Polygon3D, gfx::Polygon3D>
+void
 BSPTree::SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
                       const gfx::Polygon3D& aPolygon,
-                      const nsTArray<float>& dots)
+                      const nsTArray<float>& dots,
+                      nsTArray<gfx::Point3D>& backPoints,
+                      nsTArray<gfx::Point3D>& frontPoints)
 {
   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];
@@ -172,15 +176,12 @@ BSPTree::SplitPolygon(const gfx::Polygon
       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(std::move(backPoints)),
-                        gfx::Polygon3D(std::move(frontPoints)));
 }
 
 } // namespace layers
 } // namespace mozilla
--- a/gfx/layers/BSPTree.h
+++ b/gfx/layers/BSPTree.h
@@ -6,58 +6,54 @@
 #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 {
 
+gfx::Polygon3D PopFront(std::deque<gfx::Polygon3D>& aPolygons);
+
 // 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 {
-  explicit BSPTreeNode(const gfx::Polygon3D& aPolygon)
+  explicit BSPTreeNode(gfx::Polygon3D && aPolygon)
   {
-    AddPolygon(aPolygon);
-  }
-
-  void AddPolygon(const gfx::Polygon3D& aPolygon)
-  {
-    polygons.AppendElement(aPolygon);
+    polygons.push_back(std::move(aPolygon));
   }
 
   const gfx::Polygon3D& First() const
   {
     return polygons[0];
   }
 
   UniquePtr<BSPTreeNode> front;
   UniquePtr<BSPTreeNode> back;
-  nsTArray<gfx::Polygon3D> polygons;
+  std::deque<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()))
+  // This constructor takes the ownership of polygons in the given list.
+  explicit BSPTree(std::deque<gfx::Polygon3D>& aPolygons)
+    : mRoot(new BSPTreeNode(PopFront(aPolygons)))
   {
-    aPolygons.pop_front();
     BuildTree(mRoot, aPolygons);
   }
 
   // Returns the root node of the BSP tree.
   const UniquePtr<BSPTreeNode>& GetRoot() const
   {
     return mRoot;
   }
@@ -78,18 +74,19 @@ private:
 
   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);
+  void SplitPolygon(const gfx::Polygon3D& aSplittingPlane,
+                    const gfx::Polygon3D& aPolygon,
+                    const nsTArray<float>& dots,
+                    nsTArray<gfx::Point3D>& backPoints,
+                    nsTArray<gfx::Point3D>& frontPoints);
 };
 
 } // namespace layers
 } // namespace mozilla
 
 #endif /* MOZILLA_LAYERS_BSPTREE_H */
\ No newline at end of file
--- a/gfx/tests/gtest/TestBSPTree.cpp
+++ b/gfx/tests/gtest/TestBSPTree.cpp
@@ -62,18 +62,18 @@ static bool operator==(const Polygon3D& 
     if (!FuzzyCompare(left[i], right[j])) {
       return false;
     }
   }
 
   return true;
 }
 
-static void RunTest(const std::deque<Polygon3D>& aPolygons,
-                    const std::deque<Polygon3D>& aExpected)
+static void RunTest(std::deque<Polygon3D> aPolygons,
+                    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]);