diff options
author | Mike Reed <reed@google.com> | 2018-01-06 13:19:18 +0000 |
---|---|---|
committer | Skia Commit-Bot <skia-commit-bot@chromium.org> | 2018-01-06 13:19:26 +0000 |
commit | 4d1d8bcf6df52bd8e9ae5b0289815c1a2527e7c8 (patch) | |
tree | 590774dc7a8bbaa11165e2413ac7c5e623731fa0 | |
parent | 6e8208b275d230c6996603012bf06b935a3ab165 (diff) |
Revert "remove unused SkCurveMeasure"
This reverts commit 065c2e827e3a5c7aab8f276b1f5358ba3ac33fa8.
Reason for revert: change static initializer count?
Original change's description:
> 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>
TBR=reed@google.com
Change-Id: I0d8ad2aa8b38a389048ba8bf5cafafea5788c3e1
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: skia:
Reviewed-on: https://skia-review.googlesource.com/91343
Reviewed-by: Mike Reed <reed@google.com>
Commit-Queue: Mike Reed <reed@google.com>
-rw-r--r-- | bench/MeasureBench.cpp | 177 | ||||
-rw-r--r-- | gn/bench.gni | 1 | ||||
-rw-r--r-- | gn/utils.gni | 3 | ||||
-rw-r--r-- | src/utils/SkCurveMeasure.cpp | 319 | ||||
-rw-r--r-- | src/utils/SkCurveMeasure.h | 76 |
5 files changed, 576 insertions, 0 deletions
diff --git a/bench/MeasureBench.cpp b/bench/MeasureBench.cpp new file mode 100644 index 0000000000..1b0ec21dc9 --- /dev/null +++ b/bench/MeasureBench.cpp @@ -0,0 +1,177 @@ +/* + * 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 e70916c160..e1df5ba09d 100644 --- a/gn/bench.gni +++ b/gn/bench.gni @@ -70,6 +70,7 @@ 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 6801bcf336..59f665c314 100644 --- a/gn/utils.gni +++ b/gn/utils.gni @@ -32,6 +32,8 @@ 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", @@ -85,4 +87,5 @@ 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 new file mode 100644 index 0000000000..140228dbfa --- /dev/null +++ b/src/utils/SkCurveMeasure.cpp @@ -0,0 +1,319 @@ +/* + * 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 new file mode 100644 index 0000000000..3d1c415598 --- /dev/null +++ b/src/utils/SkCurveMeasure.h @@ -0,0 +1,76 @@ +/* + * 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 |