--- a/gfx/2d/Polygon.h
+++ b/gfx/2d/Polygon.h
@@ -1,49 +1,129 @@
/* -*- 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_GFX_POLYGON_H
#define MOZILLA_GFX_POLYGON_H
#include "Matrix.h"
#include "mozilla/InitializerList.h"
+#include "mozilla/Move.h"
#include "nsTArray.h"
#include "Point.h"
+#include "Triangle.h"
namespace mozilla {
namespace gfx {
-// BasePolygon3D stores the points of a convex planar polygon.
+// Polygon3DTyped stores the points of a convex planar polygon.
template<class Units>
-class BasePolygon3D {
+class Polygon3DTyped {
public:
- BasePolygon3D() {}
+ Polygon3DTyped() {}
+
+ explicit Polygon3DTyped(const std::initializer_list<Point3DTyped<Units>>& aPoints,
+ Point3DTyped<Units> aNormal =
+ Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
+ : mNormal(aNormal), mPoints(aPoints)
+ {
+#ifdef DEBUG
+ EnsurePlanarPolygon();
+#endif
+ }
- explicit BasePolygon3D(const std::initializer_list<Point3DTyped<Units>>& aPoints,
- Point3DTyped<Units> aNormal =
- Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
+ explicit Polygon3DTyped(nsTArray<Point3DTyped<Units>>&& aPoints,
+ Point3DTyped<Units> aNormal =
+ Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
+ : mNormal(aNormal), mPoints(Move(aPoints))
+ {
+#ifdef DEBUG
+ EnsurePlanarPolygon();
+#endif
+ }
+
+ explicit Polygon3DTyped(const nsTArray<Point3DTyped<Units>>& aPoints,
+ Point3DTyped<Units> aNormal =
+ Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
: mNormal(aNormal), mPoints(aPoints)
{
#ifdef DEBUG
EnsurePlanarPolygon();
#endif
}
- explicit BasePolygon3D(nsTArray<Point3DTyped<Units>>&& aPoints,
- Point3DTyped<Units> aNormal =
- Point3DTyped<Units>(0.0f, 0.0f, 1.0f))
- : mNormal(aNormal), mPoints(aPoints)
+ RectTyped<Units> BoundingBox() const
+ {
+ float minX, maxX, minY, maxY;
+ minX = maxX = mPoints[0].x;
+ minY = maxY = mPoints[0].y;
+
+ for (const Point3DTyped<Units>& point : mPoints) {
+ minX = std::min(point.x, minX);
+ maxX = std::max(point.x, maxX);
+
+ minY = std::min(point.y, minY);
+ maxY = std::max(point.y, maxY);
+ }
+
+ return RectTyped<Units>(minX, minY, maxX - minX, maxY - minY);
+ }
+
+ nsTArray<float>
+ CalculateDotProducts(const Polygon3DTyped<Units>& aPlane,
+ size_t& aPos, size_t& aNeg) const
{
-#ifdef DEBUG
- EnsurePlanarPolygon();
-#endif
+ // Point classification might produce incorrect results due to numerical
+ // inaccuracies. Using an epsilon value makes the splitting plane "thicker".
+ const float epsilon = 0.05f;
+
+ MOZ_ASSERT(!aPlane.GetPoints().IsEmpty());
+ const Point3DTyped<Units>& planeNormal = aPlane.GetNormal();
+ const Point3DTyped<Units>& planePoint = aPlane[0];
+
+ aPos = aNeg = 0;
+ nsTArray<float> dotProducts;
+ for (const Point3DTyped<Units>& point : mPoints) {
+ float dot = (point - planePoint).DotProduct(planeNormal);
+
+ if (dot > epsilon) {
+ aPos++;
+ } else if (dot < -epsilon) {
+ aNeg++;
+ } else {
+ // The point is within the thick plane.
+ dot = 0.0f;
+ }
+
+ dotProducts.AppendElement(dot);
+ }
+
+ return dotProducts;
+ }
+
+ // Clips the polygon against the given 2D rectangle.
+ Polygon3DTyped<Units> ClipPolygon(const RectTyped<Units>& aRect) const
+ {
+ Polygon3DTyped<Units> polygon(mPoints, mNormal);
+
+ // Left edge
+ ClipPolygonWithEdge(polygon, aRect.BottomLeft(), aRect.TopLeft());
+
+ // Bottom edge
+ ClipPolygonWithEdge(polygon, aRect.BottomRight(), aRect.BottomLeft());
+
+ // Right edge
+ ClipPolygonWithEdge(polygon, aRect.TopRight(), aRect.BottomRight());
+
+ // Top edge
+ ClipPolygonWithEdge(polygon, aRect.TopLeft(), aRect.TopRight());
+
+ return polygon;
}
const Point3DTyped<Units>& GetNormal() const
{
return mNormal;
}
const nsTArray<Point3DTyped<Units>>& GetPoints() const
@@ -52,40 +132,129 @@ public:
}
const Point3DTyped<Units>& operator[](size_t aIndex) const
{
MOZ_ASSERT(mPoints.Length() > aIndex);
return mPoints[aIndex];
}
- void TransformToLayerSpace(const Matrix4x4Typed<Units, Units>& aInverseTransform)
+ void SplitPolygon(const Polygon3DTyped<Units>& aSplittingPlane,
+ const nsTArray<float>& aDots,
+ nsTArray<Point3DTyped<Units>>& aBackPoints,
+ nsTArray<Point3DTyped<Units>>& aFrontPoints) const
{
- TransformPoints(aInverseTransform);
+ static const auto Sign = [](const float& f) {
+ if (f > 0.0f) return 1;
+ if (f < 0.0f) return -1;
+ return 0;
+ };
+
+ const Point3DTyped<Units>& normal = aSplittingPlane.GetNormal();
+ const size_t pointCount = mPoints.Length();
+
+ for (size_t i = 0; i < pointCount; ++i) {
+ size_t j = (i + 1) % pointCount;
+
+ const Point3DTyped<Units>& a = mPoints[i];
+ const Point3DTyped<Units>& b = mPoints[j];
+ const float dotA = aDots[i];
+ const float dotB = aDots[j];
+
+ // The point is in front of or on the plane.
+ if (dotA >= 0) {
+ aFrontPoints.AppendElement(a);
+ }
+
+ // The point is behind or on the plane.
+ if (dotA <= 0) {
+ aBackPoints.AppendElement(a);
+ }
+
+ // If the sign of the dot products changes between two consecutive
+ // vertices, then the plane intersects with the polygon edge.
+ // The case where the polygon edge is within the plane is handled above.
+ if (Sign(dotA) && Sign(dotB) && Sign(dotA) != Sign(dotB)) {
+ // Calculate the line segment and plane intersection point.
+ const Point3DTyped<Units> ab = b - a;
+ const float dotAB = ab.DotProduct(normal);
+ const float t = -dotA / dotAB;
+ const Point3DTyped<Units> p = a + (ab * t);
+
+ // Add the intersection point to both polygons.
+ aBackPoints.AppendElement(p);
+ aFrontPoints.AppendElement(p);
+ }
+ }
+ }
+
+ void TransformToLayerSpace(const Matrix4x4Typed<Units, Units>& aTransform)
+ {
+ TransformPoints(aTransform);
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);
}
+ nsTArray<TriangleTyped<Units>> Triangulate() const
+ {
+ nsTArray<TriangleTyped<Units>> triangles;
+
+ if (mPoints.Length() < 3) {
+ return triangles;
+ }
+
+ for (size_t i = 1; i < mPoints.Length() - 1; ++i) {
+ TriangleTyped<Units> triangle(Point(mPoints[0].x, mPoints[0].y),
+ Point(mPoints[i].x, mPoints[i].y),
+ Point(mPoints[i+1].x, mPoints[i+1].y));
+ triangles.AppendElement(Move(triangle));
+ }
+
+ return triangles;
+ }
+
private:
+ void ClipPolygonWithEdge(Polygon3DTyped<Units>& aPolygon,
+ const PointTyped<Units>& aFirst,
+ const PointTyped<Units>& aSecond) const
+ {
+ const Point3DTyped<Units> a(aFirst.x, aFirst.y, 0.0f);
+ const Point3DTyped<Units> b(aSecond.x, aSecond.y, 0.0f);
+ const Point3DTyped<Units> normal(b.y - a.y, a.x - b.x, 0.0f);
+ Polygon3DTyped<Units> plane({a, b}, normal);
+
+ size_t pos, neg;
+ nsTArray<float> dots = aPolygon.CalculateDotProducts(plane, pos, neg);
+
+ nsTArray<Point3DTyped<Units>> backPoints, frontPoints;
+ aPolygon.SplitPolygon(plane, dots, backPoints, frontPoints);
+
+ // Only use the points that are behind the clipping plane.
+ aPolygon = Polygon3DTyped<Units>(Move(backPoints), aPolygon.GetNormal());
+ }
#ifdef DEBUG
void EnsurePlanarPolygon() const
{
- MOZ_ASSERT(mPoints.Length() >= 3);
+ if (mPoints.Length() <= 3) {
+ // Polygons with three or less points are guaranteed to be planar.
+ return;
+ }
// This normal calculation method works only for planar polygons.
- // The resulting normal vector will point towards the viewer when the polygon
- // has a counter-clockwise winding order from the perspective of the viewer.
+ // 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;
for (size_t i = 1; i < mPoints.Length() - 1; ++i) {
normal +=
(mPoints[i] - mPoints[0]).CrossProduct(mPoints[i + 1] - mPoints[0]);
}
// Ensure that at least one component is greater than zero.
@@ -101,26 +270,25 @@ private:
// http://mathworld.wolfram.com/Point-PlaneDistance.html
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
-
void TransformPoints(const Matrix4x4Typed<Units, Units>& aTransform)
{
for (Point3DTyped<Units>& point : mPoints) {
point = aTransform.TransformPoint(point);
}
}
Point3DTyped<Units> mNormal;
nsTArray<Point3DTyped<Units>> mPoints;
};
-typedef BasePolygon3D<UnknownUnits> Polygon3D;
+typedef Polygon3DTyped<UnknownUnits> Polygon3D;
} // namespace gfx
} // namespace mozilla
#endif /* MOZILLA_GFX_POLYGON_H */
new file mode 100644
--- /dev/null
+++ b/gfx/2d/Triangle.h
@@ -0,0 +1,66 @@
+/* -*- 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_GFX_TRIANGLE_H
+#define MOZILLA_GFX_TRIANGLE_H
+
+#include <algorithm>
+
+#include "mozilla/Move.h"
+#include "Point.h"
+#include "Rect.h"
+
+namespace mozilla {
+namespace gfx {
+
+/**
+ * A simple triangle data structure.
+ */
+template<class Units, class F = Float>
+struct TriangleTyped
+{
+ PointTyped<Units, F> p1, p2, p3;
+ F width, height;
+
+ TriangleTyped()
+ : p1(), p2(), p3() {}
+
+ TriangleTyped(PointTyped<Units, F> aP1,
+ PointTyped<Units, F> aP2,
+ PointTyped<Units, F> aP3)
+ : p1(aP1), p2(aP2), p3(aP3) {}
+
+ RectTyped<Units, F> BoundingBox() const
+ {
+ F minX = std::min(std::min(p1.x, p2.x), p3.x);
+ F maxX = std::max(std::max(p1.x, p2.x), p3.x);
+
+ F minY = std::min(std::min(p1.y, p2.y), p3.y);
+ F maxY = std::max(std::max(p1.y, p2.y), p3.y);
+
+ return RectTyped<Units, F>(minX, minY, maxX - minX, maxY - minY);
+ }
+};
+
+typedef TriangleTyped<UnknownUnits, Float> Triangle;
+
+template<class Units, class F = Float>
+struct TexturedTriangleTyped : public TriangleTyped<Units, F>
+{
+ explicit TexturedTriangleTyped(const TriangleTyped<Units, F>& aTriangle)
+ : TriangleTyped<Units, F>(aTriangle) {}
+
+ explicit TexturedTriangleTyped(TriangleTyped<Units, F>&& aTriangle)
+ : TriangleTyped<Units, F>(Move(aTriangle)) {}
+
+ TriangleTyped<Units, F> textureCoords;
+};
+
+typedef TexturedTriangleTyped<UnknownUnits, Float> TexturedTriangle;
+
+} // namespace gfx
+} // namespace mozilla
+
+#endif /* MOZILLA_GFX_TRIANGLE_H */
--- a/gfx/2d/moz.build
+++ b/gfx/2d/moz.build
@@ -47,16 +47,17 @@ EXPORTS.mozilla.gfx += [
'Rect.h',
'Scale.h',
'ScaleFactor.h',
'ScaleFactors2D.h',
'SourceSurfaceCairo.h',
'SourceSurfaceRawData.h',
'StackArray.h',
'Tools.h',
+ 'Triangle.h',
'Types.h',
'UserData.h',
]
EXPORTS.mozilla.gfx += ['ssse3-scaler.h']
if CONFIG['MOZ_WIDGET_TOOLKIT'] in ('cocoa', 'uikit'):
EXPORTS.mozilla.gfx += [
--- a/gfx/layers/BSPTree.cpp
+++ b/gfx/layers/BSPTree.cpp
@@ -6,114 +6,21 @@
#include "BSPTree.h"
#include "mozilla/gfx/Polygon.h"
namespace mozilla {
namespace layers {
LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers)
{
- LayerPolygon layer = std::move(aLayers.front());
+ LayerPolygon layer = Move(aLayers.front());
aLayers.pop_front();
return layer;
}
-namespace {
-
-nsTArray<float>
-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];
-
- nsTArray<float> dotProducts;
-
- for (const gfx::Point3D& point : aSecond.GetPoints()) {
- float dot = (point - planePoint).DotProduct(normal);
-
- if (dot > epsilon) {
- aPos++;
- } else if (dot < -epsilon) {
- aNeg++;
- } else {
- // The point is within the thick plane.
- dot = 0.0f;
- }
-
- dotProducts.AppendElement(dot);
- }
-
- return dotProducts;
-}
-
-int Sign(float aValue) {
- if (aValue > 0) return 1;
- if (aValue < 0) return -1;
-
- return 0;
-}
-
-void
-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];
-
- // 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 (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;
@@ -126,60 +33,67 @@ BSPTree::BuildDrawOrder(const UniquePtr<
std::swap(front, back);
}
if (*front) {
BuildDrawOrder(*front, aLayers);
}
for (LayerPolygon& layer : aNode->layers) {
- aLayers.AppendElement(std::move(layer));
+ MOZ_ASSERT(layer.geometry);
+
+ if (layer.geometry->GetPoints().Length() >= 3) {
+ aLayers.AppendElement(Move(layer));
+ }
}
if (*back) {
BuildDrawOrder(*back, aLayers);
}
}
void
BSPTree::BuildTree(UniquePtr<BSPTreeNode>& aRoot,
std::deque<LayerPolygon>& aLayers)
{
if (aLayers.empty()) {
return;
}
- const gfx::Polygon3D& splittingPlane = aRoot->First();
+ const gfx::Polygon3D& plane = aRoot->First();
std::deque<LayerPolygon> backLayers, frontLayers;
for (LayerPolygon& layerPolygon : aLayers) {
- size_t pos = 0, neg = 0;
+ const Maybe<gfx::Polygon3D>& geometry = layerPolygon.geometry;
- nsTArray<float> dots =
- CalculateDotProduct(splittingPlane, *layerPolygon.geometry, pos, neg);
+ size_t pos = 0, neg = 0;
+ nsTArray<float> dots = geometry->CalculateDotProducts(plane, pos, neg);
// Back polygon
if (pos == 0 && neg > 0) {
- backLayers.push_back(std::move(layerPolygon));
+ backLayers.push_back(Move(layerPolygon));
}
// Front polygon
else if (pos > 0 && neg == 0) {
- frontLayers.push_back(std::move(layerPolygon));
+ frontLayers.push_back(Move(layerPolygon));
}
// Coplanar polygon
else if (pos == 0 && neg == 0) {
- aRoot->layers.push_back(std::move(layerPolygon));
+ aRoot->layers.push_back(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);
+ nsTArray<gfx::Point3D> backPoints, frontPoints;
+ geometry->SplitPolygon(plane, dots, backPoints, frontPoints);
- backLayers.push_back(LayerPolygon(std::move(back), layerPolygon.layer));
- frontLayers.push_back(LayerPolygon(std::move(front), layerPolygon.layer));
+ const gfx::Point3D& normal = geometry->GetNormal();
+ Layer *layer = layerPolygon.layer;
+
+ backLayers.push_back(LayerPolygon(layer, Move(backPoints), normal));
+ frontLayers.push_back(LayerPolygon(layer, Move(frontPoints), normal));
}
}
if (!backLayers.empty()) {
aRoot->back.reset(new BSPTreeNode(PopFront(backLayers)));
BuildTree(aRoot->back, backLayers);
}
--- a/gfx/layers/BSPTree.h
+++ b/gfx/layers/BSPTree.h
@@ -2,47 +2,53 @@
* 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/Move.h"
#include "mozilla/UniquePtr.h"
#include "nsTArray.h"
#include <deque>
namespace mozilla {
namespace layers {
class Layer;
// Represents a layer that might have a non-rectangular geometry.
struct LayerPolygon {
- LayerPolygon(gfx::Polygon3D&& aGeometry, Layer *aLayer)
+ explicit LayerPolygon(Layer *aLayer)
+ : layer(aLayer) {}
+
+ LayerPolygon(Layer *aLayer,
+ gfx::Polygon3D&& aGeometry)
: layer(aLayer), geometry(Some(aGeometry)) {}
- explicit LayerPolygon(Layer *aLayer)
- : layer(aLayer) {}
+ LayerPolygon(Layer *aLayer,
+ nsTArray<gfx::Point3D>&& aPoints, const gfx::Point3D& aNormal)
+ : layer(aLayer), geometry(Some(gfx::Polygon3D(Move(aPoints), aNormal))) {}
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(LayerPolygon&& layer)
{
- layers.push_back(std::move(layer));
+ layers.push_back(Move(layer));
}
const gfx::Polygon3D& First() const
{
MOZ_ASSERT(layers[0].geometry);
return *layers[0].geometry;
}
new file mode 100644
--- /dev/null
+++ b/gfx/tests/gtest/PolygonTestUtils.cpp
@@ -0,0 +1,171 @@
+/* -*- 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 "PolygonTestUtils.h"
+
+#include <cmath>
+
+namespace mozilla {
+namespace gfx {
+
+const float kEpsilon = 0.001f;
+
+// Compares two points while allowing some numerical inaccuracy.
+bool FuzzyEquals(const Point3D& lhs, const Point3D& rhs)
+{
+ const Point3D d = lhs - rhs;
+
+ return std::abs(d.x) < kEpsilon &&
+ std::abs(d.y) < kEpsilon &&
+ std::abs(d.z) < kEpsilon;
+}
+
+bool FuzzyEquals(const Point& lhs, const Point& rhs)
+{
+ const Point d = lhs - rhs;
+
+ return std::abs(d.x) < kEpsilon &&
+ std::abs(d.y) < kEpsilon;
+}
+
+bool operator==(const Triangle& lhs, const Triangle& rhs)
+{
+ return FuzzyEquals(lhs.p1, rhs.p1) &&
+ FuzzyEquals(lhs.p2, rhs.p2) &&
+ FuzzyEquals(lhs.p3, rhs.p3);
+}
+
+// Compares the points of two polygons and ensures
+// that the points are in the same winding order.
+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 (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 (!FuzzyEquals(left[i], right[j])) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+} // namespace gfx
+} // namespace mozilla
+
+
+TEST(PolygonTestUtils, 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);
+
+ const nsTArray<Triangle> t1 {
+ Triangle(Point(0.0f, 0.0f), Point(0.0f, 1.0f), Point(1.0f, 1.0f))
+ };
+
+ const nsTArray<Triangle> t2 {
+ Triangle(Point(0.0f, 0.0f), Point(1.0f, 1.0f), Point(1.0f, 0.0f))
+ };
+
+ const nsTArray<Triangle> t3 {
+ Triangle(
+ Point(0.00001f, 0.00001f),
+ Point(0.00001f, 1.00001f),
+ Point(1.00001f, 1.00001f)
+ )
+ };
+
+ EXPECT_TRUE(t1[0] == t1[0]);
+ EXPECT_TRUE(t2[0] == t2[0]);
+ EXPECT_TRUE(t3[0] == t1[0]);
+
+ EXPECT_FALSE(t1[0] == t2[0]);
+ EXPECT_FALSE(t2[0] == t3[0]);
+
+ AssertArrayEQ(t1, t1);
+ AssertArrayEQ(t2, t2);
+}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/gfx/tests/gtest/PolygonTestUtils.h
@@ -0,0 +1,39 @@
+/* -*- 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 GFX_TEST_POLYGONUTILS_H
+#define GFX_TEST_POLYGONUTILS_H
+
+#include "gtest/gtest.h"
+
+#include "nsTArray.h"
+#include "Point.h"
+#include "Polygon.h"
+#include "Triangle.h"
+
+namespace mozilla {
+namespace gfx {
+
+bool FuzzyEquals(const Point3D& lhs, const Point3D& rhs);
+bool FuzzyEquals(const Point& lhs, const Point& rhs);
+
+bool operator==(const Triangle& lhs, const Triangle& rhs);
+bool operator==(const Polygon3D& lhs, const Polygon3D& rhs);
+
+// Compares two arrays with the equality operator.
+template<typename T>
+void AssertArrayEQ(const nsTArray<T>& rhs, const nsTArray<T>& lhs)
+{
+ ASSERT_EQ(lhs.Length(), rhs.Length());
+
+ for (size_t i = 0; i < lhs.Length(); ++i) {
+ EXPECT_TRUE(lhs[i] == rhs[i]);
+ }
+}
+
+} // namespace gfx
+} // namespace mozilla
+
+#endif /* GFX_TEST_POLYGONUTILS_H */
--- a/gfx/tests/gtest/TestBSPTree.cpp
+++ b/gfx/tests/gtest/TestBSPTree.cpp
@@ -1,167 +1,46 @@
/* -*- 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 "gtest/gtest.h"
+
#include "BSPTree.h"
#include "Polygon.h"
-
-#include "gtest/gtest.h"
+#include "PolygonTestUtils.h"
#include <deque>
-using mozilla::layers::BSPTree;
-using mozilla::layers::LayerPolygon;
-using mozilla::gfx::Point3D;
-using mozilla::gfx::Polygon3D;
+using namespace mozilla::gfx;
+using namespace mozilla::layers;
namespace {
-// Compares two points while allowing some numerical inaccuracy.
-static bool FuzzyEquals(const Point3D& lhs, const Point3D& rhs)
-{
- const float epsilon = 0.001f;
- const Point3D d = lhs - rhs;
-
- // 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();
-
- // 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 (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 (!FuzzyEquals(left[i], right[j])) {
- return false;
- }
- }
-
- return true;
-}
-
static void RunTest(std::deque<Polygon3D> aPolygons,
std::deque<Polygon3D> aExpected)
{
std::deque<LayerPolygon> layers;
for (Polygon3D& polygon : aPolygons) {
- layers.push_back(LayerPolygon(std::move(polygon), nullptr));
+ layers.push_back(LayerPolygon(nullptr, Move(polygon)));
}
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(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),
Point3D(1.0f, 1.0f, 0.0f),
@@ -193,16 +72,94 @@ TEST(BSPTree, OneChild)
Point3D(1.0f, 1.0f, 1.0f),
Point3D(0.0f, 1.0f, 1.0f)
};
::RunTest({p1, p2}, {p1, p2});
::RunTest({p2, p1}, {p1, p2});
}
+TEST(BSPTree, SharedEdge1)
+{
+ Polygon3D p1 {
+ Point3D(1.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f)
+ };
+
+ Polygon3D p2 {
+ Point3D(1.0f, 0.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f),
+ Point3D(2.0f, 2.0f, 1.0f),
+ Point3D(2.0f, 0.0f, 1.0f)
+ };
+
+ ::RunTest({p1, p2}, {p1, p2});
+}
+
+TEST(BSPTree, SharedEdge2)
+{
+ Polygon3D p1 {
+ Point3D(1.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f)
+ };
+
+ Polygon3D p2 {
+ Point3D(1.0f, 0.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f),
+ Point3D(2.0f, 2.0f, 0.0f),
+ Point3D(2.0f, 0.0f, 0.0f)
+ };
+
+ ::RunTest({p1, p2}, {p2, p1});
+}
+
+TEST(BSPTree, SplitSharedEdge)
+{
+ Polygon3D p1 {
+ Point3D(1.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f)
+ };
+
+ Polygon3D p2 {
+ Point3D(1.0f, 0.0f, 2.0f),
+ Point3D(1.0f, 1.0f, 2.0f),
+ Point3D(1.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 0.0f, 0.0f)
+ };
+
+ const std::deque<Polygon3D> expected {
+ Polygon3D {
+ Point3D(1.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 0.0f, 0.0f),
+ Point3D(1.0f, 0.0f, 1.0f)
+ },
+ Polygon3D {
+ Point3D(1.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f)
+ },
+ Polygon3D {
+ Point3D(1.0f, 0.0f, 2.0f),
+ Point3D(1.0f, 1.0f, 2.0f),
+ Point3D(1.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 0.0f, 1.0f)
+ }
+ };
+
+ ::RunTest({p1, p2}, expected);
+}
+
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)
};
new file mode 100644
--- /dev/null
+++ b/gfx/tests/gtest/TestPolygon.cpp
@@ -0,0 +1,143 @@
+/* -*- 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 "gtest/gtest.h"
+
+#include "PolygonTestUtils.h"
+
+#include "nsTArray.h"
+#include "Point.h"
+#include "Polygon.h"
+#include "Triangle.h"
+
+using namespace mozilla::gfx;
+
+TEST(Polygon3D, TriangulateRectangle)
+{
+ const Polygon3D p {
+ Point3D(0.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 0.0f, 1.0f)
+ };
+
+ const nsTArray<Triangle> triangles = p.Triangulate();
+ const nsTArray<Triangle> expected = {
+ Triangle(Point(0.0f, 0.0f), Point(0.0f, 1.0f), Point(1.0f, 1.0f)),
+ Triangle(Point(0.0f, 0.0f), Point(1.0f, 1.0f), Point(1.0f, 0.0f))
+ };
+
+ AssertArrayEQ(triangles, expected);
+}
+
+TEST(Polygon3D, TriangulatePentagon)
+{
+ const Polygon3D p {
+ Point3D(0.0f, 0.0f, 1.0f),
+ Point3D(0.0f, 1.0f, 1.0f),
+ Point3D(0.5f, 1.5f, 1.0f),
+ Point3D(1.0f, 1.0f, 1.0f),
+ Point3D(1.0f, 0.0f, 1.0f)
+ };
+
+ const nsTArray<Triangle> triangles = p.Triangulate();
+ const nsTArray<Triangle> expected = {
+ Triangle(Point(0.0f, 0.0f), Point(0.0f, 1.0f), Point(0.5f, 1.5f)),
+ Triangle(Point(0.0f, 0.0f), Point(0.5f, 1.5f), Point(1.0f, 1.0f)),
+ Triangle(Point(0.0f, 0.0f), Point(1.0f, 1.0f), Point(1.0f, 0.0f))
+ };
+
+ AssertArrayEQ(triangles, expected);
+}
+
+TEST(Polygon3D, ClipRectangle)
+{
+ Polygon3D clipped, expected;
+
+ Polygon3D polygon {
+ Point3D(0.0f, 0.0f, 0.0f),
+ Point3D(0.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 0.0f, 0.0f)
+ };
+
+ clipped = polygon.ClipPolygon(Rect(0.0f, 0.0f, 1.0f, 1.0f));
+ EXPECT_TRUE(clipped == polygon);
+
+
+ clipped = polygon.ClipPolygon(Rect(0.0f, 0.0f, 0.8f, 0.8f));
+ expected = Polygon3D {
+ Point3D(0.0f, 0.0f, 0.0f),
+ Point3D(0.0f, 0.8f, 0.0f),
+ Point3D(0.8f, 0.8f, 0.0f),
+ Point3D(0.8f, 0.0f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+
+
+ clipped = polygon.ClipPolygon(Rect(0.2f, 0.2f, 0.8f, 0.8f));
+ expected = Polygon3D {
+ Point3D(0.2f, 0.2f, 0.0f),
+ Point3D(0.2f, 1.0f, 0.0f),
+ Point3D(1.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 0.2f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+
+
+ clipped = polygon.ClipPolygon(Rect(0.2f, 0.2f, 0.6f, 0.6f));
+ expected = Polygon3D {
+ Point3D(0.2f, 0.2f, 0.0f),
+ Point3D(0.2f, 0.8f, 0.0f),
+ Point3D(0.8f, 0.8f, 0.0f),
+ Point3D(0.8f, 0.2f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+}
+
+TEST(Polygon3D, ClipTriangle)
+{
+ Polygon3D clipped, expected;
+ const Polygon3D polygon {
+ Point3D(0.0f, 0.0f, 0.0f),
+ Point3D(0.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 1.0f, 0.0f)
+ };
+
+ clipped = polygon.ClipPolygon(Rect(0.0f, 0.0f, 1.0f, 1.0f));
+ expected = Polygon3D {
+ Point3D(0.0f, 0.0f, 0.0f),
+ Point3D(0.0f, 1.0f, 0.0f),
+ Point3D(1.0f, 1.0f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+
+
+ clipped = polygon.ClipPolygon(Rect(0.0f, 0.0f, 0.8f, 0.8f));
+ expected = Polygon3D {
+ Point3D(0.0f, 0.0f, 0.0f),
+ Point3D(0.0f, 0.8f, 0.0f),
+ Point3D(0.8f, 0.8f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+
+
+ clipped = polygon.ClipPolygon(Rect(0.2f, 0.2f, 0.8f, 0.8f));
+ expected = Polygon3D {
+ Point3D(0.2f, 0.2f, 0.0f),
+ Point3D(0.2f, 1.0f, 0.0f),
+ Point3D(1.0f, 1.0f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+
+
+ clipped = polygon.ClipPolygon(Rect(0.2f, 0.2f, 0.6f, 0.6f));
+ expected = Polygon3D {
+ Point3D(0.2f, 0.2f, 0.0f),
+ Point3D(0.2f, 0.8f, 0.0f),
+ Point3D(0.8f, 0.8f, 0.0f)
+ };
+ EXPECT_TRUE(clipped == expected);
+}
--- a/gfx/tests/gtest/moz.build
+++ b/gfx/tests/gtest/moz.build
@@ -1,27 +1,29 @@
# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
# vim: set filetype=python:
# 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',
+ 'PolygonTestUtils.cpp',
'TestArena.cpp',
'TestArrayView.cpp',
'TestBSPTree.cpp',
'TestBufferRotation.cpp',
'TestColorNames.cpp',
'TestCompositor.cpp',
'TestGfxPrefs.cpp',
'TestGfxWidgets.cpp',
'TestJobScheduler.cpp',
'TestLayers.cpp',
'TestMoz2D.cpp',
+ 'TestPolygon.cpp',
'TestQcms.cpp',
'TestRect.cpp',
'TestRegion.cpp',
'TestSkipChars.cpp',
# Hangs on linux in ApplyGdkScreenFontOptions
#'gfxFontSelectionTest.cpp',
'TestTextures.cpp',
'TestTreeTraversal.cpp',