Index: src/utils/SkCurveMeasure.cpp |
diff --git a/src/utils/SkCurveMeasure.cpp b/src/utils/SkCurveMeasure.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..10d7dae51f94eb5a9f8526ac7a4eda022ec4b88e |
--- /dev/null |
+++ b/src/utils/SkCurveMeasure.cpp |
@@ -0,0 +1,173 @@ |
+/* |
+ * 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" |
+ |
+// for abs |
+#include <cmath> |
+ |
+SkCurveMeasure::SkCurveMeasure(SkPoint pts[3]) { |
+ for (size_t i = 0; i < 3; i++) { |
+ fPts[i] = pts[i]; |
+ } |
+ // need to switch on segment type and template for the integrator or something |
+ fIntegrator = new QuadArcLengthIntegrator(pts); |
+} |
+ |
+// this will be removed when switch to templated integrator or something |
+SkCurveMeasure::~SkCurveMeasure() { |
+ delete fIntegrator; |
+} |
+ |
+SkScalar SkCurveMeasure::getLength() { |
+ if (-1.0 == 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 (SkScalarNearlyEqual(targetLength, currentLength)) { |
+ return 1.0f; |
+ } |
+ |
+ // 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) { |
+ // TODO(hstern) switch here on curve type. or template on an |
+ // evaluator. |
+ // This is just newton's formula. |
+ SkScalar dt = evaluateQuadDerivative(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::getPosTan(SkScalar targetLength, SkPoint* pos, |
+ SkVector* tan) { |
+ SkScalar t = getTime(targetLength); |
+ |
+ if (pos) { |
+ // TODO(hstern) switch here on curve type. or template on evaluator. |
+ *pos = evaluateQuad(t); |
+ } |
+ if (tan) { |
+ // TODO(hstern) switch here on curve type. or template on evaluator. |
+ *tan = evaluateQuadDerivative(t); |
+ } |
+} |
+ |
+// this is why I feel that the ArcLengthIntegrators should be combined |
+// with some sort of evaluator that caches the constants computed from the |
+// control points. this is basically the same code in QuadArcLengthIntegrator |
+SkPoint SkCurveMeasure::evaluateQuad(SkScalar t) { |
+ SkScalar ti = 1.0f - t; |
+ |
+ SkScalar Ax = fPts[0].x(); |
+ SkScalar Bx = fPts[1].x(); |
+ SkScalar Cx = fPts[2].x(); |
+ SkScalar Ay = fPts[0].y(); |
+ SkScalar By = fPts[1].y(); |
+ SkScalar Cy = fPts[2].y(); |
+ |
+ SkScalar x = Ax*ti*ti + 2.0f*Bx*t*ti + Cx*t*t; |
+ SkScalar y = Ay*ti*ti + 2.0f*By*t*ti + Cy*t*t; |
+ return SkPoint::Make(x, y); |
+} |
+ |
+SkVector SkCurveMeasure::evaluateQuadDerivative(SkScalar t) { |
+ SkScalar Ax = fPts[0].x(); |
+ SkScalar Bx = fPts[1].x(); |
+ SkScalar Cx = fPts[2].x(); |
+ SkScalar Ay = fPts[0].y(); |
+ SkScalar By = fPts[1].y(); |
+ SkScalar Cy = fPts[2].y(); |
+ |
+ SkScalar A2BCx = 2.0f*(Ax - 2*Bx + Cx); |
+ SkScalar A2BCy = 2.0f*(Ay - 2*By + Cy); |
+ SkScalar ABx = 2.0f*(Bx - Ax); |
+ SkScalar ABy = 2.0f*(By - Ay); |
+ |
+ return SkPoint::Make(A2BCx*t + ABx, A2BCy*t + ABy); |
+} |