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 #if 0 55 static inline bool tangents_too_curvy(const SkVector& tan0, SkVector& tan1) { 56 static const SkScalar kFlatEnoughTangentDotProd = SK_Scalar1 * 99 / 100; 57 58 SkASSERT(kFlatEnoughTangentDotProd > 0 && 59 kFlatEnoughTangentDotProd < SK_Scalar1); 60 61 return SkPoint::DotProduct(tan0, tan1) < kFlatEnoughTangentDotProd; 62 } 63 #endif 64 65 // can't use tangents, since we need [0..1..................2] to be seen 66 // as definitely not a line (it is when drawn, but not parametrically) 67 // so we compare midpoints 68 #define CHEAP_DIST_LIMIT (SK_Scalar1/2) // just made this value up 69 70 static bool quad_too_curvy(const SkPoint pts[3]) { 71 // diff = (a/4 + b/2 + c/4) - (a/2 + c/2) 72 // diff = -a/4 + b/2 - c/4 73 SkScalar dx = SkScalarHalf(pts[1].fX) - 74 SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX)); 75 SkScalar dy = SkScalarHalf(pts[1].fY) - 76 SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY)); 77 78 SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy)); 79 return dist > CHEAP_DIST_LIMIT; 80 } 81 82 static bool cheap_dist_exceeds_limit(const SkPoint& pt, 83 SkScalar x, SkScalar y) { 84 SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY)); 85 // just made up the 1/2 86 return dist > CHEAP_DIST_LIMIT; 87 } 88 89 static bool cubic_too_curvy(const SkPoint pts[4]) { 90 return cheap_dist_exceeds_limit(pts[1], 91 SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3), 92 SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3)) 93 || 94 cheap_dist_exceeds_limit(pts[2], 95 SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3), 96 SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3)); 97 } 98 99 SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3], 100 SkScalar distance, int mint, int maxt, int ptIndex) { 101 if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) { 102 SkPoint tmp[5]; 103 int halft = (mint + maxt) >> 1; 104 105 SkChopQuadAtHalf(pts, tmp); 106 distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex); 107 distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex); 108 } else { 109 SkScalar d = SkPoint::Distance(pts[0], pts[2]); 110 SkASSERT(d >= 0); 111 if (!SkScalarNearlyZero(d)) { 112 distance += d; 113 Segment* seg = fSegments.append(); 114 seg->fDistance = distance; 115 seg->fPtIndex = ptIndex; 116 seg->fType = kQuad_SegType; 117 seg->fTValue = maxt; 118 } 119 } 120 return distance; 121 } 122 123 SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4], 124 SkScalar distance, int mint, int maxt, int ptIndex) { 125 if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) { 126 SkPoint tmp[7]; 127 int halft = (mint + maxt) >> 1; 128 129 SkChopCubicAtHalf(pts, tmp); 130 distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex); 131 distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex); 132 } else { 133 SkScalar d = SkPoint::Distance(pts[0], pts[3]); 134 SkASSERT(d >= 0); 135 if (!SkScalarNearlyZero(d)) { 136 distance += d; 137 Segment* seg = fSegments.append(); 138 seg->fDistance = distance; 139 seg->fPtIndex = ptIndex; 140 seg->fType = kCubic_SegType; 141 seg->fTValue = maxt; 142 } 143 } 144 return distance; 145 } 146 147 void SkPathMeasure::buildSegments() { 148 SkPoint pts[4]; 149 int ptIndex = fFirstPtIndex; 150 SkScalar d, distance = 0; 151 bool isClosed = fForceClosed; 152 bool firstMoveTo = ptIndex < 0; 153 Segment* seg; 154 155 fSegments.reset(); 156 bool done = false; 157 do { 158 switch (fIter.next(pts)) { 159 case SkPath::kMove_Verb: 160 ptIndex += 1; 161 fPts.append(1, pts); 162 if (!firstMoveTo) { 163 done = true; 164 break; 165 } 166 firstMoveTo = false; 167 break; 168 169 case SkPath::kLine_Verb: 170 d = SkPoint::Distance(pts[0], pts[1]); 171 SkASSERT(d >= 0); 172 distance += d; 173 seg = fSegments.append(); 174 seg->fDistance = distance; 175 seg->fPtIndex = ptIndex; 176 seg->fType = kLine_SegType; 177 seg->fTValue = kMaxTValue; 178 fPts.append(1, pts + 1); 179 ptIndex++; 180 break; 181 182 case SkPath::kQuad_Verb: 183 distance = this->compute_quad_segs(pts, distance, 0, 184 kMaxTValue, ptIndex); 185 fPts.append(2, pts + 1); 186 ptIndex += 2; 187 break; 188 189 case SkPath::kCubic_Verb: 190 distance = this->compute_cubic_segs(pts, distance, 0, 191 kMaxTValue, ptIndex); 192 fPts.append(3, pts + 1); 193 ptIndex += 3; 194 break; 195 196 case SkPath::kClose_Verb: 197 isClosed = true; 198 break; 199 200 case SkPath::kDone_Verb: 201 done = true; 202 break; 203 } 204 } while (!done); 205 206 fLength = distance; 207 fIsClosed = isClosed; 208 fFirstPtIndex = ptIndex; 209 210 #ifdef SK_DEBUG 211 { 212 const Segment* seg = fSegments.begin(); 213 const Segment* stop = fSegments.end(); 214 unsigned ptIndex = 0; 215 SkScalar distance = 0; 216 217 while (seg < stop) { 218 SkASSERT(seg->fDistance > distance); 219 SkASSERT(seg->fPtIndex >= ptIndex); 220 SkASSERT(seg->fTValue > 0); 221 222 const Segment* s = seg; 223 while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) { 224 SkASSERT(s[0].fType == s[1].fType); 225 SkASSERT(s[0].fTValue < s[1].fTValue); 226 s += 1; 227 } 228 229 distance = seg->fDistance; 230 ptIndex = seg->fPtIndex; 231 seg += 1; 232 } 233 // SkDebugf("\n"); 234 } 235 #endif 236 } 237 238 static void compute_pos_tan(const SkTDArray<SkPoint>& segmentPts, int ptIndex, 239 int segType, SkScalar t, SkPoint* pos, SkVector* tangent) { 240 const SkPoint* pts = &segmentPts[ptIndex]; 241 242 switch (segType) { 243 case kLine_SegType: 244 if (pos) { 245 pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t), 246 SkScalarInterp(pts[0].fY, pts[1].fY, t)); 247 } 248 if (tangent) { 249 tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY); 250 } 251 break; 252 case kQuad_SegType: 253 SkEvalQuadAt(pts, t, pos, tangent); 254 if (tangent) { 255 tangent->normalize(); 256 } 257 break; 258 case kCubic_SegType: 259 SkEvalCubicAt(pts, t, pos, tangent, NULL); 260 if (tangent) { 261 tangent->normalize(); 262 } 263 break; 264 default: 265 SkDEBUGFAIL("unknown segType"); 266 } 267 } 268 269 static void seg_to(const SkTDArray<SkPoint>& segmentPts, int ptIndex, 270 int segType, SkScalar startT, SkScalar stopT, SkPath* dst) { 271 SkASSERT(startT >= 0 && startT <= SK_Scalar1); 272 SkASSERT(stopT >= 0 && stopT <= SK_Scalar1); 273 SkASSERT(startT <= stopT); 274 275 if (SkScalarNearlyZero(stopT - startT)) { 276 return; 277 } 278 279 const SkPoint* pts = &segmentPts[ptIndex]; 280 SkPoint tmp0[7], tmp1[7]; 281 282 switch (segType) { 283 case kLine_SegType: 284 if (stopT == kMaxTValue) { 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 (startT == 0) { 293 if (stopT == SK_Scalar1) { 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 (stopT == SK_Scalar1) { 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 (startT == 0) { 312 if (stopT == SK_Scalar1) { 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 (stopT == SK_Scalar1) { 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, 391 sizeof(Segment)); 392 // don't care if we hit an exact match or not, so we xor index if it is negative 393 index ^= (index >> 31); 394 seg = &seg[index]; 395 396 // now interpolate t-values with the prev segment (if possible) 397 SkScalar startT = 0, startD = 0; 398 // check if the prev segment is legal, and references the same set of points 399 if (index > 0) { 400 startD = seg[-1].fDistance; 401 if (seg[-1].fPtIndex == seg->fPtIndex) { 402 SkASSERT(seg[-1].fType == seg->fType); 403 startT = seg[-1].getScalarT(); 404 } 405 } 406 407 SkASSERT(seg->getScalarT() > startT); 408 SkASSERT(distance >= startD); 409 SkASSERT(seg->fDistance > startD); 410 411 *t = startT + SkScalarMulDiv(seg->getScalarT() - startT, 412 distance - startD, 413 seg->fDistance - startD); 414 return seg; 415 } 416 417 bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos, 418 SkVector* tangent) { 419 SkASSERT(fPath); 420 if (fPath == NULL) { 421 return false; 422 } 423 424 SkScalar length = this->getLength(); // call this to force computing it 425 int count = fSegments.count(); 426 427 if (count == 0 || length == 0) { 428 return false; 429 } 430 431 // pin the distance to a legal range 432 if (distance < 0) { 433 distance = 0; 434 } else if (distance > length) { 435 distance = length; 436 } 437 438 SkScalar t; 439 const Segment* seg = this->distanceToSegment(distance, &t); 440 441 compute_pos_tan(fPts, seg->fPtIndex, seg->fType, t, pos, tangent); 442 return true; 443 } 444 445 bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix, 446 MatrixFlags flags) { 447 SkPoint position; 448 SkVector tangent; 449 450 if (this->getPosTan(distance, &position, &tangent)) { 451 if (matrix) { 452 if (flags & kGetTangent_MatrixFlag) { 453 matrix->setSinCos(tangent.fY, tangent.fX, 0, 0); 454 } else { 455 matrix->reset(); 456 } 457 if (flags & kGetPosition_MatrixFlag) { 458 matrix->postTranslate(position.fX, position.fY); 459 } 460 } 461 return true; 462 } 463 return false; 464 } 465 466 bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst, 467 bool startWithMoveTo) { 468 SkASSERT(dst); 469 470 SkScalar length = this->getLength(); // ensure we have built our segments 471 472 if (startD < 0) { 473 startD = 0; 474 } 475 if (stopD > length) { 476 stopD = length; 477 } 478 if (startD >= stopD) { 479 return false; 480 } 481 482 SkPoint p; 483 SkScalar startT, stopT; 484 const Segment* seg = this->distanceToSegment(startD, &startT); 485 const Segment* stopSeg = this->distanceToSegment(stopD, &stopT); 486 SkASSERT(seg <= stopSeg); 487 488 if (startWithMoveTo) { 489 compute_pos_tan(fPts, seg->fPtIndex, seg->fType, startT, &p, NULL); 490 dst->moveTo(p); 491 } 492 493 if (seg->fPtIndex == stopSeg->fPtIndex) { 494 seg_to(fPts, seg->fPtIndex, seg->fType, startT, stopT, dst); 495 } else { 496 do { 497 seg_to(fPts, seg->fPtIndex, seg->fType, startT, SK_Scalar1, dst); 498 seg = SkPathMeasure::NextSegment(seg); 499 startT = 0; 500 } while (seg->fPtIndex < stopSeg->fPtIndex); 501 seg_to(fPts, seg->fPtIndex, seg->fType, 0, stopT, dst); 502 } 503 return true; 504 } 505 506 bool SkPathMeasure::isClosed() { 507 (void)this->getLength(); 508 return fIsClosed; 509 } 510 511 /** Move to the next contour in the path. Return true if one exists, or false if 512 we're done with the path. 513 */ 514 bool SkPathMeasure::nextContour() { 515 fLength = -1; 516 return this->getLength() > 0; 517 } 518 519 /////////////////////////////////////////////////////////////////////////////// 520 /////////////////////////////////////////////////////////////////////////////// 521 522 #ifdef SK_DEBUG 523 524 void SkPathMeasure::dump() { 525 SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count()); 526 527 for (int i = 0; i < fSegments.count(); i++) { 528 const Segment* seg = &fSegments[i]; 529 SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n", 530 i, seg->fDistance, seg->fPtIndex, seg->getScalarT(), 531 seg->fType); 532 } 533 } 534 535 #endif 536
