Line data Source code
1 : /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 : * This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #ifndef MOZILLA_GFX_POLYGON_H
7 : #define MOZILLA_GFX_POLYGON_H
8 :
9 : #include "Matrix.h"
10 : #include "mozilla/Move.h"
11 : #include "nsTArray.h"
12 : #include "Point.h"
13 : #include "Triangle.h"
14 :
15 : #include <initializer_list>
16 :
17 : namespace mozilla {
18 : namespace gfx {
19 :
20 : /**
21 : * Calculates the w = 0 intersection point for the edge defined by
22 : * |aFirst| and |aSecond|.
23 : */
24 : template<class Units>
25 : Point4DTyped<Units>
26 0 : CalculateEdgeIntersect(const Point4DTyped<Units>& aFirst,
27 : const Point4DTyped<Units>& aSecond)
28 : {
29 : static const float w = 0.00001f;
30 0 : const float t = (w - aFirst.w) / (aSecond.w - aFirst.w);
31 0 : return aFirst + (aSecond - aFirst) * t;
32 : }
33 :
34 : /**
35 : * Clips the polygon defined by |aPoints| so that there are no points with
36 : * w <= 0.
37 : */
38 : template<class Units>
39 : nsTArray<Point4DTyped<Units>>
40 0 : ClipPointsAtInfinity(const nsTArray<Point4DTyped<Units>>& aPoints)
41 : {
42 0 : nsTArray<Point4DTyped<Units>> outPoints(aPoints.Length());
43 :
44 0 : const size_t pointCount = aPoints.Length();
45 0 : for (size_t i = 0; i < pointCount; ++i) {
46 0 : const Point4DTyped<Units>& first = aPoints[i];
47 0 : const Point4DTyped<Units>& second = aPoints[(i + 1) % pointCount];
48 :
49 0 : if (!first.w || !second.w) {
50 : // Skip edges at infinity.
51 0 : continue;
52 : }
53 :
54 0 : if (first.w > 0.0f) {
55 0 : outPoints.AppendElement(first);
56 : }
57 :
58 0 : if ((first.w <= 0.0f) ^ (second.w <= 0.0f)) {
59 0 : outPoints.AppendElement(CalculateEdgeIntersect(first, second));
60 : }
61 : }
62 :
63 0 : return outPoints;
64 : }
65 :
66 : /**
67 : * Calculates the distances between the points in |aPoints| and the plane
68 : * defined by |aPlaneNormal| and |aPlanePoint|.
69 : */
70 : template<class Units>
71 : nsTArray<float>
72 0 : CalculatePointPlaneDistances(const nsTArray<Point4DTyped<Units>>& aPoints,
73 : const Point4DTyped<Units>& aPlaneNormal,
74 : const Point4DTyped<Units>& aPlanePoint,
75 : size_t& aPos, size_t& aNeg)
76 : {
77 : // Point classification might produce incorrect results due to numerical
78 : // inaccuracies. Using an epsilon value makes the splitting plane "thicker".
79 0 : const float epsilon = 0.05f;
80 :
81 0 : aPos = aNeg = 0;
82 0 : nsTArray<float> distances(aPoints.Length());
83 :
84 0 : for (const Point4DTyped<Units>& point : aPoints) {
85 0 : float dot = (point - aPlanePoint).DotProduct(aPlaneNormal);
86 :
87 0 : if (dot > epsilon) {
88 0 : aPos++;
89 0 : } else if (dot < -epsilon) {
90 0 : aNeg++;
91 : } else {
92 : // The point is within the thick plane.
93 0 : dot = 0.0f;
94 : }
95 :
96 0 : distances.AppendElement(dot);
97 : }
98 :
99 0 : return distances;
100 : }
101 :
102 : /**
103 : * Clips the polygon defined by |aPoints|. The clipping uses previously
104 : * calculated plane to point distances and the plane normal |aNormal|.
105 : * The result of clipping is stored in |aBackPoints| and |aFrontPoints|.
106 : */
107 : template<class Units>
108 : void
109 0 : ClipPointsWithPlane(const nsTArray<Point4DTyped<Units>>& aPoints,
110 : const Point4DTyped<Units>& aNormal,
111 : const nsTArray<float>& aDots,
112 : nsTArray<Point4DTyped<Units>>& aBackPoints,
113 : nsTArray<Point4DTyped<Units>>& aFrontPoints)
114 : {
115 0 : static const auto Sign = [](const float& f) {
116 0 : if (f > 0.0f) return 1;
117 0 : if (f < 0.0f) return -1;
118 0 : return 0;
119 : };
120 :
121 0 : const size_t pointCount = aPoints.Length();
122 0 : for (size_t i = 0; i < pointCount; ++i) {
123 0 : size_t j = (i + 1) % pointCount;
124 :
125 0 : const Point4DTyped<Units>& a = aPoints[i];
126 0 : const Point4DTyped<Units>& b = aPoints[j];
127 0 : const float dotA = aDots[i];
128 0 : const float dotB = aDots[j];
129 :
130 : // The point is in front of or on the plane.
131 0 : if (dotA >= 0) {
132 0 : aFrontPoints.AppendElement(a);
133 : }
134 :
135 : // The point is behind or on the plane.
136 0 : if (dotA <= 0) {
137 0 : aBackPoints.AppendElement(a);
138 : }
139 :
140 : // If the sign of the dot products changes between two consecutive
141 : // vertices, then the plane intersects with the polygon edge.
142 : // The case where the polygon edge is within the plane is handled above.
143 0 : if (Sign(dotA) && Sign(dotB) && Sign(dotA) != Sign(dotB)) {
144 : // Calculate the line segment and plane intersection point.
145 0 : const Point4DTyped<Units> ab = b - a;
146 0 : const float dotAB = ab.DotProduct(aNormal);
147 0 : const float t = -dotA / dotAB;
148 0 : const Point4DTyped<Units> p = a + (ab * t);
149 :
150 : // Add the intersection point to both polygons.
151 0 : aBackPoints.AppendElement(p);
152 0 : aFrontPoints.AppendElement(p);
153 : }
154 : }
155 0 : }
156 :
157 : /**
158 : * PolygonTyped stores the points of a convex planar polygon.
159 : */
160 : template<class Units>
161 0 : class PolygonTyped {
162 : typedef Point3DTyped<Units> Point3DType;
163 : typedef Point4DTyped<Units> Point4DType;
164 :
165 : public:
166 0 : PolygonTyped() {}
167 :
168 : explicit PolygonTyped(const nsTArray<Point4DType>& aPoints,
169 : const Point4DType& aNormal = DefaultNormal())
170 : : mNormal(aNormal), mPoints(aPoints) {}
171 :
172 0 : explicit PolygonTyped(nsTArray<Point4DType>&& aPoints,
173 0 : const Point4DType& aNormal = DefaultNormal())
174 0 : : mNormal(aNormal), mPoints(Move(aPoints)) {}
175 :
176 : explicit PolygonTyped(const std::initializer_list<Point4DType>& aPoints,
177 : const Point4DType& aNormal = DefaultNormal())
178 : : mNormal(aNormal), mPoints(aPoints)
179 : {
180 : #ifdef DEBUG
181 : EnsurePlanarPolygon();
182 : #endif
183 : }
184 :
185 : /**
186 : * Returns the smallest 2D rectangle that can fully cover the polygon.
187 : */
188 0 : RectTyped<Units> BoundingBox() const
189 : {
190 0 : if (mPoints.IsEmpty()) {
191 0 : return RectTyped<Units>();
192 : }
193 :
194 : float minX, maxX, minY, maxY;
195 0 : minX = maxX = mPoints[0].x;
196 0 : minY = maxY = mPoints[0].y;
197 :
198 0 : for (const Point4DType& point : mPoints) {
199 0 : minX = std::min(point.x, minX);
200 0 : maxX = std::max(point.x, maxX);
201 :
202 0 : minY = std::min(point.y, minY);
203 0 : maxY = std::max(point.y, maxY);
204 : }
205 :
206 0 : return RectTyped<Units>(minX, minY, maxX - minX, maxY - minY);
207 : }
208 :
209 : /**
210 : * Clips the polygon against the given 2D rectangle.
211 : */
212 0 : PolygonTyped<Units> ClipPolygon(const RectTyped<Units>& aRect) const
213 : {
214 0 : if (aRect.IsEmpty()) {
215 0 : return PolygonTyped<Units>();
216 : }
217 :
218 0 : return ClipPolygon(FromRect(aRect));
219 : }
220 :
221 : /**
222 : * Clips this polygon against |aPolygon| in 2D and returns a new polygon.
223 : */
224 0 : PolygonTyped<Units> ClipPolygon(const PolygonTyped<Units>& aPolygon) const
225 : {
226 0 : const nsTArray<Point4DType>& points = aPolygon.GetPoints();
227 :
228 0 : if (mPoints.IsEmpty() || points.IsEmpty()) {
229 0 : return PolygonTyped<Units>();
230 : }
231 :
232 0 : nsTArray<Point4DType> clippedPoints(mPoints);
233 :
234 : size_t pos, neg;
235 0 : nsTArray<Point4DType> backPoints(4), frontPoints(4);
236 :
237 : // Iterate over all the edges of the clipping polygon |aPolygon| and clip
238 : // this polygon against the edges.
239 0 : const size_t pointCount = points.Length();
240 0 : for (size_t i = 0; i < pointCount; ++i) {
241 0 : const Point4DType p1 = points[(i + 1) % pointCount];
242 0 : const Point4DType p2 = points[i];
243 :
244 : // Calculate the normal for the edge defined by |p1| and |p2|.
245 0 : const Point4DType normal(p2.y - p1.y, p1.x - p2.x, 0.0f, 0.0f);
246 :
247 : // Calculate the distances between the points of the polygon and the
248 : // plane defined by |aPolygon|.
249 : const nsTArray<float> distances =
250 0 : CalculatePointPlaneDistances(clippedPoints, normal, p1, pos, neg);
251 :
252 0 : backPoints.ClearAndRetainStorage();
253 0 : frontPoints.ClearAndRetainStorage();
254 :
255 : // Clip the polygon points using the previously calculated distances.
256 0 : ClipPointsWithPlane(clippedPoints, normal, distances,
257 : backPoints, frontPoints);
258 :
259 : // Only use the points behind the clipping plane.
260 0 : clippedPoints = Move(backPoints);
261 :
262 0 : if (clippedPoints.Length() < 3) {
263 : // The clipping created a polygon with no area.
264 0 : return PolygonTyped<Units>();
265 : }
266 : }
267 :
268 0 : return PolygonTyped<Units>(Move(clippedPoints), mNormal);
269 : }
270 :
271 : /**
272 : * Returns a new polygon containing the bounds of the given 2D rectangle.
273 : */
274 0 : static PolygonTyped<Units> FromRect(const RectTyped<Units>& aRect)
275 : {
276 : nsTArray<Point4DType> points {
277 0 : Point4DType(aRect.x, aRect.y, 0.0f, 1.0f),
278 0 : Point4DType(aRect.x, aRect.YMost(), 0.0f, 1.0f),
279 : Point4DType(aRect.XMost(), aRect.YMost(), 0.0f, 1.0f),
280 0 : Point4DType(aRect.XMost(), aRect.y, 0.0f, 1.0f)
281 0 : };
282 :
283 0 : return PolygonTyped<Units>(Move(points));
284 : }
285 :
286 0 : const Point4DType& GetNormal() const
287 : {
288 0 : return mNormal;
289 : }
290 :
291 0 : const nsTArray<Point4DType>& GetPoints() const
292 : {
293 0 : return mPoints;
294 : }
295 :
296 0 : bool IsEmpty() const
297 : {
298 : // If the polygon has less than three points, it has no visible area.
299 0 : return mPoints.Length() < 3;
300 : }
301 :
302 : /**
303 : * Returns a list of triangles covering the polygon.
304 : */
305 0 : nsTArray<TriangleTyped<Units>> ToTriangles() const
306 : {
307 0 : nsTArray<TriangleTyped<Units>> triangles;
308 :
309 0 : if (IsEmpty()) {
310 0 : return triangles;
311 : }
312 :
313 : // This fan triangulation method only works for convex polygons.
314 0 : for (size_t i = 1; i < mPoints.Length() - 1; ++i) {
315 0 : TriangleTyped<Units> triangle(Point(mPoints[0].x, mPoints[0].y),
316 0 : Point(mPoints[i].x, mPoints[i].y),
317 0 : Point(mPoints[i + 1].x, mPoints[i + 1].y));
318 0 : triangles.AppendElement(Move(triangle));
319 : }
320 :
321 0 : return triangles;
322 : }
323 :
324 0 : void TransformToLayerSpace(const Matrix4x4Typed<Units, Units>& aTransform)
325 : {
326 0 : TransformPoints(aTransform, true);
327 0 : mNormal = DefaultNormal();
328 0 : }
329 :
330 0 : void TransformToScreenSpace(const Matrix4x4Typed<Units, Units>& aTransform)
331 : {
332 0 : MOZ_ASSERT(!aTransform.IsSingular());
333 :
334 0 : TransformPoints(aTransform, false);
335 :
336 : // Perspective projection transformation might produce points with w <= 0,
337 : // so we need to clip these points.
338 0 : mPoints = ClipPointsAtInfinity(mPoints);
339 :
340 : // Normal vectors should be transformed using inverse transpose.
341 0 : mNormal = aTransform.Inverse().Transpose().TransformPoint(mNormal);
342 0 : }
343 :
344 : private:
345 0 : static Point4DType DefaultNormal()
346 : {
347 0 : return Point4DType(0.0f, 0.0f, 1.0f, 0.0f);
348 : }
349 :
350 : #ifdef DEBUG
351 : void EnsurePlanarPolygon() const
352 : {
353 : if (mPoints.Length() <= 3) {
354 : // Polygons with three or less points are guaranteed to be planar.
355 : return;
356 : }
357 :
358 : // This normal calculation method works only for planar polygons.
359 : // The resulting normal vector will point towards the viewer when the
360 : // polygon has a counter-clockwise winding order from the perspective
361 : // of the viewer.
362 : Point3DType normal;
363 : const Point3DType p0 = mPoints[0].As3DPoint();
364 :
365 : for (size_t i = 1; i < mPoints.Length() - 1; ++i) {
366 : const Point3DType p1 = mPoints[i].As3DPoint();
367 : const Point3DType p2 = mPoints[i + 1].As3DPoint();
368 :
369 : normal += (p1 - p0).CrossProduct(p2 - p0);
370 : }
371 :
372 : // Ensure that at least one component is greater than zero.
373 : // This avoids division by zero when normalizing the vector.
374 : bool hasNonZeroComponent = std::abs(normal.x) > 0.0f ||
375 : std::abs(normal.y) > 0.0f ||
376 : std::abs(normal.z) > 0.0f;
377 :
378 : MOZ_ASSERT(hasNonZeroComponent);
379 :
380 : normal.Normalize();
381 :
382 : // Ensure that the polygon is planar.
383 : // http://mathworld.wolfram.com/Point-PlaneDistance.html
384 : const float epsilon = 0.01f;
385 : for (const Point4DType& point : mPoints) {
386 : const Point3DType p1 = point.As3DPoint();
387 : const float d = normal.DotProduct(p1 - p0);
388 :
389 : MOZ_ASSERT(std::abs(d) < epsilon);
390 : }
391 : }
392 : #endif
393 :
394 0 : void TransformPoints(const Matrix4x4Typed<Units, Units>& aTransform,
395 : const bool aDivideByW)
396 : {
397 0 : for (Point4DType& point : mPoints) {
398 0 : point = aTransform.TransformPoint(point);
399 :
400 0 : if (aDivideByW && point.w > 0.0f) {
401 0 : point = point / point.w;
402 : }
403 : }
404 0 : }
405 :
406 : Point4DType mNormal;
407 : nsTArray<Point4DType> mPoints;
408 : };
409 :
410 : typedef PolygonTyped<UnknownUnits> Polygon;
411 :
412 : } // namespace gfx
413 : } // namespace mozilla
414 :
415 : #endif /* MOZILLA_GFX_POLYGON_H */
|
