SkPath.cpp 127 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902
  1. /*
  2. * Copyright 2006 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 "include/core/SkPath.h"
  8. #include "include/core/SkData.h"
  9. #include "include/core/SkMath.h"
  10. #include "include/core/SkRRect.h"
  11. #include "include/private/SkMacros.h"
  12. #include "include/private/SkPathRef.h"
  13. #include "include/private/SkTo.h"
  14. #include "src/core/SkBuffer.h"
  15. #include "src/core/SkCubicClipper.h"
  16. #include "src/core/SkGeometry.h"
  17. #include "src/core/SkMatrixPriv.h"
  18. #include "src/core/SkPathPriv.h"
  19. #include "src/core/SkPointPriv.h"
  20. #include "src/core/SkSafeMath.h"
  21. #include "src/core/SkTLazy.h"
  22. // need SkDVector
  23. #include "src/pathops/SkPathOpsPoint.h"
  24. #include <cmath>
  25. #include <utility>
  26. struct SkPath_Storage_Equivalent {
  27. void* fPtr;
  28. int32_t fIndex;
  29. uint32_t fFlags;
  30. };
  31. static_assert(sizeof(SkPath) == sizeof(SkPath_Storage_Equivalent),
  32. "Please keep an eye on SkPath packing.");
  33. static float poly_eval(float A, float B, float C, float t) {
  34. return (A * t + B) * t + C;
  35. }
  36. static float poly_eval(float A, float B, float C, float D, float t) {
  37. return ((A * t + B) * t + C) * t + D;
  38. }
  39. ////////////////////////////////////////////////////////////////////////////
  40. /**
  41. * Path.bounds is defined to be the bounds of all the control points.
  42. * If we called bounds.join(r) we would skip r if r was empty, which breaks
  43. * our promise. Hence we have a custom joiner that doesn't look at emptiness
  44. */
  45. static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) {
  46. dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft);
  47. dst->fTop = SkMinScalar(dst->fTop, src.fTop);
  48. dst->fRight = SkMaxScalar(dst->fRight, src.fRight);
  49. dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom);
  50. }
  51. static bool is_degenerate(const SkPath& path) {
  52. SkPath::Iter iter(path, false);
  53. SkPoint pts[4];
  54. return SkPath::kDone_Verb == iter.next(pts);
  55. }
  56. class SkAutoDisableDirectionCheck {
  57. public:
  58. SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
  59. fSaved = static_cast<SkPathPriv::FirstDirection>(fPath->getFirstDirection());
  60. }
  61. ~SkAutoDisableDirectionCheck() {
  62. fPath->setFirstDirection(fSaved);
  63. }
  64. private:
  65. SkPath* fPath;
  66. SkPathPriv::FirstDirection fSaved;
  67. };
  68. #define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
  69. /* This guy's constructor/destructor bracket a path editing operation. It is
  70. used when we know the bounds of the amount we are going to add to the path
  71. (usually a new contour, but not required).
  72. It captures some state about the path up front (i.e. if it already has a
  73. cached bounds), and then if it can, it updates the cache bounds explicitly,
  74. avoiding the need to revisit all of the points in getBounds().
  75. It also notes if the path was originally degenerate, and if so, sets
  76. isConvex to true. Thus it can only be used if the contour being added is
  77. convex.
  78. */
  79. class SkAutoPathBoundsUpdate {
  80. public:
  81. SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
  82. this->init(path);
  83. }
  84. SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top,
  85. SkScalar right, SkScalar bottom) {
  86. fRect.set(left, top, right, bottom);
  87. this->init(path);
  88. }
  89. ~SkAutoPathBoundsUpdate() {
  90. fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity
  91. : SkPath::kUnknown_Convexity);
  92. if ((fEmpty || fHasValidBounds) && fRect.isFinite()) {
  93. fPath->setBounds(fRect);
  94. }
  95. }
  96. private:
  97. SkPath* fPath;
  98. SkRect fRect;
  99. bool fHasValidBounds;
  100. bool fDegenerate;
  101. bool fEmpty;
  102. void init(SkPath* path) {
  103. // Cannot use fRect for our bounds unless we know it is sorted
  104. fRect.sort();
  105. fPath = path;
  106. // Mark the path's bounds as dirty if (1) they are, or (2) the path
  107. // is non-finite, and therefore its bounds are not meaningful
  108. fHasValidBounds = path->hasComputedBounds() && path->isFinite();
  109. fEmpty = path->isEmpty();
  110. if (fHasValidBounds && !fEmpty) {
  111. joinNoEmptyChecks(&fRect, fPath->getBounds());
  112. }
  113. fDegenerate = is_degenerate(*path);
  114. }
  115. };
  116. #define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate)
  117. ////////////////////////////////////////////////////////////////////////////
  118. /*
  119. Stores the verbs and points as they are given to us, with exceptions:
  120. - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic
  121. - we insert a Move(0,0) if Line | Quad | Cubic is our first command
  122. The iterator does more cleanup, especially if forceClose == true
  123. 1. If we encounter degenerate segments, remove them
  124. 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
  125. 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2
  126. 4. if we encounter Line | Quad | Cubic after Close, cons up a Move
  127. */
  128. ////////////////////////////////////////////////////////////////////////////
  129. // flag to require a moveTo if we begin with something else, like lineTo etc.
  130. #define INITIAL_LASTMOVETOINDEX_VALUE ~0
  131. SkPath::SkPath()
  132. : fPathRef(SkPathRef::CreateEmpty()) {
  133. this->resetFields();
  134. fIsVolatile = false;
  135. }
  136. void SkPath::resetFields() {
  137. //fPathRef is assumed to have been emptied by the caller.
  138. fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
  139. fFillType = kWinding_FillType;
  140. this->setConvexity(kUnknown_Convexity);
  141. this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
  142. // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we
  143. // don't want to muck with it if it's been set to something non-nullptr.
  144. }
  145. SkPath::SkPath(const SkPath& that)
  146. : fPathRef(SkRef(that.fPathRef.get())) {
  147. this->copyFields(that);
  148. SkDEBUGCODE(that.validate();)
  149. }
  150. SkPath::~SkPath() {
  151. SkDEBUGCODE(this->validate();)
  152. }
  153. SkPath& SkPath::operator=(const SkPath& that) {
  154. SkDEBUGCODE(that.validate();)
  155. if (this != &that) {
  156. fPathRef.reset(SkRef(that.fPathRef.get()));
  157. this->copyFields(that);
  158. }
  159. SkDEBUGCODE(this->validate();)
  160. return *this;
  161. }
  162. void SkPath::copyFields(const SkPath& that) {
  163. //fPathRef is assumed to have been set by the caller.
  164. fLastMoveToIndex = that.fLastMoveToIndex;
  165. fFillType = that.fFillType;
  166. fIsVolatile = that.fIsVolatile;
  167. // Non-atomic assignment of atomic values.
  168. this->setConvexity(that.getConvexityOrUnknown());
  169. this->setFirstDirection(that.getFirstDirection());
  170. }
  171. bool operator==(const SkPath& a, const SkPath& b) {
  172. // note: don't need to look at isConvex or bounds, since just comparing the
  173. // raw data is sufficient.
  174. return &a == &b ||
  175. (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
  176. }
  177. void SkPath::swap(SkPath& that) {
  178. if (this != &that) {
  179. fPathRef.swap(that.fPathRef);
  180. std::swap(fLastMoveToIndex, that.fLastMoveToIndex);
  181. const auto ft = fFillType;
  182. fFillType = that.fFillType;
  183. that.fFillType = ft;
  184. const auto iv = fIsVolatile;
  185. fIsVolatile = that.fIsVolatile;
  186. that.fIsVolatile = iv;
  187. // Non-atomic swaps of atomic values.
  188. Convexity c = this->getConvexityOrUnknown();
  189. this->setConvexity(that.getConvexityOrUnknown());
  190. that.setConvexity(c);
  191. uint8_t fd = this->getFirstDirection();
  192. this->setFirstDirection(that.getFirstDirection());
  193. that.setFirstDirection(fd);
  194. }
  195. }
  196. bool SkPath::isInterpolatable(const SkPath& compare) const {
  197. int count = fPathRef->countVerbs();
  198. if (count != compare.fPathRef->countVerbs()) {
  199. return false;
  200. }
  201. if (!count) {
  202. return true;
  203. }
  204. if (memcmp(fPathRef->verbsMemBegin(), compare.fPathRef->verbsMemBegin(),
  205. count)) {
  206. return false;
  207. }
  208. return !fPathRef->countWeights() ||
  209. !SkToBool(memcmp(fPathRef->conicWeights(), compare.fPathRef->conicWeights(),
  210. fPathRef->countWeights() * sizeof(*fPathRef->conicWeights())));
  211. }
  212. bool SkPath::interpolate(const SkPath& ending, SkScalar weight, SkPath* out) const {
  213. int pointCount = fPathRef->countPoints();
  214. if (pointCount != ending.fPathRef->countPoints()) {
  215. return false;
  216. }
  217. if (!pointCount) {
  218. return true;
  219. }
  220. out->reset();
  221. out->addPath(*this);
  222. fPathRef->interpolate(*ending.fPathRef, weight, out->fPathRef.get());
  223. return true;
  224. }
  225. static inline bool check_edge_against_rect(const SkPoint& p0,
  226. const SkPoint& p1,
  227. const SkRect& rect,
  228. SkPathPriv::FirstDirection dir) {
  229. const SkPoint* edgeBegin;
  230. SkVector v;
  231. if (SkPathPriv::kCW_FirstDirection == dir) {
  232. v = p1 - p0;
  233. edgeBegin = &p0;
  234. } else {
  235. v = p0 - p1;
  236. edgeBegin = &p1;
  237. }
  238. if (v.fX || v.fY) {
  239. // check the cross product of v with the vec from edgeBegin to each rect corner
  240. SkScalar yL = v.fY * (rect.fLeft - edgeBegin->fX);
  241. SkScalar xT = v.fX * (rect.fTop - edgeBegin->fY);
  242. SkScalar yR = v.fY * (rect.fRight - edgeBegin->fX);
  243. SkScalar xB = v.fX * (rect.fBottom - edgeBegin->fY);
  244. if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
  245. return false;
  246. }
  247. }
  248. return true;
  249. }
  250. bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
  251. // This only handles non-degenerate convex paths currently.
  252. if (kConvex_Convexity != this->getConvexity()) {
  253. return false;
  254. }
  255. SkPathPriv::FirstDirection direction;
  256. if (!SkPathPriv::CheapComputeFirstDirection(*this, &direction)) {
  257. return false;
  258. }
  259. SkPoint firstPt;
  260. SkPoint prevPt;
  261. SkPath::Iter iter(*this, true);
  262. SkPath::Verb verb;
  263. SkPoint pts[4];
  264. int segmentCount = 0;
  265. SkDEBUGCODE(int moveCnt = 0;)
  266. SkDEBUGCODE(int closeCount = 0;)
  267. while ((verb = iter.next(pts, true, true)) != kDone_Verb) {
  268. int nextPt = -1;
  269. switch (verb) {
  270. case kMove_Verb:
  271. SkASSERT(!segmentCount && !closeCount);
  272. SkDEBUGCODE(++moveCnt);
  273. firstPt = prevPt = pts[0];
  274. break;
  275. case kLine_Verb:
  276. nextPt = 1;
  277. SkASSERT(moveCnt && !closeCount);
  278. ++segmentCount;
  279. break;
  280. case kQuad_Verb:
  281. case kConic_Verb:
  282. SkASSERT(moveCnt && !closeCount);
  283. ++segmentCount;
  284. nextPt = 2;
  285. break;
  286. case kCubic_Verb:
  287. SkASSERT(moveCnt && !closeCount);
  288. ++segmentCount;
  289. nextPt = 3;
  290. break;
  291. case kClose_Verb:
  292. SkDEBUGCODE(++closeCount;)
  293. break;
  294. default:
  295. SkDEBUGFAIL("unknown verb");
  296. }
  297. if (-1 != nextPt) {
  298. if (SkPath::kConic_Verb == verb) {
  299. SkConic orig;
  300. orig.set(pts, iter.conicWeight());
  301. SkPoint quadPts[5];
  302. int count = orig.chopIntoQuadsPOW2(quadPts, 1);
  303. SkASSERT_RELEASE(2 == count);
  304. if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) {
  305. return false;
  306. }
  307. if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) {
  308. return false;
  309. }
  310. } else {
  311. if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
  312. return false;
  313. }
  314. }
  315. prevPt = pts[nextPt];
  316. }
  317. }
  318. if (segmentCount) {
  319. return check_edge_against_rect(prevPt, firstPt, rect, direction);
  320. }
  321. return false;
  322. }
  323. uint32_t SkPath::getGenerationID() const {
  324. uint32_t genID = fPathRef->genID();
  325. #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
  326. SkASSERT((unsigned)fFillType < (1 << (32 - SkPathPriv::kPathRefGenIDBitCnt)));
  327. genID |= static_cast<uint32_t>(fFillType) << SkPathPriv::kPathRefGenIDBitCnt;
  328. #endif
  329. return genID;
  330. }
  331. SkPath& SkPath::reset() {
  332. SkDEBUGCODE(this->validate();)
  333. fPathRef.reset(SkPathRef::CreateEmpty());
  334. this->resetFields();
  335. return *this;
  336. }
  337. SkPath& SkPath::rewind() {
  338. SkDEBUGCODE(this->validate();)
  339. SkPathRef::Rewind(&fPathRef);
  340. this->resetFields();
  341. return *this;
  342. }
  343. bool SkPath::isLastContourClosed() const {
  344. int verbCount = fPathRef->countVerbs();
  345. if (0 == verbCount) {
  346. return false;
  347. }
  348. return kClose_Verb == fPathRef->atVerb(verbCount - 1);
  349. }
  350. bool SkPath::isLine(SkPoint line[2]) const {
  351. int verbCount = fPathRef->countVerbs();
  352. if (2 == verbCount) {
  353. SkASSERT(kMove_Verb == fPathRef->atVerb(0));
  354. if (kLine_Verb == fPathRef->atVerb(1)) {
  355. SkASSERT(2 == fPathRef->countPoints());
  356. if (line) {
  357. const SkPoint* pts = fPathRef->points();
  358. line[0] = pts[0];
  359. line[1] = pts[1];
  360. }
  361. return true;
  362. }
  363. }
  364. return false;
  365. }
  366. /*
  367. Determines if path is a rect by keeping track of changes in direction
  368. and looking for a loop either clockwise or counterclockwise.
  369. The direction is computed such that:
  370. 0: vertical up
  371. 1: horizontal left
  372. 2: vertical down
  373. 3: horizontal right
  374. A rectangle cycles up/right/down/left or up/left/down/right.
  375. The test fails if:
  376. The path is closed, and followed by a line.
  377. A second move creates a new endpoint.
  378. A diagonal line is parsed.
  379. There's more than four changes of direction.
  380. There's a discontinuity on the line (e.g., a move in the middle)
  381. The line reverses direction.
  382. The path contains a quadratic or cubic.
  383. The path contains fewer than four points.
  384. *The rectangle doesn't complete a cycle.
  385. *The final point isn't equal to the first point.
  386. *These last two conditions we relax if we have a 3-edge path that would
  387. form a rectangle if it were closed (as we do when we fill a path)
  388. It's OK if the path has:
  389. Several colinear line segments composing a rectangle side.
  390. Single points on the rectangle side.
  391. The direction takes advantage of the corners found since opposite sides
  392. must travel in opposite directions.
  393. FIXME: Allow colinear quads and cubics to be treated like lines.
  394. FIXME: If the API passes fill-only, return true if the filled stroke
  395. is a rectangle, though the caller failed to close the path.
  396. directions values:
  397. 0x1 is set if the segment is horizontal
  398. 0x2 is set if the segment is moving to the right or down
  399. thus:
  400. two directions are opposites iff (dirA ^ dirB) == 0x2
  401. two directions are perpendicular iff (dirA ^ dirB) == 0x1
  402. */
  403. static int rect_make_dir(SkScalar dx, SkScalar dy) {
  404. return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
  405. }
  406. bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr,
  407. bool* isClosed, Direction* direction, SkRect* rect) const {
  408. int corners = 0;
  409. SkPoint closeXY; // used to determine if final line falls on a diagonal
  410. SkPoint lineStart; // used to construct line from previous point
  411. const SkPoint* firstPt = nullptr; // first point in the rect (last of first moves)
  412. const SkPoint* lastPt = nullptr; // last point in the rect (last of lines or first if closed)
  413. SkPoint firstCorner;
  414. SkPoint thirdCorner;
  415. const SkPoint* pts = *ptsPtr;
  416. const SkPoint* savePts = nullptr; // used to allow caller to iterate through a pair of rects
  417. lineStart.set(0, 0);
  418. signed char directions[] = {-1, -1, -1, -1, -1}; // -1 to 3; -1 is uninitialized
  419. bool closedOrMoved = false;
  420. bool autoClose = false;
  421. bool insertClose = false;
  422. int verbCnt = fPathRef->countVerbs();
  423. while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
  424. uint8_t verb = insertClose ? (uint8_t) kClose_Verb : fPathRef->atVerb(*currVerb);
  425. switch (verb) {
  426. case kClose_Verb:
  427. savePts = pts;
  428. autoClose = true;
  429. insertClose = false;
  430. case kLine_Verb: {
  431. if (kClose_Verb != verb) {
  432. lastPt = pts;
  433. }
  434. SkPoint lineEnd = kClose_Verb == verb ? *firstPt : *pts++;
  435. SkVector lineDelta = lineEnd - lineStart;
  436. if (lineDelta.fX && lineDelta.fY) {
  437. return false; // diagonal
  438. }
  439. if (!lineDelta.isFinite()) {
  440. return false; // path contains infinity or NaN
  441. }
  442. if (lineStart == lineEnd) {
  443. break; // single point on side OK
  444. }
  445. int nextDirection = rect_make_dir(lineDelta.fX, lineDelta.fY); // 0 to 3
  446. if (0 == corners) {
  447. directions[0] = nextDirection;
  448. corners = 1;
  449. closedOrMoved = false;
  450. lineStart = lineEnd;
  451. break;
  452. }
  453. if (closedOrMoved) {
  454. return false; // closed followed by a line
  455. }
  456. if (autoClose && nextDirection == directions[0]) {
  457. break; // colinear with first
  458. }
  459. closedOrMoved = autoClose;
  460. if (directions[corners - 1] == nextDirection) {
  461. if (3 == corners && kLine_Verb == verb) {
  462. thirdCorner = lineEnd;
  463. }
  464. lineStart = lineEnd;
  465. break; // colinear segment
  466. }
  467. directions[corners++] = nextDirection;
  468. // opposite lines must point in opposite directions; xoring them should equal 2
  469. switch (corners) {
  470. case 2:
  471. firstCorner = lineStart;
  472. break;
  473. case 3:
  474. if ((directions[0] ^ directions[2]) != 2) {
  475. return false;
  476. }
  477. thirdCorner = lineEnd;
  478. break;
  479. case 4:
  480. if ((directions[1] ^ directions[3]) != 2) {
  481. return false;
  482. }
  483. break;
  484. default:
  485. return false; // too many direction changes
  486. }
  487. lineStart = lineEnd;
  488. break;
  489. }
  490. case kQuad_Verb:
  491. case kConic_Verb:
  492. case kCubic_Verb:
  493. return false; // quadratic, cubic not allowed
  494. case kMove_Verb:
  495. if (allowPartial && !autoClose && directions[0] >= 0) {
  496. insertClose = true;
  497. *currVerb -= 1; // try move again afterwards
  498. goto addMissingClose;
  499. }
  500. if (!corners) {
  501. firstPt = pts;
  502. } else {
  503. closeXY = *firstPt - *lastPt;
  504. if (closeXY.fX && closeXY.fY) {
  505. return false; // we're diagonal, abort
  506. }
  507. }
  508. lineStart = *pts++;
  509. closedOrMoved = true;
  510. break;
  511. default:
  512. SkDEBUGFAIL("unexpected verb");
  513. break;
  514. }
  515. *currVerb += 1;
  516. addMissingClose:
  517. ;
  518. }
  519. // Success if 4 corners and first point equals last
  520. if (corners < 3 || corners > 4) {
  521. return false;
  522. }
  523. if (savePts) {
  524. *ptsPtr = savePts;
  525. }
  526. // check if close generates diagonal
  527. closeXY = *firstPt - *lastPt;
  528. if (closeXY.fX && closeXY.fY) {
  529. return false;
  530. }
  531. if (rect) {
  532. rect->set(firstCorner, thirdCorner);
  533. }
  534. if (isClosed) {
  535. *isClosed = autoClose;
  536. }
  537. if (direction) {
  538. *direction = directions[0] == ((directions[1] + 1) & 3) ? kCW_Direction : kCCW_Direction;
  539. }
  540. return true;
  541. }
  542. bool SkPath::isRect(SkRect* rect, bool* isClosed, Direction* direction) const {
  543. SkDEBUGCODE(this->validate();)
  544. int currVerb = 0;
  545. const SkPoint* pts = fPathRef->points();
  546. return this->isRectContour(false, &currVerb, &pts, isClosed, direction, rect);
  547. }
  548. bool SkPath::isNestedFillRects(SkRect rects[2], Direction dirs[2]) const {
  549. SkDEBUGCODE(this->validate();)
  550. int currVerb = 0;
  551. const SkPoint* pts = fPathRef->points();
  552. Direction testDirs[2];
  553. SkRect testRects[2];
  554. if (!isRectContour(true, &currVerb, &pts, nullptr, &testDirs[0], &testRects[0])) {
  555. return false;
  556. }
  557. if (isRectContour(false, &currVerb, &pts, nullptr, &testDirs[1], &testRects[1])) {
  558. if (testRects[0].contains(testRects[1])) {
  559. if (rects) {
  560. rects[0] = testRects[0];
  561. rects[1] = testRects[1];
  562. }
  563. if (dirs) {
  564. dirs[0] = testDirs[0];
  565. dirs[1] = testDirs[1];
  566. }
  567. return true;
  568. }
  569. if (testRects[1].contains(testRects[0])) {
  570. if (rects) {
  571. rects[0] = testRects[1];
  572. rects[1] = testRects[0];
  573. }
  574. if (dirs) {
  575. dirs[0] = testDirs[1];
  576. dirs[1] = testDirs[0];
  577. }
  578. return true;
  579. }
  580. }
  581. return false;
  582. }
  583. bool SkPath::isOval(SkRect* bounds) const {
  584. return SkPathPriv::IsOval(*this, bounds, nullptr, nullptr);
  585. }
  586. bool SkPath::isRRect(SkRRect* rrect) const {
  587. return SkPathPriv::IsRRect(*this, rrect, nullptr, nullptr);
  588. }
  589. int SkPath::countPoints() const {
  590. return fPathRef->countPoints();
  591. }
  592. int SkPath::getPoints(SkPoint dst[], int max) const {
  593. SkDEBUGCODE(this->validate();)
  594. SkASSERT(max >= 0);
  595. SkASSERT(!max || dst);
  596. int count = SkMin32(max, fPathRef->countPoints());
  597. sk_careful_memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
  598. return fPathRef->countPoints();
  599. }
  600. SkPoint SkPath::getPoint(int index) const {
  601. if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
  602. return fPathRef->atPoint(index);
  603. }
  604. return SkPoint::Make(0, 0);
  605. }
  606. int SkPath::countVerbs() const {
  607. return fPathRef->countVerbs();
  608. }
  609. static inline void copy_verbs_reverse(uint8_t* inorderDst,
  610. const uint8_t* reversedSrc,
  611. int count) {
  612. for (int i = 0; i < count; ++i) {
  613. inorderDst[i] = reversedSrc[~i];
  614. }
  615. }
  616. int SkPath::getVerbs(uint8_t dst[], int max) const {
  617. SkDEBUGCODE(this->validate();)
  618. SkASSERT(max >= 0);
  619. SkASSERT(!max || dst);
  620. int count = SkMin32(max, fPathRef->countVerbs());
  621. copy_verbs_reverse(dst, fPathRef->verbs(), count);
  622. return fPathRef->countVerbs();
  623. }
  624. size_t SkPath::approximateBytesUsed() const {
  625. size_t size = sizeof (SkPath);
  626. if (fPathRef != nullptr) {
  627. size += fPathRef->countPoints() * sizeof(SkPoint)
  628. + fPathRef->countVerbs()
  629. + fPathRef->countWeights() * sizeof(SkScalar);
  630. }
  631. return size;
  632. }
  633. bool SkPath::getLastPt(SkPoint* lastPt) const {
  634. SkDEBUGCODE(this->validate();)
  635. int count = fPathRef->countPoints();
  636. if (count > 0) {
  637. if (lastPt) {
  638. *lastPt = fPathRef->atPoint(count - 1);
  639. }
  640. return true;
  641. }
  642. if (lastPt) {
  643. lastPt->set(0, 0);
  644. }
  645. return false;
  646. }
  647. void SkPath::setPt(int index, SkScalar x, SkScalar y) {
  648. SkDEBUGCODE(this->validate();)
  649. int count = fPathRef->countPoints();
  650. if (count <= index) {
  651. return;
  652. } else {
  653. SkPathRef::Editor ed(&fPathRef);
  654. ed.atPoint(index)->set(x, y);
  655. }
  656. }
  657. void SkPath::setLastPt(SkScalar x, SkScalar y) {
  658. SkDEBUGCODE(this->validate();)
  659. int count = fPathRef->countPoints();
  660. if (count == 0) {
  661. this->moveTo(x, y);
  662. } else {
  663. SkPathRef::Editor ed(&fPathRef);
  664. ed.atPoint(count-1)->set(x, y);
  665. }
  666. }
  667. // This is the public-facing non-const setConvexity().
  668. void SkPath::setConvexity(Convexity c) {
  669. fConvexity.store(c, std::memory_order_relaxed);
  670. }
  671. // Const hooks for working with fConvexity and fFirstDirection from const methods.
  672. void SkPath::setConvexity(Convexity c) const {
  673. fConvexity.store(c, std::memory_order_relaxed);
  674. }
  675. void SkPath::setFirstDirection(uint8_t d) const {
  676. fFirstDirection.store(d, std::memory_order_relaxed);
  677. }
  678. uint8_t SkPath::getFirstDirection() const {
  679. return fFirstDirection.load(std::memory_order_relaxed);
  680. }
  681. //////////////////////////////////////////////////////////////////////////////
  682. // Construction methods
  683. #define DIRTY_AFTER_EDIT \
  684. do { \
  685. this->setConvexity(kUnknown_Convexity); \
  686. this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection); \
  687. } while (0)
  688. void SkPath::incReserve(int inc) {
  689. SkDEBUGCODE(this->validate();)
  690. if (inc > 0) {
  691. SkPathRef::Editor(&fPathRef, inc, inc);
  692. }
  693. SkDEBUGCODE(this->validate();)
  694. }
  695. SkPath& SkPath::moveTo(SkScalar x, SkScalar y) {
  696. SkDEBUGCODE(this->validate();)
  697. SkPathRef::Editor ed(&fPathRef);
  698. // remember our index
  699. fLastMoveToIndex = fPathRef->countPoints();
  700. ed.growForVerb(kMove_Verb)->set(x, y);
  701. DIRTY_AFTER_EDIT;
  702. return *this;
  703. }
  704. SkPath& SkPath::rMoveTo(SkScalar x, SkScalar y) {
  705. SkPoint pt;
  706. this->getLastPt(&pt);
  707. return this->moveTo(pt.fX + x, pt.fY + y);
  708. }
  709. void SkPath::injectMoveToIfNeeded() {
  710. if (fLastMoveToIndex < 0) {
  711. SkScalar x, y;
  712. if (fPathRef->countVerbs() == 0) {
  713. x = y = 0;
  714. } else {
  715. const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
  716. x = pt.fX;
  717. y = pt.fY;
  718. }
  719. this->moveTo(x, y);
  720. }
  721. }
  722. SkPath& SkPath::lineTo(SkScalar x, SkScalar y) {
  723. SkDEBUGCODE(this->validate();)
  724. this->injectMoveToIfNeeded();
  725. SkPathRef::Editor ed(&fPathRef);
  726. ed.growForVerb(kLine_Verb)->set(x, y);
  727. DIRTY_AFTER_EDIT;
  728. return *this;
  729. }
  730. SkPath& SkPath::rLineTo(SkScalar x, SkScalar y) {
  731. this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
  732. SkPoint pt;
  733. this->getLastPt(&pt);
  734. return this->lineTo(pt.fX + x, pt.fY + y);
  735. }
  736. SkPath& SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
  737. SkDEBUGCODE(this->validate();)
  738. this->injectMoveToIfNeeded();
  739. SkPathRef::Editor ed(&fPathRef);
  740. SkPoint* pts = ed.growForVerb(kQuad_Verb);
  741. pts[0].set(x1, y1);
  742. pts[1].set(x2, y2);
  743. DIRTY_AFTER_EDIT;
  744. return *this;
  745. }
  746. SkPath& SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
  747. this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
  748. SkPoint pt;
  749. this->getLastPt(&pt);
  750. return this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
  751. }
  752. SkPath& SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
  753. SkScalar w) {
  754. // check for <= 0 or NaN with this test
  755. if (!(w > 0)) {
  756. this->lineTo(x2, y2);
  757. } else if (!SkScalarIsFinite(w)) {
  758. this->lineTo(x1, y1);
  759. this->lineTo(x2, y2);
  760. } else if (SK_Scalar1 == w) {
  761. this->quadTo(x1, y1, x2, y2);
  762. } else {
  763. SkDEBUGCODE(this->validate();)
  764. this->injectMoveToIfNeeded();
  765. SkPathRef::Editor ed(&fPathRef);
  766. SkPoint* pts = ed.growForVerb(kConic_Verb, w);
  767. pts[0].set(x1, y1);
  768. pts[1].set(x2, y2);
  769. DIRTY_AFTER_EDIT;
  770. }
  771. return *this;
  772. }
  773. SkPath& SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
  774. SkScalar w) {
  775. this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
  776. SkPoint pt;
  777. this->getLastPt(&pt);
  778. return this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
  779. }
  780. SkPath& SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
  781. SkScalar x3, SkScalar y3) {
  782. SkDEBUGCODE(this->validate();)
  783. this->injectMoveToIfNeeded();
  784. SkPathRef::Editor ed(&fPathRef);
  785. SkPoint* pts = ed.growForVerb(kCubic_Verb);
  786. pts[0].set(x1, y1);
  787. pts[1].set(x2, y2);
  788. pts[2].set(x3, y3);
  789. DIRTY_AFTER_EDIT;
  790. return *this;
  791. }
  792. SkPath& SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
  793. SkScalar x3, SkScalar y3) {
  794. this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
  795. SkPoint pt;
  796. this->getLastPt(&pt);
  797. return this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
  798. pt.fX + x3, pt.fY + y3);
  799. }
  800. SkPath& SkPath::close() {
  801. SkDEBUGCODE(this->validate();)
  802. int count = fPathRef->countVerbs();
  803. if (count > 0) {
  804. switch (fPathRef->atVerb(count - 1)) {
  805. case kLine_Verb:
  806. case kQuad_Verb:
  807. case kConic_Verb:
  808. case kCubic_Verb:
  809. case kMove_Verb: {
  810. SkPathRef::Editor ed(&fPathRef);
  811. ed.growForVerb(kClose_Verb);
  812. break;
  813. }
  814. case kClose_Verb:
  815. // don't add a close if it's the first verb or a repeat
  816. break;
  817. default:
  818. SkDEBUGFAIL("unexpected verb");
  819. break;
  820. }
  821. }
  822. // signal that we need a moveTo to follow us (unless we're done)
  823. #if 0
  824. if (fLastMoveToIndex >= 0) {
  825. fLastMoveToIndex = ~fLastMoveToIndex;
  826. }
  827. #else
  828. fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
  829. #endif
  830. return *this;
  831. }
  832. ///////////////////////////////////////////////////////////////////////////////
  833. namespace {
  834. template <unsigned N>
  835. class PointIterator {
  836. public:
  837. PointIterator(SkPath::Direction dir, unsigned startIndex)
  838. : fCurrent(startIndex % N)
  839. , fAdvance(dir == SkPath::kCW_Direction ? 1 : N - 1) { }
  840. const SkPoint& current() const {
  841. SkASSERT(fCurrent < N);
  842. return fPts[fCurrent];
  843. }
  844. const SkPoint& next() {
  845. fCurrent = (fCurrent + fAdvance) % N;
  846. return this->current();
  847. }
  848. protected:
  849. SkPoint fPts[N];
  850. private:
  851. unsigned fCurrent;
  852. unsigned fAdvance;
  853. };
  854. class RectPointIterator : public PointIterator<4> {
  855. public:
  856. RectPointIterator(const SkRect& rect, SkPath::Direction dir, unsigned startIndex)
  857. : PointIterator(dir, startIndex) {
  858. fPts[0] = SkPoint::Make(rect.fLeft, rect.fTop);
  859. fPts[1] = SkPoint::Make(rect.fRight, rect.fTop);
  860. fPts[2] = SkPoint::Make(rect.fRight, rect.fBottom);
  861. fPts[3] = SkPoint::Make(rect.fLeft, rect.fBottom);
  862. }
  863. };
  864. class OvalPointIterator : public PointIterator<4> {
  865. public:
  866. OvalPointIterator(const SkRect& oval, SkPath::Direction dir, unsigned startIndex)
  867. : PointIterator(dir, startIndex) {
  868. const SkScalar cx = oval.centerX();
  869. const SkScalar cy = oval.centerY();
  870. fPts[0] = SkPoint::Make(cx, oval.fTop);
  871. fPts[1] = SkPoint::Make(oval.fRight, cy);
  872. fPts[2] = SkPoint::Make(cx, oval.fBottom);
  873. fPts[3] = SkPoint::Make(oval.fLeft, cy);
  874. }
  875. };
  876. class RRectPointIterator : public PointIterator<8> {
  877. public:
  878. RRectPointIterator(const SkRRect& rrect, SkPath::Direction dir, unsigned startIndex)
  879. : PointIterator(dir, startIndex) {
  880. const SkRect& bounds = rrect.getBounds();
  881. const SkScalar L = bounds.fLeft;
  882. const SkScalar T = bounds.fTop;
  883. const SkScalar R = bounds.fRight;
  884. const SkScalar B = bounds.fBottom;
  885. fPts[0] = SkPoint::Make(L + rrect.radii(SkRRect::kUpperLeft_Corner).fX, T);
  886. fPts[1] = SkPoint::Make(R - rrect.radii(SkRRect::kUpperRight_Corner).fX, T);
  887. fPts[2] = SkPoint::Make(R, T + rrect.radii(SkRRect::kUpperRight_Corner).fY);
  888. fPts[3] = SkPoint::Make(R, B - rrect.radii(SkRRect::kLowerRight_Corner).fY);
  889. fPts[4] = SkPoint::Make(R - rrect.radii(SkRRect::kLowerRight_Corner).fX, B);
  890. fPts[5] = SkPoint::Make(L + rrect.radii(SkRRect::kLowerLeft_Corner).fX, B);
  891. fPts[6] = SkPoint::Make(L, B - rrect.radii(SkRRect::kLowerLeft_Corner).fY);
  892. fPts[7] = SkPoint::Make(L, T + rrect.radii(SkRRect::kUpperLeft_Corner).fY);
  893. }
  894. };
  895. } // anonymous namespace
  896. static void assert_known_direction(int dir) {
  897. SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
  898. }
  899. SkPath& SkPath::addRect(const SkRect& rect, Direction dir) {
  900. return this->addRect(rect, dir, 0);
  901. }
  902. SkPath& SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
  903. SkScalar bottom, Direction dir) {
  904. return this->addRect(SkRect::MakeLTRB(left, top, right, bottom), dir, 0);
  905. }
  906. SkPath& SkPath::addRect(const SkRect &rect, Direction dir, unsigned startIndex) {
  907. assert_known_direction(dir);
  908. this->setFirstDirection(this->hasOnlyMoveTos() ? (SkPathPriv::FirstDirection)dir
  909. : SkPathPriv::kUnknown_FirstDirection);
  910. SkAutoDisableDirectionCheck addc(this);
  911. SkAutoPathBoundsUpdate apbu(this, rect);
  912. SkDEBUGCODE(int initialVerbCount = this->countVerbs());
  913. const int kVerbs = 5; // moveTo + 3x lineTo + close
  914. this->incReserve(kVerbs);
  915. RectPointIterator iter(rect, dir, startIndex);
  916. this->moveTo(iter.current());
  917. this->lineTo(iter.next());
  918. this->lineTo(iter.next());
  919. this->lineTo(iter.next());
  920. this->close();
  921. SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
  922. return *this;
  923. }
  924. SkPath& SkPath::addPoly(const SkPoint pts[], int count, bool close) {
  925. SkDEBUGCODE(this->validate();)
  926. if (count <= 0) {
  927. return *this;
  928. }
  929. fLastMoveToIndex = fPathRef->countPoints();
  930. // +close makes room for the extra kClose_Verb
  931. SkPathRef::Editor ed(&fPathRef, count+close, count);
  932. ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
  933. if (count > 1) {
  934. SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
  935. memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
  936. }
  937. if (close) {
  938. ed.growForVerb(kClose_Verb);
  939. fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
  940. }
  941. DIRTY_AFTER_EDIT;
  942. SkDEBUGCODE(this->validate();)
  943. return *this;
  944. }
  945. #include "src/core/SkGeometry.h"
  946. static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
  947. SkPoint* pt) {
  948. if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) {
  949. // Chrome uses this path to move into and out of ovals. If not
  950. // treated as a special case the moves can distort the oval's
  951. // bounding box (and break the circle special case).
  952. pt->set(oval.fRight, oval.centerY());
  953. return true;
  954. } else if (0 == oval.width() && 0 == oval.height()) {
  955. // Chrome will sometimes create 0 radius round rects. Having degenerate
  956. // quad segments in the path prevents the path from being recognized as
  957. // a rect.
  958. // TODO: optimizing the case where only one of width or height is zero
  959. // should also be considered. This case, however, doesn't seem to be
  960. // as common as the single point case.
  961. pt->set(oval.fRight, oval.fTop);
  962. return true;
  963. }
  964. return false;
  965. }
  966. // Return the unit vectors pointing at the start/stop points for the given start/sweep angles
  967. //
  968. static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle,
  969. SkVector* startV, SkVector* stopV, SkRotationDirection* dir) {
  970. SkScalar startRad = SkDegreesToRadians(startAngle),
  971. stopRad = SkDegreesToRadians(startAngle + sweepAngle);
  972. startV->fY = SkScalarSinSnapToZero(startRad);
  973. startV->fX = SkScalarCosSnapToZero(startRad);
  974. stopV->fY = SkScalarSinSnapToZero(stopRad);
  975. stopV->fX = SkScalarCosSnapToZero(stopRad);
  976. /* If the sweep angle is nearly (but less than) 360, then due to precision
  977. loss in radians-conversion and/or sin/cos, we may end up with coincident
  978. vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
  979. of drawing a nearly complete circle (good).
  980. e.g. canvas.drawArc(0, 359.99, ...)
  981. -vs- canvas.drawArc(0, 359.9, ...)
  982. We try to detect this edge case, and tweak the stop vector
  983. */
  984. if (*startV == *stopV) {
  985. SkScalar sw = SkScalarAbs(sweepAngle);
  986. if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
  987. // make a guess at a tiny angle (in radians) to tweak by
  988. SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
  989. // not sure how much will be enough, so we use a loop
  990. do {
  991. stopRad -= deltaRad;
  992. stopV->fY = SkScalarSinSnapToZero(stopRad);
  993. stopV->fX = SkScalarCosSnapToZero(stopRad);
  994. } while (*startV == *stopV);
  995. }
  996. }
  997. *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
  998. }
  999. /**
  1000. * If this returns 0, then the caller should just line-to the singlePt, else it should
  1001. * ignore singlePt and append the specified number of conics.
  1002. */
  1003. static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop,
  1004. SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc],
  1005. SkPoint* singlePt) {
  1006. SkMatrix matrix;
  1007. matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
  1008. matrix.postTranslate(oval.centerX(), oval.centerY());
  1009. int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
  1010. if (0 == count) {
  1011. matrix.mapXY(stop.x(), stop.y(), singlePt);
  1012. }
  1013. return count;
  1014. }
  1015. SkPath& SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
  1016. Direction dir) {
  1017. SkRRect rrect;
  1018. rrect.setRectRadii(rect, (const SkVector*) radii);
  1019. return this->addRRect(rrect, dir);
  1020. }
  1021. SkPath& SkPath::addRRect(const SkRRect& rrect, Direction dir) {
  1022. // legacy start indices: 6 (CW) and 7(CCW)
  1023. return this->addRRect(rrect, dir, dir == kCW_Direction ? 6 : 7);
  1024. }
  1025. SkPath& SkPath::addRRect(const SkRRect &rrect, Direction dir, unsigned startIndex) {
  1026. assert_known_direction(dir);
  1027. bool isRRect = hasOnlyMoveTos();
  1028. const SkRect& bounds = rrect.getBounds();
  1029. if (rrect.isRect() || rrect.isEmpty()) {
  1030. // degenerate(rect) => radii points are collapsing
  1031. this->addRect(bounds, dir, (startIndex + 1) / 2);
  1032. } else if (rrect.isOval()) {
  1033. // degenerate(oval) => line points are collapsing
  1034. this->addOval(bounds, dir, startIndex / 2);
  1035. } else {
  1036. this->setFirstDirection(this->hasOnlyMoveTos() ? (SkPathPriv::FirstDirection)dir
  1037. : SkPathPriv::kUnknown_FirstDirection);
  1038. SkAutoPathBoundsUpdate apbu(this, bounds);
  1039. SkAutoDisableDirectionCheck addc(this);
  1040. // we start with a conic on odd indices when moving CW vs. even indices when moving CCW
  1041. const bool startsWithConic = ((startIndex & 1) == (dir == kCW_Direction));
  1042. const SkScalar weight = SK_ScalarRoot2Over2;
  1043. SkDEBUGCODE(int initialVerbCount = this->countVerbs());
  1044. const int kVerbs = startsWithConic
  1045. ? 9 // moveTo + 4x conicTo + 3x lineTo + close
  1046. : 10; // moveTo + 4x lineTo + 4x conicTo + close
  1047. this->incReserve(kVerbs);
  1048. RRectPointIterator rrectIter(rrect, dir, startIndex);
  1049. // Corner iterator indices follow the collapsed radii model,
  1050. // adjusted such that the start pt is "behind" the radii start pt.
  1051. const unsigned rectStartIndex = startIndex / 2 + (dir == kCW_Direction ? 0 : 1);
  1052. RectPointIterator rectIter(bounds, dir, rectStartIndex);
  1053. this->moveTo(rrectIter.current());
  1054. if (startsWithConic) {
  1055. for (unsigned i = 0; i < 3; ++i) {
  1056. this->conicTo(rectIter.next(), rrectIter.next(), weight);
  1057. this->lineTo(rrectIter.next());
  1058. }
  1059. this->conicTo(rectIter.next(), rrectIter.next(), weight);
  1060. // final lineTo handled by close().
  1061. } else {
  1062. for (unsigned i = 0; i < 4; ++i) {
  1063. this->lineTo(rrectIter.next());
  1064. this->conicTo(rectIter.next(), rrectIter.next(), weight);
  1065. }
  1066. }
  1067. this->close();
  1068. SkPathRef::Editor ed(&fPathRef);
  1069. ed.setIsRRect(isRRect, dir, startIndex % 8);
  1070. SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
  1071. }
  1072. SkDEBUGCODE(fPathRef->validate();)
  1073. return *this;
  1074. }
  1075. bool SkPath::hasOnlyMoveTos() const {
  1076. int count = fPathRef->countVerbs();
  1077. const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin();
  1078. for (int i = 0; i < count; ++i) {
  1079. if (*verbs == kLine_Verb ||
  1080. *verbs == kQuad_Verb ||
  1081. *verbs == kConic_Verb ||
  1082. *verbs == kCubic_Verb) {
  1083. return false;
  1084. }
  1085. ++verbs;
  1086. }
  1087. return true;
  1088. }
  1089. bool SkPath::isZeroLengthSincePoint(int startPtIndex) const {
  1090. int count = fPathRef->countPoints() - startPtIndex;
  1091. if (count < 2) {
  1092. return true;
  1093. }
  1094. const SkPoint* pts = fPathRef.get()->points() + startPtIndex;
  1095. const SkPoint& first = *pts;
  1096. for (int index = 1; index < count; ++index) {
  1097. if (first != pts[index]) {
  1098. return false;
  1099. }
  1100. }
  1101. return true;
  1102. }
  1103. SkPath& SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
  1104. Direction dir) {
  1105. assert_known_direction(dir);
  1106. if (rx < 0 || ry < 0) {
  1107. return *this;
  1108. }
  1109. SkRRect rrect;
  1110. rrect.setRectXY(rect, rx, ry);
  1111. return this->addRRect(rrect, dir);
  1112. }
  1113. SkPath& SkPath::addOval(const SkRect& oval, Direction dir) {
  1114. // legacy start index: 1
  1115. return this->addOval(oval, dir, 1);
  1116. }
  1117. SkPath& SkPath::addOval(const SkRect &oval, Direction dir, unsigned startPointIndex) {
  1118. assert_known_direction(dir);
  1119. /* If addOval() is called after previous moveTo(),
  1120. this path is still marked as an oval. This is used to
  1121. fit into WebKit's calling sequences.
  1122. We can't simply check isEmpty() in this case, as additional
  1123. moveTo() would mark the path non empty.
  1124. */
  1125. bool isOval = hasOnlyMoveTos();
  1126. if (isOval) {
  1127. this->setFirstDirection((SkPathPriv::FirstDirection)dir);
  1128. } else {
  1129. this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
  1130. }
  1131. SkAutoDisableDirectionCheck addc(this);
  1132. SkAutoPathBoundsUpdate apbu(this, oval);
  1133. SkDEBUGCODE(int initialVerbCount = this->countVerbs());
  1134. const int kVerbs = 6; // moveTo + 4x conicTo + close
  1135. this->incReserve(kVerbs);
  1136. OvalPointIterator ovalIter(oval, dir, startPointIndex);
  1137. // The corner iterator pts are tracking "behind" the oval/radii pts.
  1138. RectPointIterator rectIter(oval, dir, startPointIndex + (dir == kCW_Direction ? 0 : 1));
  1139. const SkScalar weight = SK_ScalarRoot2Over2;
  1140. this->moveTo(ovalIter.current());
  1141. for (unsigned i = 0; i < 4; ++i) {
  1142. this->conicTo(rectIter.next(), ovalIter.next(), weight);
  1143. }
  1144. this->close();
  1145. SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
  1146. SkPathRef::Editor ed(&fPathRef);
  1147. ed.setIsOval(isOval, kCCW_Direction == dir, startPointIndex % 4);
  1148. return *this;
  1149. }
  1150. SkPath& SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
  1151. if (r > 0) {
  1152. this->addOval(SkRect::MakeLTRB(x - r, y - r, x + r, y + r), dir);
  1153. }
  1154. return *this;
  1155. }
  1156. SkPath& SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
  1157. bool forceMoveTo) {
  1158. if (oval.width() < 0 || oval.height() < 0) {
  1159. return *this;
  1160. }
  1161. if (fPathRef->countVerbs() == 0) {
  1162. forceMoveTo = true;
  1163. }
  1164. SkPoint lonePt;
  1165. if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) {
  1166. return forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt);
  1167. }
  1168. SkVector startV, stopV;
  1169. SkRotationDirection dir;
  1170. angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir);
  1171. SkPoint singlePt;
  1172. // Adds a move-to to 'pt' if forceMoveTo is true. Otherwise a lineTo unless we're sufficiently
  1173. // close to 'pt' currently. This prevents spurious lineTos when adding a series of contiguous
  1174. // arcs from the same oval.
  1175. auto addPt = [&forceMoveTo, this](const SkPoint& pt) {
  1176. SkPoint lastPt;
  1177. if (forceMoveTo) {
  1178. this->moveTo(pt);
  1179. } else if (!this->getLastPt(&lastPt) ||
  1180. !SkScalarNearlyEqual(lastPt.fX, pt.fX) ||
  1181. !SkScalarNearlyEqual(lastPt.fY, pt.fY)) {
  1182. this->lineTo(pt);
  1183. }
  1184. };
  1185. // At this point, we know that the arc is not a lone point, but startV == stopV
  1186. // indicates that the sweepAngle is too small such that angles_to_unit_vectors
  1187. // cannot handle it.
  1188. if (startV == stopV) {
  1189. SkScalar endAngle = SkDegreesToRadians(startAngle + sweepAngle);
  1190. SkScalar radiusX = oval.width() / 2;
  1191. SkScalar radiusY = oval.height() / 2;
  1192. // We do not use SkScalar[Sin|Cos]SnapToZero here. When sin(startAngle) is 0 and sweepAngle
  1193. // is very small and radius is huge, the expected behavior here is to draw a line. But
  1194. // calling SkScalarSinSnapToZero will make sin(endAngle) be 0 which will then draw a dot.
  1195. singlePt.set(oval.centerX() + radiusX * SkScalarCos(endAngle),
  1196. oval.centerY() + radiusY * SkScalarSin(endAngle));
  1197. addPt(singlePt);
  1198. return *this;
  1199. }
  1200. SkConic conics[SkConic::kMaxConicsForArc];
  1201. int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt);
  1202. if (count) {
  1203. this->incReserve(count * 2 + 1);
  1204. const SkPoint& pt = conics[0].fPts[0];
  1205. addPt(pt);
  1206. for (int i = 0; i < count; ++i) {
  1207. this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW);
  1208. }
  1209. } else {
  1210. addPt(singlePt);
  1211. }
  1212. return *this;
  1213. }
  1214. // This converts the SVG arc to conics.
  1215. // Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
  1216. // Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic()
  1217. // See also SVG implementation notes:
  1218. // http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
  1219. // Note that arcSweep bool value is flipped from the original implementation.
  1220. SkPath& SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge,
  1221. SkPath::Direction arcSweep, SkScalar x, SkScalar y) {
  1222. this->injectMoveToIfNeeded();
  1223. SkPoint srcPts[2];
  1224. this->getLastPt(&srcPts[0]);
  1225. // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto")
  1226. // joining the endpoints.
  1227. // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
  1228. if (!rx || !ry) {
  1229. return this->lineTo(x, y);
  1230. }
  1231. // If the current point and target point for the arc are identical, it should be treated as a
  1232. // zero length path. This ensures continuity in animations.
  1233. srcPts[1].set(x, y);
  1234. if (srcPts[0] == srcPts[1]) {
  1235. return this->lineTo(x, y);
  1236. }
  1237. rx = SkScalarAbs(rx);
  1238. ry = SkScalarAbs(ry);
  1239. SkVector midPointDistance = srcPts[0] - srcPts[1];
  1240. midPointDistance *= 0.5f;
  1241. SkMatrix pointTransform;
  1242. pointTransform.setRotate(-angle);
  1243. SkPoint transformedMidPoint;
  1244. pointTransform.mapPoints(&transformedMidPoint, &midPointDistance, 1);
  1245. SkScalar squareRx = rx * rx;
  1246. SkScalar squareRy = ry * ry;
  1247. SkScalar squareX = transformedMidPoint.fX * transformedMidPoint.fX;
  1248. SkScalar squareY = transformedMidPoint.fY * transformedMidPoint.fY;
  1249. // Check if the radii are big enough to draw the arc, scale radii if not.
  1250. // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
  1251. SkScalar radiiScale = squareX / squareRx + squareY / squareRy;
  1252. if (radiiScale > 1) {
  1253. radiiScale = SkScalarSqrt(radiiScale);
  1254. rx *= radiiScale;
  1255. ry *= radiiScale;
  1256. }
  1257. pointTransform.setScale(1 / rx, 1 / ry);
  1258. pointTransform.preRotate(-angle);
  1259. SkPoint unitPts[2];
  1260. pointTransform.mapPoints(unitPts, srcPts, (int) SK_ARRAY_COUNT(unitPts));
  1261. SkVector delta = unitPts[1] - unitPts[0];
  1262. SkScalar d = delta.fX * delta.fX + delta.fY * delta.fY;
  1263. SkScalar scaleFactorSquared = SkTMax(1 / d - 0.25f, 0.f);
  1264. SkScalar scaleFactor = SkScalarSqrt(scaleFactorSquared);
  1265. if (SkToBool(arcSweep) != SkToBool(arcLarge)) { // flipped from the original implementation
  1266. scaleFactor = -scaleFactor;
  1267. }
  1268. delta.scale(scaleFactor);
  1269. SkPoint centerPoint = unitPts[0] + unitPts[1];
  1270. centerPoint *= 0.5f;
  1271. centerPoint.offset(-delta.fY, delta.fX);
  1272. unitPts[0] -= centerPoint;
  1273. unitPts[1] -= centerPoint;
  1274. SkScalar theta1 = SkScalarATan2(unitPts[0].fY, unitPts[0].fX);
  1275. SkScalar theta2 = SkScalarATan2(unitPts[1].fY, unitPts[1].fX);
  1276. SkScalar thetaArc = theta2 - theta1;
  1277. if (thetaArc < 0 && !arcSweep) { // arcSweep flipped from the original implementation
  1278. thetaArc += SK_ScalarPI * 2;
  1279. } else if (thetaArc > 0 && arcSweep) { // arcSweep flipped from the original implementation
  1280. thetaArc -= SK_ScalarPI * 2;
  1281. }
  1282. pointTransform.setRotate(angle);
  1283. pointTransform.preScale(rx, ry);
  1284. // the arc may be slightly bigger than 1/4 circle, so allow up to 1/3rd
  1285. int segments = SkScalarCeilToInt(SkScalarAbs(thetaArc / (2 * SK_ScalarPI / 3)));
  1286. SkScalar thetaWidth = thetaArc / segments;
  1287. SkScalar t = SkScalarTan(0.5f * thetaWidth);
  1288. if (!SkScalarIsFinite(t)) {
  1289. return *this;
  1290. }
  1291. SkScalar startTheta = theta1;
  1292. SkScalar w = SkScalarSqrt(SK_ScalarHalf + SkScalarCos(thetaWidth) * SK_ScalarHalf);
  1293. auto scalar_is_integer = [](SkScalar scalar) -> bool {
  1294. return scalar == SkScalarFloorToScalar(scalar);
  1295. };
  1296. bool expectIntegers = SkScalarNearlyZero(SK_ScalarPI/2 - SkScalarAbs(thetaWidth)) &&
  1297. scalar_is_integer(rx) && scalar_is_integer(ry) &&
  1298. scalar_is_integer(x) && scalar_is_integer(y);
  1299. for (int i = 0; i < segments; ++i) {
  1300. SkScalar endTheta = startTheta + thetaWidth,
  1301. sinEndTheta = SkScalarSinSnapToZero(endTheta),
  1302. cosEndTheta = SkScalarCosSnapToZero(endTheta);
  1303. unitPts[1].set(cosEndTheta, sinEndTheta);
  1304. unitPts[1] += centerPoint;
  1305. unitPts[0] = unitPts[1];
  1306. unitPts[0].offset(t * sinEndTheta, -t * cosEndTheta);
  1307. SkPoint mapped[2];
  1308. pointTransform.mapPoints(mapped, unitPts, (int) SK_ARRAY_COUNT(unitPts));
  1309. /*
  1310. Computing the arc width introduces rounding errors that cause arcs to start
  1311. outside their marks. A round rect may lose convexity as a result. If the input
  1312. values are on integers, place the conic on integers as well.
  1313. */
  1314. if (expectIntegers) {
  1315. SkScalar* mappedScalars = &mapped[0].fX;
  1316. for (unsigned index = 0; index < sizeof(mapped) / sizeof(SkScalar); ++index) {
  1317. mappedScalars[index] = SkScalarRoundToScalar(mappedScalars[index]);
  1318. }
  1319. }
  1320. this->conicTo(mapped[0], mapped[1], w);
  1321. startTheta = endTheta;
  1322. }
  1323. return *this;
  1324. }
  1325. SkPath& SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc,
  1326. SkPath::Direction sweep, SkScalar dx, SkScalar dy) {
  1327. SkPoint currentPoint;
  1328. this->getLastPt(&currentPoint);
  1329. return this->arcTo(rx, ry, xAxisRotate, largeArc, sweep,
  1330. currentPoint.fX + dx, currentPoint.fY + dy);
  1331. }
  1332. SkPath& SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
  1333. if (oval.isEmpty() || 0 == sweepAngle) {
  1334. return *this;
  1335. }
  1336. const SkScalar kFullCircleAngle = SkIntToScalar(360);
  1337. if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
  1338. // We can treat the arc as an oval if it begins at one of our legal starting positions.
  1339. // See SkPath::addOval() docs.
  1340. SkScalar startOver90 = startAngle / 90.f;
  1341. SkScalar startOver90I = SkScalarRoundToScalar(startOver90);
  1342. SkScalar error = startOver90 - startOver90I;
  1343. if (SkScalarNearlyEqual(error, 0)) {
  1344. // Index 1 is at startAngle == 0.
  1345. SkScalar startIndex = std::fmod(startOver90I + 1.f, 4.f);
  1346. startIndex = startIndex < 0 ? startIndex + 4.f : startIndex;
  1347. return this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction,
  1348. (unsigned) startIndex);
  1349. }
  1350. }
  1351. return this->arcTo(oval, startAngle, sweepAngle, true);
  1352. }
  1353. /*
  1354. Need to handle the case when the angle is sharp, and our computed end-points
  1355. for the arc go behind pt1 and/or p2...
  1356. */
  1357. SkPath& SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) {
  1358. if (radius == 0) {
  1359. return this->lineTo(x1, y1);
  1360. }
  1361. // need to know our prev pt so we can construct tangent vectors
  1362. SkPoint start;
  1363. this->getLastPt(&start);
  1364. // need double precision for these calcs.
  1365. SkDVector befored, afterd;
  1366. befored.set({x1 - start.fX, y1 - start.fY}).normalize();
  1367. afterd.set({x2 - x1, y2 - y1}).normalize();
  1368. double cosh = befored.dot(afterd);
  1369. double sinh = befored.cross(afterd);
  1370. if (!befored.isFinite() || !afterd.isFinite() || SkScalarNearlyZero(SkDoubleToScalar(sinh))) {
  1371. return this->lineTo(x1, y1);
  1372. }
  1373. // safe to convert back to floats now
  1374. SkVector before = befored.asSkVector();
  1375. SkVector after = afterd.asSkVector();
  1376. SkScalar dist = SkScalarAbs(SkDoubleToScalar(radius * (1 - cosh) / sinh));
  1377. SkScalar xx = x1 - dist * before.fX;
  1378. SkScalar yy = y1 - dist * before.fY;
  1379. after.setLength(dist);
  1380. this->lineTo(xx, yy);
  1381. SkScalar weight = SkScalarSqrt(SkDoubleToScalar(SK_ScalarHalf + cosh * 0.5));
  1382. return this->conicTo(x1, y1, x1 + after.fX, y1 + after.fY, weight);
  1383. }
  1384. ///////////////////////////////////////////////////////////////////////////////
  1385. SkPath& SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
  1386. SkMatrix matrix;
  1387. matrix.setTranslate(dx, dy);
  1388. return this->addPath(path, matrix, mode);
  1389. }
  1390. SkPath& SkPath::addPath(const SkPath& srcPath, const SkMatrix& matrix, AddPathMode mode) {
  1391. // Detect if we're trying to add ourself
  1392. const SkPath* src = &srcPath;
  1393. SkTLazy<SkPath> tmp;
  1394. if (this == src) {
  1395. src = tmp.set(srcPath);
  1396. }
  1397. SkPathRef::Editor(&fPathRef, src->countVerbs(), src->countPoints());
  1398. RawIter iter(*src);
  1399. SkPoint pts[4];
  1400. Verb verb;
  1401. SkMatrixPriv::MapPtsProc proc = SkMatrixPriv::GetMapPtsProc(matrix);
  1402. bool firstVerb = true;
  1403. while ((verb = iter.next(pts)) != kDone_Verb) {
  1404. switch (verb) {
  1405. case kMove_Verb:
  1406. proc(matrix, &pts[0], &pts[0], 1);
  1407. if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) {
  1408. injectMoveToIfNeeded(); // In case last contour is closed
  1409. SkPoint lastPt;
  1410. // don't add lineTo if it is degenerate
  1411. if (fLastMoveToIndex < 0 || !this->getLastPt(&lastPt) || lastPt != pts[0]) {
  1412. this->lineTo(pts[0]);
  1413. }
  1414. } else {
  1415. this->moveTo(pts[0]);
  1416. }
  1417. break;
  1418. case kLine_Verb:
  1419. proc(matrix, &pts[1], &pts[1], 1);
  1420. this->lineTo(pts[1]);
  1421. break;
  1422. case kQuad_Verb:
  1423. proc(matrix, &pts[1], &pts[1], 2);
  1424. this->quadTo(pts[1], pts[2]);
  1425. break;
  1426. case kConic_Verb:
  1427. proc(matrix, &pts[1], &pts[1], 2);
  1428. this->conicTo(pts[1], pts[2], iter.conicWeight());
  1429. break;
  1430. case kCubic_Verb:
  1431. proc(matrix, &pts[1], &pts[1], 3);
  1432. this->cubicTo(pts[1], pts[2], pts[3]);
  1433. break;
  1434. case kClose_Verb:
  1435. this->close();
  1436. break;
  1437. default:
  1438. SkDEBUGFAIL("unknown verb");
  1439. }
  1440. firstVerb = false;
  1441. }
  1442. return *this;
  1443. }
  1444. ///////////////////////////////////////////////////////////////////////////////
  1445. static int pts_in_verb(unsigned verb) {
  1446. static const uint8_t gPtsInVerb[] = {
  1447. 1, // kMove
  1448. 1, // kLine
  1449. 2, // kQuad
  1450. 2, // kConic
  1451. 3, // kCubic
  1452. 0, // kClose
  1453. 0 // kDone
  1454. };
  1455. SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
  1456. return gPtsInVerb[verb];
  1457. }
  1458. // ignore the last point of the 1st contour
  1459. SkPath& SkPath::reversePathTo(const SkPath& path) {
  1460. const uint8_t* verbs = path.fPathRef->verbsMemBegin(); // points at the last verb
  1461. if (!verbs) { // empty path returns nullptr
  1462. return *this;
  1463. }
  1464. const uint8_t* verbsEnd = path.fPathRef->verbs() - 1; // points just past the first verb
  1465. SkASSERT(verbsEnd[0] == kMove_Verb);
  1466. const SkPoint* pts = path.fPathRef->pointsEnd() - 1;
  1467. const SkScalar* conicWeights = path.fPathRef->conicWeightsEnd();
  1468. while (verbs < verbsEnd) {
  1469. uint8_t v = *verbs++;
  1470. pts -= pts_in_verb(v);
  1471. switch (v) {
  1472. case kMove_Verb:
  1473. // if the path has multiple contours, stop after reversing the last
  1474. return *this;
  1475. case kLine_Verb:
  1476. this->lineTo(pts[0]);
  1477. break;
  1478. case kQuad_Verb:
  1479. this->quadTo(pts[1], pts[0]);
  1480. break;
  1481. case kConic_Verb:
  1482. this->conicTo(pts[1], pts[0], *--conicWeights);
  1483. break;
  1484. case kCubic_Verb:
  1485. this->cubicTo(pts[2], pts[1], pts[0]);
  1486. break;
  1487. case kClose_Verb:
  1488. SkASSERT(verbs - path.fPathRef->verbsMemBegin() == 1);
  1489. break;
  1490. default:
  1491. SkDEBUGFAIL("bad verb");
  1492. break;
  1493. }
  1494. }
  1495. return *this;
  1496. }
  1497. SkPath& SkPath::reverseAddPath(const SkPath& srcPath) {
  1498. // Detect if we're trying to add ourself
  1499. const SkPath* src = &srcPath;
  1500. SkTLazy<SkPath> tmp;
  1501. if (this == src) {
  1502. src = tmp.set(srcPath);
  1503. }
  1504. SkPathRef::Editor ed(&fPathRef, src->countVerbs(), src->countPoints());
  1505. const SkPoint* pts = src->fPathRef->pointsEnd();
  1506. // we will iterate through src's verbs backwards
  1507. const uint8_t* verbs = src->fPathRef->verbsMemBegin(); // points at the last verb
  1508. const uint8_t* verbsEnd = src->fPathRef->verbs(); // points just past the first verb
  1509. const SkScalar* conicWeights = src->fPathRef->conicWeightsEnd();
  1510. bool needMove = true;
  1511. bool needClose = false;
  1512. while (verbs < verbsEnd) {
  1513. uint8_t v = *(verbs++);
  1514. int n = pts_in_verb(v);
  1515. if (needMove) {
  1516. --pts;
  1517. this->moveTo(pts->fX, pts->fY);
  1518. needMove = false;
  1519. }
  1520. pts -= n;
  1521. switch (v) {
  1522. case kMove_Verb:
  1523. if (needClose) {
  1524. this->close();
  1525. needClose = false;
  1526. }
  1527. needMove = true;
  1528. pts += 1; // so we see the point in "if (needMove)" above
  1529. break;
  1530. case kLine_Verb:
  1531. this->lineTo(pts[0]);
  1532. break;
  1533. case kQuad_Verb:
  1534. this->quadTo(pts[1], pts[0]);
  1535. break;
  1536. case kConic_Verb:
  1537. this->conicTo(pts[1], pts[0], *--conicWeights);
  1538. break;
  1539. case kCubic_Verb:
  1540. this->cubicTo(pts[2], pts[1], pts[0]);
  1541. break;
  1542. case kClose_Verb:
  1543. needClose = true;
  1544. break;
  1545. default:
  1546. SkDEBUGFAIL("unexpected verb");
  1547. }
  1548. }
  1549. return *this;
  1550. }
  1551. ///////////////////////////////////////////////////////////////////////////////
  1552. void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
  1553. SkMatrix matrix;
  1554. matrix.setTranslate(dx, dy);
  1555. this->transform(matrix, dst);
  1556. }
  1557. static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
  1558. int level = 2) {
  1559. if (--level >= 0) {
  1560. SkPoint tmp[7];
  1561. SkChopCubicAtHalf(pts, tmp);
  1562. subdivide_cubic_to(path, &tmp[0], level);
  1563. subdivide_cubic_to(path, &tmp[3], level);
  1564. } else {
  1565. path->cubicTo(pts[1], pts[2], pts[3]);
  1566. }
  1567. }
  1568. void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
  1569. if (matrix.isIdentity()) {
  1570. if (dst != nullptr && dst != this) {
  1571. *dst = *this;
  1572. }
  1573. return;
  1574. }
  1575. SkDEBUGCODE(this->validate();)
  1576. if (dst == nullptr) {
  1577. dst = (SkPath*)this;
  1578. }
  1579. if (matrix.hasPerspective()) {
  1580. SkPath tmp;
  1581. tmp.fFillType = fFillType;
  1582. SkPath::Iter iter(*this, false);
  1583. SkPoint pts[4];
  1584. SkPath::Verb verb;
  1585. while ((verb = iter.next(pts, false)) != kDone_Verb) {
  1586. switch (verb) {
  1587. case kMove_Verb:
  1588. tmp.moveTo(pts[0]);
  1589. break;
  1590. case kLine_Verb:
  1591. tmp.lineTo(pts[1]);
  1592. break;
  1593. case kQuad_Verb:
  1594. // promote the quad to a conic
  1595. tmp.conicTo(pts[1], pts[2],
  1596. SkConic::TransformW(pts, SK_Scalar1, matrix));
  1597. break;
  1598. case kConic_Verb:
  1599. tmp.conicTo(pts[1], pts[2],
  1600. SkConic::TransformW(pts, iter.conicWeight(), matrix));
  1601. break;
  1602. case kCubic_Verb:
  1603. subdivide_cubic_to(&tmp, pts);
  1604. break;
  1605. case kClose_Verb:
  1606. tmp.close();
  1607. break;
  1608. default:
  1609. SkDEBUGFAIL("unknown verb");
  1610. break;
  1611. }
  1612. }
  1613. dst->swap(tmp);
  1614. SkPathRef::Editor ed(&dst->fPathRef);
  1615. matrix.mapPoints(ed.points(), ed.pathRef()->countPoints());
  1616. dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
  1617. } else {
  1618. Convexity convexity = this->getConvexityOrUnknown();
  1619. SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
  1620. if (this != dst) {
  1621. dst->fLastMoveToIndex = fLastMoveToIndex;
  1622. dst->fFillType = fFillType;
  1623. dst->fIsVolatile = fIsVolatile;
  1624. }
  1625. // Due to finite/fragile float numerics, we can't assume that a convex path remains
  1626. // convex after a transformation, so mark it as unknown here.
  1627. // However, some transformations are thought to be safe:
  1628. // axis-aligned values under scale/translate.
  1629. //
  1630. // See skbug.com/8606
  1631. // If we can land a robust convex scan-converter, we may be able to relax/remove this
  1632. // check, and keep convex paths marked as such after a general transform...
  1633. //
  1634. if (matrix.isScaleTranslate() && SkPathPriv::IsAxisAligned(*this)) {
  1635. dst->setConvexity(convexity);
  1636. } else {
  1637. dst->setConvexity(kUnknown_Convexity);
  1638. }
  1639. if (this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
  1640. dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
  1641. } else {
  1642. SkScalar det2x2 =
  1643. matrix.get(SkMatrix::kMScaleX) * matrix.get(SkMatrix::kMScaleY) -
  1644. matrix.get(SkMatrix::kMSkewX) * matrix.get(SkMatrix::kMSkewY);
  1645. if (det2x2 < 0) {
  1646. dst->setFirstDirection(
  1647. SkPathPriv::OppositeFirstDirection(
  1648. (SkPathPriv::FirstDirection)this->getFirstDirection()));
  1649. } else if (det2x2 > 0) {
  1650. dst->setFirstDirection(this->getFirstDirection());
  1651. } else {
  1652. dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
  1653. }
  1654. }
  1655. SkDEBUGCODE(dst->validate();)
  1656. }
  1657. }
  1658. ///////////////////////////////////////////////////////////////////////////////
  1659. ///////////////////////////////////////////////////////////////////////////////
  1660. SkPath::Iter::Iter() {
  1661. #ifdef SK_DEBUG
  1662. fPts = nullptr;
  1663. fConicWeights = nullptr;
  1664. fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
  1665. fForceClose = fCloseLine = false;
  1666. fSegmentState = kEmptyContour_SegmentState;
  1667. #endif
  1668. // need to init enough to make next() harmlessly return kDone_Verb
  1669. fVerbs = nullptr;
  1670. fVerbStop = nullptr;
  1671. fNeedClose = false;
  1672. }
  1673. SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
  1674. this->setPath(path, forceClose);
  1675. }
  1676. void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
  1677. fPts = path.fPathRef->points();
  1678. fVerbs = path.fPathRef->verbs();
  1679. fVerbStop = path.fPathRef->verbsMemBegin();
  1680. fConicWeights = path.fPathRef->conicWeights();
  1681. if (fConicWeights) {
  1682. fConicWeights -= 1; // begin one behind
  1683. }
  1684. fLastPt.fX = fLastPt.fY = 0;
  1685. fMoveTo.fX = fMoveTo.fY = 0;
  1686. fForceClose = SkToU8(forceClose);
  1687. fNeedClose = false;
  1688. fSegmentState = kEmptyContour_SegmentState;
  1689. }
  1690. bool SkPath::Iter::isClosedContour() const {
  1691. if (fVerbs == nullptr || fVerbs == fVerbStop) {
  1692. return false;
  1693. }
  1694. if (fForceClose) {
  1695. return true;
  1696. }
  1697. const uint8_t* verbs = fVerbs;
  1698. const uint8_t* stop = fVerbStop;
  1699. if (kMove_Verb == *(verbs - 1)) {
  1700. verbs -= 1; // skip the initial moveto
  1701. }
  1702. while (verbs > stop) {
  1703. // verbs points one beyond the current verb, decrement first.
  1704. unsigned v = *(--verbs);
  1705. if (kMove_Verb == v) {
  1706. break;
  1707. }
  1708. if (kClose_Verb == v) {
  1709. return true;
  1710. }
  1711. }
  1712. return false;
  1713. }
  1714. SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
  1715. SkASSERT(pts);
  1716. if (fLastPt != fMoveTo) {
  1717. // A special case: if both points are NaN, SkPoint::operation== returns
  1718. // false, but the iterator expects that they are treated as the same.
  1719. // (consider SkPoint is a 2-dimension float point).
  1720. if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
  1721. SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
  1722. return kClose_Verb;
  1723. }
  1724. pts[0] = fLastPt;
  1725. pts[1] = fMoveTo;
  1726. fLastPt = fMoveTo;
  1727. fCloseLine = true;
  1728. return kLine_Verb;
  1729. } else {
  1730. pts[0] = fMoveTo;
  1731. return kClose_Verb;
  1732. }
  1733. }
  1734. const SkPoint& SkPath::Iter::cons_moveTo() {
  1735. if (fSegmentState == kAfterMove_SegmentState) {
  1736. // Set the first return pt to the move pt
  1737. fSegmentState = kAfterPrimitive_SegmentState;
  1738. return fMoveTo;
  1739. }
  1740. SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
  1741. // Set the first return pt to the last pt of the previous primitive.
  1742. return fPts[-1];
  1743. }
  1744. void SkPath::Iter::consumeDegenerateSegments(bool exact) {
  1745. // We need to step over anything that will not move the current draw point
  1746. // forward before the next move is seen
  1747. const uint8_t* lastMoveVerb = nullptr;
  1748. const SkPoint* lastMovePt = nullptr;
  1749. const SkScalar* lastMoveWeight = nullptr;
  1750. SkPoint lastPt = fLastPt;
  1751. while (fVerbs != fVerbStop) {
  1752. unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb
  1753. switch (verb) {
  1754. case kMove_Verb:
  1755. // Keep a record of this most recent move
  1756. lastMoveVerb = fVerbs;
  1757. lastMovePt = fPts;
  1758. lastMoveWeight = fConicWeights;
  1759. lastPt = fPts[0];
  1760. fVerbs--;
  1761. fPts++;
  1762. break;
  1763. case kClose_Verb:
  1764. // A close when we are in a segment is always valid except when it
  1765. // follows a move which follows a segment.
  1766. if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) {
  1767. return;
  1768. }
  1769. // A close at any other time must be ignored
  1770. fVerbs--;
  1771. break;
  1772. case kLine_Verb:
  1773. if (!IsLineDegenerate(lastPt, fPts[0], exact)) {
  1774. if (lastMoveVerb) {
  1775. fVerbs = lastMoveVerb;
  1776. fPts = lastMovePt;
  1777. fConicWeights = lastMoveWeight;
  1778. return;
  1779. }
  1780. return;
  1781. }
  1782. // Ignore this line and continue
  1783. fVerbs--;
  1784. fPts++;
  1785. break;
  1786. case kConic_Verb:
  1787. case kQuad_Verb:
  1788. if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1], exact)) {
  1789. if (lastMoveVerb) {
  1790. fVerbs = lastMoveVerb;
  1791. fPts = lastMovePt;
  1792. fConicWeights = lastMoveWeight;
  1793. return;
  1794. }
  1795. return;
  1796. }
  1797. // Ignore this line and continue
  1798. fVerbs--;
  1799. fPts += 2;
  1800. fConicWeights += (kConic_Verb == verb);
  1801. break;
  1802. case kCubic_Verb:
  1803. if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2], exact)) {
  1804. if (lastMoveVerb) {
  1805. fVerbs = lastMoveVerb;
  1806. fPts = lastMovePt;
  1807. fConicWeights = lastMoveWeight;
  1808. return;
  1809. }
  1810. return;
  1811. }
  1812. // Ignore this line and continue
  1813. fVerbs--;
  1814. fPts += 3;
  1815. break;
  1816. default:
  1817. SkDEBUGFAIL("Should never see kDone_Verb");
  1818. }
  1819. }
  1820. }
  1821. SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
  1822. SkASSERT(ptsParam);
  1823. if (fVerbs == fVerbStop) {
  1824. // Close the curve if requested and if there is some curve to close
  1825. if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
  1826. if (kLine_Verb == this->autoClose(ptsParam)) {
  1827. return kLine_Verb;
  1828. }
  1829. fNeedClose = false;
  1830. return kClose_Verb;
  1831. }
  1832. return kDone_Verb;
  1833. }
  1834. // fVerbs is one beyond the current verb, decrement first
  1835. unsigned verb = *(--fVerbs);
  1836. const SkPoint* SK_RESTRICT srcPts = fPts;
  1837. SkPoint* SK_RESTRICT pts = ptsParam;
  1838. switch (verb) {
  1839. case kMove_Verb:
  1840. if (fNeedClose) {
  1841. fVerbs++; // move back one verb
  1842. verb = this->autoClose(pts);
  1843. if (verb == kClose_Verb) {
  1844. fNeedClose = false;
  1845. }
  1846. return (Verb)verb;
  1847. }
  1848. if (fVerbs == fVerbStop) { // might be a trailing moveto
  1849. return kDone_Verb;
  1850. }
  1851. fMoveTo = *srcPts;
  1852. pts[0] = *srcPts;
  1853. srcPts += 1;
  1854. fSegmentState = kAfterMove_SegmentState;
  1855. fLastPt = fMoveTo;
  1856. fNeedClose = fForceClose;
  1857. break;
  1858. case kLine_Verb:
  1859. pts[0] = this->cons_moveTo();
  1860. pts[1] = srcPts[0];
  1861. fLastPt = srcPts[0];
  1862. fCloseLine = false;
  1863. srcPts += 1;
  1864. break;
  1865. case kConic_Verb:
  1866. fConicWeights += 1;
  1867. // fall-through
  1868. case kQuad_Verb:
  1869. pts[0] = this->cons_moveTo();
  1870. memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
  1871. fLastPt = srcPts[1];
  1872. srcPts += 2;
  1873. break;
  1874. case kCubic_Verb:
  1875. pts[0] = this->cons_moveTo();
  1876. memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
  1877. fLastPt = srcPts[2];
  1878. srcPts += 3;
  1879. break;
  1880. case kClose_Verb:
  1881. verb = this->autoClose(pts);
  1882. if (verb == kLine_Verb) {
  1883. fVerbs++; // move back one verb
  1884. } else {
  1885. fNeedClose = false;
  1886. fSegmentState = kEmptyContour_SegmentState;
  1887. }
  1888. fLastPt = fMoveTo;
  1889. break;
  1890. }
  1891. fPts = srcPts;
  1892. return (Verb)verb;
  1893. }
  1894. ///////////////////////////////////////////////////////////////////////////////
  1895. #include "include/core/SkStream.h"
  1896. #include "include/core/SkString.h"
  1897. #include "src/core/SkStringUtils.h"
  1898. static void append_params(SkString* str, const char label[], const SkPoint pts[],
  1899. int count, SkScalarAsStringType strType, SkScalar conicWeight = -12345) {
  1900. str->append(label);
  1901. str->append("(");
  1902. const SkScalar* values = &pts[0].fX;
  1903. count *= 2;
  1904. for (int i = 0; i < count; ++i) {
  1905. SkAppendScalar(str, values[i], strType);
  1906. if (i < count - 1) {
  1907. str->append(", ");
  1908. }
  1909. }
  1910. if (conicWeight != -12345) {
  1911. str->append(", ");
  1912. SkAppendScalar(str, conicWeight, strType);
  1913. }
  1914. str->append(");");
  1915. if (kHex_SkScalarAsStringType == strType) {
  1916. str->append(" // ");
  1917. for (int i = 0; i < count; ++i) {
  1918. SkAppendScalarDec(str, values[i]);
  1919. if (i < count - 1) {
  1920. str->append(", ");
  1921. }
  1922. }
  1923. if (conicWeight >= 0) {
  1924. str->append(", ");
  1925. SkAppendScalarDec(str, conicWeight);
  1926. }
  1927. }
  1928. str->append("\n");
  1929. }
  1930. void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
  1931. SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
  1932. Iter iter(*this, forceClose);
  1933. SkPoint pts[4];
  1934. Verb verb;
  1935. SkString builder;
  1936. char const * const gFillTypeStrs[] = {
  1937. "Winding",
  1938. "EvenOdd",
  1939. "InverseWinding",
  1940. "InverseEvenOdd",
  1941. };
  1942. builder.printf("path.setFillType(SkPath::k%s_FillType);\n",
  1943. gFillTypeStrs[(int) this->getFillType()]);
  1944. while ((verb = iter.next(pts, false)) != kDone_Verb) {
  1945. switch (verb) {
  1946. case kMove_Verb:
  1947. append_params(&builder, "path.moveTo", &pts[0], 1, asType);
  1948. break;
  1949. case kLine_Verb:
  1950. append_params(&builder, "path.lineTo", &pts[1], 1, asType);
  1951. break;
  1952. case kQuad_Verb:
  1953. append_params(&builder, "path.quadTo", &pts[1], 2, asType);
  1954. break;
  1955. case kConic_Verb:
  1956. append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight());
  1957. break;
  1958. case kCubic_Verb:
  1959. append_params(&builder, "path.cubicTo", &pts[1], 3, asType);
  1960. break;
  1961. case kClose_Verb:
  1962. builder.append("path.close();\n");
  1963. break;
  1964. default:
  1965. SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb);
  1966. verb = kDone_Verb; // stop the loop
  1967. break;
  1968. }
  1969. if (!wStream && builder.size()) {
  1970. SkDebugf("%s", builder.c_str());
  1971. builder.reset();
  1972. }
  1973. }
  1974. if (wStream) {
  1975. wStream->writeText(builder.c_str());
  1976. }
  1977. }
  1978. void SkPath::dump() const {
  1979. this->dump(nullptr, false, false);
  1980. }
  1981. void SkPath::dumpHex() const {
  1982. this->dump(nullptr, false, true);
  1983. }
  1984. bool SkPath::isValidImpl() const {
  1985. if ((fFillType & ~3) != 0) {
  1986. return false;
  1987. }
  1988. #ifdef SK_DEBUG_PATH
  1989. if (!fBoundsIsDirty) {
  1990. SkRect bounds;
  1991. bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
  1992. if (SkToBool(fIsFinite) != isFinite) {
  1993. return false;
  1994. }
  1995. if (fPathRef->countPoints() <= 1) {
  1996. // if we're empty, fBounds may be empty but translated, so we can't
  1997. // necessarily compare to bounds directly
  1998. // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
  1999. // be [2, 2, 2, 2]
  2000. if (!bounds.isEmpty() || !fBounds.isEmpty()) {
  2001. return false;
  2002. }
  2003. } else {
  2004. if (bounds.isEmpty()) {
  2005. if (!fBounds.isEmpty()) {
  2006. return false;
  2007. }
  2008. } else {
  2009. if (!fBounds.isEmpty()) {
  2010. if (!fBounds.contains(bounds)) {
  2011. return false;
  2012. }
  2013. }
  2014. }
  2015. }
  2016. }
  2017. #endif // SK_DEBUG_PATH
  2018. return true;
  2019. }
  2020. ///////////////////////////////////////////////////////////////////////////////
  2021. #ifdef SK_LEGACY_PATH_CONVEXITY // for rebaselining Chrome
  2022. static int sign(SkScalar x) { return x < 0; }
  2023. #define kValueNeverReturnedBySign 2
  2024. enum DirChange {
  2025. kLeft_DirChange,
  2026. kRight_DirChange,
  2027. kStraight_DirChange,
  2028. kBackwards_DirChange,
  2029. kInvalid_DirChange
  2030. };
  2031. static bool almost_equal(SkScalar compA, SkScalar compB) {
  2032. // The error epsilon was empirically derived; worse case round rects
  2033. // with a mid point outset by 2x float epsilon in tests had an error
  2034. // of 12.
  2035. const int epsilon = 16;
  2036. if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
  2037. return false;
  2038. }
  2039. // no need to check for small numbers because SkPath::Iter has removed degenerate values
  2040. int aBits = SkFloatAs2sCompliment(compA);
  2041. int bBits = SkFloatAs2sCompliment(compB);
  2042. return aBits < bBits + epsilon && bBits < aBits + epsilon;
  2043. }
  2044. // only valid for a single contour
  2045. struct Convexicator {
  2046. Convexicator()
  2047. : fPtCount(0)
  2048. , fConvexity(SkPath::kConvex_Convexity)
  2049. , fFirstDirection(SkPathPriv::kUnknown_FirstDirection)
  2050. , fIsFinite(true)
  2051. , fIsCurve(false)
  2052. , fBackwards(false) {
  2053. fExpectedDir = kInvalid_DirChange;
  2054. // warnings
  2055. fPriorPt.set(0,0);
  2056. fLastPt.set(0, 0);
  2057. fCurrPt.set(0, 0);
  2058. fLastVec.set(0, 0);
  2059. fFirstVec.set(0, 0);
  2060. fDx = fDy = 0;
  2061. fSx = fSy = kValueNeverReturnedBySign;
  2062. }
  2063. SkPath::Convexity getConvexity() const { return fConvexity; }
  2064. /** The direction returned is only valid if the path is determined convex */
  2065. SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; }
  2066. void addPt(const SkPoint& pt) {
  2067. if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) {
  2068. return;
  2069. }
  2070. if (0 == fPtCount) {
  2071. fCurrPt = pt;
  2072. ++fPtCount;
  2073. } else {
  2074. SkVector vec = pt - fCurrPt;
  2075. SkScalar lengthSqd = SkPointPriv::LengthSqd(vec);
  2076. if (!SkScalarIsFinite(lengthSqd)) {
  2077. fIsFinite = false;
  2078. } else if (lengthSqd) {
  2079. fPriorPt = fLastPt;
  2080. fLastPt = fCurrPt;
  2081. fCurrPt = pt;
  2082. if (++fPtCount == 2) {
  2083. fFirstVec = fLastVec = vec;
  2084. } else {
  2085. SkASSERT(fPtCount > 2);
  2086. this->addVec(vec);
  2087. }
  2088. int sx = sign(vec.fX);
  2089. int sy = sign(vec.fY);
  2090. fDx += (sx != fSx);
  2091. fDy += (sy != fSy);
  2092. fSx = sx;
  2093. fSy = sy;
  2094. if (fDx > 3 || fDy > 3) {
  2095. fConvexity = SkPath::kConcave_Convexity;
  2096. }
  2097. }
  2098. }
  2099. }
  2100. void close() {
  2101. if (fPtCount > 2) {
  2102. this->addVec(fFirstVec);
  2103. }
  2104. }
  2105. DirChange directionChange(const SkVector& curVec) {
  2106. SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
  2107. SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
  2108. SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
  2109. largest = SkTMax(largest, -smallest);
  2110. if (!almost_equal(largest, largest + cross)) {
  2111. int sign = SkScalarSignAsInt(cross);
  2112. if (sign) {
  2113. return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
  2114. }
  2115. }
  2116. if (cross) {
  2117. double dLastVecX = SkScalarToDouble(fLastPt.fX) - SkScalarToDouble(fPriorPt.fX);
  2118. double dLastVecY = SkScalarToDouble(fLastPt.fY) - SkScalarToDouble(fPriorPt.fY);
  2119. double dCurrVecX = SkScalarToDouble(fCurrPt.fX) - SkScalarToDouble(fLastPt.fX);
  2120. double dCurrVecY = SkScalarToDouble(fCurrPt.fY) - SkScalarToDouble(fLastPt.fY);
  2121. double dCross = dLastVecX * dCurrVecY - dLastVecY * dCurrVecX;
  2122. if (!approximately_zero_when_compared_to(dCross, SkScalarToDouble(largest))) {
  2123. int sign = SkScalarSignAsInt(SkDoubleToScalar(dCross));
  2124. if (sign) {
  2125. return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
  2126. }
  2127. }
  2128. }
  2129. if (!SkScalarNearlyZero(SkPointPriv::LengthSqd(fLastVec),
  2130. SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
  2131. !SkScalarNearlyZero(SkPointPriv::LengthSqd(curVec),
  2132. SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
  2133. fLastVec.dot(curVec) < 0.0f) {
  2134. return kBackwards_DirChange;
  2135. }
  2136. return kStraight_DirChange;
  2137. }
  2138. bool hasBackwards() const {
  2139. return fBackwards;
  2140. }
  2141. bool isFinite() const {
  2142. return fIsFinite;
  2143. }
  2144. void setCurve(bool isCurve) {
  2145. fIsCurve = isCurve;
  2146. }
  2147. private:
  2148. void addVec(const SkVector& vec) {
  2149. SkASSERT(vec.fX || vec.fY);
  2150. DirChange dir = this->directionChange(vec);
  2151. switch (dir) {
  2152. case kLeft_DirChange: // fall through
  2153. case kRight_DirChange:
  2154. if (kInvalid_DirChange == fExpectedDir) {
  2155. fExpectedDir = dir;
  2156. fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection
  2157. : SkPathPriv::kCCW_FirstDirection;
  2158. } else if (dir != fExpectedDir) {
  2159. fConvexity = SkPath::kConcave_Convexity;
  2160. fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
  2161. }
  2162. fLastVec = vec;
  2163. break;
  2164. case kStraight_DirChange:
  2165. break;
  2166. case kBackwards_DirChange:
  2167. if (fIsCurve) {
  2168. // If any of the subsequent dir is non-backward, it'll be concave.
  2169. // Otherwise, it's still convex.
  2170. fExpectedDir = dir;
  2171. }
  2172. fLastVec = vec;
  2173. fBackwards = true;
  2174. break;
  2175. case kInvalid_DirChange:
  2176. SK_ABORT("Use of invalid direction change flag");
  2177. break;
  2178. }
  2179. }
  2180. SkPoint fPriorPt;
  2181. SkPoint fLastPt;
  2182. SkPoint fCurrPt;
  2183. // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product
  2184. // value with the current vec is deemed to be of a significant value.
  2185. SkVector fLastVec, fFirstVec;
  2186. int fPtCount; // non-degenerate points
  2187. DirChange fExpectedDir;
  2188. SkPath::Convexity fConvexity;
  2189. SkPathPriv::FirstDirection fFirstDirection;
  2190. int fDx, fDy, fSx, fSy;
  2191. bool fIsFinite;
  2192. bool fIsCurve;
  2193. bool fBackwards;
  2194. };
  2195. SkPath::Convexity SkPath::internalGetConvexity() const {
  2196. // Sometimes we think we need to calculate convexity but another thread already did.
  2197. auto c = this->getConvexityOrUnknown();
  2198. if (c != kUnknown_Convexity) {
  2199. return c;
  2200. }
  2201. SkPoint pts[4];
  2202. SkPath::Verb verb;
  2203. SkPath::Iter iter(*this, true);
  2204. int contourCount = 0;
  2205. int count;
  2206. Convexicator state;
  2207. if (!isFinite()) {
  2208. return kUnknown_Convexity;
  2209. }
  2210. while ((verb = iter.next(pts, false, false)) != SkPath::kDone_Verb) {
  2211. switch (verb) {
  2212. case kMove_Verb:
  2213. if (++contourCount > 1) {
  2214. this->setConvexity(kConcave_Convexity);
  2215. return kConcave_Convexity;
  2216. }
  2217. pts[1] = pts[0];
  2218. // fall through
  2219. case kLine_Verb:
  2220. count = 1;
  2221. state.setCurve(false);
  2222. break;
  2223. case kQuad_Verb:
  2224. // fall through
  2225. case kConic_Verb:
  2226. // fall through
  2227. case kCubic_Verb:
  2228. count = 2 + (kCubic_Verb == verb);
  2229. // As an additional enhancement, this could set curve true only
  2230. // if the curve is nonlinear
  2231. state.setCurve(true);
  2232. break;
  2233. case kClose_Verb:
  2234. state.setCurve(false);
  2235. state.close();
  2236. count = 0;
  2237. break;
  2238. default:
  2239. SkDEBUGFAIL("bad verb");
  2240. this->setConvexity(kConcave_Convexity);
  2241. return kConcave_Convexity;
  2242. }
  2243. for (int i = 1; i <= count; i++) {
  2244. state.addPt(pts[i]);
  2245. }
  2246. // early exit
  2247. if (!state.isFinite()) {
  2248. return kUnknown_Convexity;
  2249. }
  2250. if (kConcave_Convexity == state.getConvexity()) {
  2251. this->setConvexity(kConcave_Convexity);
  2252. return kConcave_Convexity;
  2253. }
  2254. }
  2255. this->setConvexity(state.getConvexity());
  2256. if (this->getConvexityOrUnknown() == kConvex_Convexity &&
  2257. this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
  2258. if (state.getFirstDirection() == SkPathPriv::kUnknown_FirstDirection
  2259. && !this->getBounds().isEmpty()
  2260. && !state.hasBackwards()) {
  2261. this->setConvexity(Convexity::kConcave_Convexity);
  2262. } else {
  2263. this->setFirstDirection(state.getFirstDirection());
  2264. }
  2265. }
  2266. return this->getConvexityOrUnknown();
  2267. }
  2268. #else
  2269. static int sign(SkScalar x) { return x < 0; }
  2270. #define kValueNeverReturnedBySign 2
  2271. enum DirChange {
  2272. kUnknown_DirChange,
  2273. kLeft_DirChange,
  2274. kRight_DirChange,
  2275. kStraight_DirChange,
  2276. kBackwards_DirChange, // if double back, allow simple lines to be convex
  2277. kInvalid_DirChange
  2278. };
  2279. static bool almost_equal(SkScalar compA, SkScalar compB) {
  2280. // The error epsilon was empirically derived; worse case round rects
  2281. // with a mid point outset by 2x float epsilon in tests had an error
  2282. // of 12.
  2283. const int epsilon = 16;
  2284. if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
  2285. return false;
  2286. }
  2287. // no need to check for small numbers because SkPath::Iter has removed degenerate values
  2288. int aBits = SkFloatAs2sCompliment(compA);
  2289. int bBits = SkFloatAs2sCompliment(compB);
  2290. return aBits < bBits + epsilon && bBits < aBits + epsilon;
  2291. }
  2292. // only valid for a single contour
  2293. struct Convexicator {
  2294. /** The direction returned is only valid if the path is determined convex */
  2295. SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; }
  2296. void setMovePt(const SkPoint& pt) {
  2297. fPriorPt = fLastPt = fCurrPt = pt;
  2298. }
  2299. bool addPt(const SkPoint& pt) {
  2300. if (fCurrPt == pt) {
  2301. return true;
  2302. }
  2303. fCurrPt = pt;
  2304. if (fPriorPt == fLastPt) { // should only be true for first non-zero vector
  2305. fLastVec = fCurrPt - fLastPt;
  2306. fFirstPt = pt;
  2307. } else if (!this->addVec(fCurrPt - fLastPt)) {
  2308. return false;
  2309. }
  2310. fPriorPt = fLastPt;
  2311. fLastPt = fCurrPt;
  2312. return true;
  2313. }
  2314. static SkPath::Convexity BySign(const SkPoint points[], int count) {
  2315. const SkPoint* last = points + count;
  2316. SkPoint currPt = *points++;
  2317. SkPoint firstPt = currPt;
  2318. int dxes = 0;
  2319. int dyes = 0;
  2320. int lastSx = kValueNeverReturnedBySign;
  2321. int lastSy = kValueNeverReturnedBySign;
  2322. for (int outerLoop = 0; outerLoop < 2; ++outerLoop ) {
  2323. while (points != last) {
  2324. SkVector vec = *points - currPt;
  2325. if (!vec.isZero()) {
  2326. // give up if vector construction failed
  2327. if (!vec.isFinite()) {
  2328. return SkPath::kUnknown_Convexity;
  2329. }
  2330. int sx = sign(vec.fX);
  2331. int sy = sign(vec.fY);
  2332. dxes += (sx != lastSx);
  2333. dyes += (sy != lastSy);
  2334. if (dxes > 3 || dyes > 3) {
  2335. return SkPath::kConcave_Convexity;
  2336. }
  2337. lastSx = sx;
  2338. lastSy = sy;
  2339. }
  2340. currPt = *points++;
  2341. if (outerLoop) {
  2342. break;
  2343. }
  2344. }
  2345. points = &firstPt;
  2346. }
  2347. return SkPath::kConvex_Convexity; // that is, it may be convex, don't know yet
  2348. }
  2349. bool close() {
  2350. return this->addPt(fFirstPt);
  2351. }
  2352. bool isFinite() const {
  2353. return fIsFinite;
  2354. }
  2355. int reversals() const {
  2356. return fReversals;
  2357. }
  2358. private:
  2359. DirChange directionChange(const SkVector& curVec) {
  2360. SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
  2361. if (!SkScalarIsFinite(cross)) {
  2362. return kUnknown_DirChange;
  2363. }
  2364. SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
  2365. SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
  2366. largest = SkTMax(largest, -smallest);
  2367. if (almost_equal(largest, largest + cross)) {
  2368. return fLastVec.dot(curVec) < 0 ? kBackwards_DirChange : kStraight_DirChange;
  2369. }
  2370. return 1 == SkScalarSignAsInt(cross) ? kRight_DirChange : kLeft_DirChange;
  2371. }
  2372. bool addVec(const SkVector& curVec) {
  2373. DirChange dir = this->directionChange(curVec);
  2374. switch (dir) {
  2375. case kLeft_DirChange: // fall through
  2376. case kRight_DirChange:
  2377. if (kInvalid_DirChange == fExpectedDir) {
  2378. fExpectedDir = dir;
  2379. fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection
  2380. : SkPathPriv::kCCW_FirstDirection;
  2381. } else if (dir != fExpectedDir) {
  2382. fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
  2383. return false;
  2384. }
  2385. fLastVec = curVec;
  2386. break;
  2387. case kStraight_DirChange:
  2388. break;
  2389. case kBackwards_DirChange:
  2390. // allow path to reverse direction twice
  2391. // Given path.moveTo(0, 0); path.lineTo(1, 1);
  2392. // - 1st reversal: direction change formed by line (0,0 1,1), line (1,1 0,0)
  2393. // - 2nd reversal: direction change formed by line (1,1 0,0), line (0,0 1,1)
  2394. fLastVec = curVec;
  2395. return ++fReversals < 3;
  2396. case kUnknown_DirChange:
  2397. return (fIsFinite = false);
  2398. case kInvalid_DirChange:
  2399. SK_ABORT("Use of invalid direction change flag");
  2400. break;
  2401. }
  2402. return true;
  2403. }
  2404. SkPoint fFirstPt {0, 0};
  2405. SkPoint fPriorPt {0, 0};
  2406. SkPoint fLastPt {0, 0};
  2407. SkPoint fCurrPt {0, 0};
  2408. SkVector fLastVec {0, 0};
  2409. DirChange fExpectedDir { kInvalid_DirChange };
  2410. SkPathPriv::FirstDirection fFirstDirection { SkPathPriv::kUnknown_FirstDirection };
  2411. int fReversals { 0 };
  2412. bool fIsFinite { true };
  2413. };
  2414. SkPath::Convexity SkPath::internalGetConvexity() const {
  2415. SkPoint pts[4];
  2416. SkPath::Verb verb;
  2417. SkPath::Iter iter(*this, true);
  2418. auto setComputedConvexity = [=](Convexity convexity){
  2419. SkASSERT(kUnknown_Convexity != convexity);
  2420. this->setConvexity(convexity);
  2421. return convexity;
  2422. };
  2423. // Check to see if path changes direction more than three times as quick concave test
  2424. int pointCount = this->countPoints();
  2425. // last moveTo index may exceed point count if data comes from fuzzer (via SkImageFilter)
  2426. if (0 < fLastMoveToIndex && fLastMoveToIndex < pointCount) {
  2427. pointCount = fLastMoveToIndex;
  2428. }
  2429. if (pointCount > 3) {
  2430. const SkPoint* points = fPathRef->points();
  2431. const SkPoint* last = &points[pointCount];
  2432. // only consider the last of the initial move tos
  2433. while (SkPath::kMove_Verb == iter.next(pts, false, false)) {
  2434. ++points;
  2435. }
  2436. --points;
  2437. SkPath::Convexity convexity = Convexicator::BySign(points, (int) (last - points));
  2438. if (SkPath::kConcave_Convexity == convexity) {
  2439. return setComputedConvexity(SkPath::kConcave_Convexity);
  2440. } else if (SkPath::kUnknown_Convexity == convexity) {
  2441. return SkPath::kUnknown_Convexity;
  2442. }
  2443. iter.setPath(*this, true);
  2444. } else if (!this->isFinite()) {
  2445. return kUnknown_Convexity;
  2446. }
  2447. int contourCount = 0;
  2448. int count;
  2449. Convexicator state;
  2450. auto setFail = [=](){
  2451. if (!state.isFinite()) {
  2452. return SkPath::kUnknown_Convexity;
  2453. }
  2454. return setComputedConvexity(SkPath::kConcave_Convexity);
  2455. };
  2456. while ((verb = iter.next(pts, false, false)) != SkPath::kDone_Verb) {
  2457. switch (verb) {
  2458. case kMove_Verb:
  2459. if (++contourCount > 1) {
  2460. return setComputedConvexity(kConcave_Convexity);
  2461. }
  2462. state.setMovePt(pts[0]);
  2463. count = 0;
  2464. break;
  2465. case kLine_Verb:
  2466. count = 1;
  2467. break;
  2468. case kQuad_Verb:
  2469. // fall through
  2470. case kConic_Verb:
  2471. count = 2;
  2472. break;
  2473. case kCubic_Verb:
  2474. count = 3;
  2475. break;
  2476. case kClose_Verb:
  2477. if (!state.close()) {
  2478. return setFail();
  2479. }
  2480. count = 0;
  2481. break;
  2482. default:
  2483. SkDEBUGFAIL("bad verb");
  2484. return setComputedConvexity(kConcave_Convexity);
  2485. }
  2486. for (int i = 1; i <= count; i++) {
  2487. if (!state.addPt(pts[i])) {
  2488. return setFail();
  2489. }
  2490. }
  2491. }
  2492. if (this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
  2493. if (state.getFirstDirection() == SkPathPriv::kUnknown_FirstDirection
  2494. && !this->getBounds().isEmpty()) {
  2495. return setComputedConvexity(state.reversals() < 3 ?
  2496. kConvex_Convexity : kConcave_Convexity);
  2497. }
  2498. this->setFirstDirection(state.getFirstDirection());
  2499. }
  2500. return setComputedConvexity(kConvex_Convexity);
  2501. }
  2502. bool SkPathPriv::IsConvex(const SkPoint points[], int count) {
  2503. SkPath::Convexity convexity = Convexicator::BySign(points, count);
  2504. if (SkPath::kConvex_Convexity != convexity) {
  2505. return false;
  2506. }
  2507. Convexicator state;
  2508. state.setMovePt(points[0]);
  2509. for (int i = 1; i < count; i++) {
  2510. if (!state.addPt(points[i])) {
  2511. return false;
  2512. }
  2513. }
  2514. if (!state.addPt(points[0])) {
  2515. return false;
  2516. }
  2517. if (!state.close()) {
  2518. return false;
  2519. }
  2520. return state.getFirstDirection() != SkPathPriv::kUnknown_FirstDirection
  2521. || state.reversals() < 3;
  2522. }
  2523. #endif
  2524. ///////////////////////////////////////////////////////////////////////////////
  2525. class ContourIter {
  2526. public:
  2527. ContourIter(const SkPathRef& pathRef);
  2528. bool done() const { return fDone; }
  2529. // if !done() then these may be called
  2530. int count() const { return fCurrPtCount; }
  2531. const SkPoint* pts() const { return fCurrPt; }
  2532. void next();
  2533. private:
  2534. int fCurrPtCount;
  2535. const SkPoint* fCurrPt;
  2536. const uint8_t* fCurrVerb;
  2537. const uint8_t* fStopVerbs;
  2538. const SkScalar* fCurrConicWeight;
  2539. bool fDone;
  2540. SkDEBUGCODE(int fContourCounter;)
  2541. };
  2542. ContourIter::ContourIter(const SkPathRef& pathRef) {
  2543. fStopVerbs = pathRef.verbsMemBegin();
  2544. fDone = false;
  2545. fCurrPt = pathRef.points();
  2546. fCurrVerb = pathRef.verbs();
  2547. fCurrConicWeight = pathRef.conicWeights();
  2548. fCurrPtCount = 0;
  2549. SkDEBUGCODE(fContourCounter = 0;)
  2550. this->next();
  2551. }
  2552. void ContourIter::next() {
  2553. if (fCurrVerb <= fStopVerbs) {
  2554. fDone = true;
  2555. }
  2556. if (fDone) {
  2557. return;
  2558. }
  2559. // skip pts of prev contour
  2560. fCurrPt += fCurrPtCount;
  2561. SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
  2562. int ptCount = 1; // moveTo
  2563. const uint8_t* verbs = fCurrVerb;
  2564. for (--verbs; verbs > fStopVerbs; --verbs) {
  2565. switch (verbs[~0]) {
  2566. case SkPath::kMove_Verb:
  2567. goto CONTOUR_END;
  2568. case SkPath::kLine_Verb:
  2569. ptCount += 1;
  2570. break;
  2571. case SkPath::kConic_Verb:
  2572. fCurrConicWeight += 1;
  2573. // fall-through
  2574. case SkPath::kQuad_Verb:
  2575. ptCount += 2;
  2576. break;
  2577. case SkPath::kCubic_Verb:
  2578. ptCount += 3;
  2579. break;
  2580. case SkPath::kClose_Verb:
  2581. break;
  2582. default:
  2583. SkDEBUGFAIL("unexpected verb");
  2584. break;
  2585. }
  2586. }
  2587. CONTOUR_END:
  2588. fCurrPtCount = ptCount;
  2589. fCurrVerb = verbs;
  2590. SkDEBUGCODE(++fContourCounter;)
  2591. }
  2592. // returns cross product of (p1 - p0) and (p2 - p0)
  2593. static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
  2594. SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
  2595. // We may get 0 when the above subtracts underflow. We expect this to be
  2596. // very rare and lazily promote to double.
  2597. if (0 == cross) {
  2598. double p0x = SkScalarToDouble(p0.fX);
  2599. double p0y = SkScalarToDouble(p0.fY);
  2600. double p1x = SkScalarToDouble(p1.fX);
  2601. double p1y = SkScalarToDouble(p1.fY);
  2602. double p2x = SkScalarToDouble(p2.fX);
  2603. double p2y = SkScalarToDouble(p2.fY);
  2604. cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
  2605. (p1y - p0y) * (p2x - p0x));
  2606. }
  2607. return cross;
  2608. }
  2609. // Returns the first pt with the maximum Y coordinate
  2610. static int find_max_y(const SkPoint pts[], int count) {
  2611. SkASSERT(count > 0);
  2612. SkScalar max = pts[0].fY;
  2613. int firstIndex = 0;
  2614. for (int i = 1; i < count; ++i) {
  2615. SkScalar y = pts[i].fY;
  2616. if (y > max) {
  2617. max = y;
  2618. firstIndex = i;
  2619. }
  2620. }
  2621. return firstIndex;
  2622. }
  2623. static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
  2624. int i = index;
  2625. for (;;) {
  2626. i = (i + inc) % n;
  2627. if (i == index) { // we wrapped around, so abort
  2628. break;
  2629. }
  2630. if (pts[index] != pts[i]) { // found a different point, success!
  2631. break;
  2632. }
  2633. }
  2634. return i;
  2635. }
  2636. /**
  2637. * Starting at index, and moving forward (incrementing), find the xmin and
  2638. * xmax of the contiguous points that have the same Y.
  2639. */
  2640. static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
  2641. int* maxIndexPtr) {
  2642. const SkScalar y = pts[index].fY;
  2643. SkScalar min = pts[index].fX;
  2644. SkScalar max = min;
  2645. int minIndex = index;
  2646. int maxIndex = index;
  2647. for (int i = index + 1; i < n; ++i) {
  2648. if (pts[i].fY != y) {
  2649. break;
  2650. }
  2651. SkScalar x = pts[i].fX;
  2652. if (x < min) {
  2653. min = x;
  2654. minIndex = i;
  2655. } else if (x > max) {
  2656. max = x;
  2657. maxIndex = i;
  2658. }
  2659. }
  2660. *maxIndexPtr = maxIndex;
  2661. return minIndex;
  2662. }
  2663. static void crossToDir(SkScalar cross, SkPathPriv::FirstDirection* dir) {
  2664. *dir = cross > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
  2665. }
  2666. /*
  2667. * We loop through all contours, and keep the computed cross-product of the
  2668. * contour that contained the global y-max. If we just look at the first
  2669. * contour, we may find one that is wound the opposite way (correctly) since
  2670. * it is the interior of a hole (e.g. 'o'). Thus we must find the contour
  2671. * that is outer most (or at least has the global y-max) before we can consider
  2672. * its cross product.
  2673. */
  2674. bool SkPathPriv::CheapComputeFirstDirection(const SkPath& path, FirstDirection* dir) {
  2675. auto d = path.getFirstDirection();
  2676. if (d != kUnknown_FirstDirection) {
  2677. *dir = static_cast<FirstDirection>(d);
  2678. return true;
  2679. }
  2680. // We don't want to pay the cost for computing convexity if it is unknown,
  2681. // so we call getConvexityOrUnknown() instead of isConvex().
  2682. if (path.getConvexityOrUnknown() == SkPath::kConvex_Convexity) {
  2683. SkASSERT(path.getFirstDirection() == kUnknown_FirstDirection);
  2684. *dir = static_cast<FirstDirection>(path.getFirstDirection());
  2685. return false;
  2686. }
  2687. ContourIter iter(*path.fPathRef.get());
  2688. // initialize with our logical y-min
  2689. SkScalar ymax = path.getBounds().fTop;
  2690. SkScalar ymaxCross = 0;
  2691. for (; !iter.done(); iter.next()) {
  2692. int n = iter.count();
  2693. if (n < 3) {
  2694. continue;
  2695. }
  2696. const SkPoint* pts = iter.pts();
  2697. SkScalar cross = 0;
  2698. int index = find_max_y(pts, n);
  2699. if (pts[index].fY < ymax) {
  2700. continue;
  2701. }
  2702. // If there is more than 1 distinct point at the y-max, we take the
  2703. // x-min and x-max of them and just subtract to compute the dir.
  2704. if (pts[(index + 1) % n].fY == pts[index].fY) {
  2705. int maxIndex;
  2706. int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
  2707. if (minIndex == maxIndex) {
  2708. goto TRY_CROSSPROD;
  2709. }
  2710. SkASSERT(pts[minIndex].fY == pts[index].fY);
  2711. SkASSERT(pts[maxIndex].fY == pts[index].fY);
  2712. SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
  2713. // we just subtract the indices, and let that auto-convert to
  2714. // SkScalar, since we just want - or + to signal the direction.
  2715. cross = minIndex - maxIndex;
  2716. } else {
  2717. TRY_CROSSPROD:
  2718. // Find a next and prev index to use for the cross-product test,
  2719. // but we try to find pts that form non-zero vectors from pts[index]
  2720. //
  2721. // Its possible that we can't find two non-degenerate vectors, so
  2722. // we have to guard our search (e.g. all the pts could be in the
  2723. // same place).
  2724. // we pass n - 1 instead of -1 so we don't foul up % operator by
  2725. // passing it a negative LH argument.
  2726. int prev = find_diff_pt(pts, index, n, n - 1);
  2727. if (prev == index) {
  2728. // completely degenerate, skip to next contour
  2729. continue;
  2730. }
  2731. int next = find_diff_pt(pts, index, n, 1);
  2732. SkASSERT(next != index);
  2733. cross = cross_prod(pts[prev], pts[index], pts[next]);
  2734. // if we get a zero and the points are horizontal, then we look at the spread in
  2735. // x-direction. We really should continue to walk away from the degeneracy until
  2736. // there is a divergence.
  2737. if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
  2738. // construct the subtract so we get the correct Direction below
  2739. cross = pts[index].fX - pts[next].fX;
  2740. }
  2741. }
  2742. if (cross) {
  2743. // record our best guess so far
  2744. ymax = pts[index].fY;
  2745. ymaxCross = cross;
  2746. }
  2747. }
  2748. if (ymaxCross) {
  2749. crossToDir(ymaxCross, dir);
  2750. path.setFirstDirection(*dir);
  2751. return true;
  2752. } else {
  2753. return false;
  2754. }
  2755. }
  2756. ///////////////////////////////////////////////////////////////////////////////
  2757. static bool between(SkScalar a, SkScalar b, SkScalar c) {
  2758. SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
  2759. || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
  2760. return (a - b) * (c - b) <= 0;
  2761. }
  2762. static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
  2763. SkScalar t) {
  2764. SkScalar A = c3 + 3*(c1 - c2) - c0;
  2765. SkScalar B = 3*(c2 - c1 - c1 + c0);
  2766. SkScalar C = 3*(c1 - c0);
  2767. SkScalar D = c0;
  2768. return poly_eval(A, B, C, D, t);
  2769. }
  2770. template <size_t N> static void find_minmax(const SkPoint pts[],
  2771. SkScalar* minPtr, SkScalar* maxPtr) {
  2772. SkScalar min, max;
  2773. min = max = pts[0].fX;
  2774. for (size_t i = 1; i < N; ++i) {
  2775. min = SkMinScalar(min, pts[i].fX);
  2776. max = SkMaxScalar(max, pts[i].fX);
  2777. }
  2778. *minPtr = min;
  2779. *maxPtr = max;
  2780. }
  2781. static bool checkOnCurve(SkScalar x, SkScalar y, const SkPoint& start, const SkPoint& end) {
  2782. if (start.fY == end.fY) {
  2783. return between(start.fX, x, end.fX) && x != end.fX;
  2784. } else {
  2785. return x == start.fX && y == start.fY;
  2786. }
  2787. }
  2788. static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
  2789. SkScalar y0 = pts[0].fY;
  2790. SkScalar y3 = pts[3].fY;
  2791. int dir = 1;
  2792. if (y0 > y3) {
  2793. using std::swap;
  2794. swap(y0, y3);
  2795. dir = -1;
  2796. }
  2797. if (y < y0 || y > y3) {
  2798. return 0;
  2799. }
  2800. if (checkOnCurve(x, y, pts[0], pts[3])) {
  2801. *onCurveCount += 1;
  2802. return 0;
  2803. }
  2804. if (y == y3) {
  2805. return 0;
  2806. }
  2807. // quickreject or quickaccept
  2808. SkScalar min, max;
  2809. find_minmax<4>(pts, &min, &max);
  2810. if (x < min) {
  2811. return 0;
  2812. }
  2813. if (x > max) {
  2814. return dir;
  2815. }
  2816. // compute the actual x(t) value
  2817. SkScalar t;
  2818. if (!SkCubicClipper::ChopMonoAtY(pts, y, &t)) {
  2819. return 0;
  2820. }
  2821. SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
  2822. if (SkScalarNearlyEqual(xt, x)) {
  2823. if (x != pts[3].fX || y != pts[3].fY) { // don't test end points; they're start points
  2824. *onCurveCount += 1;
  2825. return 0;
  2826. }
  2827. }
  2828. return xt < x ? dir : 0;
  2829. }
  2830. static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
  2831. SkPoint dst[10];
  2832. int n = SkChopCubicAtYExtrema(pts, dst);
  2833. int w = 0;
  2834. for (int i = 0; i <= n; ++i) {
  2835. w += winding_mono_cubic(&dst[i * 3], x, y, onCurveCount);
  2836. }
  2837. return w;
  2838. }
  2839. static double conic_eval_numerator(const SkScalar src[], SkScalar w, SkScalar t) {
  2840. SkASSERT(src);
  2841. SkASSERT(t >= 0 && t <= 1);
  2842. SkScalar src2w = src[2] * w;
  2843. SkScalar C = src[0];
  2844. SkScalar A = src[4] - 2 * src2w + C;
  2845. SkScalar B = 2 * (src2w - C);
  2846. return poly_eval(A, B, C, t);
  2847. }
  2848. static double conic_eval_denominator(SkScalar w, SkScalar t) {
  2849. SkScalar B = 2 * (w - 1);
  2850. SkScalar C = 1;
  2851. SkScalar A = -B;
  2852. return poly_eval(A, B, C, t);
  2853. }
  2854. static int winding_mono_conic(const SkConic& conic, SkScalar x, SkScalar y, int* onCurveCount) {
  2855. const SkPoint* pts = conic.fPts;
  2856. SkScalar y0 = pts[0].fY;
  2857. SkScalar y2 = pts[2].fY;
  2858. int dir = 1;
  2859. if (y0 > y2) {
  2860. using std::swap;
  2861. swap(y0, y2);
  2862. dir = -1;
  2863. }
  2864. if (y < y0 || y > y2) {
  2865. return 0;
  2866. }
  2867. if (checkOnCurve(x, y, pts[0], pts[2])) {
  2868. *onCurveCount += 1;
  2869. return 0;
  2870. }
  2871. if (y == y2) {
  2872. return 0;
  2873. }
  2874. SkScalar roots[2];
  2875. SkScalar A = pts[2].fY;
  2876. SkScalar B = pts[1].fY * conic.fW - y * conic.fW + y;
  2877. SkScalar C = pts[0].fY;
  2878. A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept)
  2879. B -= C; // B = b*w - w * yCept + yCept - a
  2880. C -= y;
  2881. int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
  2882. SkASSERT(n <= 1);
  2883. SkScalar xt;
  2884. if (0 == n) {
  2885. // zero roots are returned only when y0 == y
  2886. // Need [0] if dir == 1
  2887. // and [2] if dir == -1
  2888. xt = pts[1 - dir].fX;
  2889. } else {
  2890. SkScalar t = roots[0];
  2891. xt = conic_eval_numerator(&pts[0].fX, conic.fW, t) / conic_eval_denominator(conic.fW, t);
  2892. }
  2893. if (SkScalarNearlyEqual(xt, x)) {
  2894. if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points
  2895. *onCurveCount += 1;
  2896. return 0;
  2897. }
  2898. }
  2899. return xt < x ? dir : 0;
  2900. }
  2901. static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
  2902. // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
  2903. if (y0 == y1) {
  2904. return true;
  2905. }
  2906. if (y0 < y1) {
  2907. return y1 <= y2;
  2908. } else {
  2909. return y1 >= y2;
  2910. }
  2911. }
  2912. static int winding_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight,
  2913. int* onCurveCount) {
  2914. SkConic conic(pts, weight);
  2915. SkConic chopped[2];
  2916. // If the data points are very large, the conic may not be monotonic but may also
  2917. // fail to chop. Then, the chopper does not split the original conic in two.
  2918. bool isMono = is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY) || !conic.chopAtYExtrema(chopped);
  2919. int w = winding_mono_conic(isMono ? conic : chopped[0], x, y, onCurveCount);
  2920. if (!isMono) {
  2921. w += winding_mono_conic(chopped[1], x, y, onCurveCount);
  2922. }
  2923. return w;
  2924. }
  2925. static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
  2926. SkScalar y0 = pts[0].fY;
  2927. SkScalar y2 = pts[2].fY;
  2928. int dir = 1;
  2929. if (y0 > y2) {
  2930. using std::swap;
  2931. swap(y0, y2);
  2932. dir = -1;
  2933. }
  2934. if (y < y0 || y > y2) {
  2935. return 0;
  2936. }
  2937. if (checkOnCurve(x, y, pts[0], pts[2])) {
  2938. *onCurveCount += 1;
  2939. return 0;
  2940. }
  2941. if (y == y2) {
  2942. return 0;
  2943. }
  2944. // bounds check on X (not required. is it faster?)
  2945. #if 0
  2946. if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
  2947. return 0;
  2948. }
  2949. #endif
  2950. SkScalar roots[2];
  2951. int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
  2952. 2 * (pts[1].fY - pts[0].fY),
  2953. pts[0].fY - y,
  2954. roots);
  2955. SkASSERT(n <= 1);
  2956. SkScalar xt;
  2957. if (0 == n) {
  2958. // zero roots are returned only when y0 == y
  2959. // Need [0] if dir == 1
  2960. // and [2] if dir == -1
  2961. xt = pts[1 - dir].fX;
  2962. } else {
  2963. SkScalar t = roots[0];
  2964. SkScalar C = pts[0].fX;
  2965. SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
  2966. SkScalar B = 2 * (pts[1].fX - C);
  2967. xt = poly_eval(A, B, C, t);
  2968. }
  2969. if (SkScalarNearlyEqual(xt, x)) {
  2970. if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points
  2971. *onCurveCount += 1;
  2972. return 0;
  2973. }
  2974. }
  2975. return xt < x ? dir : 0;
  2976. }
  2977. static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
  2978. SkPoint dst[5];
  2979. int n = 0;
  2980. if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
  2981. n = SkChopQuadAtYExtrema(pts, dst);
  2982. pts = dst;
  2983. }
  2984. int w = winding_mono_quad(pts, x, y, onCurveCount);
  2985. if (n > 0) {
  2986. w += winding_mono_quad(&pts[2], x, y, onCurveCount);
  2987. }
  2988. return w;
  2989. }
  2990. static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
  2991. SkScalar x0 = pts[0].fX;
  2992. SkScalar y0 = pts[0].fY;
  2993. SkScalar x1 = pts[1].fX;
  2994. SkScalar y1 = pts[1].fY;
  2995. SkScalar dy = y1 - y0;
  2996. int dir = 1;
  2997. if (y0 > y1) {
  2998. using std::swap;
  2999. swap(y0, y1);
  3000. dir = -1;
  3001. }
  3002. if (y < y0 || y > y1) {
  3003. return 0;
  3004. }
  3005. if (checkOnCurve(x, y, pts[0], pts[1])) {
  3006. *onCurveCount += 1;
  3007. return 0;
  3008. }
  3009. if (y == y1) {
  3010. return 0;
  3011. }
  3012. SkScalar cross = (x1 - x0) * (y - pts[0].fY) - dy * (x - x0);
  3013. if (!cross) {
  3014. // zero cross means the point is on the line, and since the case where
  3015. // y of the query point is at the end point is handled above, we can be
  3016. // sure that we're on the line (excluding the end point) here
  3017. if (x != x1 || y != pts[1].fY) {
  3018. *onCurveCount += 1;
  3019. }
  3020. dir = 0;
  3021. } else if (SkScalarSignAsInt(cross) == dir) {
  3022. dir = 0;
  3023. }
  3024. return dir;
  3025. }
  3026. static void tangent_cubic(const SkPoint pts[], SkScalar x, SkScalar y,
  3027. SkTDArray<SkVector>* tangents) {
  3028. if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)
  3029. && !between(pts[2].fY, y, pts[3].fY)) {
  3030. return;
  3031. }
  3032. if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)
  3033. && !between(pts[2].fX, x, pts[3].fX)) {
  3034. return;
  3035. }
  3036. SkPoint dst[10];
  3037. int n = SkChopCubicAtYExtrema(pts, dst);
  3038. for (int i = 0; i <= n; ++i) {
  3039. SkPoint* c = &dst[i * 3];
  3040. SkScalar t;
  3041. if (!SkCubicClipper::ChopMonoAtY(c, y, &t)) {
  3042. continue;
  3043. }
  3044. SkScalar xt = eval_cubic_pts(c[0].fX, c[1].fX, c[2].fX, c[3].fX, t);
  3045. if (!SkScalarNearlyEqual(x, xt)) {
  3046. continue;
  3047. }
  3048. SkVector tangent;
  3049. SkEvalCubicAt(c, t, nullptr, &tangent, nullptr);
  3050. tangents->push_back(tangent);
  3051. }
  3052. }
  3053. static void tangent_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w,
  3054. SkTDArray<SkVector>* tangents) {
  3055. if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
  3056. return;
  3057. }
  3058. if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
  3059. return;
  3060. }
  3061. SkScalar roots[2];
  3062. SkScalar A = pts[2].fY;
  3063. SkScalar B = pts[1].fY * w - y * w + y;
  3064. SkScalar C = pts[0].fY;
  3065. A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept)
  3066. B -= C; // B = b*w - w * yCept + yCept - a
  3067. C -= y;
  3068. int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
  3069. for (int index = 0; index < n; ++index) {
  3070. SkScalar t = roots[index];
  3071. SkScalar xt = conic_eval_numerator(&pts[0].fX, w, t) / conic_eval_denominator(w, t);
  3072. if (!SkScalarNearlyEqual(x, xt)) {
  3073. continue;
  3074. }
  3075. SkConic conic(pts, w);
  3076. tangents->push_back(conic.evalTangentAt(t));
  3077. }
  3078. }
  3079. static void tangent_quad(const SkPoint pts[], SkScalar x, SkScalar y,
  3080. SkTDArray<SkVector>* tangents) {
  3081. if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
  3082. return;
  3083. }
  3084. if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
  3085. return;
  3086. }
  3087. SkScalar roots[2];
  3088. int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
  3089. 2 * (pts[1].fY - pts[0].fY),
  3090. pts[0].fY - y,
  3091. roots);
  3092. for (int index = 0; index < n; ++index) {
  3093. SkScalar t = roots[index];
  3094. SkScalar C = pts[0].fX;
  3095. SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
  3096. SkScalar B = 2 * (pts[1].fX - C);
  3097. SkScalar xt = poly_eval(A, B, C, t);
  3098. if (!SkScalarNearlyEqual(x, xt)) {
  3099. continue;
  3100. }
  3101. tangents->push_back(SkEvalQuadTangentAt(pts, t));
  3102. }
  3103. }
  3104. static void tangent_line(const SkPoint pts[], SkScalar x, SkScalar y,
  3105. SkTDArray<SkVector>* tangents) {
  3106. SkScalar y0 = pts[0].fY;
  3107. SkScalar y1 = pts[1].fY;
  3108. if (!between(y0, y, y1)) {
  3109. return;
  3110. }
  3111. SkScalar x0 = pts[0].fX;
  3112. SkScalar x1 = pts[1].fX;
  3113. if (!between(x0, x, x1)) {
  3114. return;
  3115. }
  3116. SkScalar dx = x1 - x0;
  3117. SkScalar dy = y1 - y0;
  3118. if (!SkScalarNearlyEqual((x - x0) * dy, dx * (y - y0))) {
  3119. return;
  3120. }
  3121. SkVector v;
  3122. v.set(dx, dy);
  3123. tangents->push_back(v);
  3124. }
  3125. static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
  3126. return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
  3127. }
  3128. bool SkPath::contains(SkScalar x, SkScalar y) const {
  3129. bool isInverse = this->isInverseFillType();
  3130. if (this->isEmpty()) {
  3131. return isInverse;
  3132. }
  3133. if (!contains_inclusive(this->getBounds(), x, y)) {
  3134. return isInverse;
  3135. }
  3136. SkPath::Iter iter(*this, true);
  3137. bool done = false;
  3138. int w = 0;
  3139. int onCurveCount = 0;
  3140. do {
  3141. SkPoint pts[4];
  3142. switch (iter.next(pts, false)) {
  3143. case SkPath::kMove_Verb:
  3144. case SkPath::kClose_Verb:
  3145. break;
  3146. case SkPath::kLine_Verb:
  3147. w += winding_line(pts, x, y, &onCurveCount);
  3148. break;
  3149. case SkPath::kQuad_Verb:
  3150. w += winding_quad(pts, x, y, &onCurveCount);
  3151. break;
  3152. case SkPath::kConic_Verb:
  3153. w += winding_conic(pts, x, y, iter.conicWeight(), &onCurveCount);
  3154. break;
  3155. case SkPath::kCubic_Verb:
  3156. w += winding_cubic(pts, x, y, &onCurveCount);
  3157. break;
  3158. case SkPath::kDone_Verb:
  3159. done = true;
  3160. break;
  3161. }
  3162. } while (!done);
  3163. bool evenOddFill = SkPath::kEvenOdd_FillType == this->getFillType()
  3164. || SkPath::kInverseEvenOdd_FillType == this->getFillType();
  3165. if (evenOddFill) {
  3166. w &= 1;
  3167. }
  3168. if (w) {
  3169. return !isInverse;
  3170. }
  3171. if (onCurveCount <= 1) {
  3172. return SkToBool(onCurveCount) ^ isInverse;
  3173. }
  3174. if ((onCurveCount & 1) || evenOddFill) {
  3175. return SkToBool(onCurveCount & 1) ^ isInverse;
  3176. }
  3177. // If the point touches an even number of curves, and the fill is winding, check for
  3178. // coincidence. Count coincidence as places where the on curve points have identical tangents.
  3179. iter.setPath(*this, true);
  3180. done = false;
  3181. SkTDArray<SkVector> tangents;
  3182. do {
  3183. SkPoint pts[4];
  3184. int oldCount = tangents.count();
  3185. switch (iter.next(pts, false)) {
  3186. case SkPath::kMove_Verb:
  3187. case SkPath::kClose_Verb:
  3188. break;
  3189. case SkPath::kLine_Verb:
  3190. tangent_line(pts, x, y, &tangents);
  3191. break;
  3192. case SkPath::kQuad_Verb:
  3193. tangent_quad(pts, x, y, &tangents);
  3194. break;
  3195. case SkPath::kConic_Verb:
  3196. tangent_conic(pts, x, y, iter.conicWeight(), &tangents);
  3197. break;
  3198. case SkPath::kCubic_Verb:
  3199. tangent_cubic(pts, x, y, &tangents);
  3200. break;
  3201. case SkPath::kDone_Verb:
  3202. done = true;
  3203. break;
  3204. }
  3205. if (tangents.count() > oldCount) {
  3206. int last = tangents.count() - 1;
  3207. const SkVector& tangent = tangents[last];
  3208. if (SkScalarNearlyZero(SkPointPriv::LengthSqd(tangent))) {
  3209. tangents.remove(last);
  3210. } else {
  3211. for (int index = 0; index < last; ++index) {
  3212. const SkVector& test = tangents[index];
  3213. if (SkScalarNearlyZero(test.cross(tangent))
  3214. && SkScalarSignAsInt(tangent.fX * test.fX) <= 0
  3215. && SkScalarSignAsInt(tangent.fY * test.fY) <= 0) {
  3216. tangents.remove(last);
  3217. tangents.removeShuffle(index);
  3218. break;
  3219. }
  3220. }
  3221. }
  3222. }
  3223. } while (!done);
  3224. return SkToBool(tangents.count()) ^ isInverse;
  3225. }
  3226. int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
  3227. SkScalar w, SkPoint pts[], int pow2) {
  3228. const SkConic conic(p0, p1, p2, w);
  3229. return conic.chopIntoQuadsPOW2(pts, pow2);
  3230. }
  3231. bool SkPathPriv::IsSimpleClosedRect(const SkPath& path, SkRect* rect, SkPath::Direction* direction,
  3232. unsigned* start) {
  3233. if (path.getSegmentMasks() != SkPath::kLine_SegmentMask) {
  3234. return false;
  3235. }
  3236. SkPath::RawIter iter(path);
  3237. SkPoint verbPts[4];
  3238. SkPath::Verb v;
  3239. SkPoint rectPts[5];
  3240. int rectPtCnt = 0;
  3241. while ((v = iter.next(verbPts)) != SkPath::kDone_Verb) {
  3242. switch (v) {
  3243. case SkPath::kMove_Verb:
  3244. if (0 != rectPtCnt) {
  3245. return false;
  3246. }
  3247. rectPts[0] = verbPts[0];
  3248. ++rectPtCnt;
  3249. break;
  3250. case SkPath::kLine_Verb:
  3251. if (5 == rectPtCnt) {
  3252. return false;
  3253. }
  3254. rectPts[rectPtCnt] = verbPts[1];
  3255. ++rectPtCnt;
  3256. break;
  3257. case SkPath::kClose_Verb:
  3258. if (4 == rectPtCnt) {
  3259. rectPts[4] = rectPts[0];
  3260. rectPtCnt = 5;
  3261. }
  3262. break;
  3263. default:
  3264. return false;
  3265. }
  3266. }
  3267. if (rectPtCnt < 5) {
  3268. return false;
  3269. }
  3270. if (rectPts[0] != rectPts[4]) {
  3271. return false;
  3272. }
  3273. // Check for two cases of rectangles: pts 0 and 3 form a vertical edge or a horizontal edge (
  3274. // and pts 1 and 2 the opposite vertical or horizontal edge).
  3275. bool vec03IsVertical;
  3276. if (rectPts[0].fX == rectPts[3].fX && rectPts[1].fX == rectPts[2].fX &&
  3277. rectPts[0].fY == rectPts[1].fY && rectPts[3].fY == rectPts[2].fY) {
  3278. // Make sure it has non-zero width and height
  3279. if (rectPts[0].fX == rectPts[1].fX || rectPts[0].fY == rectPts[3].fY) {
  3280. return false;
  3281. }
  3282. vec03IsVertical = true;
  3283. } else if (rectPts[0].fY == rectPts[3].fY && rectPts[1].fY == rectPts[2].fY &&
  3284. rectPts[0].fX == rectPts[1].fX && rectPts[3].fX == rectPts[2].fX) {
  3285. // Make sure it has non-zero width and height
  3286. if (rectPts[0].fY == rectPts[1].fY || rectPts[0].fX == rectPts[3].fX) {
  3287. return false;
  3288. }
  3289. vec03IsVertical = false;
  3290. } else {
  3291. return false;
  3292. }
  3293. // Set sortFlags so that it has the low bit set if pt index 0 is on right edge and second bit
  3294. // set if it is on the bottom edge.
  3295. unsigned sortFlags =
  3296. ((rectPts[0].fX < rectPts[2].fX) ? 0b00 : 0b01) |
  3297. ((rectPts[0].fY < rectPts[2].fY) ? 0b00 : 0b10);
  3298. switch (sortFlags) {
  3299. case 0b00:
  3300. rect->set(rectPts[0].fX, rectPts[0].fY, rectPts[2].fX, rectPts[2].fY);
  3301. *direction = vec03IsVertical ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
  3302. *start = 0;
  3303. break;
  3304. case 0b01:
  3305. rect->set(rectPts[2].fX, rectPts[0].fY, rectPts[0].fX, rectPts[2].fY);
  3306. *direction = vec03IsVertical ? SkPath::kCCW_Direction : SkPath::kCW_Direction;
  3307. *start = 1;
  3308. break;
  3309. case 0b10:
  3310. rect->set(rectPts[0].fX, rectPts[2].fY, rectPts[2].fX, rectPts[0].fY);
  3311. *direction = vec03IsVertical ? SkPath::kCCW_Direction : SkPath::kCW_Direction;
  3312. *start = 3;
  3313. break;
  3314. case 0b11:
  3315. rect->set(rectPts[2].fX, rectPts[2].fY, rectPts[0].fX, rectPts[0].fY);
  3316. *direction = vec03IsVertical ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
  3317. *start = 2;
  3318. break;
  3319. }
  3320. return true;
  3321. }
  3322. bool SkPathPriv::DrawArcIsConvex(SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) {
  3323. if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) {
  3324. // This gets converted to an oval.
  3325. return true;
  3326. }
  3327. if (useCenter) {
  3328. // This is a pie wedge. It's convex if the angle is <= 180.
  3329. return SkScalarAbs(sweepAngle) <= 180.f;
  3330. }
  3331. // When the angle exceeds 360 this wraps back on top of itself. Otherwise it is a circle clipped
  3332. // to a secant, i.e. convex.
  3333. return SkScalarAbs(sweepAngle) <= 360.f;
  3334. }
  3335. void SkPathPriv::CreateDrawArcPath(SkPath* path, const SkRect& oval, SkScalar startAngle,
  3336. SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) {
  3337. SkASSERT(!oval.isEmpty());
  3338. SkASSERT(sweepAngle);
  3339. path->reset();
  3340. path->setIsVolatile(true);
  3341. path->setFillType(SkPath::kWinding_FillType);
  3342. if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) {
  3343. path->addOval(oval);
  3344. SkASSERT(path->isConvex() && DrawArcIsConvex(sweepAngle, false, isFillNoPathEffect));
  3345. return;
  3346. }
  3347. if (useCenter) {
  3348. path->moveTo(oval.centerX(), oval.centerY());
  3349. }
  3350. auto firstDir =
  3351. sweepAngle > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
  3352. bool convex = DrawArcIsConvex(sweepAngle, useCenter, isFillNoPathEffect);
  3353. // Arc to mods at 360 and drawArc is not supposed to.
  3354. bool forceMoveTo = !useCenter;
  3355. while (sweepAngle <= -360.f) {
  3356. path->arcTo(oval, startAngle, -180.f, forceMoveTo);
  3357. startAngle -= 180.f;
  3358. path->arcTo(oval, startAngle, -180.f, false);
  3359. startAngle -= 180.f;
  3360. forceMoveTo = false;
  3361. sweepAngle += 360.f;
  3362. }
  3363. while (sweepAngle >= 360.f) {
  3364. path->arcTo(oval, startAngle, 180.f, forceMoveTo);
  3365. startAngle += 180.f;
  3366. path->arcTo(oval, startAngle, 180.f, false);
  3367. startAngle += 180.f;
  3368. forceMoveTo = false;
  3369. sweepAngle -= 360.f;
  3370. }
  3371. path->arcTo(oval, startAngle, sweepAngle, forceMoveTo);
  3372. if (useCenter) {
  3373. path->close();
  3374. }
  3375. path->setConvexity(convex ? SkPath::kConvex_Convexity : SkPath::kConcave_Convexity);
  3376. path->setFirstDirection(firstDir);
  3377. }
  3378. ///////////////////////////////////////////////////////////////////////////////////////////////////
  3379. #include "include/private/SkNx.h"
  3380. static int compute_quad_extremas(const SkPoint src[3], SkPoint extremas[3]) {
  3381. SkScalar ts[2];
  3382. int n = SkFindQuadExtrema(src[0].fX, src[1].fX, src[2].fX, ts);
  3383. n += SkFindQuadExtrema(src[0].fY, src[1].fY, src[2].fY, &ts[n]);
  3384. SkASSERT(n >= 0 && n <= 2);
  3385. for (int i = 0; i < n; ++i) {
  3386. extremas[i] = SkEvalQuadAt(src, ts[i]);
  3387. }
  3388. extremas[n] = src[2];
  3389. return n + 1;
  3390. }
  3391. static int compute_conic_extremas(const SkPoint src[3], SkScalar w, SkPoint extremas[3]) {
  3392. SkConic conic(src[0], src[1], src[2], w);
  3393. SkScalar ts[2];
  3394. int n = conic.findXExtrema(ts);
  3395. n += conic.findYExtrema(&ts[n]);
  3396. SkASSERT(n >= 0 && n <= 2);
  3397. for (int i = 0; i < n; ++i) {
  3398. extremas[i] = conic.evalAt(ts[i]);
  3399. }
  3400. extremas[n] = src[2];
  3401. return n + 1;
  3402. }
  3403. static int compute_cubic_extremas(const SkPoint src[4], SkPoint extremas[5]) {
  3404. SkScalar ts[4];
  3405. int n = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, src[3].fX, ts);
  3406. n += SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, src[3].fY, &ts[n]);
  3407. SkASSERT(n >= 0 && n <= 4);
  3408. for (int i = 0; i < n; ++i) {
  3409. SkEvalCubicAt(src, ts[i], &extremas[i], nullptr, nullptr);
  3410. }
  3411. extremas[n] = src[3];
  3412. return n + 1;
  3413. }
  3414. SkRect SkPath::computeTightBounds() const {
  3415. if (0 == this->countVerbs()) {
  3416. return SkRect::MakeEmpty();
  3417. }
  3418. if (this->getSegmentMasks() == SkPath::kLine_SegmentMask) {
  3419. return this->getBounds();
  3420. }
  3421. SkPoint extremas[5]; // big enough to hold worst-case curve type (cubic) extremas + 1
  3422. SkPoint pts[4];
  3423. SkPath::RawIter iter(*this);
  3424. // initial with the first MoveTo, so we don't have to check inside the switch
  3425. Sk2s min, max;
  3426. min = max = from_point(this->getPoint(0));
  3427. for (;;) {
  3428. int count = 0;
  3429. switch (iter.next(pts)) {
  3430. case SkPath::kMove_Verb:
  3431. extremas[0] = pts[0];
  3432. count = 1;
  3433. break;
  3434. case SkPath::kLine_Verb:
  3435. extremas[0] = pts[1];
  3436. count = 1;
  3437. break;
  3438. case SkPath::kQuad_Verb:
  3439. count = compute_quad_extremas(pts, extremas);
  3440. break;
  3441. case SkPath::kConic_Verb:
  3442. count = compute_conic_extremas(pts, iter.conicWeight(), extremas);
  3443. break;
  3444. case SkPath::kCubic_Verb:
  3445. count = compute_cubic_extremas(pts, extremas);
  3446. break;
  3447. case SkPath::kClose_Verb:
  3448. break;
  3449. case SkPath::kDone_Verb:
  3450. goto DONE;
  3451. }
  3452. for (int i = 0; i < count; ++i) {
  3453. Sk2s tmp = from_point(extremas[i]);
  3454. min = Sk2s::Min(min, tmp);
  3455. max = Sk2s::Max(max, tmp);
  3456. }
  3457. }
  3458. DONE:
  3459. SkRect bounds;
  3460. min.store((SkPoint*)&bounds.fLeft);
  3461. max.store((SkPoint*)&bounds.fRight);
  3462. return bounds;
  3463. }
  3464. bool SkPath::IsLineDegenerate(const SkPoint& p1, const SkPoint& p2, bool exact) {
  3465. return exact ? p1 == p2 : SkPointPriv::EqualsWithinTolerance(p1, p2);
  3466. }
  3467. bool SkPath::IsQuadDegenerate(const SkPoint& p1, const SkPoint& p2,
  3468. const SkPoint& p3, bool exact) {
  3469. return exact ? p1 == p2 && p2 == p3 : SkPointPriv::EqualsWithinTolerance(p1, p2) &&
  3470. SkPointPriv::EqualsWithinTolerance(p2, p3);
  3471. }
  3472. bool SkPath::IsCubicDegenerate(const SkPoint& p1, const SkPoint& p2,
  3473. const SkPoint& p3, const SkPoint& p4, bool exact) {
  3474. return exact ? p1 == p2 && p2 == p3 && p3 == p4 :
  3475. SkPointPriv::EqualsWithinTolerance(p1, p2) &&
  3476. SkPointPriv::EqualsWithinTolerance(p2, p3) &&
  3477. SkPointPriv::EqualsWithinTolerance(p3, p4);
  3478. }