Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 396 insertions, 0 deletions

diff --git a/gfx/2d/Polygon.h b/gfx/2d/Polygon.h
new file mode 100644
index 0000000000..3de3d684f9
--- /dev/null
+++ b/gfx/2d/Polygon.h
@@ -0,0 +1,396 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* 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 <initializer_list>
+#include <utility>
+
+#include "Matrix.h"
+#include "Point.h"
+#include "Triangle.h"
+#include "nsTArray.h"
+
+namespace mozilla {
+namespace gfx {
+
+/**
+ * Calculates the w = 0 intersection point for the edge defined by
+ * |aFirst| and |aSecond|.
+ */
+template <class Units>
+Point4DTyped<Units> CalculateEdgeIntersect(const Point4DTyped<Units>& aFirst,
+                                           const Point4DTyped<Units>& aSecond) {
+  static const float w = 0.00001f;
+  const float t = (w - aFirst.w) / (aSecond.w - aFirst.w);
+  return aFirst + (aSecond - aFirst) * t;
+}
+
+/**
+ * Clips the polygon defined by |aPoints| so that there are no points with
+ * w <= 0.
+ */
+template <class Units>
+nsTArray<Point4DTyped<Units>> ClipPointsAtInfinity(
+    const nsTArray<Point4DTyped<Units>>& aPoints) {
+  nsTArray<Point4DTyped<Units>> outPoints(aPoints.Length());
+
+  const size_t pointCount = aPoints.Length();
+  for (size_t i = 0; i < pointCount; ++i) {
+    const Point4DTyped<Units>& first = aPoints[i];
+    const Point4DTyped<Units>& second = aPoints[(i + 1) % pointCount];
+
+    if (!first.w || !second.w) {
+      // Skip edges at infinity.
+      continue;
+    }
+
+    if (first.w > 0.0f) {
+      outPoints.AppendElement(first);
+    }
+
+    if ((first.w <= 0.0f) ^ (second.w <= 0.0f)) {
+      outPoints.AppendElement(CalculateEdgeIntersect(first, second));
+    }
+  }
+
+  return outPoints;
+}
+
+/**
+ * Calculates the distances between the points in |aPoints| and the plane
+ * defined by |aPlaneNormal| and |aPlanePoint|.
+ */
+template <class Units>
+nsTArray<float> CalculatePointPlaneDistances(
+    const nsTArray<Point4DTyped<Units>>& aPoints,
+    const Point4DTyped<Units>& aPlaneNormal,
+    const Point4DTyped<Units>& aPlanePoint, 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;
+
+  aPos = aNeg = 0;
+  nsTArray<float> distances(aPoints.Length());
+
+  for (const Point4DTyped<Units>& point : aPoints) {
+    float dot = (point - aPlanePoint).DotProduct(aPlaneNormal);
+
+    if (dot > epsilon) {
+      aPos++;
+    } else if (dot < -epsilon) {
+      aNeg++;
+    } else {
+      // The point is within the thick plane.
+      dot = 0.0f;
+    }
+
+    distances.AppendElement(dot);
+  }
+
+  return distances;
+}
+
+/**
+ * Clips the polygon defined by |aPoints|. The clipping uses previously
+ * calculated plane to point distances and the plane normal |aNormal|.
+ * The result of clipping is stored in |aBackPoints| and |aFrontPoints|.
+ */
+template <class Units>
+void ClipPointsWithPlane(const nsTArray<Point4DTyped<Units>>& aPoints,
+                         const Point4DTyped<Units>& aNormal,
+                         const nsTArray<float>& aDots,
+                         nsTArray<Point4DTyped<Units>>& aBackPoints,
+                         nsTArray<Point4DTyped<Units>>& aFrontPoints) {
+  static const auto Sign = [](const float& f) {
+    if (f > 0.0f) return 1;
+    if (f < 0.0f) return -1;
+    return 0;
+  };
+
+  const size_t pointCount = aPoints.Length();
+  for (size_t i = 0; i < pointCount; ++i) {
+    size_t j = (i + 1) % pointCount;
+
+    const Point4DTyped<Units>& a = aPoints[i];
+    const Point4DTyped<Units>& b = aPoints[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 Point4DTyped<Units> ab = b - a;
+      const float dotAB = ab.DotProduct(aNormal);
+      const float t = -dotA / dotAB;
+      const Point4DTyped<Units> p = a + (ab * t);
+
+      // Add the intersection point to both polygons.
+      aBackPoints.AppendElement(p);
+      aFrontPoints.AppendElement(p);
+    }
+  }
+}
+
+/**
+ * PolygonTyped stores the points of a convex planar polygon.
+ */
+template <class Units>
+class PolygonTyped {
+  typedef Point3DTyped<Units> Point3DType;
+  typedef Point4DTyped<Units> Point4DType;
+
+ public:
+  PolygonTyped() = default;
+
+  explicit PolygonTyped(const nsTArray<Point4DType>& aPoints,
+                        const Point4DType& aNormal = DefaultNormal())
+      : mNormal(aNormal), mPoints(aPoints) {}
+
+  explicit PolygonTyped(nsTArray<Point4DType>&& aPoints,
+                        const Point4DType& aNormal = DefaultNormal())
+      : mNormal(aNormal), mPoints(std::move(aPoints)) {}
+
+  explicit PolygonTyped(const std::initializer_list<Point4DType>& aPoints,
+                        const Point4DType& aNormal = DefaultNormal())
+      : mNormal(aNormal), mPoints(aPoints) {
+#ifdef DEBUG
+    EnsurePlanarPolygon();
+#endif
+  }
+
+  /**
+   * Returns the smallest 2D rectangle that can fully cover the polygon.
+   */
+  RectTyped<Units> BoundingBox() const {
+    if (mPoints.IsEmpty()) {
+      return RectTyped<Units>();
+    }
+
+    float minX, maxX, minY, maxY;
+    minX = maxX = mPoints[0].x;
+    minY = maxY = mPoints[0].y;
+
+    for (const Point4DType& 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);
+  }
+
+  /**
+   * Clips the polygon against the given 2D rectangle.
+   */
+  PolygonTyped<Units> ClipPolygon(const RectTyped<Units>& aRect) const {
+    if (aRect.IsEmpty()) {
+      return PolygonTyped<Units>();
+    }
+
+    return ClipPolygon(FromRect(aRect));
+  }
+
+  /**
+   * Clips this polygon against |aPolygon| in 2D and returns a new polygon.
+   */
+  PolygonTyped<Units> ClipPolygon(const PolygonTyped<Units>& aPolygon) const {
+    const nsTArray<Point4DType>& points = aPolygon.GetPoints();
+
+    if (mPoints.IsEmpty() || points.IsEmpty()) {
+      return PolygonTyped<Units>();
+    }
+
+    nsTArray<Point4DType> clippedPoints(mPoints.Clone());
+
+    size_t pos, neg;
+    nsTArray<Point4DType> backPoints(4), frontPoints(4);
+
+    // Iterate over all the edges of the clipping polygon |aPolygon| and clip
+    // this polygon against the edges.
+    const size_t pointCount = points.Length();
+    for (size_t i = 0; i < pointCount; ++i) {
+      const Point4DType p1 = points[(i + 1) % pointCount];
+      const Point4DType p2 = points[i];
+
+      // Calculate the normal for the edge defined by |p1| and |p2|.
+      const Point4DType normal(p2.y - p1.y, p1.x - p2.x, 0.0f, 0.0f);
+
+      // Calculate the distances between the points of the polygon and the
+      // plane defined by |aPolygon|.
+      const nsTArray<float> distances =
+          CalculatePointPlaneDistances(clippedPoints, normal, p1, pos, neg);
+
+      backPoints.ClearAndRetainStorage();
+      frontPoints.ClearAndRetainStorage();
+
+      // Clip the polygon points using the previously calculated distances.
+      ClipPointsWithPlane(clippedPoints, normal, distances, backPoints,
+                          frontPoints);
+
+      // Only use the points behind the clipping plane.
+      clippedPoints = std::move(backPoints);
+
+      if (clippedPoints.Length() < 3) {
+        // The clipping created a polygon with no area.
+        return PolygonTyped<Units>();
+      }
+    }
+
+    return PolygonTyped<Units>(std::move(clippedPoints), mNormal);
+  }
+
+  /**
+   * Returns a new polygon containing the bounds of the given 2D rectangle.
+   */
+  static PolygonTyped<Units> FromRect(const RectTyped<Units>& aRect) {
+    nsTArray<Point4DType> points{
+        Point4DType(aRect.X(), aRect.Y(), 0.0f, 1.0f),
+        Point4DType(aRect.X(), aRect.YMost(), 0.0f, 1.0f),
+        Point4DType(aRect.XMost(), aRect.YMost(), 0.0f, 1.0f),
+        Point4DType(aRect.XMost(), aRect.Y(), 0.0f, 1.0f)};
+
+    return PolygonTyped<Units>(std::move(points));
+  }
+
+  const Point4DType& GetNormal() const { return mNormal; }
+
+  const nsTArray<Point4DType>& GetPoints() const { return mPoints; }
+
+  bool IsEmpty() const {
+    // If the polygon has less than three points, it has no visible area.
+    return mPoints.Length() < 3;
+  }
+
+  /**
+   * Returns a list of triangles covering the polygon.
+   */
+  nsTArray<TriangleTyped<Units>> ToTriangles() const {
+    nsTArray<TriangleTyped<Units>> triangles;
+
+    if (IsEmpty()) {
+      return triangles;
+    }
+
+    // This fan triangulation method only works for convex polygons.
+    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(std::move(triangle));
+    }
+
+    return triangles;
+  }
+
+  void TransformToLayerSpace(const Matrix4x4Typed<Units, Units>& aTransform) {
+    TransformPoints(aTransform, true);
+    mNormal = DefaultNormal();
+  }
+
+  void TransformToScreenSpace(
+      const Matrix4x4Typed<Units, Units>& aTransform,
+      const Matrix4x4Typed<Units, Units>& aInverseTransform) {
+    TransformPoints(aTransform, false);
+
+    // Perspective projection transformation might produce points with w <= 0,
+    // so we need to clip these points.
+    mPoints = ClipPointsAtInfinity(mPoints);
+
+    // Normal vectors should be transformed using inverse transpose.
+    mNormal = aInverseTransform.TransposeTransform4D(mNormal);
+  }
+
+  void TransformToScreenSpace(const Matrix4x4Typed<Units, Units>& aTransform) {
+    MOZ_ASSERT(!aTransform.IsSingular());
+
+    TransformToScreenSpace(aTransform, aTransform.Inverse());
+  }
+
+ private:
+  static Point4DType DefaultNormal() {
+    return Point4DType(0.0f, 0.0f, 1.0f, 0.0f);
+  }
+
+#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.
+    Point3DType normal;
+    const Point3DType p0 = mPoints[0].As3DPoint();
+
+    for (size_t i = 1; i < mPoints.Length() - 1; ++i) {
+      const Point3DType p1 = mPoints[i].As3DPoint();
+      const Point3DType p2 = mPoints[i + 1].As3DPoint();
+
+      normal += (p1 - p0).CrossProduct(p2 - p0);
+    }
+
+    // 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 Point4DType& point : mPoints) {
+      const Point3DType p1 = point.As3DPoint();
+      const float d = normal.DotProduct(p1 - p0);
+
+      MOZ_ASSERT(std::abs(d) < epsilon);
+    }
+  }
+#endif
+
+  void TransformPoints(const Matrix4x4Typed<Units, Units>& aTransform,
+                       const bool aDivideByW) {
+    for (Point4DType& point : mPoints) {
+      point = aTransform.TransformPoint(point);
+
+      if (aDivideByW && point.w > 0.0f) {
+        point = point / point.w;
+      }
+    }
+  }
+
+  Point4DType mNormal;
+  CopyableTArray<Point4DType> mPoints;
+};
+
+typedef PolygonTyped<UnknownUnits> Polygon;
+
+}  // namespace gfx
+}  // namespace mozilla
+
+#endif /* MOZILLA_GFX_POLYGON_H */