The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkPathMeasure.cpp

gfx/skia/trunk/src/core/SkPathMeasure.cpp

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial