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