Home | History | Annotate | Download | only in core 
      1 
      2 /*
      3  * Copyright 2008 The Android Open Source Project
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 #include "SkPathMeasure.h"
     11 #include "SkGeometry.h"
     12 #include "SkPath.h"
     13 #include "SkTSearch.h"
     14 
     15 // these must be 0,1,2 since they are in our 2-bit field
     16 enum {
     17     kLine_SegType,
     18     kQuad_SegType,
     19     kCubic_SegType
     20 };
     21 
     22 #define kMaxTValue  32767
     23 
     24 static inline SkScalar tValue2Scalar(int t) {
     25     SkASSERT((unsigned)t <= kMaxTValue);
     26     return t * 3.05185e-5f; // t / 32767
     27 }
     28 
     29 SkScalar SkPathMeasure::Segment::getScalarT() const {
     30     return tValue2Scalar(fTValue);
     31 }
     32 
     33 const SkPathMeasure::Segment* SkPathMeasure::NextSegment(const Segment* seg) {
     34     unsigned ptIndex = seg->fPtIndex;
     35 
     36     do {
     37         ++seg;
     38     } while (seg->fPtIndex == ptIndex);
     39     return seg;
     40 }
     41 
     42 ///////////////////////////////////////////////////////////////////////////////
     43 
     44 static inline int tspan_big_enough(int tspan) {
     45     SkASSERT((unsigned)tspan <= kMaxTValue);
     46     return tspan >> 10;
     47 }
     48 
     49 // can't use tangents, since we need [0..1..................2] to be seen
     50 // as definitely not a line (it is when drawn, but not parametrically)
     51 // so we compare midpoints
     52 #define CHEAP_DIST_LIMIT    (SK_Scalar1/2)  // just made this value up
     53 
     54 static bool quad_too_curvy(const SkPoint pts[3]) {
     55     // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
     56     // diff = -a/4 + b/2 - c/4
     57     SkScalar dx = SkScalarHalf(pts[1].fX) -
     58                         SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
     59     SkScalar dy = SkScalarHalf(pts[1].fY) -
     60                         SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
     61 
     62     SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy));
     63     return dist > CHEAP_DIST_LIMIT;
     64 }
     65 
     66 static bool cheap_dist_exceeds_limit(const SkPoint& pt,
     67                                      SkScalar x, SkScalar y) {
     68     SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
     69     // just made up the 1/2
     70     return dist > CHEAP_DIST_LIMIT;
     71 }
     72 
     73 static bool cubic_too_curvy(const SkPoint pts[4]) {
     74     return  cheap_dist_exceeds_limit(pts[1],
     75                          SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
     76                          SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3))
     77                          ||
     78             cheap_dist_exceeds_limit(pts[2],
     79                          SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
     80                          SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3));
     81 }
     82 
     83 SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3],
     84                           SkScalar distance, int mint, int maxt, int ptIndex) {
     85     if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) {
     86         SkPoint tmp[5];
     87         int     halft = (mint + maxt) >> 1;
     88 
     89         SkChopQuadAtHalf(pts, tmp);
     90         distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
     91         distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
     92     } else {
     93         SkScalar d = SkPoint::Distance(pts[0], pts[2]);
     94         SkScalar prevD = distance;
     95         distance += d;
     96         if (distance > prevD) {
     97             Segment* seg = fSegments.append();
     98             seg->fDistance = distance;
     99             seg->fPtIndex = ptIndex;
    100             seg->fType = kQuad_SegType;
    101             seg->fTValue = maxt;
    102         }
    103     }
    104     return distance;
    105 }
    106 
    107 SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4],
    108                            SkScalar distance, int mint, int maxt, int ptIndex) {
    109     if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) {
    110         SkPoint tmp[7];
    111         int     halft = (mint + maxt) >> 1;
    112 
    113         SkChopCubicAtHalf(pts, tmp);
    114         distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
    115         distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
    116     } else {
    117         SkScalar d = SkPoint::Distance(pts[0], pts[3]);
    118         SkScalar prevD = distance;
    119         distance += d;
    120         if (distance > prevD) {
    121             Segment* seg = fSegments.append();
    122             seg->fDistance = distance;
    123             seg->fPtIndex = ptIndex;
    124             seg->fType = kCubic_SegType;
    125             seg->fTValue = maxt;
    126         }
    127     }
    128     return distance;
    129 }
    130 
    131 void SkPathMeasure::buildSegments() {
    132     SkPoint         pts[4];
    133     int             ptIndex = fFirstPtIndex;
    134     SkScalar        distance = 0;
    135     bool            isClosed = fForceClosed;
    136     bool            firstMoveTo = ptIndex < 0;
    137     Segment*        seg;
    138 
    139     /*  Note:
    140      *  as we accumulate distance, we have to check that the result of +=
    141      *  actually made it larger, since a very small delta might be > 0, but
    142      *  still have no effect on distance (if distance >>> delta).
    143      *
    144      *  We do this check below, and in compute_quad_segs and compute_cubic_segs
    145      */
    146     fSegments.reset();
    147     bool done = false;
    148     do {
    149         switch (fIter.next(pts)) {
    150             case SkPath::kConic_Verb:
    151                 SkASSERT(0);
    152                 break;
    153             case SkPath::kMove_Verb:
    154                 ptIndex += 1;
    155                 fPts.append(1, pts);
    156                 if (!firstMoveTo) {
    157                     done = true;
    158                     break;
    159                 }
    160                 firstMoveTo = false;
    161                 break;
    162 
    163             case SkPath::kLine_Verb: {
    164                 SkScalar d = SkPoint::Distance(pts[0], pts[1]);
    165                 SkASSERT(d >= 0);
    166                 SkScalar prevD = distance;
    167                 distance += d;
    168                 if (distance > prevD) {
    169                     seg = fSegments.append();
    170                     seg->fDistance = distance;
    171                     seg->fPtIndex = ptIndex;
    172                     seg->fType = kLine_SegType;
    173                     seg->fTValue = kMaxTValue;
    174                     fPts.append(1, pts + 1);
    175                     ptIndex++;
    176                 }
    177             } break;
    178 
    179             case SkPath::kQuad_Verb: {
    180                 SkScalar prevD = distance;
    181                 distance = this->compute_quad_segs(pts, distance, 0,
    182                                                    kMaxTValue, ptIndex);
    183                 if (distance > prevD) {
    184                     fPts.append(2, pts + 1);
    185                     ptIndex += 2;
    186                 }
    187             } break;
    188 
    189             case SkPath::kCubic_Verb: {
    190                 SkScalar prevD = distance;
    191                 distance = this->compute_cubic_segs(pts, distance, 0,
    192                                                     kMaxTValue, ptIndex);
    193                 if (distance > prevD) {
    194                     fPts.append(3, pts + 1);
    195                     ptIndex += 3;
    196                 }
    197             } break;
    198 
    199             case SkPath::kClose_Verb:
    200                 isClosed = true;
    201                 break;
    202 
    203             case SkPath::kDone_Verb:
    204                 done = true;
    205                 break;
    206         }
    207     } while (!done);
    208 
    209     fLength = distance;
    210     fIsClosed = isClosed;
    211     fFirstPtIndex = ptIndex;
    212 
    213 #ifdef SK_DEBUG
    214     {
    215         const Segment* seg = fSegments.begin();
    216         const Segment* stop = fSegments.end();
    217         unsigned        ptIndex = 0;
    218         SkScalar        distance = 0;
    219 
    220         while (seg < stop) {
    221             SkASSERT(seg->fDistance > distance);
    222             SkASSERT(seg->fPtIndex >= ptIndex);
    223             SkASSERT(seg->fTValue > 0);
    224 
    225             const Segment* s = seg;
    226             while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) {
    227                 SkASSERT(s[0].fType == s[1].fType);
    228                 SkASSERT(s[0].fTValue < s[1].fTValue);
    229                 s += 1;
    230             }
    231 
    232             distance = seg->fDistance;
    233             ptIndex = seg->fPtIndex;
    234             seg += 1;
    235         }
    236     //  SkDebugf("\n");
    237     }
    238 #endif
    239 }
    240 
    241 static void compute_pos_tan(const SkPoint pts[], int segType,
    242                             SkScalar t, SkPoint* pos, SkVector* tangent) {
    243     switch (segType) {
    244         case kLine_SegType:
    245             if (pos) {
    246                 pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
    247                          SkScalarInterp(pts[0].fY, pts[1].fY, t));
    248             }
    249             if (tangent) {
    250                 tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
    251             }
    252             break;
    253         case kQuad_SegType:
    254             SkEvalQuadAt(pts, t, pos, tangent);
    255             if (tangent) {
    256                 tangent->normalize();
    257             }
    258             break;
    259         case kCubic_SegType:
    260             SkEvalCubicAt(pts, t, pos, tangent, NULL);
    261             if (tangent) {
    262                 tangent->normalize();
    263             }
    264             break;
    265         default:
    266             SkDEBUGFAIL("unknown segType");
    267     }
    268 }
    269 
    270 static void seg_to(const SkPoint pts[], int segType,
    271                    SkScalar startT, SkScalar stopT, SkPath* dst) {
    272     SkASSERT(startT >= 0 && startT <= SK_Scalar1);
    273     SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
    274     SkASSERT(startT <= stopT);
    275 
    276     if (startT == stopT) {
    277         return; // should we report this, to undo a moveTo?
    278     }
    279 
    280     SkPoint         tmp0[7], tmp1[7];
    281 
    282     switch (segType) {
    283         case kLine_SegType:
    284             if (SK_Scalar1 == stopT) {
    285                 dst->lineTo(pts[1]);
    286             } else {
    287                 dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
    288                             SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
    289             }
    290             break;
    291         case kQuad_SegType:
    292             if (0 == startT) {
    293                 if (SK_Scalar1 == stopT) {
    294                     dst->quadTo(pts[1], pts[2]);
    295                 } else {
    296                     SkChopQuadAt(pts, tmp0, stopT);
    297                     dst->quadTo(tmp0[1], tmp0[2]);
    298                 }
    299             } else {
    300                 SkChopQuadAt(pts, tmp0, startT);
    301                 if (SK_Scalar1 == stopT) {
    302                     dst->quadTo(tmp0[3], tmp0[4]);
    303                 } else {
    304                     SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT,
    305                                                          SK_Scalar1 - startT));
    306                     dst->quadTo(tmp1[1], tmp1[2]);
    307                 }
    308             }
    309             break;
    310         case kCubic_SegType:
    311             if (0 == startT) {
    312                 if (SK_Scalar1 == stopT) {
    313                     dst->cubicTo(pts[1], pts[2], pts[3]);
    314                 } else {
    315                     SkChopCubicAt(pts, tmp0, stopT);
    316                     dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
    317                 }
    318             } else {
    319                 SkChopCubicAt(pts, tmp0, startT);
    320                 if (SK_Scalar1 == stopT) {
    321                     dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
    322                 } else {
    323                     SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT,
    324                                                         SK_Scalar1 - startT));
    325                     dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
    326                 }
    327             }
    328             break;
    329         default:
    330             SkDEBUGFAIL("unknown segType");
    331             sk_throw();
    332     }
    333 }
    334 
    335 ////////////////////////////////////////////////////////////////////////////////
    336 ////////////////////////////////////////////////////////////////////////////////
    337 
    338 SkPathMeasure::SkPathMeasure() {
    339     fPath = NULL;
    340     fLength = -1;   // signal we need to compute it
    341     fForceClosed = false;
    342     fFirstPtIndex = -1;
    343 }
    344 
    345 SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) {
    346     fPath = &path;
    347     fLength = -1;   // signal we need to compute it
    348     fForceClosed = forceClosed;
    349     fFirstPtIndex = -1;
    350 
    351     fIter.setPath(path, forceClosed);
    352 }
    353 
    354 SkPathMeasure::~SkPathMeasure() {}
    355 
    356 /** Assign a new path, or null to have none.
    357 */
    358 void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) {
    359     fPath = path;
    360     fLength = -1;   // signal we need to compute it
    361     fForceClosed = forceClosed;
    362     fFirstPtIndex = -1;
    363 
    364     if (path) {
    365         fIter.setPath(*path, forceClosed);
    366     }
    367     fSegments.reset();
    368     fPts.reset();
    369 }
    370 
    371 SkScalar SkPathMeasure::getLength() {
    372     if (fPath == NULL) {
    373         return 0;
    374     }
    375     if (fLength < 0) {
    376         this->buildSegments();
    377     }
    378     SkASSERT(fLength >= 0);
    379     return fLength;
    380 }
    381 
    382 const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment(
    383                                             SkScalar distance, SkScalar* t) {
    384     SkDEBUGCODE(SkScalar length = ) this->getLength();
    385     SkASSERT(distance >= 0 && distance <= length);
    386 
    387     const Segment*  seg = fSegments.begin();
    388     int             count = fSegments.count();
    389 
    390     int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance, sizeof(Segment));
    391     // don't care if we hit an exact match or not, so we xor index if it is negative
    392     index ^= (index >> 31);
    393     seg = &seg[index];
    394 
    395     // now interpolate t-values with the prev segment (if possible)
    396     SkScalar    startT = 0, startD = 0;
    397     // check if the prev segment is legal, and references the same set of points
    398     if (index > 0) {
    399         startD = seg[-1].fDistance;
    400         if (seg[-1].fPtIndex == seg->fPtIndex) {
    401             SkASSERT(seg[-1].fType == seg->fType);
    402             startT = seg[-1].getScalarT();
    403         }
    404     }
    405 
    406     SkASSERT(seg->getScalarT() > startT);
    407     SkASSERT(distance >= startD);
    408     SkASSERT(seg->fDistance > startD);
    409 
    410     *t = startT + SkScalarMulDiv(seg->getScalarT() - startT,
    411                                  distance - startD,
    412                                  seg->fDistance - startD);
    413     return seg;
    414 }
    415 
    416 bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos,
    417                               SkVector* tangent) {
    418     if (NULL == fPath) {
    419         return false;
    420     }
    421 
    422     SkScalar    length = this->getLength(); // call this to force computing it
    423     int         count = fSegments.count();
    424 
    425     if (count == 0 || length == 0) {
    426         return false;
    427     }
    428 
    429     // pin the distance to a legal range
    430     if (distance < 0) {
    431         distance = 0;
    432     } else if (distance > length) {
    433         distance = length;
    434     }
    435 
    436     SkScalar        t;
    437     const Segment*  seg = this->distanceToSegment(distance, &t);
    438 
    439     compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
    440     return true;
    441 }
    442 
    443 bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix,
    444                               MatrixFlags flags) {
    445     if (NULL == fPath) {
    446         return false;
    447     }
    448 
    449     SkPoint     position;
    450     SkVector    tangent;
    451 
    452     if (this->getPosTan(distance, &position, &tangent)) {
    453         if (matrix) {
    454             if (flags & kGetTangent_MatrixFlag) {
    455                 matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
    456             } else {
    457                 matrix->reset();
    458             }
    459             if (flags & kGetPosition_MatrixFlag) {
    460                 matrix->postTranslate(position.fX, position.fY);
    461             }
    462         }
    463         return true;
    464     }
    465     return false;
    466 }
    467 
    468 bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
    469                                bool startWithMoveTo) {
    470     SkASSERT(dst);
    471 
    472     SkScalar length = this->getLength();    // ensure we have built our segments
    473 
    474     if (startD < 0) {
    475         startD = 0;
    476     }
    477     if (stopD > length) {
    478         stopD = length;
    479     }
    480     if (startD >= stopD) {
    481         return false;
    482     }
    483 
    484     SkPoint  p;
    485     SkScalar startT, stopT;
    486     const Segment* seg = this->distanceToSegment(startD, &startT);
    487     const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
    488     SkASSERT(seg <= stopSeg);
    489 
    490     if (startWithMoveTo) {
    491         compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, NULL);
    492         dst->moveTo(p);
    493     }
    494 
    495     if (seg->fPtIndex == stopSeg->fPtIndex) {
    496         seg_to(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
    497     } else {
    498         do {
    499             seg_to(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
    500             seg = SkPathMeasure::NextSegment(seg);
    501             startT = 0;
    502         } while (seg->fPtIndex < stopSeg->fPtIndex);
    503         seg_to(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
    504     }
    505     return true;
    506 }
    507 
    508 bool SkPathMeasure::isClosed() {
    509     (void)this->getLength();
    510     return fIsClosed;
    511 }
    512 
    513 /** Move to the next contour in the path. Return true if one exists, or false if
    514     we're done with the path.
    515 */
    516 bool SkPathMeasure::nextContour() {
    517     fLength = -1;
    518     return this->getLength() > 0;
    519 }
    520 
    521 ///////////////////////////////////////////////////////////////////////////////
    522 ///////////////////////////////////////////////////////////////////////////////
    523 
    524 #ifdef SK_DEBUG
    525 
    526 void SkPathMeasure::dump() {
    527     SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count());
    528 
    529     for (int i = 0; i < fSegments.count(); i++) {
    530         const Segment* seg = &fSegments[i];
    531         SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n",
    532                 i, seg->fDistance, seg->fPtIndex, seg->getScalarT(),
    533                  seg->fType);
    534     }
    535 }
    536 
    537 #endif
    538