diff options
Diffstat (limited to 'src/core/SkPathMeasure.cpp')
| -rw-r--r-- | src/core/SkPathMeasure.cpp | 598 |
1 files changed, 598 insertions, 0 deletions
diff --git a/src/core/SkPathMeasure.cpp b/src/core/SkPathMeasure.cpp new file mode 100644 index 0000000000..ec1510df32 --- /dev/null +++ b/src/core/SkPathMeasure.cpp @@ -0,0 +1,598 @@ +/* + * Copyright (C) 2006-2008 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "SkPathMeasure.h" +#include "SkGeometry.h" +#include "SkPath.h" +#include "SkTSearch.h" + +// these must be 0,1,2 since they are in our 2-bit field +enum { + kLine_SegType, + kCloseLine_SegType, + kQuad_SegType, + kCubic_SegType +}; + +#define kMaxTValue 32767 + +static inline SkScalar tValue2Scalar(int t) { + SkASSERT((unsigned)t <= kMaxTValue); + +#ifdef SK_SCALAR_IS_FLOAT + return t * 3.05185e-5f; // t / 32767 +#else + return (t + (t >> 14)) << 1; +#endif +} + +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; +} + +/////////////////////////////////////////////////////////////////////////////// + +static inline int tspan_big_enough(int tspan) { + SkASSERT((unsigned)tspan <= kMaxTValue); + return tspan >> 10; +} + +#if 0 +static inline bool tangents_too_curvy(const SkVector& tan0, SkVector& tan1) { + static const SkScalar kFlatEnoughTangentDotProd = SK_Scalar1 * 99 / 100; + + SkASSERT(kFlatEnoughTangentDotProd > 0 && + kFlatEnoughTangentDotProd < SK_Scalar1); + + return SkPoint::DotProduct(tan0, tan1) < kFlatEnoughTangentDotProd; +} +#endif + +// 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]) { + // 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 > CHEAP_DIST_LIMIT; +} + +static bool 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 > CHEAP_DIST_LIMIT; +} + +static bool 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)); +} + +SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3], + SkScalar distance, int mint, int maxt, int ptIndex) { + 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]); + SkASSERT(d >= 0); + if (!SkScalarNearlyZero(d)) { + distance += d; + Segment* seg = fSegments.append(); + seg->fDistance = distance; + seg->fPtIndex = ptIndex; + seg->fType = kQuad_SegType; + seg->fTValue = maxt; + } + } + return distance; +} + +SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4], + SkScalar distance, int mint, int maxt, int ptIndex) { + 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]); + SkASSERT(d >= 0); + if (!SkScalarNearlyZero(d)) { + distance += d; + 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]; + int ptIndex = fFirstPtIndex; + SkScalar d, distance = 0; + bool isClosed = fForceClosed; + bool firstMoveTo = ptIndex < 0; + Segment* seg; + + fSegments.reset(); + for (;;) { + switch (fIter.next(pts)) { + case SkPath::kMove_Verb: + if (!firstMoveTo) { + goto DONE; + } + ptIndex += 1; + firstMoveTo = false; + break; + + case SkPath::kLine_Verb: + d = SkPoint::Distance(pts[0], pts[1]); + SkASSERT(d >= 0); + if (!SkScalarNearlyZero(d)) { + distance += d; + seg = fSegments.append(); + seg->fDistance = distance; + seg->fPtIndex = ptIndex; + seg->fType = fIter.isCloseLine() ? + kCloseLine_SegType : kLine_SegType; + seg->fTValue = kMaxTValue; + } + ptIndex += !fIter.isCloseLine(); + break; + + case SkPath::kQuad_Verb: + distance = this->compute_quad_segs(pts, distance, 0, + kMaxTValue, ptIndex); + ptIndex += 2; + break; + + case SkPath::kCubic_Verb: + distance = this->compute_cubic_segs(pts, distance, 0, + kMaxTValue, ptIndex); + ptIndex += 3; + break; + + case SkPath::kClose_Verb: + isClosed = true; + break; + + case SkPath::kDone_Verb: + goto DONE; + } + } +DONE: + fLength = distance; + fIsClosed = isClosed; + fFirstPtIndex = ptIndex + 1; + +#ifdef SK_DEBUG + { + const Segment* seg = fSegments.begin(); + const Segment* stop = fSegments.end(); + unsigned ptIndex = 0; + SkScalar distance = 0; + + 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) { + 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 +} + +// marked as a friend in SkPath.h +const SkPoint* sk_get_path_points(const SkPath& path, int index) { + return &path.fPts[index]; +} + +static void compute_pos_tan(const SkPath& path, int firstPtIndex, int ptIndex, + int segType, SkScalar t, SkPoint* pos, SkVector* tangent) { + const SkPoint* pts = sk_get_path_points(path, ptIndex); + + switch (segType) { + case kLine_SegType: + case kCloseLine_SegType: { + const SkPoint* endp = (segType == kLine_SegType) ? + &pts[1] : + sk_get_path_points(path, firstPtIndex); + + if (pos) { + pos->set(SkScalarInterp(pts[0].fX, endp->fX, t), + SkScalarInterp(pts[0].fY, endp->fY, t)); + } + if (tangent) { + tangent->setNormalize(endp->fX - pts[0].fX, endp->fY - pts[0].fY); + } + break; + } + case kQuad_SegType: + SkEvalQuadAt(pts, t, pos, tangent); + if (tangent) { + tangent->normalize(); + } + break; + case kCubic_SegType: + SkEvalCubicAt(pts, t, pos, tangent, NULL); + if (tangent) { + tangent->normalize(); + } + break; + default: + SkASSERT(!"unknown segType"); + } +} + +static void seg_to(const SkPath& src, int firstPtIndex, int ptIndex, + int segType, SkScalar startT, SkScalar stopT, SkPath* dst) { + SkASSERT(startT >= 0 && startT <= SK_Scalar1); + SkASSERT(stopT >= 0 && stopT <= SK_Scalar1); + SkASSERT(startT <= stopT); + + if (SkScalarNearlyZero(stopT - startT)) { + return; + } + + const SkPoint* pts = sk_get_path_points(src, ptIndex); + SkPoint tmp0[7], tmp1[7]; + + switch (segType) { + case kLine_SegType: + case kCloseLine_SegType: { + const SkPoint* endp = (segType == kLine_SegType) ? + &pts[1] : + sk_get_path_points(src, firstPtIndex); + + if (stopT == kMaxTValue) { + dst->lineTo(*endp); + } else { + dst->lineTo(SkScalarInterp(pts[0].fX, endp->fX, stopT), + SkScalarInterp(pts[0].fY, endp->fY, stopT)); + } + break; + } + case kQuad_SegType: + if (startT == 0) { + if (stopT == SK_Scalar1) { + dst->quadTo(pts[1], pts[2]); + } else { + SkChopQuadAt(pts, tmp0, stopT); + dst->quadTo(tmp0[1], tmp0[2]); + } + } else { + SkChopQuadAt(pts, tmp0, startT); + if (stopT == SK_Scalar1) { + dst->quadTo(tmp0[3], tmp0[4]); + } else { + SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT, + SK_Scalar1 - startT)); + dst->quadTo(tmp1[1], tmp1[2]); + } + } + break; + case kCubic_SegType: + if (startT == 0) { + if (stopT == SK_Scalar1) { + 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 (stopT == SK_Scalar1) { + dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]); + } else { + SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT, + SK_Scalar1 - startT)); + dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]); + } + } + break; + default: + SkASSERT(!"unknown segType"); + sk_throw(); + } +} + +//////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////// + +SkPathMeasure::SkPathMeasure() { + fPath = NULL; + fLength = -1; // signal we need to compute it + fForceClosed = false; + fFirstPtIndex = -1; +} + +SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) { + fPath = &path; + fLength = -1; // signal we need to compute it + fForceClosed = forceClosed; + fFirstPtIndex = -1; + + fIter.setPath(path, forceClosed); +} + +SkPathMeasure::~SkPathMeasure() {} + +/** Assign a new path, or null to have none. +*/ +void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) { + fPath = path; + fLength = -1; // signal we need to compute it + fForceClosed = forceClosed; + fFirstPtIndex = -1; + + if (path) { + fIter.setPath(*path, forceClosed); + } + fSegments.reset(); +} + +SkScalar SkPathMeasure::getLength() { + if (fPath == NULL) { + return 0; + } + if (fLength < 0) { + this->buildSegments(); + } + SkASSERT(fLength >= 0); + return fLength; +} + +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 = SkTSearch<SkScalar>(&seg->fDistance, count, distance, + sizeof(Segment)); + // 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 + SkScalarMulDiv(seg->getScalarT() - startT, + distance - startD, + seg->fDistance - startD); + return seg; +} + +bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos, + SkVector* tangent) { + SkASSERT(fPath); + if (fPath == NULL) { + EMPTY: + return false; + } + + SkScalar length = this->getLength(); // call this to force computing it + int count = fSegments.count(); + + if (count == 0 || length == 0) { + goto EMPTY; + } + + // 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); + + compute_pos_tan(*fPath, fSegments[0].fPtIndex, 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) { + return false; + } + + SkPoint p; + SkScalar startT, stopT; + const Segment* seg = this->distanceToSegment(startD, &startT); + const Segment* stopSeg = this->distanceToSegment(stopD, &stopT); + SkASSERT(seg <= stopSeg); + + if (startWithMoveTo) { + compute_pos_tan(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, + seg->fType, startT, &p, NULL); + dst->moveTo(p); + } + + if (seg->fPtIndex == stopSeg->fPtIndex) { + seg_to(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType, + startT, stopT, dst); + } else { + do { + seg_to(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType, + startT, SK_Scalar1, dst); + seg = SkPathMeasure::NextSegment(seg); + startT = 0; + } while (seg->fPtIndex < stopSeg->fPtIndex); + seg_to(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType, + 0, stopT, dst); + } + return true; +} + +bool SkPathMeasure::isClosed() { + (void)this->getLength(); + return fIsClosed; +} + +/** 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() { + fLength = -1; + return this->getLength() > 0; +} + +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// + +#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::UnitTest() { +#ifdef SK_SUPPORT_UNITTEST + SkPath path; + + path.moveTo(0, 0); + path.lineTo(SK_Scalar1, 0); + path.lineTo(SK_Scalar1, SK_Scalar1); + path.lineTo(0, SK_Scalar1); + + SkPathMeasure meas(path, true); + SkScalar length = meas.getLength(); + SkASSERT(length == SK_Scalar1*4); + + path.reset(); + path.moveTo(0, 0); + path.lineTo(SK_Scalar1*3, SK_Scalar1*4); + meas.setPath(&path, false); + length = meas.getLength(); + SkASSERT(length == SK_Scalar1*5); + + path.reset(); + path.addCircle(0, 0, SK_Scalar1); + meas.setPath(&path, true); + length = meas.getLength(); + SkDebugf("circle arc-length = %g\n", length); + + for (int i = 0; i < 8; i++) { + SkScalar d = length * i / 8; + SkPoint p; + SkVector v; + meas.getPosTan(d, &p, &v); + SkDebugf("circle arc-length=%g, pos[%g %g] tan[%g %g]\n", + d, p.fX, p.fY, v.fX, v.fY); + } +#endif +} + +#endif |