michael@0: 
michael@0: /*
michael@0:  * Copyright 2008 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #include "SkPathMeasure.h"
michael@0: #include "SkGeometry.h"
michael@0: #include "SkPath.h"
michael@0: #include "SkTSearch.h"
michael@0: 
michael@0: // these must be 0,1,2 since they are in our 2-bit field
michael@0: enum {
michael@0:     kLine_SegType,
michael@0:     kQuad_SegType,
michael@0:     kCubic_SegType
michael@0: };
michael@0: 
michael@0: #define kMaxTValue  32767
michael@0: 
michael@0: static inline SkScalar tValue2Scalar(int t) {
michael@0:     SkASSERT((unsigned)t <= kMaxTValue);
michael@0:     return t * 3.05185e-5f; // t / 32767
michael@0: }
michael@0: 
michael@0: SkScalar SkPathMeasure::Segment::getScalarT() const {
michael@0:     return tValue2Scalar(fTValue);
michael@0: }
michael@0: 
michael@0: const SkPathMeasure::Segment* SkPathMeasure::NextSegment(const Segment* seg) {
michael@0:     unsigned ptIndex = seg->fPtIndex;
michael@0: 
michael@0:     do {
michael@0:         ++seg;
michael@0:     } while (seg->fPtIndex == ptIndex);
michael@0:     return seg;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static inline int tspan_big_enough(int tspan) {
michael@0:     SkASSERT((unsigned)tspan <= kMaxTValue);
michael@0:     return tspan >> 10;
michael@0: }
michael@0: 
michael@0: // can't use tangents, since we need [0..1..................2] to be seen
michael@0: // as definitely not a line (it is when drawn, but not parametrically)
michael@0: // so we compare midpoints
michael@0: #define CHEAP_DIST_LIMIT    (SK_Scalar1/2)  // just made this value up
michael@0: 
michael@0: static bool quad_too_curvy(const SkPoint pts[3]) {
michael@0:     // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
michael@0:     // diff = -a/4 + b/2 - c/4
michael@0:     SkScalar dx = SkScalarHalf(pts[1].fX) -
michael@0:                         SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
michael@0:     SkScalar dy = SkScalarHalf(pts[1].fY) -
michael@0:                         SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
michael@0: 
michael@0:     SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy));
michael@0:     return dist > CHEAP_DIST_LIMIT;
michael@0: }
michael@0: 
michael@0: static bool cheap_dist_exceeds_limit(const SkPoint& pt,
michael@0:                                      SkScalar x, SkScalar y) {
michael@0:     SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
michael@0:     // just made up the 1/2
michael@0:     return dist > CHEAP_DIST_LIMIT;
michael@0: }
michael@0: 
michael@0: static bool cubic_too_curvy(const SkPoint pts[4]) {
michael@0:     return  cheap_dist_exceeds_limit(pts[1],
michael@0:                          SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
michael@0:                          SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3))
michael@0:                          ||
michael@0:             cheap_dist_exceeds_limit(pts[2],
michael@0:                          SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
michael@0:                          SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3));
michael@0: }
michael@0: 
michael@0: SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3],
michael@0:                           SkScalar distance, int mint, int maxt, int ptIndex) {
michael@0:     if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) {
michael@0:         SkPoint tmp[5];
michael@0:         int     halft = (mint + maxt) >> 1;
michael@0: 
michael@0:         SkChopQuadAtHalf(pts, tmp);
michael@0:         distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
michael@0:         distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
michael@0:     } else {
michael@0:         SkScalar d = SkPoint::Distance(pts[0], pts[2]);
michael@0:         SkScalar prevD = distance;
michael@0:         distance += d;
michael@0:         if (distance > prevD) {
michael@0:             Segment* seg = fSegments.append();
michael@0:             seg->fDistance = distance;
michael@0:             seg->fPtIndex = ptIndex;
michael@0:             seg->fType = kQuad_SegType;
michael@0:             seg->fTValue = maxt;
michael@0:         }
michael@0:     }
michael@0:     return distance;
michael@0: }
michael@0: 
michael@0: SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4],
michael@0:                            SkScalar distance, int mint, int maxt, int ptIndex) {
michael@0:     if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) {
michael@0:         SkPoint tmp[7];
michael@0:         int     halft = (mint + maxt) >> 1;
michael@0: 
michael@0:         SkChopCubicAtHalf(pts, tmp);
michael@0:         distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
michael@0:         distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
michael@0:     } else {
michael@0:         SkScalar d = SkPoint::Distance(pts[0], pts[3]);
michael@0:         SkScalar prevD = distance;
michael@0:         distance += d;
michael@0:         if (distance > prevD) {
michael@0:             Segment* seg = fSegments.append();
michael@0:             seg->fDistance = distance;
michael@0:             seg->fPtIndex = ptIndex;
michael@0:             seg->fType = kCubic_SegType;
michael@0:             seg->fTValue = maxt;
michael@0:         }
michael@0:     }
michael@0:     return distance;
michael@0: }
michael@0: 
michael@0: void SkPathMeasure::buildSegments() {
michael@0:     SkPoint         pts[4];
michael@0:     int             ptIndex = fFirstPtIndex;
michael@0:     SkScalar        distance = 0;
michael@0:     bool            isClosed = fForceClosed;
michael@0:     bool            firstMoveTo = ptIndex < 0;
michael@0:     Segment*        seg;
michael@0: 
michael@0:     /*  Note:
michael@0:      *  as we accumulate distance, we have to check that the result of +=
michael@0:      *  actually made it larger, since a very small delta might be > 0, but
michael@0:      *  still have no effect on distance (if distance >>> delta).
michael@0:      *
michael@0:      *  We do this check below, and in compute_quad_segs and compute_cubic_segs
michael@0:      */
michael@0:     fSegments.reset();
michael@0:     bool done = false;
michael@0:     do {
michael@0:         switch (fIter.next(pts)) {
michael@0:             case SkPath::kConic_Verb:
michael@0:                 SkASSERT(0);
michael@0:                 break;
michael@0:             case SkPath::kMove_Verb:
michael@0:                 ptIndex += 1;
michael@0:                 fPts.append(1, pts);
michael@0:                 if (!firstMoveTo) {
michael@0:                     done = true;
michael@0:                     break;
michael@0:                 }
michael@0:                 firstMoveTo = false;
michael@0:                 break;
michael@0: 
michael@0:             case SkPath::kLine_Verb: {
michael@0:                 SkScalar d = SkPoint::Distance(pts[0], pts[1]);
michael@0:                 SkASSERT(d >= 0);
michael@0:                 SkScalar prevD = distance;
michael@0:                 distance += d;
michael@0:                 if (distance > prevD) {
michael@0:                     seg = fSegments.append();
michael@0:                     seg->fDistance = distance;
michael@0:                     seg->fPtIndex = ptIndex;
michael@0:                     seg->fType = kLine_SegType;
michael@0:                     seg->fTValue = kMaxTValue;
michael@0:                     fPts.append(1, pts + 1);
michael@0:                     ptIndex++;
michael@0:                 }
michael@0:             } break;
michael@0: 
michael@0:             case SkPath::kQuad_Verb: {
michael@0:                 SkScalar prevD = distance;
michael@0:                 distance = this->compute_quad_segs(pts, distance, 0,
michael@0:                                                    kMaxTValue, ptIndex);
michael@0:                 if (distance > prevD) {
michael@0:                     fPts.append(2, pts + 1);
michael@0:                     ptIndex += 2;
michael@0:                 }
michael@0:             } break;
michael@0: 
michael@0:             case SkPath::kCubic_Verb: {
michael@0:                 SkScalar prevD = distance;
michael@0:                 distance = this->compute_cubic_segs(pts, distance, 0,
michael@0:                                                     kMaxTValue, ptIndex);
michael@0:                 if (distance > prevD) {
michael@0:                     fPts.append(3, pts + 1);
michael@0:                     ptIndex += 3;
michael@0:                 }
michael@0:             } break;
michael@0: 
michael@0:             case SkPath::kClose_Verb:
michael@0:                 isClosed = true;
michael@0:                 break;
michael@0: 
michael@0:             case SkPath::kDone_Verb:
michael@0:                 done = true;
michael@0:                 break;
michael@0:         }
michael@0:     } while (!done);
michael@0: 
michael@0:     fLength = distance;
michael@0:     fIsClosed = isClosed;
michael@0:     fFirstPtIndex = ptIndex;
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     {
michael@0:         const Segment* seg = fSegments.begin();
michael@0:         const Segment* stop = fSegments.end();
michael@0:         unsigned        ptIndex = 0;
michael@0:         SkScalar        distance = 0;
michael@0: 
michael@0:         while (seg < stop) {
michael@0:             SkASSERT(seg->fDistance > distance);
michael@0:             SkASSERT(seg->fPtIndex >= ptIndex);
michael@0:             SkASSERT(seg->fTValue > 0);
michael@0: 
michael@0:             const Segment* s = seg;
michael@0:             while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) {
michael@0:                 SkASSERT(s[0].fType == s[1].fType);
michael@0:                 SkASSERT(s[0].fTValue < s[1].fTValue);
michael@0:                 s += 1;
michael@0:             }
michael@0: 
michael@0:             distance = seg->fDistance;
michael@0:             ptIndex = seg->fPtIndex;
michael@0:             seg += 1;
michael@0:         }
michael@0:     //  SkDebugf("\n");
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: static void compute_pos_tan(const SkPoint pts[], int segType,
michael@0:                             SkScalar t, SkPoint* pos, SkVector* tangent) {
michael@0:     switch (segType) {
michael@0:         case kLine_SegType:
michael@0:             if (pos) {
michael@0:                 pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
michael@0:                          SkScalarInterp(pts[0].fY, pts[1].fY, t));
michael@0:             }
michael@0:             if (tangent) {
michael@0:                 tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
michael@0:             }
michael@0:             break;
michael@0:         case kQuad_SegType:
michael@0:             SkEvalQuadAt(pts, t, pos, tangent);
michael@0:             if (tangent) {
michael@0:                 tangent->normalize();
michael@0:             }
michael@0:             break;
michael@0:         case kCubic_SegType:
michael@0:             SkEvalCubicAt(pts, t, pos, tangent, NULL);
michael@0:             if (tangent) {
michael@0:                 tangent->normalize();
michael@0:             }
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("unknown segType");
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void seg_to(const SkPoint pts[], int segType,
michael@0:                    SkScalar startT, SkScalar stopT, SkPath* dst) {
michael@0:     SkASSERT(startT >= 0 && startT <= SK_Scalar1);
michael@0:     SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
michael@0:     SkASSERT(startT <= stopT);
michael@0: 
michael@0:     if (startT == stopT) {
michael@0:         return; // should we report this, to undo a moveTo?
michael@0:     }
michael@0: 
michael@0:     SkPoint         tmp0[7], tmp1[7];
michael@0: 
michael@0:     switch (segType) {
michael@0:         case kLine_SegType:
michael@0:             if (SK_Scalar1 == stopT) {
michael@0:                 dst->lineTo(pts[1]);
michael@0:             } else {
michael@0:                 dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
michael@0:                             SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
michael@0:             }
michael@0:             break;
michael@0:         case kQuad_SegType:
michael@0:             if (0 == startT) {
michael@0:                 if (SK_Scalar1 == stopT) {
michael@0:                     dst->quadTo(pts[1], pts[2]);
michael@0:                 } else {
michael@0:                     SkChopQuadAt(pts, tmp0, stopT);
michael@0:                     dst->quadTo(tmp0[1], tmp0[2]);
michael@0:                 }
michael@0:             } else {
michael@0:                 SkChopQuadAt(pts, tmp0, startT);
michael@0:                 if (SK_Scalar1 == stopT) {
michael@0:                     dst->quadTo(tmp0[3], tmp0[4]);
michael@0:                 } else {
michael@0:                     SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT,
michael@0:                                                          SK_Scalar1 - startT));
michael@0:                     dst->quadTo(tmp1[1], tmp1[2]);
michael@0:                 }
michael@0:             }
michael@0:             break;
michael@0:         case kCubic_SegType:
michael@0:             if (0 == startT) {
michael@0:                 if (SK_Scalar1 == stopT) {
michael@0:                     dst->cubicTo(pts[1], pts[2], pts[3]);
michael@0:                 } else {
michael@0:                     SkChopCubicAt(pts, tmp0, stopT);
michael@0:                     dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
michael@0:                 }
michael@0:             } else {
michael@0:                 SkChopCubicAt(pts, tmp0, startT);
michael@0:                 if (SK_Scalar1 == stopT) {
michael@0:                     dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
michael@0:                 } else {
michael@0:                     SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT,
michael@0:                                                         SK_Scalar1 - startT));
michael@0:                     dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
michael@0:                 }
michael@0:             }
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("unknown segType");
michael@0:             sk_throw();
michael@0:     }
michael@0: }
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////
michael@0: ////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: SkPathMeasure::SkPathMeasure() {
michael@0:     fPath = NULL;
michael@0:     fLength = -1;   // signal we need to compute it
michael@0:     fForceClosed = false;
michael@0:     fFirstPtIndex = -1;
michael@0: }
michael@0: 
michael@0: SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) {
michael@0:     fPath = &path;
michael@0:     fLength = -1;   // signal we need to compute it
michael@0:     fForceClosed = forceClosed;
michael@0:     fFirstPtIndex = -1;
michael@0: 
michael@0:     fIter.setPath(path, forceClosed);
michael@0: }
michael@0: 
michael@0: SkPathMeasure::~SkPathMeasure() {}
michael@0: 
michael@0: /** Assign a new path, or null to have none.
michael@0: */
michael@0: void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) {
michael@0:     fPath = path;
michael@0:     fLength = -1;   // signal we need to compute it
michael@0:     fForceClosed = forceClosed;
michael@0:     fFirstPtIndex = -1;
michael@0: 
michael@0:     if (path) {
michael@0:         fIter.setPath(*path, forceClosed);
michael@0:     }
michael@0:     fSegments.reset();
michael@0:     fPts.reset();
michael@0: }
michael@0: 
michael@0: SkScalar SkPathMeasure::getLength() {
michael@0:     if (fPath == NULL) {
michael@0:         return 0;
michael@0:     }
michael@0:     if (fLength < 0) {
michael@0:         this->buildSegments();
michael@0:     }
michael@0:     SkASSERT(fLength >= 0);
michael@0:     return fLength;
michael@0: }
michael@0: 
michael@0: const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment(
michael@0:                                             SkScalar distance, SkScalar* t) {
michael@0:     SkDEBUGCODE(SkScalar length = ) this->getLength();
michael@0:     SkASSERT(distance >= 0 && distance <= length);
michael@0: 
michael@0:     const Segment*  seg = fSegments.begin();
michael@0:     int             count = fSegments.count();
michael@0: 
michael@0:     int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance, sizeof(Segment));
michael@0:     // don't care if we hit an exact match or not, so we xor index if it is negative
michael@0:     index ^= (index >> 31);
michael@0:     seg = &seg[index];
michael@0: 
michael@0:     // now interpolate t-values with the prev segment (if possible)
michael@0:     SkScalar    startT = 0, startD = 0;
michael@0:     // check if the prev segment is legal, and references the same set of points
michael@0:     if (index > 0) {
michael@0:         startD = seg[-1].fDistance;
michael@0:         if (seg[-1].fPtIndex == seg->fPtIndex) {
michael@0:             SkASSERT(seg[-1].fType == seg->fType);
michael@0:             startT = seg[-1].getScalarT();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     SkASSERT(seg->getScalarT() > startT);
michael@0:     SkASSERT(distance >= startD);
michael@0:     SkASSERT(seg->fDistance > startD);
michael@0: 
michael@0:     *t = startT + SkScalarMulDiv(seg->getScalarT() - startT,
michael@0:                                  distance - startD,
michael@0:                                  seg->fDistance - startD);
michael@0:     return seg;
michael@0: }
michael@0: 
michael@0: bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos,
michael@0:                               SkVector* tangent) {
michael@0:     if (NULL == fPath) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkScalar    length = this->getLength(); // call this to force computing it
michael@0:     int         count = fSegments.count();
michael@0: 
michael@0:     if (count == 0 || length == 0) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // pin the distance to a legal range
michael@0:     if (distance < 0) {
michael@0:         distance = 0;
michael@0:     } else if (distance > length) {
michael@0:         distance = length;
michael@0:     }
michael@0: 
michael@0:     SkScalar        t;
michael@0:     const Segment*  seg = this->distanceToSegment(distance, &t);
michael@0: 
michael@0:     compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix,
michael@0:                               MatrixFlags flags) {
michael@0:     if (NULL == fPath) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkPoint     position;
michael@0:     SkVector    tangent;
michael@0: 
michael@0:     if (this->getPosTan(distance, &position, &tangent)) {
michael@0:         if (matrix) {
michael@0:             if (flags & kGetTangent_MatrixFlag) {
michael@0:                 matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
michael@0:             } else {
michael@0:                 matrix->reset();
michael@0:             }
michael@0:             if (flags & kGetPosition_MatrixFlag) {
michael@0:                 matrix->postTranslate(position.fX, position.fY);
michael@0:             }
michael@0:         }
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
michael@0:                                bool startWithMoveTo) {
michael@0:     SkASSERT(dst);
michael@0: 
michael@0:     SkScalar length = this->getLength();    // ensure we have built our segments
michael@0: 
michael@0:     if (startD < 0) {
michael@0:         startD = 0;
michael@0:     }
michael@0:     if (stopD > length) {
michael@0:         stopD = length;
michael@0:     }
michael@0:     if (startD >= stopD) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkPoint  p;
michael@0:     SkScalar startT, stopT;
michael@0:     const Segment* seg = this->distanceToSegment(startD, &startT);
michael@0:     const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
michael@0:     SkASSERT(seg <= stopSeg);
michael@0: 
michael@0:     if (startWithMoveTo) {
michael@0:         compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, NULL);
michael@0:         dst->moveTo(p);
michael@0:     }
michael@0: 
michael@0:     if (seg->fPtIndex == stopSeg->fPtIndex) {
michael@0:         seg_to(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
michael@0:     } else {
michael@0:         do {
michael@0:             seg_to(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
michael@0:             seg = SkPathMeasure::NextSegment(seg);
michael@0:             startT = 0;
michael@0:         } while (seg->fPtIndex < stopSeg->fPtIndex);
michael@0:         seg_to(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkPathMeasure::isClosed() {
michael@0:     (void)this->getLength();
michael@0:     return fIsClosed;
michael@0: }
michael@0: 
michael@0: /** Move to the next contour in the path. Return true if one exists, or false if
michael@0:     we're done with the path.
michael@0: */
michael@0: bool SkPathMeasure::nextContour() {
michael@0:     fLength = -1;
michael@0:     return this->getLength() > 0;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: 
michael@0: void SkPathMeasure::dump() {
michael@0:     SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count());
michael@0: 
michael@0:     for (int i = 0; i < fSegments.count(); i++) {
michael@0:         const Segment* seg = &fSegments[i];
michael@0:         SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n",
michael@0:                 i, seg->fDistance, seg->fPtIndex, seg->getScalarT(),
michael@0:                  seg->fType);
michael@0:     }
michael@0: }
michael@0: 
michael@0: #endif