SkStroke.cpp 60 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579
  1. /*
  2. * Copyright 2008 The Android Open Source Project
  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 "src/core/SkStrokerPriv.h"
  8. #include "include/private/SkMacros.h"
  9. #include "include/private/SkTo.h"
  10. #include "src/core/SkGeometry.h"
  11. #include "src/core/SkPathPriv.h"
  12. #include "src/core/SkPointPriv.h"
  13. #include <utility>
  14. enum {
  15. kTangent_RecursiveLimit,
  16. kCubic_RecursiveLimit,
  17. kConic_RecursiveLimit,
  18. kQuad_RecursiveLimit
  19. };
  20. // quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure
  21. // largest seen for normal cubics : 5, 26
  22. // largest seen for normal quads : 11
  23. static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3, 11*3 }; // 3x limits seen in practice
  24. static_assert(0 == kTangent_RecursiveLimit, "cubic_stroke_relies_on_tangent_equalling_zero");
  25. static_assert(1 == kCubic_RecursiveLimit, "cubic_stroke_relies_on_cubic_equalling_one");
  26. static_assert(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1,
  27. "recursive_limits_mismatch");
  28. #if defined SK_DEBUG && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
  29. int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 };
  30. #endif
  31. #ifndef DEBUG_QUAD_STROKER
  32. #define DEBUG_QUAD_STROKER 0
  33. #endif
  34. #if DEBUG_QUAD_STROKER
  35. /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting
  36. stroke has more than the optimal number of quadratics and lines */
  37. #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
  38. SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \
  39. SkDebugf(" " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \
  40. resultType
  41. #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__
  42. #else
  43. #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
  44. resultType
  45. #define STROKER_DEBUG_PARAMS(...)
  46. #endif
  47. static inline bool degenerate_vector(const SkVector& v) {
  48. return !SkPointPriv::CanNormalize(v.fX, v.fY);
  49. }
  50. static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after, SkScalar scale,
  51. SkScalar radius,
  52. SkVector* normal, SkVector* unitNormal) {
  53. if (!unitNormal->setNormalize((after.fX - before.fX) * scale,
  54. (after.fY - before.fY) * scale)) {
  55. return false;
  56. }
  57. SkPointPriv::RotateCCW(unitNormal);
  58. unitNormal->scale(radius, normal);
  59. return true;
  60. }
  61. static bool set_normal_unitnormal(const SkVector& vec,
  62. SkScalar radius,
  63. SkVector* normal, SkVector* unitNormal) {
  64. if (!unitNormal->setNormalize(vec.fX, vec.fY)) {
  65. return false;
  66. }
  67. SkPointPriv::RotateCCW(unitNormal);
  68. unitNormal->scale(radius, normal);
  69. return true;
  70. }
  71. ///////////////////////////////////////////////////////////////////////////////
  72. struct SkQuadConstruct { // The state of the quad stroke under construction.
  73. SkPoint fQuad[3]; // the stroked quad parallel to the original curve
  74. SkPoint fTangentStart; // a point tangent to fQuad[0]
  75. SkPoint fTangentEnd; // a point tangent to fQuad[2]
  76. SkScalar fStartT; // a segment of the original curve
  77. SkScalar fMidT; // "
  78. SkScalar fEndT; // "
  79. bool fStartSet; // state to share common points across structs
  80. bool fEndSet; // "
  81. bool fOppositeTangents; // set if coincident tangents have opposite directions
  82. // return false if start and end are too close to have a unique middle
  83. bool init(SkScalar start, SkScalar end) {
  84. fStartT = start;
  85. fMidT = (start + end) * SK_ScalarHalf;
  86. fEndT = end;
  87. fStartSet = fEndSet = false;
  88. return fStartT < fMidT && fMidT < fEndT;
  89. }
  90. bool initWithStart(SkQuadConstruct* parent) {
  91. if (!init(parent->fStartT, parent->fMidT)) {
  92. return false;
  93. }
  94. fQuad[0] = parent->fQuad[0];
  95. fTangentStart = parent->fTangentStart;
  96. fStartSet = true;
  97. return true;
  98. }
  99. bool initWithEnd(SkQuadConstruct* parent) {
  100. if (!init(parent->fMidT, parent->fEndT)) {
  101. return false;
  102. }
  103. fQuad[2] = parent->fQuad[2];
  104. fTangentEnd = parent->fTangentEnd;
  105. fEndSet = true;
  106. return true;
  107. }
  108. };
  109. class SkPathStroker {
  110. public:
  111. SkPathStroker(const SkPath& src,
  112. SkScalar radius, SkScalar miterLimit, SkPaint::Cap,
  113. SkPaint::Join, SkScalar resScale,
  114. bool canIgnoreCenter);
  115. bool hasOnlyMoveTo() const { return 0 == fSegmentCount; }
  116. SkPoint moveToPt() const { return fFirstPt; }
  117. void moveTo(const SkPoint&);
  118. void lineTo(const SkPoint&, const SkPath::Iter* iter = nullptr);
  119. void quadTo(const SkPoint&, const SkPoint&);
  120. void conicTo(const SkPoint&, const SkPoint&, SkScalar weight);
  121. void cubicTo(const SkPoint&, const SkPoint&, const SkPoint&);
  122. void close(bool isLine) { this->finishContour(true, isLine); }
  123. void done(SkPath* dst, bool isLine) {
  124. this->finishContour(false, isLine);
  125. dst->swap(fOuter);
  126. }
  127. SkScalar getResScale() const { return fResScale; }
  128. bool isCurrentContourEmpty() const {
  129. return fInner.isZeroLengthSincePoint(0) &&
  130. fOuter.isZeroLengthSincePoint(fFirstOuterPtIndexInContour);
  131. }
  132. private:
  133. SkScalar fRadius;
  134. SkScalar fInvMiterLimit;
  135. SkScalar fResScale;
  136. SkScalar fInvResScale;
  137. SkScalar fInvResScaleSquared;
  138. SkVector fFirstNormal, fPrevNormal, fFirstUnitNormal, fPrevUnitNormal;
  139. SkPoint fFirstPt, fPrevPt; // on original path
  140. SkPoint fFirstOuterPt;
  141. int fFirstOuterPtIndexInContour;
  142. int fSegmentCount;
  143. bool fPrevIsLine;
  144. bool fCanIgnoreCenter;
  145. SkStrokerPriv::CapProc fCapper;
  146. SkStrokerPriv::JoinProc fJoiner;
  147. SkPath fInner, fOuter, fCusper; // outer is our working answer, inner is temp
  148. enum StrokeType {
  149. kOuter_StrokeType = 1, // use sign-opposite values later to flip perpendicular axis
  150. kInner_StrokeType = -1
  151. } fStrokeType;
  152. enum ResultType {
  153. kSplit_ResultType, // the caller should split the quad stroke in two
  154. kDegenerate_ResultType, // the caller should add a line
  155. kQuad_ResultType, // the caller should (continue to try to) add a quad stroke
  156. };
  157. enum ReductionType {
  158. kPoint_ReductionType, // all curve points are practically identical
  159. kLine_ReductionType, // the control point is on the line between the ends
  160. kQuad_ReductionType, // the control point is outside the line between the ends
  161. kDegenerate_ReductionType, // the control point is on the line but outside the ends
  162. kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic)
  163. kDegenerate3_ReductionType, // three areas of max curvature found (for cubic)
  164. };
  165. enum IntersectRayType {
  166. kCtrlPt_RayType,
  167. kResultType_RayType,
  168. };
  169. int fRecursionDepth; // track stack depth to abort if numerics run amok
  170. bool fFoundTangents; // do less work until tangents meet (cubic)
  171. bool fJoinCompleted; // previous join was not degenerate
  172. void addDegenerateLine(const SkQuadConstruct* );
  173. static ReductionType CheckConicLinear(const SkConic& , SkPoint* reduction);
  174. static ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3],
  175. const SkPoint** tanPtPtr);
  176. static ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction);
  177. ResultType compareQuadConic(const SkConic& , SkQuadConstruct* ) const;
  178. ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* );
  179. ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* );
  180. void conicPerpRay(const SkConic& , SkScalar t, SkPoint* tPt, SkPoint* onPt,
  181. SkPoint* tangent) const;
  182. void conicQuadEnds(const SkConic& , SkQuadConstruct* ) const;
  183. bool conicStroke(const SkConic& , SkQuadConstruct* );
  184. bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const;
  185. void cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
  186. SkPoint* tangent) const;
  187. void cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* );
  188. void cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const;
  189. bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* );
  190. void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd);
  191. ResultType intersectRay(SkQuadConstruct* , IntersectRayType STROKER_DEBUG_PARAMS(int) ) const;
  192. bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const;
  193. void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
  194. SkPoint* tangent) const;
  195. bool quadStroke(const SkPoint quad[3], SkQuadConstruct* );
  196. void setConicEndNormal(const SkConic& ,
  197. const SkVector& normalAB, const SkVector& unitNormalAB,
  198. SkVector* normalBC, SkVector* unitNormalBC);
  199. void setCubicEndNormal(const SkPoint cubic[4],
  200. const SkVector& normalAB, const SkVector& unitNormalAB,
  201. SkVector* normalCD, SkVector* unitNormalCD);
  202. void setQuadEndNormal(const SkPoint quad[3],
  203. const SkVector& normalAB, const SkVector& unitNormalAB,
  204. SkVector* normalBC, SkVector* unitNormalBC);
  205. void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const;
  206. static bool SlightAngle(SkQuadConstruct* );
  207. ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2],
  208. SkQuadConstruct* STROKER_DEBUG_PARAMS(int depth) ) const;
  209. ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* );
  210. void finishContour(bool close, bool isLine);
  211. bool preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal,
  212. bool isLine);
  213. void postJoinTo(const SkPoint&, const SkVector& normal,
  214. const SkVector& unitNormal);
  215. void line_to(const SkPoint& currPt, const SkVector& normal);
  216. };
  217. ///////////////////////////////////////////////////////////////////////////////
  218. bool SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal,
  219. SkVector* unitNormal, bool currIsLine) {
  220. SkASSERT(fSegmentCount >= 0);
  221. SkScalar prevX = fPrevPt.fX;
  222. SkScalar prevY = fPrevPt.fY;
  223. if (!set_normal_unitnormal(fPrevPt, currPt, fResScale, fRadius, normal, unitNormal)) {
  224. if (SkStrokerPriv::CapFactory(SkPaint::kButt_Cap) == fCapper) {
  225. return false;
  226. }
  227. /* Square caps and round caps draw even if the segment length is zero.
  228. Since the zero length segment has no direction, set the orientation
  229. to upright as the default orientation */
  230. normal->set(fRadius, 0);
  231. unitNormal->set(1, 0);
  232. }
  233. if (fSegmentCount == 0) {
  234. fFirstNormal = *normal;
  235. fFirstUnitNormal = *unitNormal;
  236. fFirstOuterPt.set(prevX + normal->fX, prevY + normal->fY);
  237. fOuter.moveTo(fFirstOuterPt.fX, fFirstOuterPt.fY);
  238. fInner.moveTo(prevX - normal->fX, prevY - normal->fY);
  239. } else { // we have a previous segment
  240. fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, *unitNormal,
  241. fRadius, fInvMiterLimit, fPrevIsLine, currIsLine);
  242. }
  243. fPrevIsLine = currIsLine;
  244. return true;
  245. }
  246. void SkPathStroker::postJoinTo(const SkPoint& currPt, const SkVector& normal,
  247. const SkVector& unitNormal) {
  248. fJoinCompleted = true;
  249. fPrevPt = currPt;
  250. fPrevUnitNormal = unitNormal;
  251. fPrevNormal = normal;
  252. fSegmentCount += 1;
  253. }
  254. void SkPathStroker::finishContour(bool close, bool currIsLine) {
  255. if (fSegmentCount > 0) {
  256. SkPoint pt;
  257. if (close) {
  258. fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt,
  259. fFirstUnitNormal, fRadius, fInvMiterLimit,
  260. fPrevIsLine, currIsLine);
  261. fOuter.close();
  262. if (fCanIgnoreCenter) {
  263. // If we can ignore the center just make sure the larger of the two paths
  264. // is preserved and don't add the smaller one.
  265. if (fInner.getBounds().contains(fOuter.getBounds())) {
  266. fInner.swap(fOuter);
  267. }
  268. } else {
  269. // now add fInner as its own contour
  270. fInner.getLastPt(&pt);
  271. fOuter.moveTo(pt.fX, pt.fY);
  272. fOuter.reversePathTo(fInner);
  273. fOuter.close();
  274. }
  275. } else { // add caps to start and end
  276. // cap the end
  277. fInner.getLastPt(&pt);
  278. fCapper(&fOuter, fPrevPt, fPrevNormal, pt,
  279. currIsLine ? &fInner : nullptr);
  280. fOuter.reversePathTo(fInner);
  281. // cap the start
  282. fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt,
  283. fPrevIsLine ? &fInner : nullptr);
  284. fOuter.close();
  285. }
  286. if (!fCusper.isEmpty()) {
  287. fOuter.addPath(fCusper);
  288. fCusper.rewind();
  289. }
  290. }
  291. // since we may re-use fInner, we rewind instead of reset, to save on
  292. // reallocating its internal storage.
  293. fInner.rewind();
  294. fSegmentCount = -1;
  295. fFirstOuterPtIndexInContour = fOuter.countPoints();
  296. }
  297. ///////////////////////////////////////////////////////////////////////////////
  298. SkPathStroker::SkPathStroker(const SkPath& src,
  299. SkScalar radius, SkScalar miterLimit,
  300. SkPaint::Cap cap, SkPaint::Join join, SkScalar resScale,
  301. bool canIgnoreCenter)
  302. : fRadius(radius)
  303. , fResScale(resScale)
  304. , fCanIgnoreCenter(canIgnoreCenter) {
  305. /* This is only used when join is miter_join, but we initialize it here
  306. so that it is always defined, to fis valgrind warnings.
  307. */
  308. fInvMiterLimit = 0;
  309. if (join == SkPaint::kMiter_Join) {
  310. if (miterLimit <= SK_Scalar1) {
  311. join = SkPaint::kBevel_Join;
  312. } else {
  313. fInvMiterLimit = SkScalarInvert(miterLimit);
  314. }
  315. }
  316. fCapper = SkStrokerPriv::CapFactory(cap);
  317. fJoiner = SkStrokerPriv::JoinFactory(join);
  318. fSegmentCount = -1;
  319. fFirstOuterPtIndexInContour = 0;
  320. fPrevIsLine = false;
  321. // Need some estimate of how large our final result (fOuter)
  322. // and our per-contour temp (fInner) will be, so we don't spend
  323. // extra time repeatedly growing these arrays.
  324. //
  325. // 3x for result == inner + outer + join (swag)
  326. // 1x for inner == 'wag' (worst contour length would be better guess)
  327. fOuter.incReserve(src.countPoints() * 3);
  328. fOuter.setIsVolatile(true);
  329. fInner.incReserve(src.countPoints());
  330. fInner.setIsVolatile(true);
  331. // TODO : write a common error function used by stroking and filling
  332. // The '4' below matches the fill scan converter's error term
  333. fInvResScale = SkScalarInvert(resScale * 4);
  334. fInvResScaleSquared = fInvResScale * fInvResScale;
  335. fRecursionDepth = 0;
  336. }
  337. void SkPathStroker::moveTo(const SkPoint& pt) {
  338. if (fSegmentCount > 0) {
  339. this->finishContour(false, false);
  340. }
  341. fSegmentCount = 0;
  342. fFirstPt = fPrevPt = pt;
  343. fJoinCompleted = false;
  344. }
  345. void SkPathStroker::line_to(const SkPoint& currPt, const SkVector& normal) {
  346. fOuter.lineTo(currPt.fX + normal.fX, currPt.fY + normal.fY);
  347. fInner.lineTo(currPt.fX - normal.fX, currPt.fY - normal.fY);
  348. }
  349. static bool has_valid_tangent(const SkPath::Iter* iter) {
  350. SkPath::Iter copy = *iter;
  351. SkPath::Verb verb;
  352. SkPoint pts[4];
  353. while ((verb = copy.next(pts))) {
  354. switch (verb) {
  355. case SkPath::kMove_Verb:
  356. return false;
  357. case SkPath::kLine_Verb:
  358. if (pts[0] == pts[1]) {
  359. continue;
  360. }
  361. return true;
  362. case SkPath::kQuad_Verb:
  363. case SkPath::kConic_Verb:
  364. if (pts[0] == pts[1] && pts[0] == pts[2]) {
  365. continue;
  366. }
  367. return true;
  368. case SkPath::kCubic_Verb:
  369. if (pts[0] == pts[1] && pts[0] == pts[2] && pts[0] == pts[3]) {
  370. continue;
  371. }
  372. return true;
  373. case SkPath::kClose_Verb:
  374. case SkPath::kDone_Verb:
  375. return false;
  376. }
  377. }
  378. return false;
  379. }
  380. void SkPathStroker::lineTo(const SkPoint& currPt, const SkPath::Iter* iter) {
  381. bool teenyLine = SkPointPriv::EqualsWithinTolerance(fPrevPt, currPt, SK_ScalarNearlyZero * fInvResScale);
  382. if (SkStrokerPriv::CapFactory(SkPaint::kButt_Cap) == fCapper && teenyLine) {
  383. return;
  384. }
  385. if (teenyLine && (fJoinCompleted || (iter && has_valid_tangent(iter)))) {
  386. return;
  387. }
  388. SkVector normal, unitNormal;
  389. if (!this->preJoinTo(currPt, &normal, &unitNormal, true)) {
  390. return;
  391. }
  392. this->line_to(currPt, normal);
  393. this->postJoinTo(currPt, normal, unitNormal);
  394. }
  395. void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB,
  396. const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) {
  397. if (!set_normal_unitnormal(quad[1], quad[2], fResScale, fRadius, normalBC, unitNormalBC)) {
  398. *normalBC = normalAB;
  399. *unitNormalBC = unitNormalAB;
  400. }
  401. }
  402. void SkPathStroker::setConicEndNormal(const SkConic& conic, const SkVector& normalAB,
  403. const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) {
  404. setQuadEndNormal(conic.fPts, normalAB, unitNormalAB, normalBC, unitNormalBC);
  405. }
  406. void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB,
  407. const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) {
  408. SkVector ab = cubic[1] - cubic[0];
  409. SkVector cd = cubic[3] - cubic[2];
  410. bool degenerateAB = degenerate_vector(ab);
  411. bool degenerateCD = degenerate_vector(cd);
  412. if (degenerateAB && degenerateCD) {
  413. goto DEGENERATE_NORMAL;
  414. }
  415. if (degenerateAB) {
  416. ab = cubic[2] - cubic[0];
  417. degenerateAB = degenerate_vector(ab);
  418. }
  419. if (degenerateCD) {
  420. cd = cubic[3] - cubic[1];
  421. degenerateCD = degenerate_vector(cd);
  422. }
  423. if (degenerateAB || degenerateCD) {
  424. DEGENERATE_NORMAL:
  425. *normalCD = normalAB;
  426. *unitNormalCD = unitNormalAB;
  427. return;
  428. }
  429. SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD));
  430. }
  431. void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart,
  432. SkScalar tEnd) {
  433. fStrokeType = strokeType;
  434. fFoundTangents = false;
  435. quadPts->init(tStart, tEnd);
  436. }
  437. // returns the distance squared from the point to the line
  438. static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) {
  439. SkVector dxy = lineEnd - lineStart;
  440. SkVector ab0 = pt - lineStart;
  441. SkScalar numer = dxy.dot(ab0);
  442. SkScalar denom = dxy.dot(dxy);
  443. SkScalar t = sk_ieee_float_divide(numer, denom);
  444. if (t >= 0 && t <= 1) {
  445. SkPoint hit;
  446. hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t;
  447. hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t;
  448. return SkPointPriv::DistanceToSqd(hit, pt);
  449. } else {
  450. return SkPointPriv::DistanceToSqd(pt, lineStart);
  451. }
  452. }
  453. /* Given a cubic, determine if all four points are in a line.
  454. Return true if the inner points is close to a line connecting the outermost points.
  455. Find the outermost point by looking for the largest difference in X or Y.
  456. Given the indices of the outermost points, and that outer_1 is greater than outer_2,
  457. this table shows the index of the smaller of the remaining points:
  458. outer_2
  459. 0 1 2 3
  460. outer_1 ----------------
  461. 0 | - 2 1 1
  462. 1 | - - 0 0
  463. 2 | - - - 0
  464. 3 | - - - -
  465. If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2.
  466. This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1
  467. Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is:
  468. mid_2 == (outer_1 ^ outer_2 ^ mid_1)
  469. */
  470. static bool cubic_in_line(const SkPoint cubic[4]) {
  471. SkScalar ptMax = -1;
  472. int outer1 SK_INIT_TO_AVOID_WARNING;
  473. int outer2 SK_INIT_TO_AVOID_WARNING;
  474. for (int index = 0; index < 3; ++index) {
  475. for (int inner = index + 1; inner < 4; ++inner) {
  476. SkVector testDiff = cubic[inner] - cubic[index];
  477. SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
  478. if (ptMax < testMax) {
  479. outer1 = index;
  480. outer2 = inner;
  481. ptMax = testMax;
  482. }
  483. }
  484. }
  485. SkASSERT(outer1 >= 0 && outer1 <= 2);
  486. SkASSERT(outer2 >= 1 && outer2 <= 3);
  487. SkASSERT(outer1 < outer2);
  488. int mid1 = (1 + (2 >> outer2)) >> outer1;
  489. SkASSERT(mid1 >= 0 && mid1 <= 2);
  490. SkASSERT(outer1 != mid1 && outer2 != mid1);
  491. int mid2 = outer1 ^ outer2 ^ mid1;
  492. SkASSERT(mid2 >= 1 && mid2 <= 3);
  493. SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1);
  494. SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f);
  495. SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air
  496. return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop
  497. && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop;
  498. }
  499. /* Given quad, see if all there points are in a line.
  500. Return true if the inside point is close to a line connecting the outermost points.
  501. Find the outermost point by looking for the largest difference in X or Y.
  502. Since the XOR of the indices is 3 (0 ^ 1 ^ 2)
  503. the missing index equals: outer_1 ^ outer_2 ^ 3
  504. */
  505. static bool quad_in_line(const SkPoint quad[3]) {
  506. SkScalar ptMax = -1;
  507. int outer1 SK_INIT_TO_AVOID_WARNING;
  508. int outer2 SK_INIT_TO_AVOID_WARNING;
  509. for (int index = 0; index < 2; ++index) {
  510. for (int inner = index + 1; inner < 3; ++inner) {
  511. SkVector testDiff = quad[inner] - quad[index];
  512. SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
  513. if (ptMax < testMax) {
  514. outer1 = index;
  515. outer2 = inner;
  516. ptMax = testMax;
  517. }
  518. }
  519. }
  520. SkASSERT(outer1 >= 0 && outer1 <= 1);
  521. SkASSERT(outer2 >= 1 && outer2 <= 2);
  522. SkASSERT(outer1 < outer2);
  523. int mid = outer1 ^ outer2 ^ 3;
  524. const float kCurvatureSlop = 0.000005f; // this multiplier is pulled out of the air
  525. SkScalar lineSlop = ptMax * ptMax * kCurvatureSlop;
  526. return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop;
  527. }
  528. static bool conic_in_line(const SkConic& conic) {
  529. return quad_in_line(conic.fPts);
  530. }
  531. SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4],
  532. SkPoint reduction[3], const SkPoint** tangentPtPtr) {
  533. bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]);
  534. bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]);
  535. bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]);
  536. if (degenerateAB & degenerateBC & degenerateCD) {
  537. return kPoint_ReductionType;
  538. }
  539. if (degenerateAB + degenerateBC + degenerateCD == 2) {
  540. return kLine_ReductionType;
  541. }
  542. if (!cubic_in_line(cubic)) {
  543. *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1];
  544. return kQuad_ReductionType;
  545. }
  546. SkScalar tValues[3];
  547. int count = SkFindCubicMaxCurvature(cubic, tValues);
  548. int rCount = 0;
  549. // Now loop over the t-values, and reject any that evaluate to either end-point
  550. for (int index = 0; index < count; ++index) {
  551. SkScalar t = tValues[index];
  552. if (0 >= t || t >= 1) {
  553. continue;
  554. }
  555. SkEvalCubicAt(cubic, t, &reduction[rCount], nullptr, nullptr);
  556. if (reduction[rCount] != cubic[0] && reduction[rCount] != cubic[3]) {
  557. ++rCount;
  558. }
  559. }
  560. if (rCount == 0) {
  561. return kLine_ReductionType;
  562. }
  563. static_assert(kQuad_ReductionType + 1 == kDegenerate_ReductionType, "enum_out_of_whack");
  564. static_assert(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, "enum_out_of_whack");
  565. static_assert(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, "enum_out_of_whack");
  566. return (ReductionType) (kQuad_ReductionType + rCount);
  567. }
  568. SkPathStroker::ReductionType SkPathStroker::CheckConicLinear(const SkConic& conic,
  569. SkPoint* reduction) {
  570. bool degenerateAB = degenerate_vector(conic.fPts[1] - conic.fPts[0]);
  571. bool degenerateBC = degenerate_vector(conic.fPts[2] - conic.fPts[1]);
  572. if (degenerateAB & degenerateBC) {
  573. return kPoint_ReductionType;
  574. }
  575. if (degenerateAB | degenerateBC) {
  576. return kLine_ReductionType;
  577. }
  578. if (!conic_in_line(conic)) {
  579. return kQuad_ReductionType;
  580. }
  581. // SkFindConicMaxCurvature would be a better solution, once we know how to
  582. // implement it. Quad curvature is a reasonable substitute
  583. SkScalar t = SkFindQuadMaxCurvature(conic.fPts);
  584. if (0 == t) {
  585. return kLine_ReductionType;
  586. }
  587. conic.evalAt(t, reduction, nullptr);
  588. return kDegenerate_ReductionType;
  589. }
  590. SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3],
  591. SkPoint* reduction) {
  592. bool degenerateAB = degenerate_vector(quad[1] - quad[0]);
  593. bool degenerateBC = degenerate_vector(quad[2] - quad[1]);
  594. if (degenerateAB & degenerateBC) {
  595. return kPoint_ReductionType;
  596. }
  597. if (degenerateAB | degenerateBC) {
  598. return kLine_ReductionType;
  599. }
  600. if (!quad_in_line(quad)) {
  601. return kQuad_ReductionType;
  602. }
  603. SkScalar t = SkFindQuadMaxCurvature(quad);
  604. if (0 == t || 1 == t) {
  605. return kLine_ReductionType;
  606. }
  607. *reduction = SkEvalQuadAt(quad, t);
  608. return kDegenerate_ReductionType;
  609. }
  610. void SkPathStroker::conicTo(const SkPoint& pt1, const SkPoint& pt2, SkScalar weight) {
  611. const SkConic conic(fPrevPt, pt1, pt2, weight);
  612. SkPoint reduction;
  613. ReductionType reductionType = CheckConicLinear(conic, &reduction);
  614. if (kPoint_ReductionType == reductionType) {
  615. /* If the stroke consists of a moveTo followed by a degenerate curve, treat it
  616. as if it were followed by a zero-length line. Lines without length
  617. can have square and round end caps. */
  618. this->lineTo(pt2);
  619. return;
  620. }
  621. if (kLine_ReductionType == reductionType) {
  622. this->lineTo(pt2);
  623. return;
  624. }
  625. if (kDegenerate_ReductionType == reductionType) {
  626. this->lineTo(reduction);
  627. SkStrokerPriv::JoinProc saveJoiner = fJoiner;
  628. fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
  629. this->lineTo(pt2);
  630. fJoiner = saveJoiner;
  631. return;
  632. }
  633. SkASSERT(kQuad_ReductionType == reductionType);
  634. SkVector normalAB, unitAB, normalBC, unitBC;
  635. if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) {
  636. this->lineTo(pt2);
  637. return;
  638. }
  639. SkQuadConstruct quadPts;
  640. this->init(kOuter_StrokeType, &quadPts, 0, 1);
  641. (void) this->conicStroke(conic, &quadPts);
  642. this->init(kInner_StrokeType, &quadPts, 0, 1);
  643. (void) this->conicStroke(conic, &quadPts);
  644. this->setConicEndNormal(conic, normalAB, unitAB, &normalBC, &unitBC);
  645. this->postJoinTo(pt2, normalBC, unitBC);
  646. }
  647. void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
  648. const SkPoint quad[3] = { fPrevPt, pt1, pt2 };
  649. SkPoint reduction;
  650. ReductionType reductionType = CheckQuadLinear(quad, &reduction);
  651. if (kPoint_ReductionType == reductionType) {
  652. /* If the stroke consists of a moveTo followed by a degenerate curve, treat it
  653. as if it were followed by a zero-length line. Lines without length
  654. can have square and round end caps. */
  655. this->lineTo(pt2);
  656. return;
  657. }
  658. if (kLine_ReductionType == reductionType) {
  659. this->lineTo(pt2);
  660. return;
  661. }
  662. if (kDegenerate_ReductionType == reductionType) {
  663. this->lineTo(reduction);
  664. SkStrokerPriv::JoinProc saveJoiner = fJoiner;
  665. fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
  666. this->lineTo(pt2);
  667. fJoiner = saveJoiner;
  668. return;
  669. }
  670. SkASSERT(kQuad_ReductionType == reductionType);
  671. SkVector normalAB, unitAB, normalBC, unitBC;
  672. if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) {
  673. this->lineTo(pt2);
  674. return;
  675. }
  676. SkQuadConstruct quadPts;
  677. this->init(kOuter_StrokeType, &quadPts, 0, 1);
  678. (void) this->quadStroke(quad, &quadPts);
  679. this->init(kInner_StrokeType, &quadPts, 0, 1);
  680. (void) this->quadStroke(quad, &quadPts);
  681. this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC);
  682. this->postJoinTo(pt2, normalBC, unitBC);
  683. }
  684. // Given a point on the curve and its derivative, scale the derivative by the radius, and
  685. // compute the perpendicular point and its tangent.
  686. void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt,
  687. SkPoint* tangent) const {
  688. if (!dxy->setLength(fRadius)) {
  689. dxy->set(fRadius, 0);
  690. }
  691. SkScalar axisFlip = SkIntToScalar(fStrokeType); // go opposite ways for outer, inner
  692. onPt->fX = tPt.fX + axisFlip * dxy->fY;
  693. onPt->fY = tPt.fY - axisFlip * dxy->fX;
  694. if (tangent) {
  695. tangent->fX = onPt->fX + dxy->fX;
  696. tangent->fY = onPt->fY + dxy->fY;
  697. }
  698. }
  699. // Given a conic and t, return the point on curve, its perpendicular, and the perpendicular tangent.
  700. // Returns false if the perpendicular could not be computed (because the derivative collapsed to 0)
  701. void SkPathStroker::conicPerpRay(const SkConic& conic, SkScalar t, SkPoint* tPt, SkPoint* onPt,
  702. SkPoint* tangent) const {
  703. SkVector dxy;
  704. conic.evalAt(t, tPt, &dxy);
  705. if (dxy.fX == 0 && dxy.fY == 0) {
  706. dxy = conic.fPts[2] - conic.fPts[0];
  707. }
  708. this->setRayPts(*tPt, &dxy, onPt, tangent);
  709. }
  710. // Given a conic and a t range, find the start and end if they haven't been found already.
  711. void SkPathStroker::conicQuadEnds(const SkConic& conic, SkQuadConstruct* quadPts) const {
  712. if (!quadPts->fStartSet) {
  713. SkPoint conicStartPt;
  714. this->conicPerpRay(conic, quadPts->fStartT, &conicStartPt, &quadPts->fQuad[0],
  715. &quadPts->fTangentStart);
  716. quadPts->fStartSet = true;
  717. }
  718. if (!quadPts->fEndSet) {
  719. SkPoint conicEndPt;
  720. this->conicPerpRay(conic, quadPts->fEndT, &conicEndPt, &quadPts->fQuad[2],
  721. &quadPts->fTangentEnd);
  722. quadPts->fEndSet = true;
  723. }
  724. }
  725. // Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent.
  726. void SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
  727. SkPoint* tangent) const {
  728. SkVector dxy;
  729. SkPoint chopped[7];
  730. SkEvalCubicAt(cubic, t, tPt, &dxy, nullptr);
  731. if (dxy.fX == 0 && dxy.fY == 0) {
  732. const SkPoint* cPts = cubic;
  733. if (SkScalarNearlyZero(t)) {
  734. dxy = cubic[2] - cubic[0];
  735. } else if (SkScalarNearlyZero(1 - t)) {
  736. dxy = cubic[3] - cubic[1];
  737. } else {
  738. // If the cubic inflection falls on the cusp, subdivide the cubic
  739. // to find the tangent at that point.
  740. SkChopCubicAt(cubic, chopped, t);
  741. dxy = chopped[3] - chopped[2];
  742. if (dxy.fX == 0 && dxy.fY == 0) {
  743. dxy = chopped[3] - chopped[1];
  744. cPts = chopped;
  745. }
  746. }
  747. if (dxy.fX == 0 && dxy.fY == 0) {
  748. dxy = cPts[3] - cPts[0];
  749. }
  750. }
  751. setRayPts(*tPt, &dxy, onPt, tangent);
  752. }
  753. // Given a cubic and a t range, find the start and end if they haven't been found already.
  754. void SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
  755. if (!quadPts->fStartSet) {
  756. SkPoint cubicStartPt;
  757. this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0],
  758. &quadPts->fTangentStart);
  759. quadPts->fStartSet = true;
  760. }
  761. if (!quadPts->fEndSet) {
  762. SkPoint cubicEndPt;
  763. this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2],
  764. &quadPts->fTangentEnd);
  765. quadPts->fEndSet = true;
  766. }
  767. }
  768. void SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts,
  769. SkPoint* mid) const {
  770. SkPoint cubicMidPt;
  771. this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, nullptr);
  772. }
  773. // Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent.
  774. void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
  775. SkPoint* tangent) const {
  776. SkVector dxy;
  777. SkEvalQuadAt(quad, t, tPt, &dxy);
  778. if (dxy.fX == 0 && dxy.fY == 0) {
  779. dxy = quad[2] - quad[0];
  780. }
  781. setRayPts(*tPt, &dxy, onPt, tangent);
  782. }
  783. // Find the intersection of the stroke tangents to construct a stroke quad.
  784. // Return whether the stroke is a degenerate (a line), a quad, or must be split.
  785. // Optionally compute the quad's control point.
  786. SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts,
  787. IntersectRayType intersectRayType STROKER_DEBUG_PARAMS(int depth)) const {
  788. const SkPoint& start = quadPts->fQuad[0];
  789. const SkPoint& end = quadPts->fQuad[2];
  790. SkVector aLen = quadPts->fTangentStart - start;
  791. SkVector bLen = quadPts->fTangentEnd - end;
  792. /* Slopes match when denom goes to zero:
  793. axLen / ayLen == bxLen / byLen
  794. (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
  795. byLen * axLen == ayLen * bxLen
  796. byLen * axLen - ayLen * bxLen ( == denom )
  797. */
  798. SkScalar denom = aLen.cross(bLen);
  799. if (denom == 0 || !SkScalarIsFinite(denom)) {
  800. quadPts->fOppositeTangents = aLen.dot(bLen) < 0;
  801. return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, "denom == 0");
  802. }
  803. quadPts->fOppositeTangents = false;
  804. SkVector ab0 = start - end;
  805. SkScalar numerA = bLen.cross(ab0);
  806. SkScalar numerB = aLen.cross(ab0);
  807. if ((numerA >= 0) == (numerB >= 0)) { // if the control point is outside the quad ends
  808. // if the perpendicular distances from the quad points to the opposite tangent line
  809. // are small, a straight line is good enough
  810. SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd);
  811. SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart);
  812. if (SkTMax(dist1, dist2) <= fInvResScaleSquared) {
  813. return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
  814. "SkTMax(dist1=%g, dist2=%g) <= fInvResScaleSquared", dist1, dist2);
  815. }
  816. return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
  817. "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB);
  818. }
  819. // check to see if the denominator is teeny relative to the numerator
  820. // if the offset by one will be lost, the ratio is too large
  821. numerA /= denom;
  822. bool validDivide = numerA > numerA - 1;
  823. if (validDivide) {
  824. if (kCtrlPt_RayType == intersectRayType) {
  825. SkPoint* ctrlPt = &quadPts->fQuad[1];
  826. // the intersection of the tangents need not be on the tangent segment
  827. // so 0 <= numerA <= 1 is not necessarily true
  828. ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA;
  829. ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA;
  830. }
  831. return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
  832. "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB);
  833. }
  834. quadPts->fOppositeTangents = aLen.dot(bLen) < 0;
  835. // if the lines are parallel, straight line is good enough
  836. return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
  837. "SkScalarNearlyZero(denom=%g)", denom);
  838. }
  839. // Given a cubic and a t-range, determine if the stroke can be described by a quadratic.
  840. SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4],
  841. SkQuadConstruct* quadPts) {
  842. this->cubicQuadEnds(cubic, quadPts);
  843. return this->intersectRay(quadPts, kResultType_RayType STROKER_DEBUG_PARAMS(fRecursionDepth));
  844. }
  845. // Intersect the line with the quad and return the t values on the quad where the line crosses.
  846. static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) {
  847. SkVector vec = line[1] - line[0];
  848. SkScalar r[3];
  849. for (int n = 0; n < 3; ++n) {
  850. r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY;
  851. }
  852. SkScalar A = r[2];
  853. SkScalar B = r[1];
  854. SkScalar C = r[0];
  855. A += C - 2 * B; // A = a - 2*b + c
  856. B -= C; // B = -(b - c)
  857. return SkFindUnitQuadRoots(A, 2 * B, C, roots);
  858. }
  859. // Return true if the point is close to the bounds of the quad. This is used as a quick reject.
  860. bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const {
  861. SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX);
  862. if (pt.fX + fInvResScale < xMin) {
  863. return false;
  864. }
  865. SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX);
  866. if (pt.fX - fInvResScale > xMax) {
  867. return false;
  868. }
  869. SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY);
  870. if (pt.fY + fInvResScale < yMin) {
  871. return false;
  872. }
  873. SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY);
  874. if (pt.fY - fInvResScale > yMax) {
  875. return false;
  876. }
  877. return true;
  878. }
  879. static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) {
  880. return SkPointPriv::DistanceToSqd(nearPt, farPt) <= limit * limit;
  881. }
  882. static bool sharp_angle(const SkPoint quad[3]) {
  883. SkVector smaller = quad[1] - quad[0];
  884. SkVector larger = quad[1] - quad[2];
  885. SkScalar smallerLen = SkPointPriv::LengthSqd(smaller);
  886. SkScalar largerLen = SkPointPriv::LengthSqd(larger);
  887. if (smallerLen > largerLen) {
  888. using std::swap;
  889. swap(smaller, larger);
  890. largerLen = smallerLen;
  891. }
  892. if (!smaller.setLength(largerLen)) {
  893. return false;
  894. }
  895. SkScalar dot = smaller.dot(larger);
  896. return dot > 0;
  897. }
  898. SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3],
  899. const SkPoint ray[2], SkQuadConstruct* quadPts STROKER_DEBUG_PARAMS(int depth)) const {
  900. SkPoint strokeMid = SkEvalQuadAt(stroke, SK_ScalarHalf);
  901. // measure the distance from the curve to the quad-stroke midpoint, compare to radius
  902. if (points_within_dist(ray[0], strokeMid, fInvResScale)) { // if the difference is small
  903. if (sharp_angle(quadPts->fQuad)) {
  904. return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
  905. "sharp_angle (1) =%g,%g, %g,%g, %g,%g",
  906. quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
  907. quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
  908. quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
  909. }
  910. return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
  911. "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fInvResScale=%g)",
  912. ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY, fInvResScale);
  913. }
  914. // measure the distance to quad's bounds (quick reject)
  915. // an alternative : look for point in triangle
  916. if (!ptInQuadBounds(stroke, ray[0])) { // if far, subdivide
  917. return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
  918. "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)",
  919. stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY,
  920. ray[0].fX, ray[0].fY);
  921. }
  922. // measure the curve ray distance to the quad-stroke
  923. SkScalar roots[2];
  924. int rootCount = intersect_quad_ray(ray, stroke, roots);
  925. if (rootCount != 1) {
  926. return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
  927. "rootCount=%d != 1", rootCount);
  928. }
  929. SkPoint quadPt = SkEvalQuadAt(stroke, roots[0]);
  930. SkScalar error = fInvResScale * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2);
  931. if (points_within_dist(ray[0], quadPt, error)) { // if the difference is small, we're done
  932. if (sharp_angle(quadPts->fQuad)) {
  933. return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
  934. "sharp_angle (2) =%g,%g, %g,%g, %g,%g",
  935. quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
  936. quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
  937. quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
  938. }
  939. return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
  940. "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)",
  941. ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error);
  942. }
  943. // otherwise, subdivide
  944. return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through");
  945. }
  946. SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4],
  947. SkQuadConstruct* quadPts) {
  948. // get the quadratic approximation of the stroke
  949. this->cubicQuadEnds(cubic, quadPts);
  950. ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType
  951. STROKER_DEBUG_PARAMS(fRecursionDepth) );
  952. if (resultType != kQuad_ResultType) {
  953. return resultType;
  954. }
  955. // project a ray from the curve to the stroke
  956. SkPoint ray[2]; // points near midpoint on quad, midpoint on cubic
  957. this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], nullptr);
  958. return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts
  959. STROKER_DEBUG_PARAMS(fRecursionDepth));
  960. }
  961. SkPathStroker::ResultType SkPathStroker::compareQuadConic(const SkConic& conic,
  962. SkQuadConstruct* quadPts) const {
  963. // get the quadratic approximation of the stroke
  964. this->conicQuadEnds(conic, quadPts);
  965. ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType
  966. STROKER_DEBUG_PARAMS(fRecursionDepth) );
  967. if (resultType != kQuad_ResultType) {
  968. return resultType;
  969. }
  970. // project a ray from the curve to the stroke
  971. SkPoint ray[2]; // points near midpoint on quad, midpoint on conic
  972. this->conicPerpRay(conic, quadPts->fMidT, &ray[1], &ray[0], nullptr);
  973. return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts
  974. STROKER_DEBUG_PARAMS(fRecursionDepth));
  975. }
  976. SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3],
  977. SkQuadConstruct* quadPts) {
  978. // get the quadratic approximation of the stroke
  979. if (!quadPts->fStartSet) {
  980. SkPoint quadStartPt;
  981. this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0],
  982. &quadPts->fTangentStart);
  983. quadPts->fStartSet = true;
  984. }
  985. if (!quadPts->fEndSet) {
  986. SkPoint quadEndPt;
  987. this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2],
  988. &quadPts->fTangentEnd);
  989. quadPts->fEndSet = true;
  990. }
  991. ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType
  992. STROKER_DEBUG_PARAMS(fRecursionDepth));
  993. if (resultType != kQuad_ResultType) {
  994. return resultType;
  995. }
  996. // project a ray from the curve to the stroke
  997. SkPoint ray[2];
  998. this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], nullptr);
  999. return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts
  1000. STROKER_DEBUG_PARAMS(fRecursionDepth));
  1001. }
  1002. void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) {
  1003. const SkPoint* quad = quadPts->fQuad;
  1004. SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
  1005. path->lineTo(quad[2].fX, quad[2].fY);
  1006. }
  1007. bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const {
  1008. SkPoint strokeMid;
  1009. this->cubicQuadMid(cubic, quadPts, &strokeMid);
  1010. SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]);
  1011. return dist < fInvResScaleSquared;
  1012. }
  1013. bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
  1014. if (!fFoundTangents) {
  1015. ResultType resultType = this->tangentsMeet(cubic, quadPts);
  1016. if (kQuad_ResultType != resultType) {
  1017. if ((kDegenerate_ResultType == resultType
  1018. || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2],
  1019. fInvResScale)) && cubicMidOnLine(cubic, quadPts)) {
  1020. addDegenerateLine(quadPts);
  1021. return true;
  1022. }
  1023. } else {
  1024. fFoundTangents = true;
  1025. }
  1026. }
  1027. if (fFoundTangents) {
  1028. ResultType resultType = this->compareQuadCubic(cubic, quadPts);
  1029. if (kQuad_ResultType == resultType) {
  1030. SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
  1031. const SkPoint* stroke = quadPts->fQuad;
  1032. path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
  1033. return true;
  1034. }
  1035. if (kDegenerate_ResultType == resultType) {
  1036. if (!quadPts->fOppositeTangents) {
  1037. addDegenerateLine(quadPts);
  1038. return true;
  1039. }
  1040. }
  1041. }
  1042. if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) {
  1043. return false; // just abort if projected quad isn't representable
  1044. }
  1045. #if QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
  1046. SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents],
  1047. fRecursionDepth + 1));
  1048. #endif
  1049. if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) {
  1050. return false; // just abort if projected quad isn't representable
  1051. }
  1052. SkQuadConstruct half;
  1053. if (!half.initWithStart(quadPts)) {
  1054. addDegenerateLine(quadPts);
  1055. --fRecursionDepth;
  1056. return true;
  1057. }
  1058. if (!this->cubicStroke(cubic, &half)) {
  1059. return false;
  1060. }
  1061. if (!half.initWithEnd(quadPts)) {
  1062. addDegenerateLine(quadPts);
  1063. --fRecursionDepth;
  1064. return true;
  1065. }
  1066. if (!this->cubicStroke(cubic, &half)) {
  1067. return false;
  1068. }
  1069. --fRecursionDepth;
  1070. return true;
  1071. }
  1072. bool SkPathStroker::conicStroke(const SkConic& conic, SkQuadConstruct* quadPts) {
  1073. ResultType resultType = this->compareQuadConic(conic, quadPts);
  1074. if (kQuad_ResultType == resultType) {
  1075. const SkPoint* stroke = quadPts->fQuad;
  1076. SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
  1077. path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
  1078. return true;
  1079. }
  1080. if (kDegenerate_ResultType == resultType) {
  1081. addDegenerateLine(quadPts);
  1082. return true;
  1083. }
  1084. #if QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
  1085. SkDEBUGCODE(gMaxRecursion[kConic_RecursiveLimit] = SkTMax(gMaxRecursion[kConic_RecursiveLimit],
  1086. fRecursionDepth + 1));
  1087. #endif
  1088. if (++fRecursionDepth > kRecursiveLimits[kConic_RecursiveLimit]) {
  1089. return false; // just abort if projected quad isn't representable
  1090. }
  1091. SkQuadConstruct half;
  1092. (void) half.initWithStart(quadPts);
  1093. if (!this->conicStroke(conic, &half)) {
  1094. return false;
  1095. }
  1096. (void) half.initWithEnd(quadPts);
  1097. if (!this->conicStroke(conic, &half)) {
  1098. return false;
  1099. }
  1100. --fRecursionDepth;
  1101. return true;
  1102. }
  1103. bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) {
  1104. ResultType resultType = this->compareQuadQuad(quad, quadPts);
  1105. if (kQuad_ResultType == resultType) {
  1106. const SkPoint* stroke = quadPts->fQuad;
  1107. SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
  1108. path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
  1109. return true;
  1110. }
  1111. if (kDegenerate_ResultType == resultType) {
  1112. addDegenerateLine(quadPts);
  1113. return true;
  1114. }
  1115. #if QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
  1116. SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit],
  1117. fRecursionDepth + 1));
  1118. #endif
  1119. if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) {
  1120. return false; // just abort if projected quad isn't representable
  1121. }
  1122. SkQuadConstruct half;
  1123. (void) half.initWithStart(quadPts);
  1124. if (!this->quadStroke(quad, &half)) {
  1125. return false;
  1126. }
  1127. (void) half.initWithEnd(quadPts);
  1128. if (!this->quadStroke(quad, &half)) {
  1129. return false;
  1130. }
  1131. --fRecursionDepth;
  1132. return true;
  1133. }
  1134. void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2,
  1135. const SkPoint& pt3) {
  1136. const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 };
  1137. SkPoint reduction[3];
  1138. const SkPoint* tangentPt;
  1139. ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt);
  1140. if (kPoint_ReductionType == reductionType) {
  1141. /* If the stroke consists of a moveTo followed by a degenerate curve, treat it
  1142. as if it were followed by a zero-length line. Lines without length
  1143. can have square and round end caps. */
  1144. this->lineTo(pt3);
  1145. return;
  1146. }
  1147. if (kLine_ReductionType == reductionType) {
  1148. this->lineTo(pt3);
  1149. return;
  1150. }
  1151. if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) {
  1152. this->lineTo(reduction[0]);
  1153. SkStrokerPriv::JoinProc saveJoiner = fJoiner;
  1154. fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
  1155. if (kDegenerate2_ReductionType <= reductionType) {
  1156. this->lineTo(reduction[1]);
  1157. }
  1158. if (kDegenerate3_ReductionType == reductionType) {
  1159. this->lineTo(reduction[2]);
  1160. }
  1161. this->lineTo(pt3);
  1162. fJoiner = saveJoiner;
  1163. return;
  1164. }
  1165. SkASSERT(kQuad_ReductionType == reductionType);
  1166. SkVector normalAB, unitAB, normalCD, unitCD;
  1167. if (!this->preJoinTo(*tangentPt, &normalAB, &unitAB, false)) {
  1168. this->lineTo(pt3);
  1169. return;
  1170. }
  1171. SkScalar tValues[2];
  1172. int count = SkFindCubicInflections(cubic, tValues);
  1173. SkScalar lastT = 0;
  1174. for (int index = 0; index <= count; ++index) {
  1175. SkScalar nextT = index < count ? tValues[index] : 1;
  1176. SkQuadConstruct quadPts;
  1177. this->init(kOuter_StrokeType, &quadPts, lastT, nextT);
  1178. (void) this->cubicStroke(cubic, &quadPts);
  1179. this->init(kInner_StrokeType, &quadPts, lastT, nextT);
  1180. (void) this->cubicStroke(cubic, &quadPts);
  1181. lastT = nextT;
  1182. }
  1183. SkScalar cusp = SkFindCubicCusp(cubic);
  1184. if (cusp > 0) {
  1185. SkPoint cuspLoc;
  1186. SkEvalCubicAt(cubic, cusp, &cuspLoc, nullptr, nullptr);
  1187. fCusper.addCircle(cuspLoc.fX, cuspLoc.fY, fRadius);
  1188. }
  1189. // emit the join even if one stroke succeeded but the last one failed
  1190. // this avoids reversing an inner stroke with a partial path followed by another moveto
  1191. this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD);
  1192. this->postJoinTo(pt3, normalCD, unitCD);
  1193. }
  1194. ///////////////////////////////////////////////////////////////////////////////
  1195. ///////////////////////////////////////////////////////////////////////////////
  1196. #include "src/core/SkPaintDefaults.h"
  1197. SkStroke::SkStroke() {
  1198. fWidth = SK_Scalar1;
  1199. fMiterLimit = SkPaintDefaults_MiterLimit;
  1200. fResScale = 1;
  1201. fCap = SkPaint::kDefault_Cap;
  1202. fJoin = SkPaint::kDefault_Join;
  1203. fDoFill = false;
  1204. }
  1205. SkStroke::SkStroke(const SkPaint& p) {
  1206. fWidth = p.getStrokeWidth();
  1207. fMiterLimit = p.getStrokeMiter();
  1208. fResScale = 1;
  1209. fCap = (uint8_t)p.getStrokeCap();
  1210. fJoin = (uint8_t)p.getStrokeJoin();
  1211. fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
  1212. }
  1213. SkStroke::SkStroke(const SkPaint& p, SkScalar width) {
  1214. fWidth = width;
  1215. fMiterLimit = p.getStrokeMiter();
  1216. fResScale = 1;
  1217. fCap = (uint8_t)p.getStrokeCap();
  1218. fJoin = (uint8_t)p.getStrokeJoin();
  1219. fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
  1220. }
  1221. void SkStroke::setWidth(SkScalar width) {
  1222. SkASSERT(width >= 0);
  1223. fWidth = width;
  1224. }
  1225. void SkStroke::setMiterLimit(SkScalar miterLimit) {
  1226. SkASSERT(miterLimit >= 0);
  1227. fMiterLimit = miterLimit;
  1228. }
  1229. void SkStroke::setCap(SkPaint::Cap cap) {
  1230. SkASSERT((unsigned)cap < SkPaint::kCapCount);
  1231. fCap = SkToU8(cap);
  1232. }
  1233. void SkStroke::setJoin(SkPaint::Join join) {
  1234. SkASSERT((unsigned)join < SkPaint::kJoinCount);
  1235. fJoin = SkToU8(join);
  1236. }
  1237. ///////////////////////////////////////////////////////////////////////////////
  1238. // If src==dst, then we use a tmp path to record the stroke, and then swap
  1239. // its contents with src when we're done.
  1240. class AutoTmpPath {
  1241. public:
  1242. AutoTmpPath(const SkPath& src, SkPath** dst) : fSrc(src) {
  1243. if (&src == *dst) {
  1244. *dst = &fTmpDst;
  1245. fSwapWithSrc = true;
  1246. } else {
  1247. (*dst)->reset();
  1248. fSwapWithSrc = false;
  1249. }
  1250. }
  1251. ~AutoTmpPath() {
  1252. if (fSwapWithSrc) {
  1253. fTmpDst.swap(*const_cast<SkPath*>(&fSrc));
  1254. }
  1255. }
  1256. private:
  1257. SkPath fTmpDst;
  1258. const SkPath& fSrc;
  1259. bool fSwapWithSrc;
  1260. };
  1261. void SkStroke::strokePath(const SkPath& src, SkPath* dst) const {
  1262. SkASSERT(dst);
  1263. SkScalar radius = SkScalarHalf(fWidth);
  1264. AutoTmpPath tmp(src, &dst);
  1265. if (radius <= 0) {
  1266. return;
  1267. }
  1268. // If src is really a rect, call our specialty strokeRect() method
  1269. {
  1270. SkRect rect;
  1271. bool isClosed;
  1272. SkPath::Direction dir;
  1273. if (src.isRect(&rect, &isClosed, &dir) && isClosed) {
  1274. this->strokeRect(rect, dst, dir);
  1275. // our answer should preserve the inverseness of the src
  1276. if (src.isInverseFillType()) {
  1277. SkASSERT(!dst->isInverseFillType());
  1278. dst->toggleInverseFillType();
  1279. }
  1280. return;
  1281. }
  1282. }
  1283. // We can always ignore centers for stroke and fill convex line-only paths
  1284. // TODO: remove the line-only restriction
  1285. bool ignoreCenter = fDoFill && (src.getSegmentMasks() == SkPath::kLine_SegmentMask) &&
  1286. src.isLastContourClosed() && src.isConvex();
  1287. SkPathStroker stroker(src, radius, fMiterLimit, this->getCap(), this->getJoin(),
  1288. fResScale, ignoreCenter);
  1289. SkPath::Iter iter(src, false);
  1290. SkPath::Verb lastSegment = SkPath::kMove_Verb;
  1291. for (;;) {
  1292. SkPoint pts[4];
  1293. switch (iter.next(pts, false)) {
  1294. case SkPath::kMove_Verb:
  1295. stroker.moveTo(pts[0]);
  1296. break;
  1297. case SkPath::kLine_Verb:
  1298. stroker.lineTo(pts[1], &iter);
  1299. lastSegment = SkPath::kLine_Verb;
  1300. break;
  1301. case SkPath::kQuad_Verb:
  1302. stroker.quadTo(pts[1], pts[2]);
  1303. lastSegment = SkPath::kQuad_Verb;
  1304. break;
  1305. case SkPath::kConic_Verb: {
  1306. stroker.conicTo(pts[1], pts[2], iter.conicWeight());
  1307. lastSegment = SkPath::kConic_Verb;
  1308. break;
  1309. } break;
  1310. case SkPath::kCubic_Verb:
  1311. stroker.cubicTo(pts[1], pts[2], pts[3]);
  1312. lastSegment = SkPath::kCubic_Verb;
  1313. break;
  1314. case SkPath::kClose_Verb:
  1315. if (SkPaint::kButt_Cap != this->getCap()) {
  1316. /* If the stroke consists of a moveTo followed by a close, treat it
  1317. as if it were followed by a zero-length line. Lines without length
  1318. can have square and round end caps. */
  1319. if (stroker.hasOnlyMoveTo()) {
  1320. stroker.lineTo(stroker.moveToPt());
  1321. goto ZERO_LENGTH;
  1322. }
  1323. /* If the stroke consists of a moveTo followed by one or more zero-length
  1324. verbs, then followed by a close, treat is as if it were followed by a
  1325. zero-length line. Lines without length can have square & round end caps. */
  1326. if (stroker.isCurrentContourEmpty()) {
  1327. ZERO_LENGTH:
  1328. lastSegment = SkPath::kLine_Verb;
  1329. break;
  1330. }
  1331. }
  1332. stroker.close(lastSegment == SkPath::kLine_Verb);
  1333. break;
  1334. case SkPath::kDone_Verb:
  1335. goto DONE;
  1336. }
  1337. }
  1338. DONE:
  1339. stroker.done(dst, lastSegment == SkPath::kLine_Verb);
  1340. if (fDoFill && !ignoreCenter) {
  1341. if (SkPathPriv::CheapIsFirstDirection(src, SkPathPriv::kCCW_FirstDirection)) {
  1342. dst->reverseAddPath(src);
  1343. } else {
  1344. dst->addPath(src);
  1345. }
  1346. } else {
  1347. // Seems like we can assume that a 2-point src would always result in
  1348. // a convex stroke, but testing has proved otherwise.
  1349. // TODO: fix the stroker to make this assumption true (without making
  1350. // it slower that the work that will be done in computeConvexity())
  1351. #if 0
  1352. // this test results in a non-convex stroke :(
  1353. static void test(SkCanvas* canvas) {
  1354. SkPoint pts[] = { 146.333328, 192.333328, 300.333344, 293.333344 };
  1355. SkPaint paint;
  1356. paint.setStrokeWidth(7);
  1357. paint.setStrokeCap(SkPaint::kRound_Cap);
  1358. canvas->drawLine(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, paint);
  1359. }
  1360. #endif
  1361. #if 0
  1362. if (2 == src.countPoints()) {
  1363. dst->setIsConvex(true);
  1364. }
  1365. #endif
  1366. }
  1367. // our answer should preserve the inverseness of the src
  1368. if (src.isInverseFillType()) {
  1369. SkASSERT(!dst->isInverseFillType());
  1370. dst->toggleInverseFillType();
  1371. }
  1372. }
  1373. static SkPath::Direction reverse_direction(SkPath::Direction dir) {
  1374. static const SkPath::Direction gOpposite[] = { SkPath::kCCW_Direction, SkPath::kCW_Direction };
  1375. return gOpposite[dir];
  1376. }
  1377. static void addBevel(SkPath* path, const SkRect& r, const SkRect& outer, SkPath::Direction dir) {
  1378. SkPoint pts[8];
  1379. if (SkPath::kCW_Direction == dir) {
  1380. pts[0].set(r.fLeft, outer.fTop);
  1381. pts[1].set(r.fRight, outer.fTop);
  1382. pts[2].set(outer.fRight, r.fTop);
  1383. pts[3].set(outer.fRight, r.fBottom);
  1384. pts[4].set(r.fRight, outer.fBottom);
  1385. pts[5].set(r.fLeft, outer.fBottom);
  1386. pts[6].set(outer.fLeft, r.fBottom);
  1387. pts[7].set(outer.fLeft, r.fTop);
  1388. } else {
  1389. pts[7].set(r.fLeft, outer.fTop);
  1390. pts[6].set(r.fRight, outer.fTop);
  1391. pts[5].set(outer.fRight, r.fTop);
  1392. pts[4].set(outer.fRight, r.fBottom);
  1393. pts[3].set(r.fRight, outer.fBottom);
  1394. pts[2].set(r.fLeft, outer.fBottom);
  1395. pts[1].set(outer.fLeft, r.fBottom);
  1396. pts[0].set(outer.fLeft, r.fTop);
  1397. }
  1398. path->addPoly(pts, 8, true);
  1399. }
  1400. void SkStroke::strokeRect(const SkRect& origRect, SkPath* dst,
  1401. SkPath::Direction dir) const {
  1402. SkASSERT(dst != nullptr);
  1403. dst->reset();
  1404. SkScalar radius = SkScalarHalf(fWidth);
  1405. if (radius <= 0) {
  1406. return;
  1407. }
  1408. SkScalar rw = origRect.width();
  1409. SkScalar rh = origRect.height();
  1410. if ((rw < 0) ^ (rh < 0)) {
  1411. dir = reverse_direction(dir);
  1412. }
  1413. SkRect rect(origRect);
  1414. rect.sort();
  1415. // reassign these, now that we know they'll be >= 0
  1416. rw = rect.width();
  1417. rh = rect.height();
  1418. SkRect r(rect);
  1419. r.outset(radius, radius);
  1420. SkPaint::Join join = (SkPaint::Join)fJoin;
  1421. if (SkPaint::kMiter_Join == join && fMiterLimit < SK_ScalarSqrt2) {
  1422. join = SkPaint::kBevel_Join;
  1423. }
  1424. switch (join) {
  1425. case SkPaint::kMiter_Join:
  1426. dst->addRect(r, dir);
  1427. break;
  1428. case SkPaint::kBevel_Join:
  1429. addBevel(dst, rect, r, dir);
  1430. break;
  1431. case SkPaint::kRound_Join:
  1432. dst->addRoundRect(r, radius, radius, dir);
  1433. break;
  1434. default:
  1435. break;
  1436. }
  1437. if (fWidth < SkMinScalar(rw, rh) && !fDoFill) {
  1438. r = rect;
  1439. r.inset(radius, radius);
  1440. dst->addRect(r, reverse_direction(dir));
  1441. }
  1442. }