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
tValue2Scalar(int t)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
getScalarT() const42 SkScalar SkPathMeasure::Segment::getScalarT() const {
43 return tValue2Scalar(fTValue);
44 }
45
NextSegment(const Segment * seg)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
tspan_big_enough(int tspan)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
quad_too_curvy(const SkPoint pts[3])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
cheap_dist_exceeds_limit(const SkPoint & pt,SkScalar x,SkScalar y)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
cubic_too_curvy(const SkPoint pts[4])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
compute_quad_segs(const SkPoint pts[3],SkScalar distance,int mint,int maxt,int ptIndex)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
compute_cubic_segs(const SkPoint pts[4],SkScalar distance,int mint,int maxt,int ptIndex)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
buildSegments()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
sk_get_path_points(const SkPath & path,int index)243 const SkPoint* sk_get_path_points(const SkPath& path, int index) {
244 return &path.fPts[index];
245 }
246
compute_pos_tan(const SkPath & path,int firstPtIndex,int ptIndex,int segType,SkScalar t,SkPoint * pos,SkVector * tangent)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
seg_to(const SkPath & src,int firstPtIndex,int ptIndex,int segType,SkScalar startT,SkScalar stopT,SkPath * dst)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
SkPathMeasure()359 SkPathMeasure::SkPathMeasure() {
360 fPath = NULL;
361 fLength = -1; // signal we need to compute it
362 fForceClosed = false;
363 fFirstPtIndex = -1;
364 }
365
SkPathMeasure(const SkPath & path,bool forceClosed)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
~SkPathMeasure()375 SkPathMeasure::~SkPathMeasure() {}
376
377 /** Assign a new path, or null to have none.
378 */
setPath(const SkPath * path,bool forceClosed)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
getLength()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
distanceToSegment(SkScalar distance,SkScalar * t)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
getPosTan(SkScalar distance,SkPoint * pos,SkVector * tangent)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
getMatrix(SkScalar distance,SkMatrix * matrix,MatrixFlags flags)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
getSegment(SkScalar startD,SkScalar stopD,SkPath * dst,bool startWithMoveTo)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
isClosed()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 */
nextContour()540 bool SkPathMeasure::nextContour() {
541 fLength = -1;
542 return this->getLength() > 0;
543 }
544
545 ///////////////////////////////////////////////////////////////////////////////
546 ///////////////////////////////////////////////////////////////////////////////
547
548 #ifdef SK_DEBUG
549
dump()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