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 // Polygon3DTyped stores the points of a convex planar polygon. 21 template<class Units> 22 class Polygon3DTyped { 23 public: Polygon3DTyped()24 Polygon3DTyped() {} 25 26 explicit Polygon3DTyped(const std::initializer_list<Point3DTyped<Units>>& aPoints, 27 Point3DTyped<Units> aNormal = 28 Point3DTyped<Units>(0.0f, 0.0f, 1.0f)) mNormal(aNormal)29 : mNormal(aNormal), mPoints(aPoints) 30 { 31 #ifdef DEBUG 32 EnsurePlanarPolygon(); 33 #endif 34 } 35 36 explicit Polygon3DTyped(nsTArray<Point3DTyped<Units>>&& aPoints, 37 Point3DTyped<Units> aNormal = 38 Point3DTyped<Units>(0.0f, 0.0f, 1.0f)) mNormal(aNormal)39 : mNormal(aNormal), mPoints(Move(aPoints)) 40 { 41 #ifdef DEBUG 42 EnsurePlanarPolygon(); 43 #endif 44 } 45 46 explicit Polygon3DTyped(const nsTArray<Point3DTyped<Units>>& aPoints, 47 Point3DTyped<Units> aNormal = 48 Point3DTyped<Units>(0.0f, 0.0f, 1.0f)) mNormal(aNormal)49 : mNormal(aNormal), mPoints(aPoints) 50 { 51 #ifdef DEBUG 52 EnsurePlanarPolygon(); 53 #endif 54 } 55 BoundingBox()56 RectTyped<Units> BoundingBox() const 57 { 58 float minX, maxX, minY, maxY; 59 minX = maxX = mPoints[0].x; 60 minY = maxY = mPoints[0].y; 61 62 for (const Point3DTyped<Units>& point : mPoints) { 63 minX = std::min(point.x, minX); 64 maxX = std::max(point.x, maxX); 65 66 minY = std::min(point.y, minY); 67 maxY = std::max(point.y, maxY); 68 } 69 70 return RectTyped<Units>(minX, minY, maxX - minX, maxY - minY); 71 } 72 73 nsTArray<float> CalculateDotProducts(const Polygon3DTyped<Units> & aPlane,size_t & aPos,size_t & aNeg)74 CalculateDotProducts(const Polygon3DTyped<Units>& aPlane, 75 size_t& aPos, size_t& aNeg) const 76 { 77 // Point classification might produce incorrect results due to numerical 78 // inaccuracies. Using an epsilon value makes the splitting plane "thicker". 79 const float epsilon = 0.05f; 80 81 MOZ_ASSERT(!aPlane.GetPoints().IsEmpty()); 82 const Point3DTyped<Units>& planeNormal = aPlane.GetNormal(); 83 const Point3DTyped<Units>& planePoint = aPlane[0]; 84 85 aPos = aNeg = 0; 86 nsTArray<float> dotProducts; 87 for (const Point3DTyped<Units>& point : mPoints) { 88 float dot = (point - planePoint).DotProduct(planeNormal); 89 90 if (dot > epsilon) { 91 aPos++; 92 } else if (dot < -epsilon) { 93 aNeg++; 94 } else { 95 // The point is within the thick plane. 96 dot = 0.0f; 97 } 98 99 dotProducts.AppendElement(dot); 100 } 101 102 return dotProducts; 103 } 104 105 // Clips the polygon against the given 2D rectangle. ClipPolygon(const RectTyped<Units> & aRect)106 Polygon3DTyped<Units> ClipPolygon(const RectTyped<Units>& aRect) const 107 { 108 Polygon3DTyped<Units> polygon(mPoints, mNormal); 109 110 // Left edge 111 ClipPolygonWithEdge(polygon, aRect.BottomLeft(), aRect.TopLeft()); 112 113 // Bottom edge 114 ClipPolygonWithEdge(polygon, aRect.BottomRight(), aRect.BottomLeft()); 115 116 // Right edge 117 ClipPolygonWithEdge(polygon, aRect.TopRight(), aRect.BottomRight()); 118 119 // Top edge 120 ClipPolygonWithEdge(polygon, aRect.TopLeft(), aRect.TopRight()); 121 122 return polygon; 123 } 124 GetNormal()125 const Point3DTyped<Units>& GetNormal() const 126 { 127 return mNormal; 128 } 129 GetPoints()130 const nsTArray<Point3DTyped<Units>>& GetPoints() const 131 { 132 return mPoints; 133 } 134 135 const Point3DTyped<Units>& operator[](size_t aIndex) const 136 { 137 MOZ_ASSERT(mPoints.Length() > aIndex); 138 return mPoints[aIndex]; 139 } 140 SplitPolygon(const Polygon3DTyped<Units> & aSplittingPlane,const nsTArray<float> & aDots,nsTArray<Point3DTyped<Units>> & aBackPoints,nsTArray<Point3DTyped<Units>> & aFrontPoints)141 void SplitPolygon(const Polygon3DTyped<Units>& aSplittingPlane, 142 const nsTArray<float>& aDots, 143 nsTArray<Point3DTyped<Units>>& aBackPoints, 144 nsTArray<Point3DTyped<Units>>& aFrontPoints) const 145 { 146 static const auto Sign = [](const float& f) { 147 if (f > 0.0f) return 1; 148 if (f < 0.0f) return -1; 149 return 0; 150 }; 151 152 const Point3DTyped<Units>& normal = aSplittingPlane.GetNormal(); 153 const size_t pointCount = mPoints.Length(); 154 155 for (size_t i = 0; i < pointCount; ++i) { 156 size_t j = (i + 1) % pointCount; 157 158 const Point3DTyped<Units>& a = mPoints[i]; 159 const Point3DTyped<Units>& b = mPoints[j]; 160 const float dotA = aDots[i]; 161 const float dotB = aDots[j]; 162 163 // The point is in front of or on the plane. 164 if (dotA >= 0) { 165 aFrontPoints.AppendElement(a); 166 } 167 168 // The point is behind or on the plane. 169 if (dotA <= 0) { 170 aBackPoints.AppendElement(a); 171 } 172 173 // If the sign of the dot products changes between two consecutive 174 // vertices, then the plane intersects with the polygon edge. 175 // The case where the polygon edge is within the plane is handled above. 176 if (Sign(dotA) && Sign(dotB) && Sign(dotA) != Sign(dotB)) { 177 // Calculate the line segment and plane intersection point. 178 const Point3DTyped<Units> ab = b - a; 179 const float dotAB = ab.DotProduct(normal); 180 const float t = -dotA / dotAB; 181 const Point3DTyped<Units> p = a + (ab * t); 182 183 // Add the intersection point to both polygons. 184 aBackPoints.AppendElement(p); 185 aFrontPoints.AppendElement(p); 186 } 187 } 188 } 189 ToTriangles()190 nsTArray<TriangleTyped<Units>> ToTriangles() const 191 { 192 nsTArray<TriangleTyped<Units>> triangles; 193 194 if (mPoints.Length() < 3) { 195 return triangles; 196 } 197 198 for (size_t i = 1; i < mPoints.Length() - 1; ++i) { 199 TriangleTyped<Units> triangle(Point(mPoints[0].x, mPoints[0].y), 200 Point(mPoints[i].x, mPoints[i].y), 201 Point(mPoints[i+1].x, mPoints[i+1].y)); 202 triangles.AppendElement(Move(triangle)); 203 } 204 205 return triangles; 206 } 207 TransformToLayerSpace(const Matrix4x4Typed<Units,Units> & aTransform)208 void TransformToLayerSpace(const Matrix4x4Typed<Units, Units>& aTransform) 209 { 210 TransformPoints(aTransform); 211 mNormal = Point3DTyped<Units>(0.0f, 0.0f, 1.0f); 212 } 213 TransformToScreenSpace(const Matrix4x4Typed<Units,Units> & aTransform)214 void TransformToScreenSpace(const Matrix4x4Typed<Units, Units>& aTransform) 215 { 216 TransformPoints(aTransform); 217 218 // Normal vectors should be transformed using inverse transpose. 219 mNormal = aTransform.Inverse().Transpose().TransformPoint(mNormal); 220 } 221 222 private: ClipPolygonWithEdge(Polygon3DTyped<Units> & aPolygon,const PointTyped<Units> & aFirst,const PointTyped<Units> & aSecond)223 void ClipPolygonWithEdge(Polygon3DTyped<Units>& aPolygon, 224 const PointTyped<Units>& aFirst, 225 const PointTyped<Units>& aSecond) const 226 { 227 const Point3DTyped<Units> a(aFirst.x, aFirst.y, 0.0f); 228 const Point3DTyped<Units> b(aSecond.x, aSecond.y, 0.0f); 229 const Point3DTyped<Units> normal(b.y - a.y, a.x - b.x, 0.0f); 230 Polygon3DTyped<Units> plane({a, b}, normal); 231 232 size_t pos, neg; 233 nsTArray<float> dots = aPolygon.CalculateDotProducts(plane, pos, neg); 234 235 nsTArray<Point3DTyped<Units>> backPoints, frontPoints; 236 aPolygon.SplitPolygon(plane, dots, backPoints, frontPoints); 237 238 // Only use the points that are behind the clipping plane. 239 aPolygon = Polygon3DTyped<Units>(Move(backPoints), aPolygon.GetNormal()); 240 } 241 242 #ifdef DEBUG EnsurePlanarPolygon()243 void EnsurePlanarPolygon() const 244 { 245 if (mPoints.Length() <= 3) { 246 // Polygons with three or less points are guaranteed to be planar. 247 return; 248 } 249 250 // This normal calculation method works only for planar polygons. 251 // The resulting normal vector will point towards the viewer when the 252 // polygon has a counter-clockwise winding order from the perspective 253 // of the viewer. 254 Point3DTyped<Units> normal; 255 256 for (size_t i = 1; i < mPoints.Length() - 1; ++i) { 257 normal += 258 (mPoints[i] - mPoints[0]).CrossProduct(mPoints[i + 1] - mPoints[0]); 259 } 260 261 // Ensure that at least one component is greater than zero. 262 // This avoids division by zero when normalizing the vector. 263 bool hasNonZeroComponent = std::abs(normal.x) > 0.0f || 264 std::abs(normal.y) > 0.0f || 265 std::abs(normal.z) > 0.0f; 266 MOZ_ASSERT(hasNonZeroComponent); 267 268 normal.Normalize(); 269 270 // Ensure that the polygon is planar. 271 // http://mathworld.wolfram.com/Point-PlaneDistance.html 272 const float epsilon = 0.01f; 273 for (const Point3DTyped<Units>& point : mPoints) { 274 float d = normal.DotProduct(point - mPoints[0]); 275 MOZ_ASSERT(std::abs(d) < epsilon); 276 } 277 } 278 #endif TransformPoints(const Matrix4x4Typed<Units,Units> & aTransform)279 void TransformPoints(const Matrix4x4Typed<Units, Units>& aTransform) 280 { 281 for (Point3DTyped<Units>& point : mPoints) { 282 point = aTransform.TransformPoint(point); 283 } 284 } 285 286 Point3DTyped<Units> mNormal; 287 nsTArray<Point3DTyped<Units>> mPoints; 288 }; 289 290 typedef Polygon3DTyped<UnknownUnits> Polygon3D; 291 292 } // namespace gfx 293 } // namespace mozilla 294 295 #endif /* MOZILLA_GFX_POLYGON_H */ 296