Add initial CurveMeasure code

src/utils/SkCurveMeasure.h

+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkCurveMeasure_DEFINED
+#define SkCurveMeasure_DEFINED
+
+#include "SkPoint.h"
+#include "SkNx.h"
+
+static SkScalar weights8[8] = {0.3626837833783620, 0.3626837833783620, 0.3137066458778873, 0.3137066458778873, 0.2223810344533745, 0.2223810344533745, 0.1012285362903763, 0.1012285362903763};

[reed1, 2016/07/27 19:59:43]

can you move these into private section of ArcLengthIntegrator?

[Harry Stern, 2016/07/27 20:39:07]

I can, but the Sk8f weights and absc would have to be initialized in the
constructor for each Integrator because SkNx has non-constexpr constructors,
from what the compiler seems to be telling me. It's not a big deal since it's
only 8 floats, so I can do it if you want. I don't really understand why they
should be, though.

I should probably rename them to kWeights and kAbsc.

+static SkScalar absc8[8] = {-0.1834346424956498, 0.1834346424956498, -0.5255324099163290, 0.5255324099163290, -0.7966664774136267, 0.7966664774136267, -0.9602898564975363, 0.9602898564975363};
+
+static Sk8f weights = Sk8f::Load(weights8);
+static Sk8f absc = 0.5f*(Sk8f::Load(absc8) + 1.0f);
+
+
+// We use Gaussian quadrature (https://en.wikipedia.org/wiki/Gaussian_quadrature)
+// to approximate the arc length integral here, because it is amenable to SIMD.
+class ArcLengthIntegrator {
+   public:
+    virtual ~ArcLengthIntegrator();
+
+    float computeLength(float t) {
+        float length = 0.0;
+        
+        Sk8f lengths = evaluate_derivative_length(absc*t);
+        lengths = weights*lengths;
+        // is it faster or more accurate to sum and then multiply or vice versa?
+        lengths = lengths*(t*0.5f);
+
+        for (size_t i = 0; i < 8; i++) {
+            length += lengths[i];
+        }
+        return length;
+    }
+
+   private:
+    Sk8f evaluate_derivative_length(Sk8f ts) {
+        Sk8f x = this->evaluate_derivative_x(ts);
+        Sk8f y = this->evaluate_derivative_y(ts);
+
+        x = x * x;
+        y = y * y;
+
+        return (x + y).sqrt();
+    }
+
+    virtual Sk8f evaluate_derivative_x(Sk8f &ts) = 0;
+    virtual Sk8f evaluate_derivative_y(Sk8f &ts) = 0;
+};
+ArcLengthIntegrator::~ArcLengthIntegrator() { }
+
+class QuadArcLengthIntegrator : public ArcLengthIntegrator {
+   public:
+    QuadArcLengthIntegrator(const SkPoint pts[3]) {
+        float Ax = pts[0].x();
+        float Bx = pts[1].x();
+        float Cx = pts[2].x();
+        float Ay = pts[0].y();
+        float By = pts[1].y();
+        float Cy = pts[2].y();
+
+        A2BC_x = Sk8f(2.0f*(Ax - 2*Bx + Cx));
+        A2BC_y = Sk8f(2.0f*(Ay - 2*By + Cy));
+
+        AB_x = Sk8f(2.0f*(Bx - Ax));
+        AB_y = Sk8f(2.0f*(By - Ay));
+    }
+
+   private:
+    Sk8f evaluate_derivative_x(Sk8f &ts) override {

[reed1, 2016/07/27 19:59:43]

const Sk8f& ts

[Harry Stern, 2016/07/27 20:39:07]

Done.

+        return A2BC_x*ts + AB_x;
+    }
+    Sk8f evaluate_derivative_y(Sk8f &ts) override {
+        return A2BC_y*ts + AB_y;
+    }
+
+    Sk8f A2BC_x, A2BC_y;
+    Sk8f AB_x, AB_y;
+};
+
+class SkCurveMeasure {
+   public:
+    // I guess this should have a parameter that uses the SegType enum in SkPathMeasure
+    // and then we can switch on that to template the evaluator and integrator
+    SkCurveMeasure(SkPoint pts[3]);
+
+    SkScalar getTime(SkScalar targetLength);
+    void getPosTan(SkScalar distance, SkPoint* pos, SkVector* tan);
+    SkScalar getLength();
+   private:
+    ~SkCurveMeasure();
+    // maybe template on an evaluator class
+    SkPoint evaluateQuad(SkScalar t);
+    SkVector evaluateQuadDerivative(SkScalar t);
+    //SkPoint evaluate_cubic(SkScalar t);
+    //SkVector evaluate_cubic_derivative(SkScalar t);
+    //SkPoint evaluate_conic(SkScalar t);
+    //SkVector evaluate_conic_derivative(SkScalar t);
+
+    const SkScalar kTolerance = 0.0001f;
+    const int kNewtonIters = 5;
+    const int kBisectIters = 5;
+    const int kPieces = 15;
+
+    SkPoint fPts[3];
+    SkScalar fLength = -1.0f;
+    ArcLengthIntegrator* fIntegrator;
+
+    // for debug purposes
+    int fIters;
+};
+
+#endif // SkCurveMeasure_DEFINED