SkDashPath.cpp 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469
  1. /*
  2. * Copyright 2014 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/core/SkPathMeasure.h"
  8. #include "include/core/SkStrokeRec.h"
  9. #include "src/core/SkPointPriv.h"
  10. #include "src/utils/SkDashPathPriv.h"
  11. #include <utility>
  12. static inline int is_even(int x) {
  13. return !(x & 1);
  14. }
  15. static SkScalar find_first_interval(const SkScalar intervals[], SkScalar phase,
  16. int32_t* index, int count) {
  17. for (int i = 0; i < count; ++i) {
  18. SkScalar gap = intervals[i];
  19. if (phase > gap || (phase == gap && gap)) {
  20. phase -= gap;
  21. } else {
  22. *index = i;
  23. return gap - phase;
  24. }
  25. }
  26. // If we get here, phase "appears" to be larger than our length. This
  27. // shouldn't happen with perfect precision, but we can accumulate errors
  28. // during the initial length computation (rounding can make our sum be too
  29. // big or too small. In that event, we just have to eat the error here.
  30. *index = 0;
  31. return intervals[0];
  32. }
  33. void SkDashPath::CalcDashParameters(SkScalar phase, const SkScalar intervals[], int32_t count,
  34. SkScalar* initialDashLength, int32_t* initialDashIndex,
  35. SkScalar* intervalLength, SkScalar* adjustedPhase) {
  36. SkScalar len = 0;
  37. for (int i = 0; i < count; i++) {
  38. len += intervals[i];
  39. }
  40. *intervalLength = len;
  41. // Adjust phase to be between 0 and len, "flipping" phase if negative.
  42. // e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
  43. if (adjustedPhase) {
  44. if (phase < 0) {
  45. phase = -phase;
  46. if (phase > len) {
  47. phase = SkScalarMod(phase, len);
  48. }
  49. phase = len - phase;
  50. // Due to finite precision, it's possible that phase == len,
  51. // even after the subtract (if len >>> phase), so fix that here.
  52. // This fixes http://crbug.com/124652 .
  53. SkASSERT(phase <= len);
  54. if (phase == len) {
  55. phase = 0;
  56. }
  57. } else if (phase >= len) {
  58. phase = SkScalarMod(phase, len);
  59. }
  60. *adjustedPhase = phase;
  61. }
  62. SkASSERT(phase >= 0 && phase < len);
  63. *initialDashLength = find_first_interval(intervals, phase,
  64. initialDashIndex, count);
  65. SkASSERT(*initialDashLength >= 0);
  66. SkASSERT(*initialDashIndex >= 0 && *initialDashIndex < count);
  67. }
  68. static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
  69. SkScalar radius = SkScalarHalf(rec.getWidth());
  70. if (0 == radius) {
  71. radius = SK_Scalar1; // hairlines
  72. }
  73. if (SkPaint::kMiter_Join == rec.getJoin()) {
  74. radius *= rec.getMiter();
  75. }
  76. rect->outset(radius, radius);
  77. }
  78. // If line is zero-length, bump out the end by a tiny amount
  79. // to draw endcaps. The bump factor is sized so that
  80. // SkPoint::Distance() computes a non-zero length.
  81. // Offsets SK_ScalarNearlyZero or smaller create empty paths when Iter measures length.
  82. // Large values are scaled by SK_ScalarNearlyZero so significant bits change.
  83. static void adjust_zero_length_line(SkPoint pts[2]) {
  84. SkASSERT(pts[0] == pts[1]);
  85. pts[1].fX += SkTMax(1.001f, pts[1].fX) * SK_ScalarNearlyZero;
  86. }
  87. static bool clip_line(SkPoint pts[2], const SkRect& bounds, SkScalar intervalLength,
  88. SkScalar priorPhase) {
  89. SkVector dxy = pts[1] - pts[0];
  90. // only horizontal or vertical lines
  91. if (dxy.fX && dxy.fY) {
  92. return false;
  93. }
  94. int xyOffset = SkToBool(dxy.fY); // 0 to adjust horizontal, 1 to adjust vertical
  95. SkScalar minXY = (&pts[0].fX)[xyOffset];
  96. SkScalar maxXY = (&pts[1].fX)[xyOffset];
  97. bool swapped = maxXY < minXY;
  98. if (swapped) {
  99. using std::swap;
  100. swap(minXY, maxXY);
  101. }
  102. SkASSERT(minXY <= maxXY);
  103. SkScalar leftTop = (&bounds.fLeft)[xyOffset];
  104. SkScalar rightBottom = (&bounds.fRight)[xyOffset];
  105. if (maxXY < leftTop || minXY > rightBottom) {
  106. return false;
  107. }
  108. // Now we actually perform the chop, removing the excess to the left/top and
  109. // right/bottom of the bounds (keeping our new line "in phase" with the dash,
  110. // hence the (mod intervalLength).
  111. if (minXY < leftTop) {
  112. minXY = leftTop - SkScalarMod(leftTop - minXY, intervalLength);
  113. if (!swapped) {
  114. minXY -= priorPhase; // for rectangles, adjust by prior phase
  115. }
  116. }
  117. if (maxXY > rightBottom) {
  118. maxXY = rightBottom + SkScalarMod(maxXY - rightBottom, intervalLength);
  119. if (swapped) {
  120. maxXY += priorPhase; // for rectangles, adjust by prior phase
  121. }
  122. }
  123. SkASSERT(maxXY >= minXY);
  124. if (swapped) {
  125. using std::swap;
  126. swap(minXY, maxXY);
  127. }
  128. (&pts[0].fX)[xyOffset] = minXY;
  129. (&pts[1].fX)[xyOffset] = maxXY;
  130. if (minXY == maxXY) {
  131. adjust_zero_length_line(pts);
  132. }
  133. return true;
  134. }
  135. static bool contains_inclusive(const SkRect& rect, const SkPoint& pt) {
  136. return rect.fLeft <= pt.fX && pt.fX <= rect.fRight &&
  137. rect.fTop <= pt.fY && pt.fY <= rect.fBottom;
  138. }
  139. // Returns true is b is between a and c, that is: a <= b <= c, or a >= b >= c.
  140. // Can perform this test with one branch by observing that, relative to b,
  141. // the condition is true only if one side is positive and one side is negative.
  142. // If the numbers are very small, the optimization may return the wrong result
  143. // because the multiply may generate a zero where the simple compare does not.
  144. // For this reason the assert does not fire when all three numbers are near zero.
  145. static bool between(SkScalar a, SkScalar b, SkScalar c) {
  146. SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
  147. || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
  148. return (a - b) * (c - b) <= 0;
  149. }
  150. // Only handles lines for now. If returns true, dstPath is the new (smaller)
  151. // path. If returns false, then dstPath parameter is ignored.
  152. static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
  153. const SkRect* cullRect, SkScalar intervalLength,
  154. SkPath* dstPath) {
  155. SkPoint pts[4];
  156. if (nullptr == cullRect) {
  157. if (srcPath.isLine(pts) && pts[0] == pts[1]) {
  158. adjust_zero_length_line(pts);
  159. } else {
  160. return false;
  161. }
  162. } else {
  163. SkRect bounds;
  164. bool isLine = srcPath.isLine(pts);
  165. bool isRect = !isLine && srcPath.isRect(nullptr);
  166. if (!isLine && !isRect) {
  167. return false;
  168. }
  169. bounds = *cullRect;
  170. outset_for_stroke(&bounds, rec);
  171. if (isRect) {
  172. // break rect into four lines, and call each one separately
  173. SkPath::Iter iter(srcPath, false);
  174. SkAssertResult(SkPath::kMove_Verb == iter.next(pts));
  175. SkScalar priorLength = 0;
  176. while (SkPath::kLine_Verb == iter.next(pts)) {
  177. SkVector v = pts[1] - pts[0];
  178. // if line is entirely outside clip rect, skip it
  179. if (v.fX ? between(bounds.fTop, pts[0].fY, bounds.fBottom) :
  180. between(bounds.fLeft, pts[0].fX, bounds.fRight)) {
  181. bool skipMoveTo = contains_inclusive(bounds, pts[0]);
  182. if (clip_line(pts, bounds, intervalLength,
  183. SkScalarMod(priorLength, intervalLength))) {
  184. if (0 == priorLength || !skipMoveTo) {
  185. dstPath->moveTo(pts[0]);
  186. }
  187. dstPath->lineTo(pts[1]);
  188. }
  189. }
  190. // keep track of all prior lengths to set phase of next line
  191. priorLength += SkScalarAbs(v.fX ? v.fX : v.fY);
  192. }
  193. return !dstPath->isEmpty();
  194. }
  195. SkASSERT(isLine);
  196. if (!clip_line(pts, bounds, intervalLength, 0)) {
  197. return false;
  198. }
  199. }
  200. dstPath->moveTo(pts[0]);
  201. dstPath->lineTo(pts[1]);
  202. return true;
  203. }
  204. class SpecialLineRec {
  205. public:
  206. bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
  207. int intervalCount, SkScalar intervalLength) {
  208. if (rec->isHairlineStyle() || !src.isLine(fPts)) {
  209. return false;
  210. }
  211. // can relax this in the future, if we handle square and round caps
  212. if (SkPaint::kButt_Cap != rec->getCap()) {
  213. return false;
  214. }
  215. SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
  216. fTangent = fPts[1] - fPts[0];
  217. if (fTangent.isZero()) {
  218. return false;
  219. }
  220. fPathLength = pathLength;
  221. fTangent.scale(SkScalarInvert(pathLength));
  222. SkPointPriv::RotateCCW(fTangent, &fNormal);
  223. fNormal.scale(SkScalarHalf(rec->getWidth()));
  224. // now estimate how many quads will be added to the path
  225. // resulting segments = pathLen * intervalCount / intervalLen
  226. // resulting points = 4 * segments
  227. SkScalar ptCount = pathLength * intervalCount / (float)intervalLength;
  228. ptCount = SkTMin(ptCount, SkDashPath::kMaxDashCount);
  229. int n = SkScalarCeilToInt(ptCount) << 2;
  230. dst->incReserve(n);
  231. // we will take care of the stroking
  232. rec->setFillStyle();
  233. return true;
  234. }
  235. void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
  236. SkASSERT(d0 <= fPathLength);
  237. // clamp the segment to our length
  238. if (d1 > fPathLength) {
  239. d1 = fPathLength;
  240. }
  241. SkScalar x0 = fPts[0].fX + fTangent.fX * d0;
  242. SkScalar x1 = fPts[0].fX + fTangent.fX * d1;
  243. SkScalar y0 = fPts[0].fY + fTangent.fY * d0;
  244. SkScalar y1 = fPts[0].fY + fTangent.fY * d1;
  245. SkPoint pts[4];
  246. pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo
  247. pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo
  248. pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo
  249. pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo
  250. path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
  251. }
  252. private:
  253. SkPoint fPts[2];
  254. SkVector fTangent;
  255. SkVector fNormal;
  256. SkScalar fPathLength;
  257. };
  258. bool SkDashPath::InternalFilter(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
  259. const SkRect* cullRect, const SkScalar aIntervals[],
  260. int32_t count, SkScalar initialDashLength, int32_t initialDashIndex,
  261. SkScalar intervalLength,
  262. StrokeRecApplication strokeRecApplication) {
  263. // we must always have an even number of intervals
  264. SkASSERT(is_even(count));
  265. // we do nothing if the src wants to be filled
  266. SkStrokeRec::Style style = rec->getStyle();
  267. if (SkStrokeRec::kFill_Style == style || SkStrokeRec::kStrokeAndFill_Style == style) {
  268. return false;
  269. }
  270. const SkScalar* intervals = aIntervals;
  271. SkScalar dashCount = 0;
  272. int segCount = 0;
  273. SkPath cullPathStorage;
  274. const SkPath* srcPtr = &src;
  275. if (cull_path(src, *rec, cullRect, intervalLength, &cullPathStorage)) {
  276. // if rect is closed, starts in a dash, and ends in a dash, add the initial join
  277. // potentially a better fix is described here: bug.skia.org/7445
  278. if (src.isRect(nullptr) && src.isLastContourClosed() && is_even(initialDashIndex)) {
  279. SkScalar pathLength = SkPathMeasure(src, false, rec->getResScale()).getLength();
  280. SkScalar endPhase = SkScalarMod(pathLength + initialDashLength, intervalLength);
  281. int index = 0;
  282. while (endPhase > intervals[index]) {
  283. endPhase -= intervals[index++];
  284. SkASSERT(index <= count);
  285. if (index == count) {
  286. // We have run out of intervals. endPhase "should" never get to this point,
  287. // but it could if the subtracts underflowed. Hence we will pin it as if it
  288. // perfectly ran through the intervals.
  289. // See crbug.com/875494 (and skbug.com/8274)
  290. endPhase = 0;
  291. break;
  292. }
  293. }
  294. // if dash ends inside "on", or ends at beginning of "off"
  295. if (is_even(index) == (endPhase > 0)) {
  296. SkPoint midPoint = src.getPoint(0);
  297. // get vector at end of rect
  298. int last = src.countPoints() - 1;
  299. while (midPoint == src.getPoint(last)) {
  300. --last;
  301. SkASSERT(last >= 0);
  302. }
  303. // get vector at start of rect
  304. int next = 1;
  305. while (midPoint == src.getPoint(next)) {
  306. ++next;
  307. SkASSERT(next < last);
  308. }
  309. SkVector v = midPoint - src.getPoint(last);
  310. const SkScalar kTinyOffset = SK_ScalarNearlyZero;
  311. // scale vector to make start of tiny right angle
  312. v *= kTinyOffset;
  313. cullPathStorage.moveTo(midPoint - v);
  314. cullPathStorage.lineTo(midPoint);
  315. v = midPoint - src.getPoint(next);
  316. // scale vector to make end of tiny right angle
  317. v *= kTinyOffset;
  318. cullPathStorage.lineTo(midPoint - v);
  319. }
  320. }
  321. srcPtr = &cullPathStorage;
  322. }
  323. SpecialLineRec lineRec;
  324. bool specialLine = (StrokeRecApplication::kAllow == strokeRecApplication) &&
  325. lineRec.init(*srcPtr, dst, rec, count >> 1, intervalLength);
  326. SkPathMeasure meas(*srcPtr, false, rec->getResScale());
  327. do {
  328. bool skipFirstSegment = meas.isClosed();
  329. bool addedSegment = false;
  330. SkScalar length = meas.getLength();
  331. int index = initialDashIndex;
  332. // Since the path length / dash length ratio may be arbitrarily large, we can exert
  333. // significant memory pressure while attempting to build the filtered path. To avoid this,
  334. // we simply give up dashing beyond a certain threshold.
  335. //
  336. // The original bug report (http://crbug.com/165432) is based on a path yielding more than
  337. // 90 million dash segments and crashing the memory allocator. A limit of 1 million
  338. // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
  339. // maximum dash memory overhead at roughly 17MB per path.
  340. dashCount += length * (count >> 1) / intervalLength;
  341. if (dashCount > kMaxDashCount) {
  342. dst->reset();
  343. return false;
  344. }
  345. // Using double precision to avoid looping indefinitely due to single precision rounding
  346. // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
  347. double distance = 0;
  348. double dlen = initialDashLength;
  349. while (distance < length) {
  350. SkASSERT(dlen >= 0);
  351. addedSegment = false;
  352. if (is_even(index) && !skipFirstSegment) {
  353. addedSegment = true;
  354. ++segCount;
  355. if (specialLine) {
  356. lineRec.addSegment(SkDoubleToScalar(distance),
  357. SkDoubleToScalar(distance + dlen),
  358. dst);
  359. } else {
  360. meas.getSegment(SkDoubleToScalar(distance),
  361. SkDoubleToScalar(distance + dlen),
  362. dst, true);
  363. }
  364. }
  365. distance += dlen;
  366. // clear this so we only respect it the first time around
  367. skipFirstSegment = false;
  368. // wrap around our intervals array if necessary
  369. index += 1;
  370. SkASSERT(index <= count);
  371. if (index == count) {
  372. index = 0;
  373. }
  374. // fetch our next dlen
  375. dlen = intervals[index];
  376. }
  377. // extend if we ended on a segment and we need to join up with the (skipped) initial segment
  378. if (meas.isClosed() && is_even(initialDashIndex) &&
  379. initialDashLength >= 0) {
  380. meas.getSegment(0, initialDashLength, dst, !addedSegment);
  381. ++segCount;
  382. }
  383. } while (meas.nextContour());
  384. if (segCount > 1) {
  385. dst->setConvexity(SkPath::kConcave_Convexity);
  386. }
  387. return true;
  388. }
  389. bool SkDashPath::FilterDashPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
  390. const SkRect* cullRect, const SkPathEffect::DashInfo& info) {
  391. if (!ValidDashPath(info.fPhase, info.fIntervals, info.fCount)) {
  392. return false;
  393. }
  394. SkScalar initialDashLength = 0;
  395. int32_t initialDashIndex = 0;
  396. SkScalar intervalLength = 0;
  397. CalcDashParameters(info.fPhase, info.fIntervals, info.fCount,
  398. &initialDashLength, &initialDashIndex, &intervalLength);
  399. return InternalFilter(dst, src, rec, cullRect, info.fIntervals, info.fCount, initialDashLength,
  400. initialDashIndex, intervalLength);
  401. }
  402. bool SkDashPath::ValidDashPath(SkScalar phase, const SkScalar intervals[], int32_t count) {
  403. if (count < 2 || !SkIsAlign2(count)) {
  404. return false;
  405. }
  406. SkScalar length = 0;
  407. for (int i = 0; i < count; i++) {
  408. if (intervals[i] < 0) {
  409. return false;
  410. }
  411. length += intervals[i];
  412. }
  413. // watch out for values that might make us go out of bounds
  414. return length > 0 && SkScalarIsFinite(phase) && SkScalarIsFinite(length);
  415. }