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