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 16enum { 17 kLine_SegType, 18 kQuad_SegType, 19 kCubic_SegType 20}; 21 22#define kMaxTValue 32767 23 24static 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 34SkScalar SkPathMeasure::Segment::getScalarT() const { 35 return tValue2Scalar(fTValue); 36} 37 38const 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 49static 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 59static 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 71static 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 78static 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 88SkScalar 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 112SkScalar 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 136void 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::kMove_Verb: 156 ptIndex += 1; 157 fPts.append(1, pts); 158 if (!firstMoveTo) { 159 done = true; 160 break; 161 } 162 firstMoveTo = false; 163 break; 164 165 case SkPath::kLine_Verb: { 166 SkScalar d = SkPoint::Distance(pts[0], pts[1]); 167 SkASSERT(d >= 0); 168 SkScalar prevD = distance; 169 distance += d; 170 if (distance > prevD) { 171 seg = fSegments.append(); 172 seg->fDistance = distance; 173 seg->fPtIndex = ptIndex; 174 seg->fType = kLine_SegType; 175 seg->fTValue = kMaxTValue; 176 fPts.append(1, pts + 1); 177 ptIndex++; 178 } 179 } break; 180 181 case SkPath::kQuad_Verb: { 182 SkScalar prevD = distance; 183 distance = this->compute_quad_segs(pts, distance, 0, 184 kMaxTValue, ptIndex); 185 if (distance > prevD) { 186 fPts.append(2, pts + 1); 187 ptIndex += 2; 188 } 189 } break; 190 191 case SkPath::kCubic_Verb: { 192 SkScalar prevD = distance; 193 distance = this->compute_cubic_segs(pts, distance, 0, 194 kMaxTValue, ptIndex); 195 if (distance > prevD) { 196 fPts.append(3, pts + 1); 197 ptIndex += 3; 198 } 199 } break; 200 201 case SkPath::kClose_Verb: 202 isClosed = true; 203 break; 204 205 case SkPath::kDone_Verb: 206 done = true; 207 break; 208 } 209 } while (!done); 210 211 fLength = distance; 212 fIsClosed = isClosed; 213 fFirstPtIndex = ptIndex; 214 215#ifdef SK_DEBUG 216 { 217 const Segment* seg = fSegments.begin(); 218 const Segment* stop = fSegments.end(); 219 unsigned ptIndex = 0; 220 SkScalar distance = 0; 221 222 while (seg < stop) { 223 SkASSERT(seg->fDistance > distance); 224 SkASSERT(seg->fPtIndex >= ptIndex); 225 SkASSERT(seg->fTValue > 0); 226 227 const Segment* s = seg; 228 while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) { 229 SkASSERT(s[0].fType == s[1].fType); 230 SkASSERT(s[0].fTValue < s[1].fTValue); 231 s += 1; 232 } 233 234 distance = seg->fDistance; 235 ptIndex = seg->fPtIndex; 236 seg += 1; 237 } 238 // SkDebugf("\n"); 239 } 240#endif 241} 242 243static void compute_pos_tan(const SkPoint pts[], int segType, 244 SkScalar t, SkPoint* pos, SkVector* tangent) { 245 switch (segType) { 246 case kLine_SegType: 247 if (pos) { 248 pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t), 249 SkScalarInterp(pts[0].fY, pts[1].fY, t)); 250 } 251 if (tangent) { 252 tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY); 253 } 254 break; 255 case kQuad_SegType: 256 SkEvalQuadAt(pts, t, pos, tangent); 257 if (tangent) { 258 tangent->normalize(); 259 } 260 break; 261 case kCubic_SegType: 262 SkEvalCubicAt(pts, t, pos, tangent, NULL); 263 if (tangent) { 264 tangent->normalize(); 265 } 266 break; 267 default: 268 SkDEBUGFAIL("unknown segType"); 269 } 270} 271 272static void seg_to(const SkPoint pts[], int segType, 273 SkScalar startT, SkScalar stopT, SkPath* dst) { 274 SkASSERT(startT >= 0 && startT <= SK_Scalar1); 275 SkASSERT(stopT >= 0 && stopT <= SK_Scalar1); 276 SkASSERT(startT <= stopT); 277 278 if (startT == stopT) { 279 return; // should we report this, to undo a moveTo? 280 } 281 282 SkPoint tmp0[7], tmp1[7]; 283 284 switch (segType) { 285 case kLine_SegType: 286 if (stopT == kMaxTValue) { 287 dst->lineTo(pts[1]); 288 } else { 289 dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT), 290 SkScalarInterp(pts[0].fY, pts[1].fY, stopT)); 291 } 292 break; 293 case kQuad_SegType: 294 if (startT == 0) { 295 if (stopT == SK_Scalar1) { 296 dst->quadTo(pts[1], pts[2]); 297 } else { 298 SkChopQuadAt(pts, tmp0, stopT); 299 dst->quadTo(tmp0[1], tmp0[2]); 300 } 301 } else { 302 SkChopQuadAt(pts, tmp0, startT); 303 if (stopT == SK_Scalar1) { 304 dst->quadTo(tmp0[3], tmp0[4]); 305 } else { 306 SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT, 307 SK_Scalar1 - startT)); 308 dst->quadTo(tmp1[1], tmp1[2]); 309 } 310 } 311 break; 312 case kCubic_SegType: 313 if (startT == 0) { 314 if (stopT == SK_Scalar1) { 315 dst->cubicTo(pts[1], pts[2], pts[3]); 316 } else { 317 SkChopCubicAt(pts, tmp0, stopT); 318 dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]); 319 } 320 } else { 321 SkChopCubicAt(pts, tmp0, startT); 322 if (stopT == SK_Scalar1) { 323 dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]); 324 } else { 325 SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT, 326 SK_Scalar1 - startT)); 327 dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]); 328 } 329 } 330 break; 331 default: 332 SkDEBUGFAIL("unknown segType"); 333 sk_throw(); 334 } 335} 336 337//////////////////////////////////////////////////////////////////////////////// 338//////////////////////////////////////////////////////////////////////////////// 339 340SkPathMeasure::SkPathMeasure() { 341 fPath = NULL; 342 fLength = -1; // signal we need to compute it 343 fForceClosed = false; 344 fFirstPtIndex = -1; 345} 346 347SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) { 348 fPath = &path; 349 fLength = -1; // signal we need to compute it 350 fForceClosed = forceClosed; 351 fFirstPtIndex = -1; 352 353 fIter.setPath(path, forceClosed); 354} 355 356SkPathMeasure::~SkPathMeasure() {} 357 358/** Assign a new path, or null to have none. 359*/ 360void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) { 361 fPath = path; 362 fLength = -1; // signal we need to compute it 363 fForceClosed = forceClosed; 364 fFirstPtIndex = -1; 365 366 if (path) { 367 fIter.setPath(*path, forceClosed); 368 } 369 fSegments.reset(); 370 fPts.reset(); 371} 372 373SkScalar SkPathMeasure::getLength() { 374 if (fPath == NULL) { 375 return 0; 376 } 377 if (fLength < 0) { 378 this->buildSegments(); 379 } 380 SkASSERT(fLength >= 0); 381 return fLength; 382} 383 384const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment( 385 SkScalar distance, SkScalar* t) { 386 SkDEBUGCODE(SkScalar length = ) this->getLength(); 387 SkASSERT(distance >= 0 && distance <= length); 388 389 const Segment* seg = fSegments.begin(); 390 int count = fSegments.count(); 391 392 int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance, 393 sizeof(Segment)); 394 // don't care if we hit an exact match or not, so we xor index if it is negative 395 index ^= (index >> 31); 396 seg = &seg[index]; 397 398 // now interpolate t-values with the prev segment (if possible) 399 SkScalar startT = 0, startD = 0; 400 // check if the prev segment is legal, and references the same set of points 401 if (index > 0) { 402 startD = seg[-1].fDistance; 403 if (seg[-1].fPtIndex == seg->fPtIndex) { 404 SkASSERT(seg[-1].fType == seg->fType); 405 startT = seg[-1].getScalarT(); 406 } 407 } 408 409 SkASSERT(seg->getScalarT() > startT); 410 SkASSERT(distance >= startD); 411 SkASSERT(seg->fDistance > startD); 412 413 *t = startT + SkScalarMulDiv(seg->getScalarT() - startT, 414 distance - startD, 415 seg->fDistance - startD); 416 return seg; 417} 418 419bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos, 420 SkVector* tangent) { 421 if (NULL == fPath) { 422 return false; 423 } 424 425 SkScalar length = this->getLength(); // call this to force computing it 426 int count = fSegments.count(); 427 428 if (count == 0 || length == 0) { 429 return false; 430 } 431 432 // pin the distance to a legal range 433 if (distance < 0) { 434 distance = 0; 435 } else if (distance > length) { 436 distance = length; 437 } 438 439 SkScalar t; 440 const Segment* seg = this->distanceToSegment(distance, &t); 441 442 compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent); 443 return true; 444} 445 446bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix, 447 MatrixFlags flags) { 448 if (NULL == fPath) { 449 return false; 450 } 451 452 SkPoint position; 453 SkVector tangent; 454 455 if (this->getPosTan(distance, &position, &tangent)) { 456 if (matrix) { 457 if (flags & kGetTangent_MatrixFlag) { 458 matrix->setSinCos(tangent.fY, tangent.fX, 0, 0); 459 } else { 460 matrix->reset(); 461 } 462 if (flags & kGetPosition_MatrixFlag) { 463 matrix->postTranslate(position.fX, position.fY); 464 } 465 } 466 return true; 467 } 468 return false; 469} 470 471bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst, 472 bool startWithMoveTo) { 473 SkASSERT(dst); 474 475 SkScalar length = this->getLength(); // ensure we have built our segments 476 477 if (startD < 0) { 478 startD = 0; 479 } 480 if (stopD > length) { 481 stopD = length; 482 } 483 if (startD >= stopD) { 484 return false; 485 } 486 487 SkPoint p; 488 SkScalar startT, stopT; 489 const Segment* seg = this->distanceToSegment(startD, &startT); 490 const Segment* stopSeg = this->distanceToSegment(stopD, &stopT); 491 SkASSERT(seg <= stopSeg); 492 493 if (startWithMoveTo) { 494 compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, NULL); 495 dst->moveTo(p); 496 } 497 498 if (seg->fPtIndex == stopSeg->fPtIndex) { 499 seg_to(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst); 500 } else { 501 do { 502 seg_to(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst); 503 seg = SkPathMeasure::NextSegment(seg); 504 startT = 0; 505 } while (seg->fPtIndex < stopSeg->fPtIndex); 506 seg_to(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst); 507 } 508 return true; 509} 510 511bool SkPathMeasure::isClosed() { 512 (void)this->getLength(); 513 return fIsClosed; 514} 515 516/** Move to the next contour in the path. Return true if one exists, or false if 517 we're done with the path. 518*/ 519bool SkPathMeasure::nextContour() { 520 fLength = -1; 521 return this->getLength() > 0; 522} 523 524/////////////////////////////////////////////////////////////////////////////// 525/////////////////////////////////////////////////////////////////////////////// 526 527#ifdef SK_DEBUG 528 529void SkPathMeasure::dump() { 530 SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count()); 531 532 for (int i = 0; i < fSegments.count(); i++) { 533 const Segment* seg = &fSegments[i]; 534 SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n", 535 i, seg->fDistance, seg->fPtIndex, seg->getScalarT(), 536 seg->fType); 537 } 538} 539 540#endif 541