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