aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bench/MeasureBench.cpp177
-rw-r--r--gn/bench.gni1
-rw-r--r--gn/utils.gni3
-rw-r--r--src/utils/SkCurveMeasure.cpp319
-rw-r--r--src/utils/SkCurveMeasure.h76
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-04 22:44:34 +0000