per-contour variant of SkPathMeasure
Bug: skia:8721
Change-Id: I1e79a49dee25ccc9138baf6fb2df3dc80d1ff66b
Reviewed-on: https://skia-review.googlesource.com/c/187922
Commit-Queue: Mike Reed <reed@google.com>
Reviewed-by: Kevin Lubick <kjlubick@google.com>
diff --git a/BUILD.gn b/BUILD.gn
index 497587b..23f8ba8 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -1093,6 +1093,7 @@
sources += [
"src/core/SkAnalyticEdge.cpp",
"src/core/SkArenaAlloc.cpp",
+ "src/core/SkContourMeasure.cpp",
"src/core/SkCubicMap.cpp",
"src/core/SkEdge.cpp",
"src/core/SkEdgeBuilder.cpp",
diff --git a/gn/core.gni b/gn/core.gni
index 3e7a18a..50b7086 100644
--- a/gn/core.gni
+++ b/gn/core.gni
@@ -68,6 +68,7 @@
"$_src/core/SkColorSpaceXformSteps.cpp",
"$_src/core/SkColorSpaceXformer.cpp",
"$_src/core/SkColorSpaceXformer.h",
+ "$_src/core/SkContourMeasure.cpp",
"$_src/core/SkConvertPixels.cpp",
"$_src/core/SkConvertPixels.h",
"$_src/core/SkCoreBlitters.h",
diff --git a/include/core/SkContourMeasure.h b/include/core/SkContourMeasure.h
new file mode 100644
index 0000000..223f3b5
--- /dev/null
+++ b/include/core/SkContourMeasure.h
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2018 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkContourMeasure_DEFINED
+#define SkContourMeasure_DEFINED
+
+#include "../private/SkNoncopyable.h"
+#include "../private/SkTDArray.h"
+#include "SkPath.h"
+#include "SkRefCnt.h"
+
+struct SkConic;
+
+class SK_API SkContourMeasure : public SkRefCnt {
+public:
+ /** Return the length of the contour.
+ */
+ SkScalar length() const { return fLength; }
+
+ /** Pins distance to 0 <= distance <= length(), and then computes the corresponding
+ * position and tangent.
+ */
+ bool SK_WARN_UNUSED_RESULT getPosTan(SkScalar distance, SkPoint* position,
+ SkVector* tangent) const;
+
+ enum MatrixFlags {
+ kGetPosition_MatrixFlag = 0x01,
+ kGetTangent_MatrixFlag = 0x02,
+ kGetPosAndTan_MatrixFlag = kGetPosition_MatrixFlag | kGetTangent_MatrixFlag
+ };
+
+ /** Pins distance to 0 <= distance <= getLength(), and then computes
+ the corresponding matrix (by calling getPosTan).
+ Returns false if there is no path, or a zero-length path was specified, in which case
+ matrix is unchanged.
+ */
+ bool SK_WARN_UNUSED_RESULT getMatrix(SkScalar distance, SkMatrix* matrix,
+ MatrixFlags flags = kGetPosAndTan_MatrixFlag) const;
+
+ /** Given a start and stop distance, return in dst the intervening segment(s).
+ If the segment is zero-length, return false, else return true.
+ startD and stopD are pinned to legal values (0..getLength()). If startD > stopD
+ then return false (and leave dst untouched).
+ Begin the segment with a moveTo if startWithMoveTo is true
+ */
+ bool SK_WARN_UNUSED_RESULT getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
+ bool startWithMoveTo) const;
+
+ /** Return true if the contour is closed()
+ */
+ bool isClosed() const { return fIsClosed; }
+
+private:
+ struct Segment {
+ SkScalar fDistance; // total distance up to this point
+ unsigned fPtIndex; // index into the fPts array
+ unsigned fTValue : 30;
+ unsigned fType : 2; // actually the enum SkSegType
+ // See SkPathMeasurePriv.h
+
+ SkScalar getScalarT() const;
+
+ static const Segment* Next(const Segment* seg) {
+ unsigned ptIndex = seg->fPtIndex;
+ do {
+ ++seg;
+ } while (seg->fPtIndex == ptIndex);
+ return seg;
+ }
+
+ };
+
+ const SkTDArray<Segment> fSegments;
+ const SkTDArray<SkPoint> fPts; // Points used to define the segments
+
+ const SkScalar fLength;
+ const bool fIsClosed;
+
+ SkContourMeasure(SkTDArray<Segment>&& segs, SkTDArray<SkPoint>&& pts,
+ SkScalar length, bool isClosed);
+ ~SkContourMeasure() override {}
+
+ const Segment* distanceToSegment(SkScalar distance, SkScalar* t) const;
+
+ friend class SkContourMeasureIter;
+};
+
+class SK_API SkContourMeasureIter : SkNoncopyable {
+public:
+ SkContourMeasureIter();
+ SkContourMeasureIter(const SkPath& path, bool forceClosed, SkScalar resScale = 1);
+ ~SkContourMeasureIter();
+
+ void reset(const SkPath& path, bool forceClosed, SkScalar resScale = 1);
+
+ /**
+ * Iterates through contours in path, returning a contour-measure object for each contour
+ * in the path. Returns null when it is done.
+ *
+ * This only returns non-zero length contours, where a contour is the segments between
+ * a kMove_Verb and either ...
+ * - the next kMove_Verb
+ * - kClose_Verb (1 or more)
+ * - kDone_Verb
+ * If it encounters a zero-length contour, it is skipped.
+ */
+ sk_sp<SkContourMeasure> next();
+
+private:
+ SkPath::Iter fIter;
+ SkPath fPath;
+ SkScalar fTolerance;
+ bool fForceClosed;
+
+ // temporary
+ SkTDArray<SkContourMeasure::Segment> fSegments;
+ SkTDArray<SkPoint> fPts; // Points used to define the segments
+
+ SkContourMeasure* buildSegments();
+
+ SkScalar compute_quad_segs(const SkPoint pts[3], SkScalar distance,
+ int mint, int maxt, unsigned ptIndex);
+ SkScalar compute_conic_segs(const SkConic& conic, SkScalar distance,
+ int mint, const SkPoint& minPt,
+ int maxt, const SkPoint& maxPt,
+ unsigned ptIndex);
+ SkScalar compute_cubic_segs(const SkPoint pts[4], SkScalar distance,
+ int mint, int maxt, unsigned ptIndex);
+};
+
+#endif
diff --git a/include/core/SkPath.h b/include/core/SkPath.h
index 183f1c3..f19bae4 100644
--- a/include/core/SkPath.h
+++ b/include/core/SkPath.h
@@ -1485,6 +1485,9 @@
*/
bool isClosedContour() const;
+ // Returns the next verb, or kDone, without changing the state of the iterator
+ Verb peekVerb() const;
+
private:
const SkPoint* fPts;
const uint8_t* fVerbs;
diff --git a/include/core/SkPathMeasure.h b/include/core/SkPathMeasure.h
index ae4c4e6..9d77da2 100644
--- a/include/core/SkPathMeasure.h
+++ b/include/core/SkPathMeasure.h
@@ -10,10 +10,9 @@
#include "../private/SkNoncopyable.h"
#include "../private/SkTDArray.h"
+#include "SkContourMeasure.h"
#include "SkPath.h"
-struct SkConic;
-
class SK_API SkPathMeasure : SkNoncopyable {
public:
SkPathMeasure();
@@ -84,43 +83,8 @@
#endif
private:
- SkPath::Iter fIter;
- SkPath fPath;
- SkScalar fTolerance;
- SkScalar fLength; // relative to the current contour
- unsigned fFirstPtIndex; // relative to the current contour
- bool fIsClosed; // relative to the current contour
- bool fForceClosed;
-#if defined(IS_FUZZING_WITH_LIBFUZZER)
- int fSubdivisionsMax;
-#endif
- struct Segment {
- SkScalar fDistance; // total distance up to this point
- unsigned fPtIndex; // index into the fPts array
- unsigned fTValue : 30;
- unsigned fType : 2; // actually the enum SkSegType
- // See SkPathMeasurePriv.h
-
- SkScalar getScalarT() const;
- };
- SkTDArray<Segment> fSegments;
- SkTDArray<SkPoint> fPts; // Points used to define the segments
-
- static const Segment* NextSegment(const Segment*);
-
- void buildSegments();
- SkScalar compute_quad_segs(const SkPoint pts[3], SkScalar distance,
- int mint, int maxt, unsigned ptIndex);
- SkScalar compute_conic_segs(const SkConic&, SkScalar distance,
- int mint, const SkPoint& minPt,
- int maxt, const SkPoint& maxPt, unsigned ptIndex);
- SkScalar compute_cubic_segs(const SkPoint pts[3], SkScalar distance,
- int mint, int maxt, unsigned ptIndex);
- const Segment* distanceToSegment(SkScalar distance, SkScalar* t);
- bool quad_too_curvy(const SkPoint pts[3]);
- bool conic_too_curvy(const SkPoint& firstPt, const SkPoint& midTPt,const SkPoint& lastPt);
- bool cheap_dist_exceeds_limit(const SkPoint& pt, SkScalar x, SkScalar y);
- bool cubic_too_curvy(const SkPoint pts[4]);
+ SkContourMeasureIter fIter;
+ sk_sp<SkContourMeasure> fContour;
};
#endif
diff --git a/src/core/SkContourMeasure.cpp b/src/core/SkContourMeasure.cpp
new file mode 100644
index 0000000..5252655
--- /dev/null
+++ b/src/core/SkContourMeasure.cpp
@@ -0,0 +1,637 @@
+/*
+ * Copyright 2018 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkContourMeasure.h"
+#include "SkPathMeasurePriv.h"
+#include "SkGeometry.h"
+#include "SkPath.h"
+#include "SkTSearch.h"
+
+#define kMaxTValue 0x3FFFFFFF
+
+static inline SkScalar tValue2Scalar(int t) {
+ SkASSERT((unsigned)t <= kMaxTValue);
+ const SkScalar kMaxTReciprocal = 1.0f / kMaxTValue;
+ return t * kMaxTReciprocal;
+}
+
+SkScalar SkContourMeasure::Segment::getScalarT() const {
+ return tValue2Scalar(fTValue);
+}
+
+void SkContourMeasure_segTo(const SkPoint pts[], unsigned segType,
+ SkScalar startT, SkScalar stopT, SkPath* dst) {
+ SkASSERT(startT >= 0 && startT <= SK_Scalar1);
+ SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
+ SkASSERT(startT <= stopT);
+
+ if (startT == stopT) {
+ if (!dst->isEmpty()) {
+ /* if the dash as a zero-length on segment, add a corresponding zero-length line.
+ The stroke code will add end caps to zero length lines as appropriate */
+ SkPoint lastPt;
+ SkAssertResult(dst->getLastPt(&lastPt));
+ dst->lineTo(lastPt);
+ }
+ return;
+ }
+
+ SkPoint tmp0[7], tmp1[7];
+
+ switch (segType) {
+ case kLine_SegType:
+ if (SK_Scalar1 == stopT) {
+ dst->lineTo(pts[1]);
+ } else {
+ dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
+ SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
+ }
+ break;
+ case kQuad_SegType:
+ if (0 == startT) {
+ if (SK_Scalar1 == stopT) {
+ dst->quadTo(pts[1], pts[2]);
+ } else {
+ SkChopQuadAt(pts, tmp0, stopT);
+ dst->quadTo(tmp0[1], tmp0[2]);
+ }
+ } else {
+ SkChopQuadAt(pts, tmp0, startT);
+ if (SK_Scalar1 == stopT) {
+ dst->quadTo(tmp0[3], tmp0[4]);
+ } else {
+ SkChopQuadAt(&tmp0[2], tmp1, (stopT - startT) / (1 - startT));
+ dst->quadTo(tmp1[1], tmp1[2]);
+ }
+ }
+ break;
+ case kConic_SegType: {
+ SkConic conic(pts[0], pts[2], pts[3], pts[1].fX);
+
+ if (0 == startT) {
+ if (SK_Scalar1 == stopT) {
+ dst->conicTo(conic.fPts[1], conic.fPts[2], conic.fW);
+ } else {
+ SkConic tmp[2];
+ if (conic.chopAt(stopT, tmp)) {
+ dst->conicTo(tmp[0].fPts[1], tmp[0].fPts[2], tmp[0].fW);
+ }
+ }
+ } else {
+ if (SK_Scalar1 == stopT) {
+ SkConic tmp1[2];
+ if (conic.chopAt(startT, tmp1)) {
+ dst->conicTo(tmp1[1].fPts[1], tmp1[1].fPts[2], tmp1[1].fW);
+ }
+ } else {
+ SkConic tmp;
+ conic.chopAt(startT, stopT, &tmp);
+ dst->conicTo(tmp.fPts[1], tmp.fPts[2], tmp.fW);
+ }
+ }
+ } break;
+ case kCubic_SegType:
+ if (0 == startT) {
+ if (SK_Scalar1 == stopT) {
+ dst->cubicTo(pts[1], pts[2], pts[3]);
+ } else {
+ SkChopCubicAt(pts, tmp0, stopT);
+ dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
+ }
+ } else {
+ SkChopCubicAt(pts, tmp0, startT);
+ if (SK_Scalar1 == stopT) {
+ dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
+ } else {
+ SkChopCubicAt(&tmp0[3], tmp1, (stopT - startT) / (1 - startT));
+ dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
+ }
+ }
+ break;
+ default:
+ SK_ABORT("unknown segType");
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+static inline int tspan_big_enough(int tspan) {
+ SkASSERT((unsigned)tspan <= kMaxTValue);
+ return tspan >> 10;
+}
+
+// can't use tangents, since we need [0..1..................2] to be seen
+// as definitely not a line (it is when drawn, but not parametrically)
+// so we compare midpoints
+#define CHEAP_DIST_LIMIT (SK_Scalar1/2) // just made this value up
+
+static bool quad_too_curvy(const SkPoint pts[3], SkScalar tolerance) {
+ // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
+ // diff = -a/4 + b/2 - c/4
+ SkScalar dx = SkScalarHalf(pts[1].fX) -
+ SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
+ SkScalar dy = SkScalarHalf(pts[1].fY) -
+ SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
+
+ SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy));
+ return dist > tolerance;
+}
+
+static bool conic_too_curvy(const SkPoint& firstPt, const SkPoint& midTPt,
+ const SkPoint& lastPt, SkScalar tolerance) {
+ SkPoint midEnds = firstPt + lastPt;
+ midEnds *= 0.5f;
+ SkVector dxy = midTPt - midEnds;
+ SkScalar dist = SkMaxScalar(SkScalarAbs(dxy.fX), SkScalarAbs(dxy.fY));
+ return dist > tolerance;
+}
+
+static bool cheap_dist_exceeds_limit(const SkPoint& pt, SkScalar x, SkScalar y,
+ SkScalar tolerance) {
+ SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
+ // just made up the 1/2
+ return dist > tolerance;
+}
+
+static bool cubic_too_curvy(const SkPoint pts[4], SkScalar tolerance) {
+ return cheap_dist_exceeds_limit(pts[1],
+ SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
+ SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3), tolerance)
+ ||
+ cheap_dist_exceeds_limit(pts[2],
+ SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
+ SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3), tolerance);
+}
+
+SkScalar SkContourMeasureIter::compute_quad_segs(const SkPoint pts[3], SkScalar distance,
+ int mint, int maxt, unsigned ptIndex) {
+#if defined(IS_FUZZING_WITH_LIBFUZZER)
+ --fSubdivisionsMax;
+#endif
+ if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts, fTolerance)) {
+ SkPoint tmp[5];
+ int halft = (mint + maxt) >> 1;
+
+ SkChopQuadAtHalf(pts, tmp);
+ distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
+ distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
+ } else {
+ SkScalar d = SkPoint::Distance(pts[0], pts[2]);
+ SkScalar prevD = distance;
+ distance += d;
+ if (distance > prevD) {
+ SkContourMeasure::Segment* seg = fSegments.append();
+ seg->fDistance = distance;
+ seg->fPtIndex = ptIndex;
+ seg->fType = kQuad_SegType;
+ seg->fTValue = maxt;
+ }
+ }
+ return distance;
+}
+
+SkScalar SkContourMeasureIter::compute_conic_segs(const SkConic& conic, SkScalar distance,
+ int mint, const SkPoint& minPt,
+ int maxt, const SkPoint& maxPt,
+ unsigned ptIndex) {
+#if defined(IS_FUZZING_WITH_LIBFUZZER)
+ --fSubdivisionsMax;
+#endif
+ int halft = (mint + maxt) >> 1;
+ SkPoint halfPt = conic.evalAt(tValue2Scalar(halft));
+ if (!halfPt.isFinite()) {
+ return distance;
+ }
+ if (tspan_big_enough(maxt - mint) && conic_too_curvy(minPt, halfPt, maxPt, fTolerance)) {
+ distance = this->compute_conic_segs(conic, distance, mint, minPt, halft, halfPt, ptIndex);
+ distance = this->compute_conic_segs(conic, distance, halft, halfPt, maxt, maxPt, ptIndex);
+ } else {
+ SkScalar d = SkPoint::Distance(minPt, maxPt);
+ SkScalar prevD = distance;
+ distance += d;
+ if (distance > prevD) {
+ SkContourMeasure::Segment* seg = fSegments.append();
+ seg->fDistance = distance;
+ seg->fPtIndex = ptIndex;
+ seg->fType = kConic_SegType;
+ seg->fTValue = maxt;
+ }
+ }
+ return distance;
+}
+
+SkScalar SkContourMeasureIter::compute_cubic_segs(const SkPoint pts[4], SkScalar distance,
+ int mint, int maxt, unsigned ptIndex) {
+#if defined(IS_FUZZING_WITH_LIBFUZZER)
+ --fSubdivisionsMax;
+#endif
+ if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts, fTolerance)) {
+ SkPoint tmp[7];
+ int halft = (mint + maxt) >> 1;
+
+ SkChopCubicAtHalf(pts, tmp);
+ distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
+ distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
+ } else {
+ SkScalar d = SkPoint::Distance(pts[0], pts[3]);
+ SkScalar prevD = distance;
+ distance += d;
+ if (distance > prevD) {
+ SkContourMeasure::Segment* seg = fSegments.append();
+ seg->fDistance = distance;
+ seg->fPtIndex = ptIndex;
+ seg->fType = kCubic_SegType;
+ seg->fTValue = maxt;
+ }
+ }
+ return distance;
+}
+
+SkContourMeasure* SkContourMeasureIter::buildSegments() {
+ SkPoint pts[4];
+ int ptIndex = -1;
+ SkScalar distance = 0;
+ bool isClosed = fForceClosed;
+ bool firstMoveTo = true;
+ SkContourMeasure::Segment* seg;
+
+ /* Note:
+ * as we accumulate distance, we have to check that the result of +=
+ * actually made it larger, since a very small delta might be > 0, but
+ * still have no effect on distance (if distance >>> delta).
+ *
+ * We do this check below, and in compute_quad_segs and compute_cubic_segs
+ */
+ fSegments.reset();
+ bool done = false;
+ #if defined(IS_FUZZING_WITH_LIBFUZZER)
+ fSubdivisionsMax = 10000000;
+#endif
+ do {
+ if (!firstMoveTo && fIter.peekVerb() == SkPath::kMove_Verb) {
+ break;
+ }
+ switch (fIter.next(pts)) {
+ case SkPath::kMove_Verb:
+ ptIndex += 1;
+ fPts.append(1, pts);
+ SkASSERT(firstMoveTo);
+ firstMoveTo = false;
+ break;
+
+ case SkPath::kLine_Verb: {
+ SkScalar d = SkPoint::Distance(pts[0], pts[1]);
+ SkASSERT(d >= 0);
+ SkScalar prevD = distance;
+ distance += d;
+ if (distance > prevD) {
+ seg = fSegments.append();
+ seg->fDistance = distance;
+ seg->fPtIndex = ptIndex;
+ seg->fType = kLine_SegType;
+ seg->fTValue = kMaxTValue;
+ fPts.append(1, pts + 1);
+ ptIndex++;
+ }
+ } break;
+
+ case SkPath::kQuad_Verb: {
+ SkScalar prevD = distance;
+ distance = this->compute_quad_segs(pts, distance, 0, kMaxTValue, ptIndex);
+ if (distance > prevD) {
+ fPts.append(2, pts + 1);
+ ptIndex += 2;
+ }
+ } break;
+
+ case SkPath::kConic_Verb: {
+ const SkConic conic(pts, fIter.conicWeight());
+ SkScalar prevD = distance;
+ distance = this->compute_conic_segs(conic, distance, 0, conic.fPts[0],
+ kMaxTValue, conic.fPts[2], ptIndex);
+ if (distance > prevD) {
+ // we store the conic weight in our next point, followed by the last 2 pts
+ // thus to reconstitue a conic, you'd need to say
+ // SkConic(pts[0], pts[2], pts[3], weight = pts[1].fX)
+ fPts.append()->set(conic.fW, 0);
+ fPts.append(2, pts + 1);
+ ptIndex += 3;
+ }
+ } break;
+
+ case SkPath::kCubic_Verb: {
+ SkScalar prevD = distance;
+ distance = this->compute_cubic_segs(pts, distance, 0, kMaxTValue, ptIndex);
+ if (distance > prevD) {
+ fPts.append(3, pts + 1);
+ ptIndex += 3;
+ }
+ } break;
+
+ case SkPath::kClose_Verb:
+ isClosed = true;
+ break;
+
+ case SkPath::kDone_Verb:
+ done = true;
+ break;
+ }
+#if defined(IS_FUZZING_WITH_LIBFUZZER)
+ if (fSubdivisionsMax < 0) {
+ return nullptr;
+ }
+#endif
+
+ } while (!done);
+
+ if (!SkScalarIsFinite(distance)) {
+ return nullptr;
+ }
+ if (fSegments.count() == 0) {
+ return nullptr;
+ }
+#if defined(IS_FUZZING_WITH_LIBFUZZER)
+ if (fSubdivisionsMax < 0) {
+ return nullptr;
+ }
+#endif
+
+#ifdef SK_DEBUG
+ {
+ const SkContourMeasure::Segment* seg = fSegments.begin();
+ const SkContourMeasure::Segment* stop = fSegments.end();
+ unsigned ptIndex = 0;
+ SkScalar distance = 0;
+ // limit the loop to a reasonable number; pathological cases can run for minutes
+ int maxChecks = 10000000; // set to INT_MAX to defeat the check
+ while (seg < stop) {
+ SkASSERT(seg->fDistance > distance);
+ SkASSERT(seg->fPtIndex >= ptIndex);
+ SkASSERT(seg->fTValue > 0);
+
+ const SkContourMeasure::Segment* s = seg;
+ while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex && --maxChecks > 0) {
+ SkASSERT(s[0].fType == s[1].fType);
+ SkASSERT(s[0].fTValue < s[1].fTValue);
+ s += 1;
+ }
+
+ distance = seg->fDistance;
+ ptIndex = seg->fPtIndex;
+ seg += 1;
+ }
+ // SkDebugf("\n");
+ }
+#endif
+
+ return new SkContourMeasure(std::move(fSegments), std::move(fPts), distance, isClosed);
+}
+
+static void compute_pos_tan(const SkPoint pts[], unsigned segType,
+ SkScalar t, SkPoint* pos, SkVector* tangent) {
+ switch (segType) {
+ case kLine_SegType:
+ if (pos) {
+ pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
+ SkScalarInterp(pts[0].fY, pts[1].fY, t));
+ }
+ if (tangent) {
+ tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
+ }
+ break;
+ case kQuad_SegType:
+ SkEvalQuadAt(pts, t, pos, tangent);
+ if (tangent) {
+ tangent->normalize();
+ }
+ break;
+ case kConic_SegType: {
+ SkConic(pts[0], pts[2], pts[3], pts[1].fX).evalAt(t, pos, tangent);
+ if (tangent) {
+ tangent->normalize();
+ }
+ } break;
+ case kCubic_SegType:
+ SkEvalCubicAt(pts, t, pos, tangent, nullptr);
+ if (tangent) {
+ tangent->normalize();
+ }
+ break;
+ default:
+ SkDEBUGFAIL("unknown segType");
+ }
+}
+
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+SkContourMeasureIter::SkContourMeasureIter() {
+ fTolerance = CHEAP_DIST_LIMIT;
+ fForceClosed = false;
+}
+
+SkContourMeasureIter::SkContourMeasureIter(const SkPath& path, bool forceClosed,
+ SkScalar resScale) {
+ fPath = path.isFinite() ? path : SkPath();
+ fTolerance = CHEAP_DIST_LIMIT * SkScalarInvert(resScale);
+ fForceClosed = forceClosed;
+
+ fIter.setPath(fPath, forceClosed);
+}
+
+SkContourMeasureIter::~SkContourMeasureIter() {}
+
+/** Assign a new path, or null to have none.
+*/
+void SkContourMeasureIter::reset(const SkPath& path, bool forceClosed, SkScalar resScale) {
+ if (path.isFinite()) {
+ fPath = path;
+ } else {
+ fPath.reset();
+ }
+ fForceClosed = forceClosed;
+
+ fIter.setPath(fPath, forceClosed);
+ fSegments.reset();
+ fPts.reset();
+}
+
+sk_sp<SkContourMeasure> SkContourMeasureIter::next() {
+ while (fIter.peekVerb() != SkPath::kDone_Verb) {
+ auto cm = this->buildSegments();
+ if (cm) {
+ return sk_sp<SkContourMeasure>(cm);
+ }
+ }
+ return nullptr;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+SkContourMeasure::SkContourMeasure(SkTDArray<Segment>&& segs, SkTDArray<SkPoint>&& pts, SkScalar length, bool isClosed)
+ : fSegments(std::move(segs))
+ , fPts(std::move(pts))
+ , fLength(length)
+ , fIsClosed(isClosed)
+ {}
+
+template <typename T, typename K>
+int SkTKSearch(const T base[], int count, const K& key) {
+ SkASSERT(count >= 0);
+ if (count <= 0) {
+ return ~0;
+ }
+
+ SkASSERT(base != nullptr); // base may be nullptr if count is zero
+
+ unsigned lo = 0;
+ unsigned hi = count - 1;
+
+ while (lo < hi) {
+ unsigned mid = (hi + lo) >> 1;
+ if (base[mid].fDistance < key) {
+ lo = mid + 1;
+ } else {
+ hi = mid;
+ }
+ }
+
+ if (base[hi].fDistance < key) {
+ hi += 1;
+ hi = ~hi;
+ } else if (key < base[hi].fDistance) {
+ hi = ~hi;
+ }
+ return hi;
+}
+
+const SkContourMeasure::Segment* SkContourMeasure::distanceToSegment( SkScalar distance,
+ SkScalar* t) const {
+ SkDEBUGCODE(SkScalar length = ) this->length();
+ SkASSERT(distance >= 0 && distance <= length);
+
+ const Segment* seg = fSegments.begin();
+ int count = fSegments.count();
+
+ int index = SkTKSearch<Segment, SkScalar>(seg, count, distance);
+ // don't care if we hit an exact match or not, so we xor index if it is negative
+ index ^= (index >> 31);
+ seg = &seg[index];
+
+ // now interpolate t-values with the prev segment (if possible)
+ SkScalar startT = 0, startD = 0;
+ // check if the prev segment is legal, and references the same set of points
+ if (index > 0) {
+ startD = seg[-1].fDistance;
+ if (seg[-1].fPtIndex == seg->fPtIndex) {
+ SkASSERT(seg[-1].fType == seg->fType);
+ startT = seg[-1].getScalarT();
+ }
+ }
+
+ SkASSERT(seg->getScalarT() > startT);
+ SkASSERT(distance >= startD);
+ SkASSERT(seg->fDistance > startD);
+
+ *t = startT + (seg->getScalarT() - startT) * (distance - startD) / (seg->fDistance - startD);
+ return seg;
+}
+
+bool SkContourMeasure::getPosTan(SkScalar distance, SkPoint* pos, SkVector* tangent) const {
+ if (SkScalarIsNaN(distance)) {
+ return false;
+ }
+
+ const SkScalar length = this->length();
+ SkASSERT(length > 0 && fSegments.count() > 0);
+
+ // pin the distance to a legal range
+ if (distance < 0) {
+ distance = 0;
+ } else if (distance > length) {
+ distance = length;
+ }
+
+ SkScalar t;
+ const Segment* seg = this->distanceToSegment(distance, &t);
+ if (SkScalarIsNaN(t)) {
+ return false;
+ }
+
+ compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
+ return true;
+}
+
+bool SkContourMeasure::getMatrix(SkScalar distance, SkMatrix* matrix, MatrixFlags flags) const {
+ SkPoint position;
+ SkVector tangent;
+
+ if (this->getPosTan(distance, &position, &tangent)) {
+ if (matrix) {
+ if (flags & kGetTangent_MatrixFlag) {
+ matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
+ } else {
+ matrix->reset();
+ }
+ if (flags & kGetPosition_MatrixFlag) {
+ matrix->postTranslate(position.fX, position.fY);
+ }
+ }
+ return true;
+ }
+ return false;
+}
+
+bool SkContourMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
+ bool startWithMoveTo) const {
+ SkASSERT(dst);
+
+ SkScalar length = this->length(); // ensure we have built our segments
+
+ if (startD < 0) {
+ startD = 0;
+ }
+ if (stopD > length) {
+ stopD = length;
+ }
+ if (!(startD <= stopD)) { // catch NaN values as well
+ return false;
+ }
+ if (!fSegments.count()) {
+ return false;
+ }
+
+ SkPoint p;
+ SkScalar startT, stopT;
+ const Segment* seg = this->distanceToSegment(startD, &startT);
+ if (!SkScalarIsFinite(startT)) {
+ return false;
+ }
+ const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
+ if (!SkScalarIsFinite(stopT)) {
+ return false;
+ }
+ SkASSERT(seg <= stopSeg);
+ if (startWithMoveTo) {
+ compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, nullptr);
+ dst->moveTo(p);
+ }
+
+ if (seg->fPtIndex == stopSeg->fPtIndex) {
+ SkContourMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
+ } else {
+ do {
+ SkContourMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
+ seg = SkContourMeasure::Segment::Next(seg);
+ startT = 0;
+ } while (seg->fPtIndex < stopSeg->fPtIndex);
+ SkContourMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
+ }
+
+ return true;
+}
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 6feafd8..9650849 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -1959,6 +1959,13 @@
return false;
}
+SkPath::Verb SkPath::Iter::peekVerb() const {
+ if (fVerbs == nullptr || fVerbs == fVerbStop) {
+ return kDone_Verb;
+ }
+ return (Verb)fVerbs[-1];
+}
+
SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
SkASSERT(pts);
if (fLastPt != fMoveTo) {
diff --git a/src/core/SkPathMeasure.cpp b/src/core/SkPathMeasure.cpp
index 43a3168..17506e9 100644
--- a/src/core/SkPathMeasure.cpp
+++ b/src/core/SkPathMeasure.cpp
@@ -5,733 +5,49 @@
* found in the LICENSE file.
*/
-
#include "SkPathMeasure.h"
-#include "SkPathMeasurePriv.h"
-#include "SkGeometry.h"
-#include "SkPath.h"
-#include "SkTSearch.h"
+#include "SkContourMeasure.h"
-#define kMaxTValue 0x3FFFFFFF
+SkPathMeasure::SkPathMeasure() {}
-static inline SkScalar tValue2Scalar(int t) {
- SkASSERT((unsigned)t <= kMaxTValue);
- const SkScalar kMaxTReciprocal = 1.0f / kMaxTValue;
- return t * kMaxTReciprocal;
-}
-
-SkScalar SkPathMeasure::Segment::getScalarT() const {
- return tValue2Scalar(fTValue);
-}
-
-const SkPathMeasure::Segment* SkPathMeasure::NextSegment(const Segment* seg) {
- unsigned ptIndex = seg->fPtIndex;
-
- do {
- ++seg;
- } while (seg->fPtIndex == ptIndex);
- return seg;
-}
-
-void SkPathMeasure_segTo(const SkPoint pts[], unsigned segType,
- SkScalar startT, SkScalar stopT, SkPath* dst) {
- SkASSERT(startT >= 0 && startT <= SK_Scalar1);
- SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
- SkASSERT(startT <= stopT);
-
- if (startT == stopT) {
- if (!dst->isEmpty()) {
- /* if the dash as a zero-length on segment, add a corresponding zero-length line.
- The stroke code will add end caps to zero length lines as appropriate */
- SkPoint lastPt;
- SkAssertResult(dst->getLastPt(&lastPt));
- dst->lineTo(lastPt);
- }
- return;
- }
-
- SkPoint tmp0[7], tmp1[7];
-
- switch (segType) {
- case kLine_SegType:
- if (SK_Scalar1 == stopT) {
- dst->lineTo(pts[1]);
- } else {
- dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
- SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
- }
- break;
- case kQuad_SegType:
- if (0 == startT) {
- if (SK_Scalar1 == stopT) {
- dst->quadTo(pts[1], pts[2]);
- } else {
- SkChopQuadAt(pts, tmp0, stopT);
- dst->quadTo(tmp0[1], tmp0[2]);
- }
- } else {
- SkChopQuadAt(pts, tmp0, startT);
- if (SK_Scalar1 == stopT) {
- dst->quadTo(tmp0[3], tmp0[4]);
- } else {
- SkChopQuadAt(&tmp0[2], tmp1, (stopT - startT) / (1 - startT));
- dst->quadTo(tmp1[1], tmp1[2]);
- }
- }
- break;
- case kConic_SegType: {
- SkConic conic(pts[0], pts[2], pts[3], pts[1].fX);
-
- if (0 == startT) {
- if (SK_Scalar1 == stopT) {
- dst->conicTo(conic.fPts[1], conic.fPts[2], conic.fW);
- } else {
- SkConic tmp[2];
- if (conic.chopAt(stopT, tmp)) {
- dst->conicTo(tmp[0].fPts[1], tmp[0].fPts[2], tmp[0].fW);
- }
- }
- } else {
- if (SK_Scalar1 == stopT) {
- SkConic tmp1[2];
- if (conic.chopAt(startT, tmp1)) {
- dst->conicTo(tmp1[1].fPts[1], tmp1[1].fPts[2], tmp1[1].fW);
- }
- } else {
- SkConic tmp;
- conic.chopAt(startT, stopT, &tmp);
- dst->conicTo(tmp.fPts[1], tmp.fPts[2], tmp.fW);
- }
- }
- } break;
- case kCubic_SegType:
- if (0 == startT) {
- if (SK_Scalar1 == stopT) {
- dst->cubicTo(pts[1], pts[2], pts[3]);
- } else {
- SkChopCubicAt(pts, tmp0, stopT);
- dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
- }
- } else {
- SkChopCubicAt(pts, tmp0, startT);
- if (SK_Scalar1 == stopT) {
- dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
- } else {
- SkChopCubicAt(&tmp0[3], tmp1, (stopT - startT) / (1 - startT));
- dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
- }
- }
- break;
- default:
- SK_ABORT("unknown segType");
- }
-}
-
-///////////////////////////////////////////////////////////////////////////////
-
-static inline int tspan_big_enough(int tspan) {
- SkASSERT((unsigned)tspan <= kMaxTValue);
- return tspan >> 10;
-}
-
-// can't use tangents, since we need [0..1..................2] to be seen
-// as definitely not a line (it is when drawn, but not parametrically)
-// so we compare midpoints
-#define CHEAP_DIST_LIMIT (SK_Scalar1/2) // just made this value up
-
-bool SkPathMeasure::quad_too_curvy(const SkPoint pts[3]) {
- // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
- // diff = -a/4 + b/2 - c/4
- SkScalar dx = SkScalarHalf(pts[1].fX) -
- SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
- SkScalar dy = SkScalarHalf(pts[1].fY) -
- SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
-
- SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy));
- return dist > fTolerance;
-}
-
-bool SkPathMeasure::conic_too_curvy(const SkPoint& firstPt, const SkPoint& midTPt,
- const SkPoint& lastPt) {
- SkPoint midEnds = firstPt + lastPt;
- midEnds *= 0.5f;
- SkVector dxy = midTPt - midEnds;
- SkScalar dist = SkMaxScalar(SkScalarAbs(dxy.fX), SkScalarAbs(dxy.fY));
- return dist > fTolerance;
-}
-
-bool SkPathMeasure::cheap_dist_exceeds_limit(const SkPoint& pt,
- SkScalar x, SkScalar y) {
- SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
- // just made up the 1/2
- return dist > fTolerance;
-}
-
-bool SkPathMeasure::cubic_too_curvy(const SkPoint pts[4]) {
- return cheap_dist_exceeds_limit(pts[1],
- SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
- SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3))
- ||
- cheap_dist_exceeds_limit(pts[2],
- SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
- SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3));
-}
-
-static SkScalar quad_folded_len(const SkPoint pts[3]) {
- SkScalar t = SkFindQuadMaxCurvature(pts);
- SkPoint pt = SkEvalQuadAt(pts, t);
- SkVector a = pts[2] - pt;
- SkScalar result = a.length();
- if (0 != t && 1 != t) {
- SkVector b = pts[0] - pt;
- result += b.length();
- }
- SkASSERT(SkScalarIsFinite(result));
- return result;
-}
-
-/* from http://www.malczak.linuxpl.com/blog/quadratic-bezier-curve-length/ */
-/* This works -- more needs to be done to see if it is performant on all platforms.
- To use this to measure parts of quads requires recomputing everything -- perhaps
- a chop-like interface can start from a larger measurement and get two new measurements
- with one call here.
- */
-static SkScalar compute_quad_len(const SkPoint pts[3]) {
- SkPoint a,b;
- a.fX = pts[0].fX - 2 * pts[1].fX + pts[2].fX;
- a.fY = pts[0].fY - 2 * pts[1].fY + pts[2].fY;
- SkScalar A = 4 * (a.fX * a.fX + a.fY * a.fY);
- if (0 == A) {
- a = pts[2] - pts[0];
- return a.length();
- }
- b.fX = 2 * (pts[1].fX - pts[0].fX);
- b.fY = 2 * (pts[1].fY - pts[0].fY);
- SkScalar B = 4 * (a.fX * b.fX + a.fY * b.fY);
- SkScalar C = b.fX * b.fX + b.fY * b.fY;
- SkScalar Sabc = 2 * SkScalarSqrt(A + B + C);
- SkScalar A_2 = SkScalarSqrt(A);
- SkScalar A_32 = 2 * A * A_2;
- SkScalar C_2 = 2 * SkScalarSqrt(C);
- SkScalar BA = B / A_2;
- if (0 == BA + C_2) {
- return quad_folded_len(pts);
- }
- SkScalar J = A_32 * Sabc + A_2 * B * (Sabc - C_2);
- SkScalar K = 4 * C * A - B * B;
- SkScalar L = (2 * A_2 + BA + Sabc) / (BA + C_2);
- if (L <= 0) {
- return quad_folded_len(pts);
- }
- SkScalar M = SkScalarLog(L);
- SkScalar result = (J + K * M) / (4 * A_32);
- SkASSERT(SkScalarIsFinite(result));
- return result;
-}
-
-SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3],
- SkScalar distance, int mint, int maxt, unsigned ptIndex) {
-#if defined(IS_FUZZING_WITH_LIBFUZZER)
- --fSubdivisionsMax;
-#endif
- if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) {
- SkPoint tmp[5];
- int halft = (mint + maxt) >> 1;
-
- SkChopQuadAtHalf(pts, tmp);
- distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
- distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
- } else {
- SkScalar d = SkPoint::Distance(pts[0], pts[2]);
- SkScalar prevD = distance;
- distance += d;
- if (distance > prevD) {
- Segment* seg = fSegments.append();
- seg->fDistance = distance;
- seg->fPtIndex = ptIndex;
- seg->fType = kQuad_SegType;
- seg->fTValue = maxt;
- }
- }
- return distance;
-}
-
-SkScalar SkPathMeasure::compute_conic_segs(const SkConic& conic, SkScalar distance,
- int mint, const SkPoint& minPt,
- int maxt, const SkPoint& maxPt, unsigned ptIndex) {
-#if defined(IS_FUZZING_WITH_LIBFUZZER)
- --fSubdivisionsMax;
-#endif
- int halft = (mint + maxt) >> 1;
- SkPoint halfPt = conic.evalAt(tValue2Scalar(halft));
- if (!halfPt.isFinite()) {
- return distance;
- }
- if (tspan_big_enough(maxt - mint) && conic_too_curvy(minPt, halfPt, maxPt)) {
- distance = this->compute_conic_segs(conic, distance, mint, minPt, halft, halfPt, ptIndex);
- distance = this->compute_conic_segs(conic, distance, halft, halfPt, maxt, maxPt, ptIndex);
- } else {
- SkScalar d = SkPoint::Distance(minPt, maxPt);
- SkScalar prevD = distance;
- distance += d;
- if (distance > prevD) {
- Segment* seg = fSegments.append();
- seg->fDistance = distance;
- seg->fPtIndex = ptIndex;
- seg->fType = kConic_SegType;
- seg->fTValue = maxt;
- }
- }
- return distance;
-}
-
-SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4],
- SkScalar distance, int mint, int maxt, unsigned ptIndex) {
-#if defined(IS_FUZZING_WITH_LIBFUZZER)
- --fSubdivisionsMax;
-#endif
- if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) {
- SkPoint tmp[7];
- int halft = (mint + maxt) >> 1;
-
- SkChopCubicAtHalf(pts, tmp);
- distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
- distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
- } else {
- SkScalar d = SkPoint::Distance(pts[0], pts[3]);
- SkScalar prevD = distance;
- distance += d;
- if (distance > prevD) {
- Segment* seg = fSegments.append();
- seg->fDistance = distance;
- seg->fPtIndex = ptIndex;
- seg->fType = kCubic_SegType;
- seg->fTValue = maxt;
- }
- }
- return distance;
-}
-
-void SkPathMeasure::buildSegments() {
- SkPoint pts[4];
- unsigned ptIndex = fFirstPtIndex;
- SkScalar distance = 0;
- bool isClosed = fForceClosed;
- bool firstMoveTo = ptIndex == (unsigned) -1;
- Segment* seg;
-
- /* Note:
- * as we accumulate distance, we have to check that the result of +=
- * actually made it larger, since a very small delta might be > 0, but
- * still have no effect on distance (if distance >>> delta).
- *
- * We do this check below, and in compute_quad_segs and compute_cubic_segs
- */
- fSegments.reset();
- bool done = false;
- #if defined(IS_FUZZING_WITH_LIBFUZZER)
- fSubdivisionsMax = 10000000;
-#endif
- do {
- switch (fIter.next(pts)) {
- case SkPath::kMove_Verb:
- ptIndex += 1;
- fPts.append(1, pts);
- if (!firstMoveTo) {
- done = true;
- break;
- }
- firstMoveTo = false;
- break;
-
- case SkPath::kLine_Verb: {
- SkScalar d = SkPoint::Distance(pts[0], pts[1]);
- SkASSERT(d >= 0);
- SkScalar prevD = distance;
- distance += d;
- if (distance > prevD) {
- seg = fSegments.append();
- seg->fDistance = distance;
- seg->fPtIndex = ptIndex;
- seg->fType = kLine_SegType;
- seg->fTValue = kMaxTValue;
- fPts.append(1, pts + 1);
- ptIndex++;
- }
- } break;
-
- case SkPath::kQuad_Verb: {
- SkScalar prevD = distance;
- if (false) {
- SkScalar length = compute_quad_len(pts);
- if (length) {
- distance += length;
- Segment* seg = fSegments.append();
- seg->fDistance = distance;
- seg->fPtIndex = ptIndex;
- seg->fType = kQuad_SegType;
- seg->fTValue = kMaxTValue;
- }
- } else {
- distance = this->compute_quad_segs(pts, distance, 0, kMaxTValue, ptIndex);
- }
- if (distance > prevD) {
- fPts.append(2, pts + 1);
- ptIndex += 2;
- }
- } break;
-
- case SkPath::kConic_Verb: {
- const SkConic conic(pts, fIter.conicWeight());
- SkScalar prevD = distance;
- distance = this->compute_conic_segs(conic, distance, 0, conic.fPts[0],
- kMaxTValue, conic.fPts[2], ptIndex);
- if (distance > prevD) {
- // we store the conic weight in our next point, followed by the last 2 pts
- // thus to reconstitue a conic, you'd need to say
- // SkConic(pts[0], pts[2], pts[3], weight = pts[1].fX)
- fPts.append()->set(conic.fW, 0);
- fPts.append(2, pts + 1);
- ptIndex += 3;
- }
- } break;
-
- case SkPath::kCubic_Verb: {
- SkScalar prevD = distance;
- distance = this->compute_cubic_segs(pts, distance, 0, kMaxTValue, ptIndex);
- if (distance > prevD) {
- fPts.append(3, pts + 1);
- ptIndex += 3;
- }
- } break;
-
- case SkPath::kClose_Verb:
- isClosed = true;
- break;
-
- case SkPath::kDone_Verb:
- done = true;
- break;
- }
-#if defined(IS_FUZZING_WITH_LIBFUZZER)
- if (fSubdivisionsMax < 0) {
- fLength = 0;
- return;
- }
-#endif
-
- } while (!done);
-
- fLength = distance;
- fIsClosed = isClosed;
- fFirstPtIndex = ptIndex;
-
-#ifdef SK_DEBUG
- {
- const Segment* seg = fSegments.begin();
- const Segment* stop = fSegments.end();
- unsigned ptIndex = 0;
- SkScalar distance = 0;
- // limit the loop to a reasonable number; pathological cases can run for minutes
- int maxChecks = 10000000; // set to INT_MAX to defeat the check
- while (seg < stop) {
- SkASSERT(seg->fDistance > distance);
- SkASSERT(seg->fPtIndex >= ptIndex);
- SkASSERT(seg->fTValue > 0);
-
- const Segment* s = seg;
- while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex && --maxChecks > 0) {
- SkASSERT(s[0].fType == s[1].fType);
- SkASSERT(s[0].fTValue < s[1].fTValue);
- s += 1;
- }
-
- distance = seg->fDistance;
- ptIndex = seg->fPtIndex;
- seg += 1;
- }
- // SkDebugf("\n");
- }
-#endif
-}
-
-static void compute_pos_tan(const SkPoint pts[], unsigned segType,
- SkScalar t, SkPoint* pos, SkVector* tangent) {
- switch (segType) {
- case kLine_SegType:
- if (pos) {
- pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
- SkScalarInterp(pts[0].fY, pts[1].fY, t));
- }
- if (tangent) {
- tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
- }
- break;
- case kQuad_SegType:
- SkEvalQuadAt(pts, t, pos, tangent);
- if (tangent) {
- tangent->normalize();
- }
- break;
- case kConic_SegType: {
- SkConic(pts[0], pts[2], pts[3], pts[1].fX).evalAt(t, pos, tangent);
- if (tangent) {
- tangent->normalize();
- }
- } break;
- case kCubic_SegType:
- SkEvalCubicAt(pts, t, pos, tangent, nullptr);
- if (tangent) {
- tangent->normalize();
- }
- break;
- default:
- SkDEBUGFAIL("unknown segType");
- }
-}
-
-
-////////////////////////////////////////////////////////////////////////////////
-////////////////////////////////////////////////////////////////////////////////
-
-SkPathMeasure::SkPathMeasure() {
- fTolerance = CHEAP_DIST_LIMIT;
- fLength = -1; // signal we need to compute it
- fForceClosed = false;
- fFirstPtIndex = -1;
-}
-
-SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed, SkScalar resScale) {
- fPath = path.isFinite() ? path : SkPath();
- fTolerance = CHEAP_DIST_LIMIT * SkScalarInvert(resScale);
- fLength = -1; // signal we need to compute it
- fForceClosed = forceClosed;
- fFirstPtIndex = -1;
-
- fIter.setPath(fPath, forceClosed);
+SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed, SkScalar resScale)
+ : fIter(path, forceClosed, resScale)
+{
+ fContour = fIter.next();
}
SkPathMeasure::~SkPathMeasure() {}
-/** Assign a new path, or null to have none.
-*/
void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) {
- if (path && path->isFinite()) {
- fPath = *path;
- } else {
- fPath.reset();
- }
- fLength = -1; // signal we need to compute it
- fForceClosed = forceClosed;
- fFirstPtIndex = -1;
-
- fIter.setPath(fPath, forceClosed);
- fSegments.reset();
- fPts.reset();
+ fIter.reset(path ? *path : SkPath(), forceClosed);
+ fContour = fIter.next();
}
SkScalar SkPathMeasure::getLength() {
- if (fLength < 0) {
- this->buildSegments();
- }
- if (SkScalarIsNaN(fLength)) {
- fLength = 0;
- fSegments.reset(); // may contain inf or NaN, which will fail later
- }
- SkASSERT(fLength >= 0);
- return fLength;
+ return fContour ? fContour->length() : 0;
}
-template <typename T, typename K>
-int SkTKSearch(const T base[], int count, const K& key) {
- SkASSERT(count >= 0);
- if (count <= 0) {
- return ~0;
- }
-
- SkASSERT(base != nullptr); // base may be nullptr if count is zero
-
- unsigned lo = 0;
- unsigned hi = count - 1;
-
- while (lo < hi) {
- unsigned mid = (hi + lo) >> 1;
- if (base[mid].fDistance < key) {
- lo = mid + 1;
- } else {
- hi = mid;
- }
- }
-
- if (base[hi].fDistance < key) {
- hi += 1;
- hi = ~hi;
- } else if (key < base[hi].fDistance) {
- hi = ~hi;
- }
- return hi;
+bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* position, SkVector* tangent) {
+ return fContour && fContour->getPosTan(distance, position, tangent);
}
-const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment(
- SkScalar distance, SkScalar* t) {
- SkDEBUGCODE(SkScalar length = ) this->getLength();
- SkASSERT(distance >= 0 && distance <= length);
-
- const Segment* seg = fSegments.begin();
- int count = fSegments.count();
-
- int index = SkTKSearch<Segment, SkScalar>(seg, count, distance);
- // don't care if we hit an exact match or not, so we xor index if it is negative
- index ^= (index >> 31);
- seg = &seg[index];
-
- // now interpolate t-values with the prev segment (if possible)
- SkScalar startT = 0, startD = 0;
- // check if the prev segment is legal, and references the same set of points
- if (index > 0) {
- startD = seg[-1].fDistance;
- if (seg[-1].fPtIndex == seg->fPtIndex) {
- SkASSERT(seg[-1].fType == seg->fType);
- startT = seg[-1].getScalarT();
- }
- }
-
- SkASSERT(seg->getScalarT() > startT);
- SkASSERT(distance >= startD);
- SkASSERT(seg->fDistance > startD);
-
- *t = startT + (seg->getScalarT() - startT) * (distance - startD) / (seg->fDistance - startD);
- return seg;
+bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix, MatrixFlags flags) {
+ return fContour && fContour->getMatrix(distance, matrix, (SkContourMeasure::MatrixFlags)flags);
}
-bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos, SkVector* tangent) {
- SkScalar length = this->getLength(); // call this to force computing it
- int count = fSegments.count();
-
- if (count == 0 || length == 0 || SkScalarIsNaN(distance)) {
- return false;
- }
-
- // pin the distance to a legal range
- if (distance < 0) {
- distance = 0;
- } else if (distance > length) {
- distance = length;
- }
-
- SkScalar t;
- const Segment* seg = this->distanceToSegment(distance, &t);
- if (SkScalarIsNaN(t)) {
- return false;
- }
-
- compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
- return true;
-}
-
-bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix,
- MatrixFlags flags) {
- SkPoint position;
- SkVector tangent;
-
- if (this->getPosTan(distance, &position, &tangent)) {
- if (matrix) {
- if (flags & kGetTangent_MatrixFlag) {
- matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
- } else {
- matrix->reset();
- }
- if (flags & kGetPosition_MatrixFlag) {
- matrix->postTranslate(position.fX, position.fY);
- }
- }
- return true;
- }
- return false;
-}
-
-bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
- bool startWithMoveTo) {
- SkASSERT(dst);
-
- SkScalar length = this->getLength(); // ensure we have built our segments
-
- if (startD < 0) {
- startD = 0;
- }
- if (stopD > length) {
- stopD = length;
- }
- if (!(startD <= stopD)) { // catch NaN values as well
- return false;
- }
- if (!fSegments.count()) {
- return false;
- }
-
- SkPoint p;
- SkScalar startT, stopT;
- const Segment* seg = this->distanceToSegment(startD, &startT);
- if (!SkScalarIsFinite(startT)) {
- return false;
- }
- const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
- if (!SkScalarIsFinite(stopT)) {
- return false;
- }
- SkASSERT(seg <= stopSeg);
- if (startWithMoveTo) {
- compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, nullptr);
- dst->moveTo(p);
- }
-
- if (seg->fPtIndex == stopSeg->fPtIndex) {
- SkPathMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
- } else {
- do {
- SkPathMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
- seg = SkPathMeasure::NextSegment(seg);
- startT = 0;
- } while (seg->fPtIndex < stopSeg->fPtIndex);
- SkPathMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
- }
-
- return true;
+bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst, bool startWithMoveTo) {
+ return fContour && fContour->getSegment(startD, stopD, dst, startWithMoveTo);
}
bool SkPathMeasure::isClosed() {
- (void)this->getLength(); // make sure we measure the current contour
- return fIsClosed;
+ return fContour && fContour->isClosed();
}
-/** Move to the next contour in the path. Return true if one exists, or false if
- we're done with the path.
-*/
bool SkPathMeasure::nextContour() {
- (void)this->getLength(); // make sure we measure the current contour
-#if defined(IS_FUZZING_WITH_LIBFUZZER)
- if (fSubdivisionsMax < 0) {
- return false;
- }
-#endif
- fLength = -1; // now signal that we should build the next set of segments
- return this->getLength() > 0;
+ fContour = fIter.next();
+ return !!fContour;
}
-///////////////////////////////////////////////////////////////////////////////
-///////////////////////////////////////////////////////////////////////////////
-
#ifdef SK_DEBUG
-
-void SkPathMeasure::dump() {
- SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count());
-
- for (int i = 0; i < fSegments.count(); i++) {
- const Segment* seg = &fSegments[i];
- SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n",
- i, seg->fDistance, seg->fPtIndex, seg->getScalarT(),
- seg->fType);
- }
-}
-
+void SkPathMeasure::dump() {}
#endif
diff --git a/tests/PathMeasureTest.cpp b/tests/PathMeasureTest.cpp
index bc75c5f..c944f86 100644
--- a/tests/PathMeasureTest.cpp
+++ b/tests/PathMeasureTest.cpp
@@ -227,3 +227,67 @@
// only expect 1 contour, even if we didn't explicitly call getLength() ourselves
REPORTER_ASSERT(reporter, !meas.nextContour());
}
+
+#include "SkContourMeasure.h"
+
+static void test_90_degrees(sk_sp<SkContourMeasure> cm, SkScalar radius,
+ skiatest::Reporter* reporter) {
+ SkPoint pos;
+ SkVector tan;
+ SkScalar distance = cm->length() / 4;
+ bool success = cm->getPosTan(distance, &pos, &tan);
+
+ REPORTER_ASSERT(reporter, success);
+ REPORTER_ASSERT(reporter, SkScalarNearlyEqual(pos.fX, 0));
+ REPORTER_ASSERT(reporter, SkScalarNearlyEqual(pos.fY, radius));
+ REPORTER_ASSERT(reporter, SkScalarNearlyEqual(tan.fX, -1));
+ REPORTER_ASSERT(reporter, SkScalarNearlyEqual(tan.fY, 0));
+}
+
+static void test_empty_contours(skiatest::Reporter* reporter) {
+ SkPath path;
+
+ path.moveTo(0, 0).lineTo(100, 100).lineTo(200, 100);
+ path.moveTo(2, 2).moveTo(3, 3); // zero-length(s)
+ path.moveTo(4, 4).close().close().close(); // zero-length
+ path.moveTo(5, 5).lineTo(5, 5); // zero-length
+ path.moveTo(5, 5).lineTo(5, 5).close(); // zero-length
+ path.moveTo(5, 5).lineTo(5, 5).close().close(); // zero-length
+ path.moveTo(6, 6).lineTo(7, 7);
+ path.moveTo(10, 10); // zero-length
+
+ SkContourMeasureIter fact(path, false);
+
+ // given the above construction, we expect only 2 contours (the rest are "empty")
+
+ REPORTER_ASSERT(reporter, fact.next());
+ REPORTER_ASSERT(reporter, fact.next());
+ REPORTER_ASSERT(reporter, !fact.next());
+}
+
+DEF_TEST(contour_measure, reporter) {
+ SkPath path;
+ path.addCircle(0, 0, 100);
+ path.addCircle(0, 0, 10);
+
+ SkContourMeasureIter fact(path, false);
+ path.reset(); // we should not need the path avert we created the factory
+
+ auto cm0 = fact.next();
+ auto cm1 = fact.next();
+
+ REPORTER_ASSERT(reporter, cm0->isClosed());
+ REPORTER_ASSERT(reporter, SkScalarNearlyEqual(cm0->length(), 200 * SK_ScalarPI, 1.5f));
+
+ test_90_degrees(cm0, 100, reporter);
+
+ REPORTER_ASSERT(reporter, cm1->isClosed());
+ REPORTER_ASSERT(reporter, SkScalarNearlyEqual(cm1->length(), 20 * SK_ScalarPI, 0.5f));
+
+ test_90_degrees(cm1, 10, reporter);
+
+ auto cm2 = fact.next();
+ REPORTER_ASSERT(reporter, !cm2);
+
+ test_empty_contours(reporter);
+}