Add Polygon data structure. draft
authorMiko Mynttinen <mikokm@gmail.com>
Tue, 09 Aug 2016 11:24:18 -0700
changeset 399338 5e2d6f6f323015b3d3a3ac23b9192e92ae2a0625
parent 399141 c12bb83ad278a7884af9c70c3622dc6b4c819eaf
child 399339 ebef7d5cfab568cc6ac441f3d746bbf5f94a8dd2
push id25804
push userbmo:mikokm@gmail.com
push dateWed, 10 Aug 2016 22:02:14 +0000
milestone51.0a1
Add Polygon data structure. MozReview-Commit-ID: HFgVFgLqB12
gfx/2d/Polygon.h
gfx/2d/moz.build
new file mode 100644
--- /dev/null
+++ b/gfx/2d/Polygon.h
@@ -0,0 +1,91 @@
+/* -*- 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 "mozilla/InitializerList.h"
+#include "nsTArray.h"
+#include "Point.h"
+
+namespace mozilla {
+namespace gfx {
+
+
+// BasePolygon3D stores the points of a convex planar polygon.
+template<class Units>
+class BasePolygon3D {
+public:
+  explicit BasePolygon3D(const std::initializer_list<Point3DTyped<Units>>& aPoints)
+    : mPoints(aPoints)
+  {
+    CalculateNormal();
+  }
+
+  explicit BasePolygon3D(nsTArray<Point3DTyped<Units>> && aPoints)
+    : mPoints(aPoints)
+  {
+    CalculateNormal();
+  }
+
+  const Point3DTyped<Units>& GetNormal() const
+  {
+    return mNormal;
+  }
+
+  const nsTArray<Point3D>& GetPoints() const
+  {
+    return mPoints;
+  }
+
+  const Point3DTyped<Units>& operator[](size_t aIndex) const
+  {
+    MOZ_ASSERT(mPoints.Length() > aIndex);
+    return mPoints[aIndex];
+  }
+
+private:
+  // Calculates the polygon surface normal.
+  // The resulting normal vector will point towards the viewer when the polygon
+  // has a counter-clockwise winding order from the perspective of the viewer.
+  void CalculateNormal()
+  {
+    MOZ_ASSERT(mPoints.Length() >= 3);
+
+    // This normal calculation method works only for planar polygons.
+    mNormal = (mPoints[1] - mPoints[0]).CrossProduct(mPoints[2] - mPoints[0]);
+
+    const float epsilon = 0.001f;
+    if (mNormal.Length() < epsilon) {
+      // The first three points were too close.
+      // Use more points for better accuracy.
+      for (size_t i = 2; i < mPoints.Length() - 1; ++i) {
+        mNormal += (mPoints[i] - mPoints[0]).CrossProduct(mPoints[i + 1] - mPoints[0]);
+      }
+    }
+
+    mNormal.Normalize();
+
+    #ifdef DEBUG
+    // Ensure that the polygon is planar.
+    // http://mathworld.wolfram.com/Point-PlaneDistance.html
+    for (const gfx::Point3DTyped<Units>& point : mPoints) {
+      float d = mNormal.DotProduct(point - mPoints[0]);
+      MOZ_ASSERT(std::abs(d) < epsilon);
+    }
+    #endif
+  }
+
+  nsTArray<Point3DTyped<Units>> mPoints;
+  Point3DTyped<Units> mNormal;
+};
+
+typedef BasePolygon3D<UnknownUnits> Polygon3D;
+
+} // namespace gfx
+} // namespace mozilla
+
+#endif /* MOZILLA_GFX_POLYGON_H */
\ No newline at end of file
--- a/gfx/2d/moz.build
+++ b/gfx/2d/moz.build
@@ -35,16 +35,17 @@ EXPORTS.mozilla.gfx += [
     'Logging.h',
     'LoggingConstants.h',
     'Matrix.h',
     'MatrixFwd.h',
     'NumericTools.h',
     'PathHelpers.h',
     'PatternHelpers.h',
     'Point.h',
+    'Polygon.h',
     'Quaternion.h',
     'RecordedEvent.h',
     'RecordingTypes.h',
     'Rect.h',
     'Scale.h',
     'ScaleFactor.h',
     'ScaleFactors2D.h',
     'SourceSurfaceCairo.h',