remove unused SkCurveMeasure

Bug: skia:
Change-Id: I36eb00883bc17e8eef4d1d226972f0125f0e2630
Reviewed-on: https://skia-review.googlesource.com/91702
Reviewed-by: Mike Reed <reed@google.com>
Commit-Queue: Mike Reed <reed@google.com>

5 files changed, 0 insertions, 576 deletions

diff --git a/bench/MeasureBench.cpp b/bench/MeasureBench.cpp
deleted file mode 100644
index 1b0ec21dc9..0000000000
--- a/bench/MeasureBench.cpp
+++ /dev/null
@@ -1,177 +0,0 @@
-/*
- * Copyright 2016 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-// for std::max
-#include <algorithm>
-
-#include "Benchmark.h"
-#include "SkCurveMeasure.h"
-#include "SkPath.h"
-#include "SkPathMeasure.h"
-#include "SkString.h"
-
-#define NORMALIZE_LOOPS
-
-class MeasureBench : public Benchmark {
-   protected:
-    SkString fName;
-
-    SkPath fPath;
-
-    bool fUsePathMeasure;
-    float fSize;
-    size_t fPieces;
-
-    SkPoint fPts[3];
-
-   public:
-    MeasureBench(bool usePathMeasure, float size, size_t pieces)
-        : fUsePathMeasure(usePathMeasure),
-          fSize(size),
-          fPieces(pieces) {
-        fName.printf("measure_%s_%.1f_" SK_SIZE_T_SPECIFIER,
-                     fUsePathMeasure ? "pathMeasure" : "curveMeasure", fSize,
-                     fPieces);
-
-        auto p1 = SkPoint::Make(0, 0);
-        auto p2 = SkPoint::Make(30*fSize, 0);
-        auto p3 = SkPoint::Make(15*fSize, 15*fSize);
-
-        fPts[0] = p1;
-        fPts[1] = p2;
-        fPts[2] = p3;
-
-        this->setPath();
-    }
-
-   protected:
-    const char* onGetName() override { return fName.c_str(); }
-
-    void setPath() {
-        fPath.moveTo(fPts[0]);
-        fPath.quadTo(fPts[1], fPts[2]);
-    }
-
-    int numLoops() {
-#ifdef NORMALIZE_LOOPS
-        // arbitrary heuristic
-        return std::max(2, 10000 / ((int)fSize*(int)fPieces));
-#else
-        return 1000;
-#endif // NORMALIZE_LOOPS
-    }
-
-    //// measurement code
-
-    void do_pathMeasure(SkCanvas* canvas) {
-        SkPathMeasure meas(fPath, false);
-
-        SkScalar totalLength = meas.getLength();
-        SkScalar pieceLength = totalLength / fPieces;
-
-        SkPoint point;
-        for (size_t i = 0; i <= fPieces; i++) {
-            if (meas.getPosTan(i * pieceLength, &point, nullptr)) {
-            };
-        }
-    }
-
-    void do_curveMeasure(SkCanvas* canvas) {
-        SkCurveMeasure meas(fPts, kQuad_SegType);
-
-        SkScalar totalLength = meas.getLength();
-        SkScalar pieceLength = totalLength / fPieces;
-
-        SkPoint point;
-        for (size_t i = 0; i <= fPieces; i++) {
-            meas.getPosTanTime(i*pieceLength, &point, nullptr, nullptr);
-        }
-    }
-
-    void onDraw(int loops, SkCanvas* canvas) override {
-        int inner_loops = numLoops();
-        for (int i = 0; i < loops; i++) {
-            for (int j = 0; j < inner_loops; j++) {
-                if (fUsePathMeasure) {
-                    do_pathMeasure(canvas);
-                }
-                else {
-                    do_curveMeasure(canvas);
-                }
-            }
-        }
-    }
-
-   private:
-    typedef Benchmark INHERITED;
-};
-
-///////////////////////////////////////////////////////////////////////////////
-
-DEF_BENCH(return new MeasureBench(true, 1, 2);)
-DEF_BENCH(return new MeasureBench(true, 2, 2);)
-DEF_BENCH(return new MeasureBench(true, 10, 2);)
-DEF_BENCH(return new MeasureBench(true, 100, 2);)
-DEF_BENCH(return new MeasureBench(true, 1000, 2);)
-
-DEF_BENCH(return new MeasureBench(true, 1, 1);)
-DEF_BENCH(return new MeasureBench(true, 1, 2);)
-DEF_BENCH(return new MeasureBench(true, 1, 3);)
-DEF_BENCH(return new MeasureBench(true, 1, 4);)
-DEF_BENCH(return new MeasureBench(true, 1, 5);)
-DEF_BENCH(return new MeasureBench(true, 2, 1);)
-DEF_BENCH(return new MeasureBench(true, 2, 2);)
-DEF_BENCH(return new MeasureBench(true, 2, 3);)
-DEF_BENCH(return new MeasureBench(true, 2, 4);)
-DEF_BENCH(return new MeasureBench(true, 2, 5);)
-DEF_BENCH(return new MeasureBench(true, 10, 10);)
-DEF_BENCH(return new MeasureBench(true, 10, 20);)
-DEF_BENCH(return new MeasureBench(true, 10, 30);)
-DEF_BENCH(return new MeasureBench(true, 10, 40);)
-DEF_BENCH(return new MeasureBench(true, 10, 50);)
-DEF_BENCH(return new MeasureBench(true, 100, 100);)
-DEF_BENCH(return new MeasureBench(true, 100, 200);)
-DEF_BENCH(return new MeasureBench(true, 100, 300);)
-DEF_BENCH(return new MeasureBench(true, 100, 400);)
-DEF_BENCH(return new MeasureBench(true, 100, 500);)
-DEF_BENCH(return new MeasureBench(true, 1000, 1000);)
-DEF_BENCH(return new MeasureBench(true, 1000, 2000);)
-DEF_BENCH(return new MeasureBench(true, 1000, 3000);)
-DEF_BENCH(return new MeasureBench(true, 1000, 4000);)
-DEF_BENCH(return new MeasureBench(true, 1000, 5000);)
-
-DEF_BENCH(return new MeasureBench(false, 1, 2);)
-DEF_BENCH(return new MeasureBench(false, 2, 2);)
-DEF_BENCH(return new MeasureBench(false, 10, 2);)
-DEF_BENCH(return new MeasureBench(false, 100, 2);)
-DEF_BENCH(return new MeasureBench(false, 1000, 2);)
-
-DEF_BENCH(return new MeasureBench(false, 1, 1);)
-DEF_BENCH(return new MeasureBench(false, 1, 2);)
-DEF_BENCH(return new MeasureBench(false, 1, 3);)
-DEF_BENCH(return new MeasureBench(false, 1, 4);)
-DEF_BENCH(return new MeasureBench(false, 1, 5);)
-DEF_BENCH(return new MeasureBench(false, 2, 1);)
-DEF_BENCH(return new MeasureBench(false, 2, 2);)
-DEF_BENCH(return new MeasureBench(false, 2, 3);)
-DEF_BENCH(return new MeasureBench(false, 2, 4);)
-DEF_BENCH(return new MeasureBench(false, 2, 5);)
-DEF_BENCH(return new MeasureBench(false, 10, 10);)
-DEF_BENCH(return new MeasureBench(false, 10, 20);)
-DEF_BENCH(return new MeasureBench(false, 10, 30);)
-DEF_BENCH(return new MeasureBench(false, 10, 40);)
-DEF_BENCH(return new MeasureBench(false, 10, 50);)
-DEF_BENCH(return new MeasureBench(false, 100, 100);)
-DEF_BENCH(return new MeasureBench(false, 100, 200);)
-DEF_BENCH(return new MeasureBench(false, 100, 300);)
-DEF_BENCH(return new MeasureBench(false, 100, 400);)
-DEF_BENCH(return new MeasureBench(false, 100, 500);)
-DEF_BENCH(return new MeasureBench(false, 1000, 1000);)
-DEF_BENCH(return new MeasureBench(false, 1000, 2000);)
-DEF_BENCH(return new MeasureBench(false, 1000, 3000);)
-DEF_BENCH(return new MeasureBench(false, 1000, 4000);)
-DEF_BENCH(return new MeasureBench(false, 1000, 5000);)
diff --git a/gn/bench.gni b/gn/bench.gni
index e1df5ba09d..e70916c160 100644
--- a/gn/bench.gni
+++ b/gn/bench.gni
@@ -70,7 +70,6 @@ bench_sources = [
   "$_bench/Matrix44Bench.cpp",
   "$_bench/MatrixBench.cpp",
   "$_bench/MatrixConvolutionBench.cpp",
-  "$_bench/MeasureBench.cpp",
   "$_bench/MemsetBench.cpp",
   "$_bench/MergeBench.cpp",
   "$_bench/MipMapBench.cpp",
diff --git a/gn/utils.gni b/gn/utils.gni
index 59f665c314..6801bcf336 100644
--- a/gn/utils.gni
+++ b/gn/utils.gni
@@ -32,8 +32,6 @@ skia_utils_sources = [
   "$_src/utils/SkCanvasStack.h",
   "$_src/utils/SkCanvasStack.cpp",
   "$_src/utils/SkCanvasStateUtils.cpp",
-  "$_src/utils/SkCurveMeasure.cpp",
-  "$_src/utils/SkCurveMeasure.h",
   "$_src/utils/SkDashPath.cpp",
   "$_src/utils/SkDashPathPriv.h",
   "$_src/utils/SkDumpCanvas.cpp",
@@ -87,5 +85,4 @@ skia_utils_sources = [
   "$_src/utils/win/SkTScopedComPtr.h",
   "$_src/utils/win/SkWGL.h",
   "$_src/utils/win/SkWGL_win.cpp",
-
 ]
diff --git a/src/utils/SkCurveMeasure.cpp b/src/utils/SkCurveMeasure.cpp
deleted file mode 100644
index 140228dbfa..0000000000
--- a/src/utils/SkCurveMeasure.cpp
+++ /dev/null
@@ -1,319 +0,0 @@
-/*
- * Copyright 2016 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "SkCurveMeasure.h"
-#include "SkGeometry.h"
-
-// for abs
-#include <cmath>
-
-#define UNIMPLEMENTED SkDEBUGF(("%s:%d unimplemented\n", __FILE__, __LINE__))
-
-/// Used inside SkCurveMeasure::getTime's Newton's iteration
-static inline SkPoint evaluate(const SkPoint pts[4], SkSegType segType,
-                               SkScalar t) {
-    SkPoint pos;
-    switch (segType) {
-        case kQuad_SegType:
-            pos = SkEvalQuadAt(pts, t);
-            break;
-        case kLine_SegType:
-            pos = SkPoint::Make(SkScalarInterp(pts[0].x(), pts[1].x(), t),
-                                SkScalarInterp(pts[0].y(), pts[1].y(), t));
-            break;
-        case kCubic_SegType:
-            SkEvalCubicAt(pts, t, &pos, nullptr, nullptr);
-            break;
-        case kConic_SegType: {
-            SkConic conic(pts, pts[3].x());
-            conic.evalAt(t, &pos);
-        }
-            break;
-        default:
-            UNIMPLEMENTED;
-    }
-
-    return pos;
-}
-
-/// Used inside SkCurveMeasure::getTime's Newton's iteration
-static inline SkVector evaluateDerivative(const SkPoint pts[4],
-                                          SkSegType segType, SkScalar t) {
-    SkVector tan;
-    switch (segType) {
-        case kQuad_SegType:
-            tan = SkEvalQuadTangentAt(pts, t);
-            break;
-        case kLine_SegType:
-            tan = pts[1] - pts[0];
-            break;
-        case kCubic_SegType:
-            SkEvalCubicAt(pts, t, nullptr, &tan, nullptr);
-            break;
-        case kConic_SegType: {
-            SkConic conic(pts, pts[3].x());
-            conic.evalAt(t, nullptr, &tan);
-        }
-            break;
-        default:
-            UNIMPLEMENTED;
-    }
-
-    return tan;
-}
-/// Used in ArcLengthIntegrator::computeLength
-static inline Sk8f evaluateDerivativeLength(const Sk8f& ts,
-                                            const float (&xCoeff)[3][8],
-                                            const float (&yCoeff)[3][8],
-                                            const SkSegType segType) {
-    Sk8f x;
-    Sk8f y;
-
-    Sk8f x0 = Sk8f::Load(&xCoeff[0]),
-         x1 = Sk8f::Load(&xCoeff[1]),
-         x2 = Sk8f::Load(&xCoeff[2]);
-
-    Sk8f y0 = Sk8f::Load(&yCoeff[0]),
-         y1 = Sk8f::Load(&yCoeff[1]),
-         y2 = Sk8f::Load(&yCoeff[2]);
-
-    switch (segType) {
-        case kQuad_SegType:
-            x = x0*ts + x1;
-            y = y0*ts + y1;
-            break;
-        case kCubic_SegType:
-            x = (x0*ts + x1)*ts + x2;
-            y = (y0*ts + y1)*ts + y2;
-            break;
-        case kConic_SegType:
-            UNIMPLEMENTED;
-            break;
-        default:
-            UNIMPLEMENTED;
-    }
-
-    x = x * x;
-    y = y * y;
-
-    return (x + y).sqrt();
-}
-
-ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType)
-    : fSegType(segType) {
-    switch (fSegType) {
-        case kQuad_SegType: {
-            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();
-
-            // precompute coefficients for derivative
-            Sk8f(2*(Ax - 2*Bx + Cx)).store(&xCoeff[0]);
-            Sk8f(2*(Bx - Ax)).store(&xCoeff[1]);
-
-            Sk8f(2*(Ay - 2*By + Cy)).store(&yCoeff[0]);
-            Sk8f(2*(By - Ay)).store(&yCoeff[1]);
-        }
-            break;
-        case kCubic_SegType:
-        {
-            float Ax = pts[0].x();
-            float Bx = pts[1].x();
-            float Cx = pts[2].x();
-            float Dx = pts[3].x();
-            float Ay = pts[0].y();
-            float By = pts[1].y();
-            float Cy = pts[2].y();
-            float Dy = pts[3].y();
-
-            // precompute coefficients for derivative
-            Sk8f(3*(-Ax + 3*(Bx - Cx) + Dx)).store(&xCoeff[0]);
-            Sk8f(6*(Ax - 2*Bx + Cx)).store(&xCoeff[1]);
-            Sk8f(3*(-Ax + Bx)).store(&xCoeff[2]);
-
-            Sk8f(3*(-Ay + 3*(By - Cy) + Dy)).store(&yCoeff[0]);
-            Sk8f(6*(Ay - 2*By + Cy)).store(&yCoeff[1]);
-            Sk8f(3*(-Ay + By)).store(&yCoeff[2]);
-        }
-            break;
-        case kConic_SegType:
-            UNIMPLEMENTED;
-            break;
-        default:
-            UNIMPLEMENTED;
-    }
-}
-
-// We use Gaussian quadrature
-// (https://en.wikipedia.org/wiki/Gaussian_quadrature)
-// to approximate the arc length integral here, because it is amenable to SIMD.
-SkScalar ArcLengthIntegrator::computeLength(SkScalar t) {
-    SkScalar length = 0.0f;
-
-    Sk8f lengths = evaluateDerivativeLength(absc*t, xCoeff, yCoeff, fSegType);
-    lengths = weights*lengths;
-    // is it faster or more accurate to sum and then multiply or vice versa?
-    lengths = lengths*(t*0.5f);
-
-    // Why does SkNx index with ints? does negative index mean something?
-    for (int i = 0; i < 8; i++) {
-        length += lengths[i];
-    }
-    return length;
-}
-
-SkCurveMeasure::SkCurveMeasure(const SkPoint* pts, SkSegType segType)
-    : fSegType(segType) {
-    switch (fSegType) {
-        case SkSegType::kQuad_SegType:
-            for (size_t i = 0; i < 3; i++) {
-                fPts[i] = pts[i];
-            }
-            break;
-        case SkSegType::kLine_SegType:
-            fPts[0] = pts[0];
-            fPts[1] = pts[1];
-            fLength = (fPts[1] - fPts[0]).length();
-            break;
-        case SkSegType::kCubic_SegType:
-            for (size_t i = 0; i < 4; i++) {
-                fPts[i] = pts[i];
-            }
-            break;
-        case SkSegType::kConic_SegType:
-            for (size_t i = 0; i < 4; i++) {
-                fPts[i] = pts[i];
-            }
-            break;
-        default:
-            UNIMPLEMENTED;
-            break;
-    }
-    if (kLine_SegType != segType) {
-        fIntegrator = ArcLengthIntegrator(fPts, fSegType);
-    }
-}
-
-SkScalar SkCurveMeasure::getLength() {
-    if (-1.0f == fLength) {
-        fLength = fIntegrator.computeLength(1.0f);
-    }
-    return fLength;
-}
-
-// Given an arc length targetLength, we want to determine what t
-// gives us the corresponding arc length along the curve.
-// We do this by letting the arc length integral := f(t) and
-// solving for the root of the equation f(t) - targetLength = 0
-// using Newton's method and lerp-bisection.
-// The computationally expensive parts are the integral approximation
-// at each step, and computing the derivative of the arc length integral,
-// which is equal to the length of the tangent (so we have to do a sqrt).
-
-SkScalar SkCurveMeasure::getTime(SkScalar targetLength) {
-    if (targetLength <= 0.0f) {
-        return 0.0f;
-    }
-
-    SkScalar currentLength = getLength();
-
-    if (targetLength > currentLength || (SkScalarNearlyEqual(targetLength, currentLength))) {
-        return 1.0f;
-    }
-    if (kLine_SegType == fSegType) {
-        return targetLength / currentLength;
-    }
-
-    // initial estimate of t is percentage of total length
-    SkScalar currentT = targetLength / currentLength;
-    SkScalar prevT = -1.0f;
-    SkScalar newT;
-
-    SkScalar minT = 0.0f;
-    SkScalar maxT = 1.0f;
-
-    int iterations = 0;
-    while (iterations < kNewtonIters + kBisectIters) {
-        currentLength = fIntegrator.computeLength(currentT);
-        SkScalar lengthDiff = currentLength - targetLength;
-
-        // Update root bounds.
-        // If lengthDiff is positive, we have overshot the target, so
-        // we know the current t is an upper bound, and similarly
-        // for the lower bound.
-        if (lengthDiff > 0.0f) {
-            if (currentT < maxT) {
-                maxT = currentT;
-            }
-        } else {
-            if (currentT > minT) {
-                minT = currentT;
-            }
-        }
-
-        // We have a tolerance on both the absolute value of the difference and
-        // on the t value
-        // because we may not have enough precision in the t to get close enough
-        // in the length.
-        if ((std::abs(lengthDiff) < kTolerance) ||
-            (std::abs(prevT - currentT) < kTolerance)) {
-            break;
-        }
-
-        prevT = currentT;
-        if (iterations < kNewtonIters) {
-            // This is just newton's formula.
-            SkScalar dt = evaluateDerivative(fPts, fSegType, currentT).length();
-            newT = currentT - (lengthDiff / dt);
-
-            // If newT is out of bounds, bisect inside newton.
-            if ((newT < 0.0f) || (newT > 1.0f)) {
-                newT = (minT + maxT) * 0.5f;
-            }
-        } else if (iterations < kNewtonIters + kBisectIters) {
-            if (lengthDiff > 0.0f) {
-                maxT = currentT;
-            } else {
-                minT = currentT;
-            }
-            // TODO(hstern) do a lerp here instead of a bisection
-            newT = (minT + maxT) * 0.5f;
-        } else {
-            SkDEBUGF(("%.7f %.7f didn't get close enough after bisection.\n",
-                      currentT, currentLength));
-            break;
-        }
-        currentT = newT;
-
-        SkASSERT(minT <= maxT);
-
-        iterations++;
-    }
-
-    // debug. is there an SKDEBUG or something for ifdefs?
-    fIters = iterations;
-
-    return currentT;
-}
-
-void SkCurveMeasure::getPosTanTime(SkScalar targetLength, SkPoint* pos,
-                                   SkVector* tan, SkScalar* time) {
-    SkScalar t = getTime(targetLength);
-
-    if (time) {
-        *time = t;
-    }
-    if (pos) {
-        *pos = evaluate(fPts, fSegType, t);
-    }
-    if (tan) {
-        *tan = evaluateDerivative(fPts, fSegType, t);
-    }
-}
diff --git a/src/utils/SkCurveMeasure.h b/src/utils/SkCurveMeasure.h
deleted file mode 100644
index 3d1c415598..0000000000
--- a/src/utils/SkCurveMeasure.h
+++ /dev/null
@@ -1,76 +0,0 @@
-/*
- * 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 "SkPathMeasurePriv.h"
-#include "SkPoint.h"
-#include "SkNx.h"
-
-// These are weights and abscissae for gaussian quadrature with weight function
-// w(x) = 1
-static SkScalar weights8[8] = {0.3626837833783620f, 0.3626837833783620f,
-                               0.3137066458778873f, 0.3137066458778873f,
-                               0.2223810344533745f, 0.2223810344533745f,
-                               0.1012285362903763f, 0.1012285362903763f};
-static SkScalar absc8[8] = {-0.1834346424956498f, 0.1834346424956498f,
-                            -0.5255324099163290f, 0.5255324099163290f,
-                            -0.7966664774136267f, 0.7966664774136267f,
-                            -0.9602898564975363f, 0.9602898564975363f};
-
-static Sk8f weights = Sk8f::Load(weights8);
-static Sk8f absc = 0.5f*(Sk8f::Load(absc8) + 1.0f);
-
-
-class ArcLengthIntegrator {
-public:
-    ArcLengthIntegrator() {}
-    ArcLengthIntegrator(const SkPoint* pts, SkSegType segType);
-    SkScalar computeLength(SkScalar t);
-
-private:
-    SkSegType fSegType;
-
-    // precomputed coefficients for derivatives in Horner form
-    float xCoeff[3][8];
-    float yCoeff[3][8];
-};
-
-class SkCurveMeasure {
-public:
-    SkCurveMeasure() {}
-
-    // Almost exactly the same as in SkPath::Iter:
-    // kLine_SegType  -> 2 points: start end
-    // kQuad_SegType  -> 3 points: start control end
-    // kCubic_SegType -> 4 points: start control1 control2 end
-    // kConic_SegType -> 4 points: start control end (w, w)
-    //
-    // i.e. the only difference is that the conic's last point is a point
-    // consisting of the w value twice
-    SkCurveMeasure(const SkPoint* pts, SkSegType segType);
-
-    SkScalar getTime(SkScalar targetLength);
-    void getPosTanTime(SkScalar distance, SkPoint* pos, SkVector* tan, SkScalar* time);
-    SkScalar getLength();
-
-private:
-    const SkScalar kTolerance = 0.0001f;
-    const int kNewtonIters = 5;
-    const int kBisectIters = 5;
-
-    SkSegType fSegType;
-    SkPoint fPts[4];
-    SkScalar fLength = -1.0f;
-    ArcLengthIntegrator fIntegrator;
-
-    // for debug purposes
-    int fIters;
-};
-
-#endif  // SkCurveMeasure_DEFINED