diff options
Diffstat (limited to 'gfx/2d/Polygon.h')
| -rw-r--r-- | gfx/2d/Polygon.h | 396 |
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 */ |