summaryrefslogtreecommitdiffstats
path: root/gfx/2d/Polygon.h
diff options
context:
space:
mode:
Diffstat (limited to 'gfx/2d/Polygon.h')
-rw-r--r--gfx/2d/Polygon.h295
1 files changed, 295 insertions, 0 deletions
diff --git a/gfx/2d/Polygon.h b/gfx/2d/Polygon.h
new file mode 100644
index 000000000..e1738684c
--- /dev/null
+++ b/gfx/2d/Polygon.h
@@ -0,0 +1,295 @@
+/* -*- 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/Move.h"
+#include "nsTArray.h"
+#include "Point.h"
+#include "Triangle.h"
+
+#include <initializer_list>
+
+namespace mozilla {
+namespace gfx {
+
+// Polygon3DTyped stores the points of a convex planar polygon.
+template<class Units>
+class Polygon3DTyped {
+public:
+ 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 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
+ }
+
+ 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
+ {
+ // 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
+ {
+ return mPoints;
+ }
+
+ const Point3DTyped<Units>& operator[](size_t aIndex) const
+ {
+ MOZ_ASSERT(mPoints.Length() > aIndex);
+ return mPoints[aIndex];
+ }
+
+ void SplitPolygon(const Polygon3DTyped<Units>& aSplittingPlane,
+ const nsTArray<float>& aDots,
+ nsTArray<Point3DTyped<Units>>& aBackPoints,
+ nsTArray<Point3DTyped<Units>>& aFrontPoints) const
+ {
+ 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);
+ }
+ }
+ }
+
+ nsTArray<TriangleTyped<Units>> ToTriangles() 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;
+ }
+
+ 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);
+ }
+
+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
+ {
+ 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.
+ 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.
+ // 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);
+
+ normal.Normalize();
+
+ // Ensure that the polygon is planar.
+ // 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 Polygon3DTyped<UnknownUnits> Polygon3D;
+
+} // namespace gfx
+} // namespace mozilla
+
+#endif /* MOZILLA_GFX_POLYGON_H */