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