1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef MOZILLA_GFX_POLYGON_H
8 #define MOZILLA_GFX_POLYGON_H
10 #include <initializer_list>
22 * Calculates the w = 0 intersection point for the edge defined by
23 * |aFirst| and |aSecond|.
25 template <class Units
>
26 Point4DTyped
<Units
> CalculateEdgeIntersect(const Point4DTyped
<Units
>& aFirst
,
27 const Point4DTyped
<Units
>& aSecond
) {
28 static const float w
= 0.00001f
;
29 const float t
= (w
- aFirst
.w
) / (aSecond
.w
- aFirst
.w
);
30 return aFirst
+ (aSecond
- aFirst
) * t
;
34 * Clips the polygon defined by |aPoints| so that there are no points with
37 template <class Units
>
38 nsTArray
<Point4DTyped
<Units
>> ClipPointsAtInfinity(
39 const nsTArray
<Point4DTyped
<Units
>>& aPoints
) {
40 nsTArray
<Point4DTyped
<Units
>> outPoints(aPoints
.Length());
42 const size_t pointCount
= aPoints
.Length();
43 for (size_t i
= 0; i
< pointCount
; ++i
) {
44 const Point4DTyped
<Units
>& first
= aPoints
[i
];
45 const Point4DTyped
<Units
>& second
= aPoints
[(i
+ 1) % pointCount
];
47 if (!first
.w
|| !second
.w
) {
48 // Skip edges at infinity.
53 outPoints
.AppendElement(first
);
56 if ((first
.w
<= 0.0f
) ^ (second
.w
<= 0.0f
)) {
57 outPoints
.AppendElement(CalculateEdgeIntersect(first
, second
));
65 * Calculates the distances between the points in |aPoints| and the plane
66 * defined by |aPlaneNormal| and |aPlanePoint|.
68 template <class Units
>
69 nsTArray
<float> CalculatePointPlaneDistances(
70 const nsTArray
<Point4DTyped
<Units
>>& aPoints
,
71 const Point4DTyped
<Units
>& aPlaneNormal
,
72 const Point4DTyped
<Units
>& aPlanePoint
, size_t& aPos
, size_t& aNeg
) {
73 // Point classification might produce incorrect results due to numerical
74 // inaccuracies. Using an epsilon value makes the splitting plane "thicker".
75 const float epsilon
= 0.05f
;
78 nsTArray
<float> distances(aPoints
.Length());
80 for (const Point4DTyped
<Units
>& point
: aPoints
) {
81 float dot
= (point
- aPlanePoint
).DotProduct(aPlaneNormal
);
85 } else if (dot
< -epsilon
) {
88 // The point is within the thick plane.
92 distances
.AppendElement(dot
);
99 * Clips the polygon defined by |aPoints|. The clipping uses previously
100 * calculated plane to point distances and the plane normal |aNormal|.
101 * The result of clipping is stored in |aBackPoints| and |aFrontPoints|.
103 template <class Units
>
104 void ClipPointsWithPlane(const nsTArray
<Point4DTyped
<Units
>>& aPoints
,
105 const Point4DTyped
<Units
>& aNormal
,
106 const nsTArray
<float>& aDots
,
107 nsTArray
<Point4DTyped
<Units
>>& aBackPoints
,
108 nsTArray
<Point4DTyped
<Units
>>& aFrontPoints
) {
109 static const auto Sign
= [](const float& f
) {
110 if (f
> 0.0f
) return 1;
111 if (f
< 0.0f
) return -1;
115 const size_t pointCount
= aPoints
.Length();
116 for (size_t i
= 0; i
< pointCount
; ++i
) {
117 size_t j
= (i
+ 1) % pointCount
;
119 const Point4DTyped
<Units
>& a
= aPoints
[i
];
120 const Point4DTyped
<Units
>& b
= aPoints
[j
];
121 const float dotA
= aDots
[i
];
122 const float dotB
= aDots
[j
];
124 // The point is in front of or on the plane.
126 aFrontPoints
.AppendElement(a
);
129 // The point is behind or on the plane.
131 aBackPoints
.AppendElement(a
);
134 // If the sign of the dot products changes between two consecutive
135 // vertices, then the plane intersects with the polygon edge.
136 // The case where the polygon edge is within the plane is handled above.
137 if (Sign(dotA
) && Sign(dotB
) && Sign(dotA
) != Sign(dotB
)) {
138 // Calculate the line segment and plane intersection point.
139 const Point4DTyped
<Units
> ab
= b
- a
;
140 const float dotAB
= ab
.DotProduct(aNormal
);
141 const float t
= -dotA
/ dotAB
;
142 const Point4DTyped
<Units
> p
= a
+ (ab
* t
);
144 // Add the intersection point to both polygons.
145 aBackPoints
.AppendElement(p
);
146 aFrontPoints
.AppendElement(p
);
152 * PolygonTyped stores the points of a convex planar polygon.
154 template <class Units
>
156 typedef Point3DTyped
<Units
> Point3DType
;
157 typedef Point4DTyped
<Units
> Point4DType
;
160 PolygonTyped() = default;
162 explicit PolygonTyped(const nsTArray
<Point4DType
>& aPoints
,
163 const Point4DType
& aNormal
= DefaultNormal())
164 : mNormal(aNormal
), mPoints(aPoints
) {}
166 explicit PolygonTyped(nsTArray
<Point4DType
>&& aPoints
,
167 const Point4DType
& aNormal
= DefaultNormal())
168 : mNormal(aNormal
), mPoints(std::move(aPoints
)) {}
170 explicit PolygonTyped(const std::initializer_list
<Point4DType
>& aPoints
,
171 const Point4DType
& aNormal
= DefaultNormal())
172 : mNormal(aNormal
), mPoints(aPoints
) {
174 EnsurePlanarPolygon();
179 * Returns the smallest 2D rectangle that can fully cover the polygon.
181 RectTyped
<Units
> BoundingBox() const {
182 if (mPoints
.IsEmpty()) {
183 return RectTyped
<Units
>();
186 float minX
, maxX
, minY
, maxY
;
187 minX
= maxX
= mPoints
[0].x
;
188 minY
= maxY
= mPoints
[0].y
;
190 for (const Point4DType
& point
: mPoints
) {
191 minX
= std::min(point
.x
, minX
);
192 maxX
= std::max(point
.x
, maxX
);
194 minY
= std::min(point
.y
, minY
);
195 maxY
= std::max(point
.y
, maxY
);
198 return RectTyped
<Units
>(minX
, minY
, maxX
- minX
, maxY
- minY
);
202 * Clips the polygon against the given 2D rectangle.
204 PolygonTyped
<Units
> ClipPolygon(const RectTyped
<Units
>& aRect
) const {
205 if (aRect
.IsEmpty()) {
206 return PolygonTyped
<Units
>();
209 return ClipPolygon(FromRect(aRect
));
213 * Clips this polygon against |aPolygon| in 2D and returns a new polygon.
215 PolygonTyped
<Units
> ClipPolygon(const PolygonTyped
<Units
>& aPolygon
) const {
216 const nsTArray
<Point4DType
>& points
= aPolygon
.GetPoints();
218 if (mPoints
.IsEmpty() || points
.IsEmpty()) {
219 return PolygonTyped
<Units
>();
222 nsTArray
<Point4DType
> clippedPoints(mPoints
.Clone());
225 nsTArray
<Point4DType
> backPoints(4), frontPoints(4);
227 // Iterate over all the edges of the clipping polygon |aPolygon| and clip
228 // this polygon against the edges.
229 const size_t pointCount
= points
.Length();
230 for (size_t i
= 0; i
< pointCount
; ++i
) {
231 const Point4DType p1
= points
[(i
+ 1) % pointCount
];
232 const Point4DType p2
= points
[i
];
234 // Calculate the normal for the edge defined by |p1| and |p2|.
235 const Point4DType
normal(p2
.y
- p1
.y
, p1
.x
- p2
.x
, 0.0f
, 0.0f
);
237 // Calculate the distances between the points of the polygon and the
238 // plane defined by |aPolygon|.
239 const nsTArray
<float> distances
=
240 CalculatePointPlaneDistances(clippedPoints
, normal
, p1
, pos
, neg
);
242 backPoints
.ClearAndRetainStorage();
243 frontPoints
.ClearAndRetainStorage();
245 // Clip the polygon points using the previously calculated distances.
246 ClipPointsWithPlane(clippedPoints
, normal
, distances
, backPoints
,
249 // Only use the points behind the clipping plane.
250 clippedPoints
= std::move(backPoints
);
252 if (clippedPoints
.Length() < 3) {
253 // The clipping created a polygon with no area.
254 return PolygonTyped
<Units
>();
258 return PolygonTyped
<Units
>(std::move(clippedPoints
), mNormal
);
262 * Returns a new polygon containing the bounds of the given 2D rectangle.
264 static PolygonTyped
<Units
> FromRect(const RectTyped
<Units
>& aRect
) {
265 nsTArray
<Point4DType
> points
{
266 Point4DType(aRect
.X(), aRect
.Y(), 0.0f
, 1.0f
),
267 Point4DType(aRect
.X(), aRect
.YMost(), 0.0f
, 1.0f
),
268 Point4DType(aRect
.XMost(), aRect
.YMost(), 0.0f
, 1.0f
),
269 Point4DType(aRect
.XMost(), aRect
.Y(), 0.0f
, 1.0f
)};
271 return PolygonTyped
<Units
>(std::move(points
));
274 const Point4DType
& GetNormal() const { return mNormal
; }
276 const nsTArray
<Point4DType
>& GetPoints() const { return mPoints
; }
278 bool IsEmpty() const {
279 // If the polygon has less than three points, it has no visible area.
280 return mPoints
.Length() < 3;
284 * Returns a list of triangles covering the polygon.
286 nsTArray
<TriangleTyped
<Units
>> ToTriangles() const {
287 nsTArray
<TriangleTyped
<Units
>> triangles
;
293 // This fan triangulation method only works for convex polygons.
294 for (size_t i
= 1; i
< mPoints
.Length() - 1; ++i
) {
295 TriangleTyped
<Units
> triangle(Point(mPoints
[0].x
, mPoints
[0].y
),
296 Point(mPoints
[i
].x
, mPoints
[i
].y
),
297 Point(mPoints
[i
+ 1].x
, mPoints
[i
+ 1].y
));
298 triangles
.AppendElement(std::move(triangle
));
304 void TransformToLayerSpace(const Matrix4x4Typed
<Units
, Units
>& aTransform
) {
305 TransformPoints(aTransform
, true);
306 mNormal
= DefaultNormal();
309 void TransformToScreenSpace(
310 const Matrix4x4Typed
<Units
, Units
>& aTransform
,
311 const Matrix4x4Typed
<Units
, Units
>& aInverseTransform
) {
312 TransformPoints(aTransform
, false);
314 // Perspective projection transformation might produce points with w <= 0,
315 // so we need to clip these points.
316 mPoints
= ClipPointsAtInfinity(mPoints
);
318 // Normal vectors should be transformed using inverse transpose.
319 mNormal
= aInverseTransform
.TransposeTransform4D(mNormal
);
322 void TransformToScreenSpace(const Matrix4x4Typed
<Units
, Units
>& aTransform
) {
323 MOZ_ASSERT(!aTransform
.IsSingular());
325 TransformToScreenSpace(aTransform
, aTransform
.Inverse());
329 static Point4DType
DefaultNormal() {
330 return Point4DType(0.0f
, 0.0f
, 1.0f
, 0.0f
);
334 void EnsurePlanarPolygon() const {
335 if (mPoints
.Length() <= 3) {
336 // Polygons with three or less points are guaranteed to be planar.
340 // This normal calculation method works only for planar polygons.
341 // The resulting normal vector will point towards the viewer when the
342 // polygon has a counter-clockwise winding order from the perspective
345 const Point3DType p0
= mPoints
[0].As3DPoint();
347 for (size_t i
= 1; i
< mPoints
.Length() - 1; ++i
) {
348 const Point3DType p1
= mPoints
[i
].As3DPoint();
349 const Point3DType p2
= mPoints
[i
+ 1].As3DPoint();
351 normal
+= (p1
- p0
).CrossProduct(p2
- p0
);
354 // Ensure that at least one component is greater than zero.
355 // This avoids division by zero when normalizing the vector.
356 bool hasNonZeroComponent
= std::abs(normal
.x
) > 0.0f
||
357 std::abs(normal
.y
) > 0.0f
||
358 std::abs(normal
.z
) > 0.0f
;
360 MOZ_ASSERT(hasNonZeroComponent
);
364 // Ensure that the polygon is planar.
365 // http://mathworld.wolfram.com/Point-PlaneDistance.html
366 const float epsilon
= 0.01f
;
367 for (const Point4DType
& point
: mPoints
) {
368 const Point3DType p1
= point
.As3DPoint();
369 const float d
= normal
.DotProduct(p1
- p0
);
371 MOZ_ASSERT(std::abs(d
) < epsilon
);
376 void TransformPoints(const Matrix4x4Typed
<Units
, Units
>& aTransform
,
377 const bool aDivideByW
) {
378 for (Point4DType
& point
: mPoints
) {
379 point
= aTransform
.TransformPoint(point
);
381 if (aDivideByW
&& point
.w
> 0.0f
) {
382 point
= point
/ point
.w
;
388 CopyableTArray
<Point4DType
> mPoints
;
391 typedef PolygonTyped
<UnknownUnits
> Polygon
;
394 } // namespace mozilla
396 #endif /* MOZILLA_GFX_POLYGON_H */