tor-browser

Polygon.h (12320B)

---

/* -*- 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 */