gfx/skia/trunk/src/effects/SkDashPathEffect.cpp@6474c204b198
gfx/skia/trunk/src/effects/SkDashPathEffect.cpp
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
2 /*
3 * Copyright 2006 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 */
10 #include "SkDashPathEffect.h"
11 #include "SkReadBuffer.h"
12 #include "SkWriteBuffer.h"
13 #include "SkPathMeasure.h"
15 static inline int is_even(int x) {
16 return (~x) << 31;
17 }
19 static SkScalar FindFirstInterval(const SkScalar intervals[], SkScalar phase,
20 int32_t* index, int count) {
21 for (int i = 0; i < count; ++i) {
22 if (phase > intervals[i]) {
23 phase -= intervals[i];
24 } else {
25 *index = i;
26 return intervals[i] - phase;
27 }
28 }
29 // If we get here, phase "appears" to be larger than our length. This
30 // shouldn't happen with perfect precision, but we can accumulate errors
31 // during the initial length computation (rounding can make our sum be too
32 // big or too small. In that event, we just have to eat the error here.
33 *index = 0;
34 return intervals[0];
35 }
37 SkDashPathEffect::SkDashPathEffect(const SkScalar intervals[], int count,
38 SkScalar phase, bool scaleToFit)
39 : fScaleToFit(scaleToFit) {
40 SkASSERT(intervals);
41 SkASSERT(count > 1 && SkAlign2(count) == count);
43 fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * count);
44 fCount = count;
46 SkScalar len = 0;
47 for (int i = 0; i < count; i++) {
48 SkASSERT(intervals[i] >= 0);
49 fIntervals[i] = intervals[i];
50 len += intervals[i];
51 }
52 fIntervalLength = len;
54 // watch out for values that might make us go out of bounds
55 if ((len > 0) && SkScalarIsFinite(phase) && SkScalarIsFinite(len)) {
57 // Adjust phase to be between 0 and len, "flipping" phase if negative.
58 // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
59 if (phase < 0) {
60 phase = -phase;
61 if (phase > len) {
62 phase = SkScalarMod(phase, len);
63 }
64 phase = len - phase;
66 // Due to finite precision, it's possible that phase == len,
67 // even after the subtract (if len >>> phase), so fix that here.
68 // This fixes http://crbug.com/124652 .
69 SkASSERT(phase <= len);
70 if (phase == len) {
71 phase = 0;
72 }
73 } else if (phase >= len) {
74 phase = SkScalarMod(phase, len);
75 }
76 SkASSERT(phase >= 0 && phase < len);
78 fInitialDashLength = FindFirstInterval(intervals, phase,
79 &fInitialDashIndex, count);
81 SkASSERT(fInitialDashLength >= 0);
82 SkASSERT(fInitialDashIndex >= 0 && fInitialDashIndex < fCount);
83 } else {
84 fInitialDashLength = -1; // signal bad dash intervals
85 }
86 }
88 SkDashPathEffect::~SkDashPathEffect() {
89 sk_free(fIntervals);
90 }
92 static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
93 SkScalar radius = SkScalarHalf(rec.getWidth());
94 if (0 == radius) {
95 radius = SK_Scalar1; // hairlines
96 }
97 if (SkPaint::kMiter_Join == rec.getJoin()) {
98 radius = SkScalarMul(radius, rec.getMiter());
99 }
100 rect->outset(radius, radius);
101 }
103 // Only handles lines for now. If returns true, dstPath is the new (smaller)
104 // path. If returns false, then dstPath parameter is ignored.
105 static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
106 const SkRect* cullRect, SkScalar intervalLength,
107 SkPath* dstPath) {
108 if (NULL == cullRect) {
109 return false;
110 }
112 SkPoint pts[2];
113 if (!srcPath.isLine(pts)) {
114 return false;
115 }
117 SkRect bounds = *cullRect;
118 outset_for_stroke(&bounds, rec);
120 SkScalar dx = pts[1].x() - pts[0].x();
121 SkScalar dy = pts[1].y() - pts[0].y();
123 // just do horizontal lines for now (lazy)
124 if (dy) {
125 return false;
126 }
128 SkScalar minX = pts[0].fX;
129 SkScalar maxX = pts[1].fX;
131 if (maxX < bounds.fLeft || minX > bounds.fRight) {
132 return false;
133 }
135 if (dx < 0) {
136 SkTSwap(minX, maxX);
137 }
139 // Now we actually perform the chop, removing the excess to the left and
140 // right of the bounds (keeping our new line "in phase" with the dash,
141 // hence the (mod intervalLength).
143 if (minX < bounds.fLeft) {
144 minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX,
145 intervalLength);
146 }
147 if (maxX > bounds.fRight) {
148 maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight,
149 intervalLength);
150 }
152 SkASSERT(maxX >= minX);
153 if (dx < 0) {
154 SkTSwap(minX, maxX);
155 }
156 pts[0].fX = minX;
157 pts[1].fX = maxX;
159 dstPath->moveTo(pts[0]);
160 dstPath->lineTo(pts[1]);
161 return true;
162 }
164 class SpecialLineRec {
165 public:
166 bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
167 int intervalCount, SkScalar intervalLength) {
168 if (rec->isHairlineStyle() || !src.isLine(fPts)) {
169 return false;
170 }
172 // can relax this in the future, if we handle square and round caps
173 if (SkPaint::kButt_Cap != rec->getCap()) {
174 return false;
175 }
177 SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
179 fTangent = fPts[1] - fPts[0];
180 if (fTangent.isZero()) {
181 return false;
182 }
184 fPathLength = pathLength;
185 fTangent.scale(SkScalarInvert(pathLength));
186 fTangent.rotateCCW(&fNormal);
187 fNormal.scale(SkScalarHalf(rec->getWidth()));
189 // now estimate how many quads will be added to the path
190 // resulting segments = pathLen * intervalCount / intervalLen
191 // resulting points = 4 * segments
193 SkScalar ptCount = SkScalarMulDiv(pathLength,
194 SkIntToScalar(intervalCount),
195 intervalLength);
196 int n = SkScalarCeilToInt(ptCount) << 2;
197 dst->incReserve(n);
199 // we will take care of the stroking
200 rec->setFillStyle();
201 return true;
202 }
204 void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
205 SkASSERT(d0 < fPathLength);
206 // clamp the segment to our length
207 if (d1 > fPathLength) {
208 d1 = fPathLength;
209 }
211 SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0);
212 SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1);
213 SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0);
214 SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1);
216 SkPoint pts[4];
217 pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo
218 pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo
219 pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo
220 pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo
222 path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
223 }
225 private:
226 SkPoint fPts[2];
227 SkVector fTangent;
228 SkVector fNormal;
229 SkScalar fPathLength;
230 };
232 bool SkDashPathEffect::filterPath(SkPath* dst, const SkPath& src,
233 SkStrokeRec* rec, const SkRect* cullRect) const {
234 // we do nothing if the src wants to be filled, or if our dashlength is 0
235 if (rec->isFillStyle() || fInitialDashLength < 0) {
236 return false;
237 }
239 const SkScalar* intervals = fIntervals;
240 SkScalar dashCount = 0;
241 int segCount = 0;
243 SkPath cullPathStorage;
244 const SkPath* srcPtr = &src;
245 if (cull_path(src, *rec, cullRect, fIntervalLength, &cullPathStorage)) {
246 srcPtr = &cullPathStorage;
247 }
249 SpecialLineRec lineRec;
250 bool specialLine = lineRec.init(*srcPtr, dst, rec, fCount >> 1, fIntervalLength);
252 SkPathMeasure meas(*srcPtr, false);
254 do {
255 bool skipFirstSegment = meas.isClosed();
256 bool addedSegment = false;
257 SkScalar length = meas.getLength();
258 int index = fInitialDashIndex;
259 SkScalar scale = SK_Scalar1;
261 // Since the path length / dash length ratio may be arbitrarily large, we can exert
262 // significant memory pressure while attempting to build the filtered path. To avoid this,
263 // we simply give up dashing beyond a certain threshold.
264 //
265 // The original bug report (http://crbug.com/165432) is based on a path yielding more than
266 // 90 million dash segments and crashing the memory allocator. A limit of 1 million
267 // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
268 // maximum dash memory overhead at roughly 17MB per path.
269 static const SkScalar kMaxDashCount = 1000000;
270 dashCount += length * (fCount >> 1) / fIntervalLength;
271 if (dashCount > kMaxDashCount) {
272 dst->reset();
273 return false;
274 }
276 if (fScaleToFit) {
277 if (fIntervalLength >= length) {
278 scale = SkScalarDiv(length, fIntervalLength);
279 } else {
280 SkScalar div = SkScalarDiv(length, fIntervalLength);
281 int n = SkScalarFloorToInt(div);
282 scale = SkScalarDiv(length, n * fIntervalLength);
283 }
284 }
286 // Using double precision to avoid looping indefinitely due to single precision rounding
287 // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
288 double distance = 0;
289 double dlen = SkScalarMul(fInitialDashLength, scale);
291 while (distance < length) {
292 SkASSERT(dlen >= 0);
293 addedSegment = false;
294 if (is_even(index) && dlen > 0 && !skipFirstSegment) {
295 addedSegment = true;
296 ++segCount;
298 if (specialLine) {
299 lineRec.addSegment(SkDoubleToScalar(distance),
300 SkDoubleToScalar(distance + dlen),
301 dst);
302 } else {
303 meas.getSegment(SkDoubleToScalar(distance),
304 SkDoubleToScalar(distance + dlen),
305 dst, true);
306 }
307 }
308 distance += dlen;
310 // clear this so we only respect it the first time around
311 skipFirstSegment = false;
313 // wrap around our intervals array if necessary
314 index += 1;
315 SkASSERT(index <= fCount);
316 if (index == fCount) {
317 index = 0;
318 }
320 // fetch our next dlen
321 dlen = SkScalarMul(intervals[index], scale);
322 }
324 // extend if we ended on a segment and we need to join up with the (skipped) initial segment
325 if (meas.isClosed() && is_even(fInitialDashIndex) &&
326 fInitialDashLength > 0) {
327 meas.getSegment(0, SkScalarMul(fInitialDashLength, scale), dst, !addedSegment);
328 ++segCount;
329 }
330 } while (meas.nextContour());
332 if (segCount > 1) {
333 dst->setConvexity(SkPath::kConcave_Convexity);
334 }
336 return true;
337 }
339 // Currently asPoints is more restrictive then it needs to be. In the future
340 // we need to:
341 // allow kRound_Cap capping (could allow rotations in the matrix with this)
342 // allow paths to be returned
343 bool SkDashPathEffect::asPoints(PointData* results,
344 const SkPath& src,
345 const SkStrokeRec& rec,
346 const SkMatrix& matrix,
347 const SkRect* cullRect) const {
348 // width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out
349 if (fInitialDashLength < 0 || 0 >= rec.getWidth()) {
350 return false;
351 }
353 // TODO: this next test could be eased up. We could allow any number of
354 // intervals as long as all the ons match and all the offs match.
355 // Additionally, they do not necessarily need to be integers.
356 // We cannot allow arbitrary intervals since we want the returned points
357 // to be uniformly sized.
358 if (fCount != 2 ||
359 !SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) ||
360 !SkScalarIsInt(fIntervals[0]) ||
361 !SkScalarIsInt(fIntervals[1])) {
362 return false;
363 }
365 // TODO: this next test could be eased up. The rescaling should not impact
366 // the equality of the ons & offs. However, we would need to remove the
367 // integer intervals restriction first
368 if (fScaleToFit) {
369 return false;
370 }
372 SkPoint pts[2];
374 if (!src.isLine(pts)) {
375 return false;
376 }
378 // TODO: this test could be eased up to allow circles
379 if (SkPaint::kButt_Cap != rec.getCap()) {
380 return false;
381 }
383 // TODO: this test could be eased up for circles. Rotations could be allowed.
384 if (!matrix.rectStaysRect()) {
385 return false;
386 }
388 SkScalar length = SkPoint::Distance(pts[1], pts[0]);
390 SkVector tangent = pts[1] - pts[0];
391 if (tangent.isZero()) {
392 return false;
393 }
395 tangent.scale(SkScalarInvert(length));
397 // TODO: make this test for horizontal & vertical lines more robust
398 bool isXAxis = true;
399 if (SK_Scalar1 == tangent.fX || -SK_Scalar1 == tangent.fX) {
400 results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth()));
401 } else if (SK_Scalar1 == tangent.fY || -SK_Scalar1 == tangent.fY) {
402 results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0]));
403 isXAxis = false;
404 } else if (SkPaint::kRound_Cap != rec.getCap()) {
405 // Angled lines don't have axis-aligned boxes.
406 return false;
407 }
409 if (NULL != results) {
410 results->fFlags = 0;
411 SkScalar clampedInitialDashLength = SkMinScalar(length, fInitialDashLength);
413 if (SkPaint::kRound_Cap == rec.getCap()) {
414 results->fFlags |= PointData::kCircles_PointFlag;
415 }
417 results->fNumPoints = 0;
418 SkScalar len2 = length;
419 if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
420 SkASSERT(len2 >= clampedInitialDashLength);
421 if (0 == fInitialDashIndex) {
422 if (clampedInitialDashLength > 0) {
423 if (clampedInitialDashLength >= fIntervals[0]) {
424 ++results->fNumPoints; // partial first dash
425 }
426 len2 -= clampedInitialDashLength;
427 }
428 len2 -= fIntervals[1]; // also skip first space
429 if (len2 < 0) {
430 len2 = 0;
431 }
432 } else {
433 len2 -= clampedInitialDashLength; // skip initial partial empty
434 }
435 }
436 int numMidPoints = SkScalarFloorToInt(SkScalarDiv(len2, fIntervalLength));
437 results->fNumPoints += numMidPoints;
438 len2 -= numMidPoints * fIntervalLength;
439 bool partialLast = false;
440 if (len2 > 0) {
441 if (len2 < fIntervals[0]) {
442 partialLast = true;
443 } else {
444 ++numMidPoints;
445 ++results->fNumPoints;
446 }
447 }
449 results->fPoints = new SkPoint[results->fNumPoints];
451 SkScalar distance = 0;
452 int curPt = 0;
454 if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
455 SkASSERT(clampedInitialDashLength <= length);
457 if (0 == fInitialDashIndex) {
458 if (clampedInitialDashLength > 0) {
459 // partial first block
460 SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
461 SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, SkScalarHalf(clampedInitialDashLength));
462 SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, SkScalarHalf(clampedInitialDashLength));
463 SkScalar halfWidth, halfHeight;
464 if (isXAxis) {
465 halfWidth = SkScalarHalf(clampedInitialDashLength);
466 halfHeight = SkScalarHalf(rec.getWidth());
467 } else {
468 halfWidth = SkScalarHalf(rec.getWidth());
469 halfHeight = SkScalarHalf(clampedInitialDashLength);
470 }
471 if (clampedInitialDashLength < fIntervals[0]) {
472 // This one will not be like the others
473 results->fFirst.addRect(x - halfWidth, y - halfHeight,
474 x + halfWidth, y + halfHeight);
475 } else {
476 SkASSERT(curPt < results->fNumPoints);
477 results->fPoints[curPt].set(x, y);
478 ++curPt;
479 }
481 distance += clampedInitialDashLength;
482 }
484 distance += fIntervals[1]; // skip over the next blank block too
485 } else {
486 distance += clampedInitialDashLength;
487 }
488 }
490 if (0 != numMidPoints) {
491 distance += SkScalarHalf(fIntervals[0]);
493 for (int i = 0; i < numMidPoints; ++i) {
494 SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance);
495 SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance);
497 SkASSERT(curPt < results->fNumPoints);
498 results->fPoints[curPt].set(x, y);
499 ++curPt;
501 distance += fIntervalLength;
502 }
504 distance -= SkScalarHalf(fIntervals[0]);
505 }
507 if (partialLast) {
508 // partial final block
509 SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
510 SkScalar temp = length - distance;
511 SkASSERT(temp < fIntervals[0]);
512 SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance + SkScalarHalf(temp));
513 SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance + SkScalarHalf(temp));
514 SkScalar halfWidth, halfHeight;
515 if (isXAxis) {
516 halfWidth = SkScalarHalf(temp);
517 halfHeight = SkScalarHalf(rec.getWidth());
518 } else {
519 halfWidth = SkScalarHalf(rec.getWidth());
520 halfHeight = SkScalarHalf(temp);
521 }
522 results->fLast.addRect(x - halfWidth, y - halfHeight,
523 x + halfWidth, y + halfHeight);
524 }
526 SkASSERT(curPt == results->fNumPoints);
527 }
529 return true;
530 }
532 SkFlattenable::Factory SkDashPathEffect::getFactory() const {
533 return CreateProc;
534 }
536 void SkDashPathEffect::flatten(SkWriteBuffer& buffer) const {
537 this->INHERITED::flatten(buffer);
538 buffer.writeInt(fInitialDashIndex);
539 buffer.writeScalar(fInitialDashLength);
540 buffer.writeScalar(fIntervalLength);
541 buffer.writeBool(fScaleToFit);
542 buffer.writeScalarArray(fIntervals, fCount);
543 }
545 SkFlattenable* SkDashPathEffect::CreateProc(SkReadBuffer& buffer) {
546 return SkNEW_ARGS(SkDashPathEffect, (buffer));
547 }
549 SkDashPathEffect::SkDashPathEffect(SkReadBuffer& buffer) : INHERITED(buffer) {
550 fInitialDashIndex = buffer.readInt();
551 fInitialDashLength = buffer.readScalar();
552 fIntervalLength = buffer.readScalar();
553 fScaleToFit = buffer.readBool();
555 fCount = buffer.getArrayCount();
556 size_t allocSize = sizeof(SkScalar) * fCount;
557 if (buffer.validateAvailable(allocSize)) {
558 fIntervals = (SkScalar*)sk_malloc_throw(allocSize);
559 buffer.readScalarArray(fIntervals, fCount);
560 } else {
561 fIntervals = NULL;
562 }
563 }
