--- 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]);