12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902 |
- /*
- * Copyright 2006 The Android Open Source Project
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "include/core/SkPath.h"
- #include "include/core/SkData.h"
- #include "include/core/SkMath.h"
- #include "include/core/SkRRect.h"
- #include "include/private/SkMacros.h"
- #include "include/private/SkPathRef.h"
- #include "include/private/SkTo.h"
- #include "src/core/SkBuffer.h"
- #include "src/core/SkCubicClipper.h"
- #include "src/core/SkGeometry.h"
- #include "src/core/SkMatrixPriv.h"
- #include "src/core/SkPathPriv.h"
- #include "src/core/SkPointPriv.h"
- #include "src/core/SkSafeMath.h"
- #include "src/core/SkTLazy.h"
- // need SkDVector
- #include "src/pathops/SkPathOpsPoint.h"
- #include <cmath>
- #include <utility>
- struct SkPath_Storage_Equivalent {
- void* fPtr;
- int32_t fIndex;
- uint32_t fFlags;
- };
- static_assert(sizeof(SkPath) == sizeof(SkPath_Storage_Equivalent),
- "Please keep an eye on SkPath packing.");
- static float poly_eval(float A, float B, float C, float t) {
- return (A * t + B) * t + C;
- }
- static float poly_eval(float A, float B, float C, float D, float t) {
- return ((A * t + B) * t + C) * t + D;
- }
- ////////////////////////////////////////////////////////////////////////////
- /**
- * Path.bounds is defined to be the bounds of all the control points.
- * If we called bounds.join(r) we would skip r if r was empty, which breaks
- * our promise. Hence we have a custom joiner that doesn't look at emptiness
- */
- static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) {
- dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft);
- dst->fTop = SkMinScalar(dst->fTop, src.fTop);
- dst->fRight = SkMaxScalar(dst->fRight, src.fRight);
- dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom);
- }
- static bool is_degenerate(const SkPath& path) {
- SkPath::Iter iter(path, false);
- SkPoint pts[4];
- return SkPath::kDone_Verb == iter.next(pts);
- }
- class SkAutoDisableDirectionCheck {
- public:
- SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
- fSaved = static_cast<SkPathPriv::FirstDirection>(fPath->getFirstDirection());
- }
- ~SkAutoDisableDirectionCheck() {
- fPath->setFirstDirection(fSaved);
- }
- private:
- SkPath* fPath;
- SkPathPriv::FirstDirection fSaved;
- };
- #define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
- /* This guy's constructor/destructor bracket a path editing operation. It is
- used when we know the bounds of the amount we are going to add to the path
- (usually a new contour, but not required).
- It captures some state about the path up front (i.e. if it already has a
- cached bounds), and then if it can, it updates the cache bounds explicitly,
- avoiding the need to revisit all of the points in getBounds().
- It also notes if the path was originally degenerate, and if so, sets
- isConvex to true. Thus it can only be used if the contour being added is
- convex.
- */
- class SkAutoPathBoundsUpdate {
- public:
- SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
- this->init(path);
- }
- SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top,
- SkScalar right, SkScalar bottom) {
- fRect.set(left, top, right, bottom);
- this->init(path);
- }
- ~SkAutoPathBoundsUpdate() {
- fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity
- : SkPath::kUnknown_Convexity);
- if ((fEmpty || fHasValidBounds) && fRect.isFinite()) {
- fPath->setBounds(fRect);
- }
- }
- private:
- SkPath* fPath;
- SkRect fRect;
- bool fHasValidBounds;
- bool fDegenerate;
- bool fEmpty;
- void init(SkPath* path) {
- // Cannot use fRect for our bounds unless we know it is sorted
- fRect.sort();
- fPath = path;
- // Mark the path's bounds as dirty if (1) they are, or (2) the path
- // is non-finite, and therefore its bounds are not meaningful
- fHasValidBounds = path->hasComputedBounds() && path->isFinite();
- fEmpty = path->isEmpty();
- if (fHasValidBounds && !fEmpty) {
- joinNoEmptyChecks(&fRect, fPath->getBounds());
- }
- fDegenerate = is_degenerate(*path);
- }
- };
- #define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate)
- ////////////////////////////////////////////////////////////////////////////
- /*
- Stores the verbs and points as they are given to us, with exceptions:
- - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic
- - we insert a Move(0,0) if Line | Quad | Cubic is our first command
- The iterator does more cleanup, especially if forceClose == true
- 1. If we encounter degenerate segments, remove them
- 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
- 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2
- 4. if we encounter Line | Quad | Cubic after Close, cons up a Move
- */
- ////////////////////////////////////////////////////////////////////////////
- // flag to require a moveTo if we begin with something else, like lineTo etc.
- #define INITIAL_LASTMOVETOINDEX_VALUE ~0
- SkPath::SkPath()
- : fPathRef(SkPathRef::CreateEmpty()) {
- this->resetFields();
- fIsVolatile = false;
- }
- void SkPath::resetFields() {
- //fPathRef is assumed to have been emptied by the caller.
- fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
- fFillType = kWinding_FillType;
- this->setConvexity(kUnknown_Convexity);
- this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
- // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we
- // don't want to muck with it if it's been set to something non-nullptr.
- }
- SkPath::SkPath(const SkPath& that)
- : fPathRef(SkRef(that.fPathRef.get())) {
- this->copyFields(that);
- SkDEBUGCODE(that.validate();)
- }
- SkPath::~SkPath() {
- SkDEBUGCODE(this->validate();)
- }
- SkPath& SkPath::operator=(const SkPath& that) {
- SkDEBUGCODE(that.validate();)
- if (this != &that) {
- fPathRef.reset(SkRef(that.fPathRef.get()));
- this->copyFields(that);
- }
- SkDEBUGCODE(this->validate();)
- return *this;
- }
- void SkPath::copyFields(const SkPath& that) {
- //fPathRef is assumed to have been set by the caller.
- fLastMoveToIndex = that.fLastMoveToIndex;
- fFillType = that.fFillType;
- fIsVolatile = that.fIsVolatile;
- // Non-atomic assignment of atomic values.
- this->setConvexity(that.getConvexityOrUnknown());
- this->setFirstDirection(that.getFirstDirection());
- }
- bool operator==(const SkPath& a, const SkPath& b) {
- // note: don't need to look at isConvex or bounds, since just comparing the
- // raw data is sufficient.
- return &a == &b ||
- (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
- }
- void SkPath::swap(SkPath& that) {
- if (this != &that) {
- fPathRef.swap(that.fPathRef);
- std::swap(fLastMoveToIndex, that.fLastMoveToIndex);
- const auto ft = fFillType;
- fFillType = that.fFillType;
- that.fFillType = ft;
- const auto iv = fIsVolatile;
- fIsVolatile = that.fIsVolatile;
- that.fIsVolatile = iv;
- // Non-atomic swaps of atomic values.
- Convexity c = this->getConvexityOrUnknown();
- this->setConvexity(that.getConvexityOrUnknown());
- that.setConvexity(c);
- uint8_t fd = this->getFirstDirection();
- this->setFirstDirection(that.getFirstDirection());
- that.setFirstDirection(fd);
- }
- }
- bool SkPath::isInterpolatable(const SkPath& compare) const {
- int count = fPathRef->countVerbs();
- if (count != compare.fPathRef->countVerbs()) {
- return false;
- }
- if (!count) {
- return true;
- }
- if (memcmp(fPathRef->verbsMemBegin(), compare.fPathRef->verbsMemBegin(),
- count)) {
- return false;
- }
- return !fPathRef->countWeights() ||
- !SkToBool(memcmp(fPathRef->conicWeights(), compare.fPathRef->conicWeights(),
- fPathRef->countWeights() * sizeof(*fPathRef->conicWeights())));
- }
- bool SkPath::interpolate(const SkPath& ending, SkScalar weight, SkPath* out) const {
- int pointCount = fPathRef->countPoints();
- if (pointCount != ending.fPathRef->countPoints()) {
- return false;
- }
- if (!pointCount) {
- return true;
- }
- out->reset();
- out->addPath(*this);
- fPathRef->interpolate(*ending.fPathRef, weight, out->fPathRef.get());
- return true;
- }
- static inline bool check_edge_against_rect(const SkPoint& p0,
- const SkPoint& p1,
- const SkRect& rect,
- SkPathPriv::FirstDirection dir) {
- const SkPoint* edgeBegin;
- SkVector v;
- if (SkPathPriv::kCW_FirstDirection == dir) {
- v = p1 - p0;
- edgeBegin = &p0;
- } else {
- v = p0 - p1;
- edgeBegin = &p1;
- }
- if (v.fX || v.fY) {
- // check the cross product of v with the vec from edgeBegin to each rect corner
- SkScalar yL = v.fY * (rect.fLeft - edgeBegin->fX);
- SkScalar xT = v.fX * (rect.fTop - edgeBegin->fY);
- SkScalar yR = v.fY * (rect.fRight - edgeBegin->fX);
- SkScalar xB = v.fX * (rect.fBottom - edgeBegin->fY);
- if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
- return false;
- }
- }
- return true;
- }
- bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
- // This only handles non-degenerate convex paths currently.
- if (kConvex_Convexity != this->getConvexity()) {
- return false;
- }
- SkPathPriv::FirstDirection direction;
- if (!SkPathPriv::CheapComputeFirstDirection(*this, &direction)) {
- return false;
- }
- SkPoint firstPt;
- SkPoint prevPt;
- SkPath::Iter iter(*this, true);
- SkPath::Verb verb;
- SkPoint pts[4];
- int segmentCount = 0;
- SkDEBUGCODE(int moveCnt = 0;)
- SkDEBUGCODE(int closeCount = 0;)
- while ((verb = iter.next(pts, true, true)) != kDone_Verb) {
- int nextPt = -1;
- switch (verb) {
- case kMove_Verb:
- SkASSERT(!segmentCount && !closeCount);
- SkDEBUGCODE(++moveCnt);
- firstPt = prevPt = pts[0];
- break;
- case kLine_Verb:
- nextPt = 1;
- SkASSERT(moveCnt && !closeCount);
- ++segmentCount;
- break;
- case kQuad_Verb:
- case kConic_Verb:
- SkASSERT(moveCnt && !closeCount);
- ++segmentCount;
- nextPt = 2;
- break;
- case kCubic_Verb:
- SkASSERT(moveCnt && !closeCount);
- ++segmentCount;
- nextPt = 3;
- break;
- case kClose_Verb:
- SkDEBUGCODE(++closeCount;)
- break;
- default:
- SkDEBUGFAIL("unknown verb");
- }
- if (-1 != nextPt) {
- if (SkPath::kConic_Verb == verb) {
- SkConic orig;
- orig.set(pts, iter.conicWeight());
- SkPoint quadPts[5];
- int count = orig.chopIntoQuadsPOW2(quadPts, 1);
- SkASSERT_RELEASE(2 == count);
- if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) {
- return false;
- }
- if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) {
- return false;
- }
- } else {
- if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
- return false;
- }
- }
- prevPt = pts[nextPt];
- }
- }
- if (segmentCount) {
- return check_edge_against_rect(prevPt, firstPt, rect, direction);
- }
- return false;
- }
- uint32_t SkPath::getGenerationID() const {
- uint32_t genID = fPathRef->genID();
- #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
- SkASSERT((unsigned)fFillType < (1 << (32 - SkPathPriv::kPathRefGenIDBitCnt)));
- genID |= static_cast<uint32_t>(fFillType) << SkPathPriv::kPathRefGenIDBitCnt;
- #endif
- return genID;
- }
- SkPath& SkPath::reset() {
- SkDEBUGCODE(this->validate();)
- fPathRef.reset(SkPathRef::CreateEmpty());
- this->resetFields();
- return *this;
- }
- SkPath& SkPath::rewind() {
- SkDEBUGCODE(this->validate();)
- SkPathRef::Rewind(&fPathRef);
- this->resetFields();
- return *this;
- }
- bool SkPath::isLastContourClosed() const {
- int verbCount = fPathRef->countVerbs();
- if (0 == verbCount) {
- return false;
- }
- return kClose_Verb == fPathRef->atVerb(verbCount - 1);
- }
- bool SkPath::isLine(SkPoint line[2]) const {
- int verbCount = fPathRef->countVerbs();
- if (2 == verbCount) {
- SkASSERT(kMove_Verb == fPathRef->atVerb(0));
- if (kLine_Verb == fPathRef->atVerb(1)) {
- SkASSERT(2 == fPathRef->countPoints());
- if (line) {
- const SkPoint* pts = fPathRef->points();
- line[0] = pts[0];
- line[1] = pts[1];
- }
- return true;
- }
- }
- return false;
- }
- /*
- Determines if path is a rect by keeping track of changes in direction
- and looking for a loop either clockwise or counterclockwise.
- The direction is computed such that:
- 0: vertical up
- 1: horizontal left
- 2: vertical down
- 3: horizontal right
- A rectangle cycles up/right/down/left or up/left/down/right.
- The test fails if:
- The path is closed, and followed by a line.
- A second move creates a new endpoint.
- A diagonal line is parsed.
- There's more than four changes of direction.
- There's a discontinuity on the line (e.g., a move in the middle)
- The line reverses direction.
- The path contains a quadratic or cubic.
- The path contains fewer than four points.
- *The rectangle doesn't complete a cycle.
- *The final point isn't equal to the first point.
- *These last two conditions we relax if we have a 3-edge path that would
- form a rectangle if it were closed (as we do when we fill a path)
- It's OK if the path has:
- Several colinear line segments composing a rectangle side.
- Single points on the rectangle side.
- The direction takes advantage of the corners found since opposite sides
- must travel in opposite directions.
- FIXME: Allow colinear quads and cubics to be treated like lines.
- FIXME: If the API passes fill-only, return true if the filled stroke
- is a rectangle, though the caller failed to close the path.
- directions values:
- 0x1 is set if the segment is horizontal
- 0x2 is set if the segment is moving to the right or down
- thus:
- two directions are opposites iff (dirA ^ dirB) == 0x2
- two directions are perpendicular iff (dirA ^ dirB) == 0x1
- */
- static int rect_make_dir(SkScalar dx, SkScalar dy) {
- return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
- }
- bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr,
- bool* isClosed, Direction* direction, SkRect* rect) const {
- int corners = 0;
- SkPoint closeXY; // used to determine if final line falls on a diagonal
- SkPoint lineStart; // used to construct line from previous point
- const SkPoint* firstPt = nullptr; // first point in the rect (last of first moves)
- const SkPoint* lastPt = nullptr; // last point in the rect (last of lines or first if closed)
- SkPoint firstCorner;
- SkPoint thirdCorner;
- const SkPoint* pts = *ptsPtr;
- const SkPoint* savePts = nullptr; // used to allow caller to iterate through a pair of rects
- lineStart.set(0, 0);
- signed char directions[] = {-1, -1, -1, -1, -1}; // -1 to 3; -1 is uninitialized
- bool closedOrMoved = false;
- bool autoClose = false;
- bool insertClose = false;
- int verbCnt = fPathRef->countVerbs();
- while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
- uint8_t verb = insertClose ? (uint8_t) kClose_Verb : fPathRef->atVerb(*currVerb);
- switch (verb) {
- case kClose_Verb:
- savePts = pts;
- autoClose = true;
- insertClose = false;
- case kLine_Verb: {
- if (kClose_Verb != verb) {
- lastPt = pts;
- }
- SkPoint lineEnd = kClose_Verb == verb ? *firstPt : *pts++;
- SkVector lineDelta = lineEnd - lineStart;
- if (lineDelta.fX && lineDelta.fY) {
- return false; // diagonal
- }
- if (!lineDelta.isFinite()) {
- return false; // path contains infinity or NaN
- }
- if (lineStart == lineEnd) {
- break; // single point on side OK
- }
- int nextDirection = rect_make_dir(lineDelta.fX, lineDelta.fY); // 0 to 3
- if (0 == corners) {
- directions[0] = nextDirection;
- corners = 1;
- closedOrMoved = false;
- lineStart = lineEnd;
- break;
- }
- if (closedOrMoved) {
- return false; // closed followed by a line
- }
- if (autoClose && nextDirection == directions[0]) {
- break; // colinear with first
- }
- closedOrMoved = autoClose;
- if (directions[corners - 1] == nextDirection) {
- if (3 == corners && kLine_Verb == verb) {
- thirdCorner = lineEnd;
- }
- lineStart = lineEnd;
- break; // colinear segment
- }
- directions[corners++] = nextDirection;
- // opposite lines must point in opposite directions; xoring them should equal 2
- switch (corners) {
- case 2:
- firstCorner = lineStart;
- break;
- case 3:
- if ((directions[0] ^ directions[2]) != 2) {
- return false;
- }
- thirdCorner = lineEnd;
- break;
- case 4:
- if ((directions[1] ^ directions[3]) != 2) {
- return false;
- }
- break;
- default:
- return false; // too many direction changes
- }
- lineStart = lineEnd;
- break;
- }
- case kQuad_Verb:
- case kConic_Verb:
- case kCubic_Verb:
- return false; // quadratic, cubic not allowed
- case kMove_Verb:
- if (allowPartial && !autoClose && directions[0] >= 0) {
- insertClose = true;
- *currVerb -= 1; // try move again afterwards
- goto addMissingClose;
- }
- if (!corners) {
- firstPt = pts;
- } else {
- closeXY = *firstPt - *lastPt;
- if (closeXY.fX && closeXY.fY) {
- return false; // we're diagonal, abort
- }
- }
- lineStart = *pts++;
- closedOrMoved = true;
- break;
- default:
- SkDEBUGFAIL("unexpected verb");
- break;
- }
- *currVerb += 1;
- addMissingClose:
- ;
- }
- // Success if 4 corners and first point equals last
- if (corners < 3 || corners > 4) {
- return false;
- }
- if (savePts) {
- *ptsPtr = savePts;
- }
- // check if close generates diagonal
- closeXY = *firstPt - *lastPt;
- if (closeXY.fX && closeXY.fY) {
- return false;
- }
- if (rect) {
- rect->set(firstCorner, thirdCorner);
- }
- if (isClosed) {
- *isClosed = autoClose;
- }
- if (direction) {
- *direction = directions[0] == ((directions[1] + 1) & 3) ? kCW_Direction : kCCW_Direction;
- }
- return true;
- }
- bool SkPath::isRect(SkRect* rect, bool* isClosed, Direction* direction) const {
- SkDEBUGCODE(this->validate();)
- int currVerb = 0;
- const SkPoint* pts = fPathRef->points();
- return this->isRectContour(false, &currVerb, &pts, isClosed, direction, rect);
- }
- bool SkPath::isNestedFillRects(SkRect rects[2], Direction dirs[2]) const {
- SkDEBUGCODE(this->validate();)
- int currVerb = 0;
- const SkPoint* pts = fPathRef->points();
- Direction testDirs[2];
- SkRect testRects[2];
- if (!isRectContour(true, &currVerb, &pts, nullptr, &testDirs[0], &testRects[0])) {
- return false;
- }
- if (isRectContour(false, &currVerb, &pts, nullptr, &testDirs[1], &testRects[1])) {
- if (testRects[0].contains(testRects[1])) {
- if (rects) {
- rects[0] = testRects[0];
- rects[1] = testRects[1];
- }
- if (dirs) {
- dirs[0] = testDirs[0];
- dirs[1] = testDirs[1];
- }
- return true;
- }
- if (testRects[1].contains(testRects[0])) {
- if (rects) {
- rects[0] = testRects[1];
- rects[1] = testRects[0];
- }
- if (dirs) {
- dirs[0] = testDirs[1];
- dirs[1] = testDirs[0];
- }
- return true;
- }
- }
- return false;
- }
- bool SkPath::isOval(SkRect* bounds) const {
- return SkPathPriv::IsOval(*this, bounds, nullptr, nullptr);
- }
- bool SkPath::isRRect(SkRRect* rrect) const {
- return SkPathPriv::IsRRect(*this, rrect, nullptr, nullptr);
- }
- int SkPath::countPoints() const {
- return fPathRef->countPoints();
- }
- int SkPath::getPoints(SkPoint dst[], int max) const {
- SkDEBUGCODE(this->validate();)
- SkASSERT(max >= 0);
- SkASSERT(!max || dst);
- int count = SkMin32(max, fPathRef->countPoints());
- sk_careful_memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
- return fPathRef->countPoints();
- }
- SkPoint SkPath::getPoint(int index) const {
- if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
- return fPathRef->atPoint(index);
- }
- return SkPoint::Make(0, 0);
- }
- int SkPath::countVerbs() const {
- return fPathRef->countVerbs();
- }
- static inline void copy_verbs_reverse(uint8_t* inorderDst,
- const uint8_t* reversedSrc,
- int count) {
- for (int i = 0; i < count; ++i) {
- inorderDst[i] = reversedSrc[~i];
- }
- }
- int SkPath::getVerbs(uint8_t dst[], int max) const {
- SkDEBUGCODE(this->validate();)
- SkASSERT(max >= 0);
- SkASSERT(!max || dst);
- int count = SkMin32(max, fPathRef->countVerbs());
- copy_verbs_reverse(dst, fPathRef->verbs(), count);
- return fPathRef->countVerbs();
- }
- size_t SkPath::approximateBytesUsed() const {
- size_t size = sizeof (SkPath);
- if (fPathRef != nullptr) {
- size += fPathRef->countPoints() * sizeof(SkPoint)
- + fPathRef->countVerbs()
- + fPathRef->countWeights() * sizeof(SkScalar);
- }
- return size;
- }
- bool SkPath::getLastPt(SkPoint* lastPt) const {
- SkDEBUGCODE(this->validate();)
- int count = fPathRef->countPoints();
- if (count > 0) {
- if (lastPt) {
- *lastPt = fPathRef->atPoint(count - 1);
- }
- return true;
- }
- if (lastPt) {
- lastPt->set(0, 0);
- }
- return false;
- }
- void SkPath::setPt(int index, SkScalar x, SkScalar y) {
- SkDEBUGCODE(this->validate();)
- int count = fPathRef->countPoints();
- if (count <= index) {
- return;
- } else {
- SkPathRef::Editor ed(&fPathRef);
- ed.atPoint(index)->set(x, y);
- }
- }
- void SkPath::setLastPt(SkScalar x, SkScalar y) {
- SkDEBUGCODE(this->validate();)
- int count = fPathRef->countPoints();
- if (count == 0) {
- this->moveTo(x, y);
- } else {
- SkPathRef::Editor ed(&fPathRef);
- ed.atPoint(count-1)->set(x, y);
- }
- }
- // This is the public-facing non-const setConvexity().
- void SkPath::setConvexity(Convexity c) {
- fConvexity.store(c, std::memory_order_relaxed);
- }
- // Const hooks for working with fConvexity and fFirstDirection from const methods.
- void SkPath::setConvexity(Convexity c) const {
- fConvexity.store(c, std::memory_order_relaxed);
- }
- void SkPath::setFirstDirection(uint8_t d) const {
- fFirstDirection.store(d, std::memory_order_relaxed);
- }
- uint8_t SkPath::getFirstDirection() const {
- return fFirstDirection.load(std::memory_order_relaxed);
- }
- //////////////////////////////////////////////////////////////////////////////
- // Construction methods
- #define DIRTY_AFTER_EDIT \
- do { \
- this->setConvexity(kUnknown_Convexity); \
- this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection); \
- } while (0)
- void SkPath::incReserve(int inc) {
- SkDEBUGCODE(this->validate();)
- if (inc > 0) {
- SkPathRef::Editor(&fPathRef, inc, inc);
- }
- SkDEBUGCODE(this->validate();)
- }
- SkPath& SkPath::moveTo(SkScalar x, SkScalar y) {
- SkDEBUGCODE(this->validate();)
- SkPathRef::Editor ed(&fPathRef);
- // remember our index
- fLastMoveToIndex = fPathRef->countPoints();
- ed.growForVerb(kMove_Verb)->set(x, y);
- DIRTY_AFTER_EDIT;
- return *this;
- }
- SkPath& SkPath::rMoveTo(SkScalar x, SkScalar y) {
- SkPoint pt;
- this->getLastPt(&pt);
- return this->moveTo(pt.fX + x, pt.fY + y);
- }
- void SkPath::injectMoveToIfNeeded() {
- if (fLastMoveToIndex < 0) {
- SkScalar x, y;
- if (fPathRef->countVerbs() == 0) {
- x = y = 0;
- } else {
- const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
- x = pt.fX;
- y = pt.fY;
- }
- this->moveTo(x, y);
- }
- }
- SkPath& SkPath::lineTo(SkScalar x, SkScalar y) {
- SkDEBUGCODE(this->validate();)
- this->injectMoveToIfNeeded();
- SkPathRef::Editor ed(&fPathRef);
- ed.growForVerb(kLine_Verb)->set(x, y);
- DIRTY_AFTER_EDIT;
- return *this;
- }
- SkPath& SkPath::rLineTo(SkScalar x, SkScalar y) {
- this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
- SkPoint pt;
- this->getLastPt(&pt);
- return this->lineTo(pt.fX + x, pt.fY + y);
- }
- SkPath& SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
- SkDEBUGCODE(this->validate();)
- this->injectMoveToIfNeeded();
- SkPathRef::Editor ed(&fPathRef);
- SkPoint* pts = ed.growForVerb(kQuad_Verb);
- pts[0].set(x1, y1);
- pts[1].set(x2, y2);
- DIRTY_AFTER_EDIT;
- return *this;
- }
- SkPath& SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
- this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
- SkPoint pt;
- this->getLastPt(&pt);
- return this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
- }
- SkPath& SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
- SkScalar w) {
- // check for <= 0 or NaN with this test
- if (!(w > 0)) {
- this->lineTo(x2, y2);
- } else if (!SkScalarIsFinite(w)) {
- this->lineTo(x1, y1);
- this->lineTo(x2, y2);
- } else if (SK_Scalar1 == w) {
- this->quadTo(x1, y1, x2, y2);
- } else {
- SkDEBUGCODE(this->validate();)
- this->injectMoveToIfNeeded();
- SkPathRef::Editor ed(&fPathRef);
- SkPoint* pts = ed.growForVerb(kConic_Verb, w);
- pts[0].set(x1, y1);
- pts[1].set(x2, y2);
- DIRTY_AFTER_EDIT;
- }
- return *this;
- }
- SkPath& SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
- SkScalar w) {
- this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
- SkPoint pt;
- this->getLastPt(&pt);
- return this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
- }
- SkPath& SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
- SkScalar x3, SkScalar y3) {
- SkDEBUGCODE(this->validate();)
- this->injectMoveToIfNeeded();
- SkPathRef::Editor ed(&fPathRef);
- SkPoint* pts = ed.growForVerb(kCubic_Verb);
- pts[0].set(x1, y1);
- pts[1].set(x2, y2);
- pts[2].set(x3, y3);
- DIRTY_AFTER_EDIT;
- return *this;
- }
- SkPath& SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
- SkScalar x3, SkScalar y3) {
- this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt().
- SkPoint pt;
- this->getLastPt(&pt);
- return this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
- pt.fX + x3, pt.fY + y3);
- }
- SkPath& SkPath::close() {
- SkDEBUGCODE(this->validate();)
- int count = fPathRef->countVerbs();
- if (count > 0) {
- switch (fPathRef->atVerb(count - 1)) {
- case kLine_Verb:
- case kQuad_Verb:
- case kConic_Verb:
- case kCubic_Verb:
- case kMove_Verb: {
- SkPathRef::Editor ed(&fPathRef);
- ed.growForVerb(kClose_Verb);
- break;
- }
- case kClose_Verb:
- // don't add a close if it's the first verb or a repeat
- break;
- default:
- SkDEBUGFAIL("unexpected verb");
- break;
- }
- }
- // signal that we need a moveTo to follow us (unless we're done)
- #if 0
- if (fLastMoveToIndex >= 0) {
- fLastMoveToIndex = ~fLastMoveToIndex;
- }
- #else
- fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
- #endif
- return *this;
- }
- ///////////////////////////////////////////////////////////////////////////////
- namespace {
- template <unsigned N>
- class PointIterator {
- public:
- PointIterator(SkPath::Direction dir, unsigned startIndex)
- : fCurrent(startIndex % N)
- , fAdvance(dir == SkPath::kCW_Direction ? 1 : N - 1) { }
- const SkPoint& current() const {
- SkASSERT(fCurrent < N);
- return fPts[fCurrent];
- }
- const SkPoint& next() {
- fCurrent = (fCurrent + fAdvance) % N;
- return this->current();
- }
- protected:
- SkPoint fPts[N];
- private:
- unsigned fCurrent;
- unsigned fAdvance;
- };
- class RectPointIterator : public PointIterator<4> {
- public:
- RectPointIterator(const SkRect& rect, SkPath::Direction dir, unsigned startIndex)
- : PointIterator(dir, startIndex) {
- fPts[0] = SkPoint::Make(rect.fLeft, rect.fTop);
- fPts[1] = SkPoint::Make(rect.fRight, rect.fTop);
- fPts[2] = SkPoint::Make(rect.fRight, rect.fBottom);
- fPts[3] = SkPoint::Make(rect.fLeft, rect.fBottom);
- }
- };
- class OvalPointIterator : public PointIterator<4> {
- public:
- OvalPointIterator(const SkRect& oval, SkPath::Direction dir, unsigned startIndex)
- : PointIterator(dir, startIndex) {
- const SkScalar cx = oval.centerX();
- const SkScalar cy = oval.centerY();
- fPts[0] = SkPoint::Make(cx, oval.fTop);
- fPts[1] = SkPoint::Make(oval.fRight, cy);
- fPts[2] = SkPoint::Make(cx, oval.fBottom);
- fPts[3] = SkPoint::Make(oval.fLeft, cy);
- }
- };
- class RRectPointIterator : public PointIterator<8> {
- public:
- RRectPointIterator(const SkRRect& rrect, SkPath::Direction dir, unsigned startIndex)
- : PointIterator(dir, startIndex) {
- const SkRect& bounds = rrect.getBounds();
- const SkScalar L = bounds.fLeft;
- const SkScalar T = bounds.fTop;
- const SkScalar R = bounds.fRight;
- const SkScalar B = bounds.fBottom;
- fPts[0] = SkPoint::Make(L + rrect.radii(SkRRect::kUpperLeft_Corner).fX, T);
- fPts[1] = SkPoint::Make(R - rrect.radii(SkRRect::kUpperRight_Corner).fX, T);
- fPts[2] = SkPoint::Make(R, T + rrect.radii(SkRRect::kUpperRight_Corner).fY);
- fPts[3] = SkPoint::Make(R, B - rrect.radii(SkRRect::kLowerRight_Corner).fY);
- fPts[4] = SkPoint::Make(R - rrect.radii(SkRRect::kLowerRight_Corner).fX, B);
- fPts[5] = SkPoint::Make(L + rrect.radii(SkRRect::kLowerLeft_Corner).fX, B);
- fPts[6] = SkPoint::Make(L, B - rrect.radii(SkRRect::kLowerLeft_Corner).fY);
- fPts[7] = SkPoint::Make(L, T + rrect.radii(SkRRect::kUpperLeft_Corner).fY);
- }
- };
- } // anonymous namespace
- static void assert_known_direction(int dir) {
- SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
- }
- SkPath& SkPath::addRect(const SkRect& rect, Direction dir) {
- return this->addRect(rect, dir, 0);
- }
- SkPath& SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
- SkScalar bottom, Direction dir) {
- return this->addRect(SkRect::MakeLTRB(left, top, right, bottom), dir, 0);
- }
- SkPath& SkPath::addRect(const SkRect &rect, Direction dir, unsigned startIndex) {
- assert_known_direction(dir);
- this->setFirstDirection(this->hasOnlyMoveTos() ? (SkPathPriv::FirstDirection)dir
- : SkPathPriv::kUnknown_FirstDirection);
- SkAutoDisableDirectionCheck addc(this);
- SkAutoPathBoundsUpdate apbu(this, rect);
- SkDEBUGCODE(int initialVerbCount = this->countVerbs());
- const int kVerbs = 5; // moveTo + 3x lineTo + close
- this->incReserve(kVerbs);
- RectPointIterator iter(rect, dir, startIndex);
- this->moveTo(iter.current());
- this->lineTo(iter.next());
- this->lineTo(iter.next());
- this->lineTo(iter.next());
- this->close();
- SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
- return *this;
- }
- SkPath& SkPath::addPoly(const SkPoint pts[], int count, bool close) {
- SkDEBUGCODE(this->validate();)
- if (count <= 0) {
- return *this;
- }
- fLastMoveToIndex = fPathRef->countPoints();
- // +close makes room for the extra kClose_Verb
- SkPathRef::Editor ed(&fPathRef, count+close, count);
- ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
- if (count > 1) {
- SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
- memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
- }
- if (close) {
- ed.growForVerb(kClose_Verb);
- fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
- }
- DIRTY_AFTER_EDIT;
- SkDEBUGCODE(this->validate();)
- return *this;
- }
- #include "src/core/SkGeometry.h"
- static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
- SkPoint* pt) {
- if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) {
- // Chrome uses this path to move into and out of ovals. If not
- // treated as a special case the moves can distort the oval's
- // bounding box (and break the circle special case).
- pt->set(oval.fRight, oval.centerY());
- return true;
- } else if (0 == oval.width() && 0 == oval.height()) {
- // Chrome will sometimes create 0 radius round rects. Having degenerate
- // quad segments in the path prevents the path from being recognized as
- // a rect.
- // TODO: optimizing the case where only one of width or height is zero
- // should also be considered. This case, however, doesn't seem to be
- // as common as the single point case.
- pt->set(oval.fRight, oval.fTop);
- return true;
- }
- return false;
- }
- // Return the unit vectors pointing at the start/stop points for the given start/sweep angles
- //
- static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle,
- SkVector* startV, SkVector* stopV, SkRotationDirection* dir) {
- SkScalar startRad = SkDegreesToRadians(startAngle),
- stopRad = SkDegreesToRadians(startAngle + sweepAngle);
- startV->fY = SkScalarSinSnapToZero(startRad);
- startV->fX = SkScalarCosSnapToZero(startRad);
- stopV->fY = SkScalarSinSnapToZero(stopRad);
- stopV->fX = SkScalarCosSnapToZero(stopRad);
- /* If the sweep angle is nearly (but less than) 360, then due to precision
- loss in radians-conversion and/or sin/cos, we may end up with coincident
- vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
- of drawing a nearly complete circle (good).
- e.g. canvas.drawArc(0, 359.99, ...)
- -vs- canvas.drawArc(0, 359.9, ...)
- We try to detect this edge case, and tweak the stop vector
- */
- if (*startV == *stopV) {
- SkScalar sw = SkScalarAbs(sweepAngle);
- if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
- // make a guess at a tiny angle (in radians) to tweak by
- SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
- // not sure how much will be enough, so we use a loop
- do {
- stopRad -= deltaRad;
- stopV->fY = SkScalarSinSnapToZero(stopRad);
- stopV->fX = SkScalarCosSnapToZero(stopRad);
- } while (*startV == *stopV);
- }
- }
- *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
- }
- /**
- * If this returns 0, then the caller should just line-to the singlePt, else it should
- * ignore singlePt and append the specified number of conics.
- */
- static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop,
- SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc],
- SkPoint* singlePt) {
- SkMatrix matrix;
- matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
- matrix.postTranslate(oval.centerX(), oval.centerY());
- int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
- if (0 == count) {
- matrix.mapXY(stop.x(), stop.y(), singlePt);
- }
- return count;
- }
- SkPath& SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
- Direction dir) {
- SkRRect rrect;
- rrect.setRectRadii(rect, (const SkVector*) radii);
- return this->addRRect(rrect, dir);
- }
- SkPath& SkPath::addRRect(const SkRRect& rrect, Direction dir) {
- // legacy start indices: 6 (CW) and 7(CCW)
- return this->addRRect(rrect, dir, dir == kCW_Direction ? 6 : 7);
- }
- SkPath& SkPath::addRRect(const SkRRect &rrect, Direction dir, unsigned startIndex) {
- assert_known_direction(dir);
- bool isRRect = hasOnlyMoveTos();
- const SkRect& bounds = rrect.getBounds();
- if (rrect.isRect() || rrect.isEmpty()) {
- // degenerate(rect) => radii points are collapsing
- this->addRect(bounds, dir, (startIndex + 1) / 2);
- } else if (rrect.isOval()) {
- // degenerate(oval) => line points are collapsing
- this->addOval(bounds, dir, startIndex / 2);
- } else {
- this->setFirstDirection(this->hasOnlyMoveTos() ? (SkPathPriv::FirstDirection)dir
- : SkPathPriv::kUnknown_FirstDirection);
- SkAutoPathBoundsUpdate apbu(this, bounds);
- SkAutoDisableDirectionCheck addc(this);
- // we start with a conic on odd indices when moving CW vs. even indices when moving CCW
- const bool startsWithConic = ((startIndex & 1) == (dir == kCW_Direction));
- const SkScalar weight = SK_ScalarRoot2Over2;
- SkDEBUGCODE(int initialVerbCount = this->countVerbs());
- const int kVerbs = startsWithConic
- ? 9 // moveTo + 4x conicTo + 3x lineTo + close
- : 10; // moveTo + 4x lineTo + 4x conicTo + close
- this->incReserve(kVerbs);
- RRectPointIterator rrectIter(rrect, dir, startIndex);
- // Corner iterator indices follow the collapsed radii model,
- // adjusted such that the start pt is "behind" the radii start pt.
- const unsigned rectStartIndex = startIndex / 2 + (dir == kCW_Direction ? 0 : 1);
- RectPointIterator rectIter(bounds, dir, rectStartIndex);
- this->moveTo(rrectIter.current());
- if (startsWithConic) {
- for (unsigned i = 0; i < 3; ++i) {
- this->conicTo(rectIter.next(), rrectIter.next(), weight);
- this->lineTo(rrectIter.next());
- }
- this->conicTo(rectIter.next(), rrectIter.next(), weight);
- // final lineTo handled by close().
- } else {
- for (unsigned i = 0; i < 4; ++i) {
- this->lineTo(rrectIter.next());
- this->conicTo(rectIter.next(), rrectIter.next(), weight);
- }
- }
- this->close();
- SkPathRef::Editor ed(&fPathRef);
- ed.setIsRRect(isRRect, dir, startIndex % 8);
- SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
- }
- SkDEBUGCODE(fPathRef->validate();)
- return *this;
- }
- bool SkPath::hasOnlyMoveTos() const {
- int count = fPathRef->countVerbs();
- const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin();
- for (int i = 0; i < count; ++i) {
- if (*verbs == kLine_Verb ||
- *verbs == kQuad_Verb ||
- *verbs == kConic_Verb ||
- *verbs == kCubic_Verb) {
- return false;
- }
- ++verbs;
- }
- return true;
- }
- bool SkPath::isZeroLengthSincePoint(int startPtIndex) const {
- int count = fPathRef->countPoints() - startPtIndex;
- if (count < 2) {
- return true;
- }
- const SkPoint* pts = fPathRef.get()->points() + startPtIndex;
- const SkPoint& first = *pts;
- for (int index = 1; index < count; ++index) {
- if (first != pts[index]) {
- return false;
- }
- }
- return true;
- }
- SkPath& SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
- Direction dir) {
- assert_known_direction(dir);
- if (rx < 0 || ry < 0) {
- return *this;
- }
- SkRRect rrect;
- rrect.setRectXY(rect, rx, ry);
- return this->addRRect(rrect, dir);
- }
- SkPath& SkPath::addOval(const SkRect& oval, Direction dir) {
- // legacy start index: 1
- return this->addOval(oval, dir, 1);
- }
- SkPath& SkPath::addOval(const SkRect &oval, Direction dir, unsigned startPointIndex) {
- assert_known_direction(dir);
- /* If addOval() is called after previous moveTo(),
- this path is still marked as an oval. This is used to
- fit into WebKit's calling sequences.
- We can't simply check isEmpty() in this case, as additional
- moveTo() would mark the path non empty.
- */
- bool isOval = hasOnlyMoveTos();
- if (isOval) {
- this->setFirstDirection((SkPathPriv::FirstDirection)dir);
- } else {
- this->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
- }
- SkAutoDisableDirectionCheck addc(this);
- SkAutoPathBoundsUpdate apbu(this, oval);
- SkDEBUGCODE(int initialVerbCount = this->countVerbs());
- const int kVerbs = 6; // moveTo + 4x conicTo + close
- this->incReserve(kVerbs);
- OvalPointIterator ovalIter(oval, dir, startPointIndex);
- // The corner iterator pts are tracking "behind" the oval/radii pts.
- RectPointIterator rectIter(oval, dir, startPointIndex + (dir == kCW_Direction ? 0 : 1));
- const SkScalar weight = SK_ScalarRoot2Over2;
- this->moveTo(ovalIter.current());
- for (unsigned i = 0; i < 4; ++i) {
- this->conicTo(rectIter.next(), ovalIter.next(), weight);
- }
- this->close();
- SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
- SkPathRef::Editor ed(&fPathRef);
- ed.setIsOval(isOval, kCCW_Direction == dir, startPointIndex % 4);
- return *this;
- }
- SkPath& SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
- if (r > 0) {
- this->addOval(SkRect::MakeLTRB(x - r, y - r, x + r, y + r), dir);
- }
- return *this;
- }
- SkPath& SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
- bool forceMoveTo) {
- if (oval.width() < 0 || oval.height() < 0) {
- return *this;
- }
- if (fPathRef->countVerbs() == 0) {
- forceMoveTo = true;
- }
- SkPoint lonePt;
- if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) {
- return forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt);
- }
- SkVector startV, stopV;
- SkRotationDirection dir;
- angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir);
- SkPoint singlePt;
- // Adds a move-to to 'pt' if forceMoveTo is true. Otherwise a lineTo unless we're sufficiently
- // close to 'pt' currently. This prevents spurious lineTos when adding a series of contiguous
- // arcs from the same oval.
- auto addPt = [&forceMoveTo, this](const SkPoint& pt) {
- SkPoint lastPt;
- if (forceMoveTo) {
- this->moveTo(pt);
- } else if (!this->getLastPt(&lastPt) ||
- !SkScalarNearlyEqual(lastPt.fX, pt.fX) ||
- !SkScalarNearlyEqual(lastPt.fY, pt.fY)) {
- this->lineTo(pt);
- }
- };
- // At this point, we know that the arc is not a lone point, but startV == stopV
- // indicates that the sweepAngle is too small such that angles_to_unit_vectors
- // cannot handle it.
- if (startV == stopV) {
- SkScalar endAngle = SkDegreesToRadians(startAngle + sweepAngle);
- SkScalar radiusX = oval.width() / 2;
- SkScalar radiusY = oval.height() / 2;
- // We do not use SkScalar[Sin|Cos]SnapToZero here. When sin(startAngle) is 0 and sweepAngle
- // is very small and radius is huge, the expected behavior here is to draw a line. But
- // calling SkScalarSinSnapToZero will make sin(endAngle) be 0 which will then draw a dot.
- singlePt.set(oval.centerX() + radiusX * SkScalarCos(endAngle),
- oval.centerY() + radiusY * SkScalarSin(endAngle));
- addPt(singlePt);
- return *this;
- }
- SkConic conics[SkConic::kMaxConicsForArc];
- int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt);
- if (count) {
- this->incReserve(count * 2 + 1);
- const SkPoint& pt = conics[0].fPts[0];
- addPt(pt);
- for (int i = 0; i < count; ++i) {
- this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW);
- }
- } else {
- addPt(singlePt);
- }
- return *this;
- }
- // This converts the SVG arc to conics.
- // Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
- // Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic()
- // See also SVG implementation notes:
- // http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
- // Note that arcSweep bool value is flipped from the original implementation.
- SkPath& SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge,
- SkPath::Direction arcSweep, SkScalar x, SkScalar y) {
- this->injectMoveToIfNeeded();
- SkPoint srcPts[2];
- this->getLastPt(&srcPts[0]);
- // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto")
- // joining the endpoints.
- // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
- if (!rx || !ry) {
- return this->lineTo(x, y);
- }
- // If the current point and target point for the arc are identical, it should be treated as a
- // zero length path. This ensures continuity in animations.
- srcPts[1].set(x, y);
- if (srcPts[0] == srcPts[1]) {
- return this->lineTo(x, y);
- }
- rx = SkScalarAbs(rx);
- ry = SkScalarAbs(ry);
- SkVector midPointDistance = srcPts[0] - srcPts[1];
- midPointDistance *= 0.5f;
- SkMatrix pointTransform;
- pointTransform.setRotate(-angle);
- SkPoint transformedMidPoint;
- pointTransform.mapPoints(&transformedMidPoint, &midPointDistance, 1);
- SkScalar squareRx = rx * rx;
- SkScalar squareRy = ry * ry;
- SkScalar squareX = transformedMidPoint.fX * transformedMidPoint.fX;
- SkScalar squareY = transformedMidPoint.fY * transformedMidPoint.fY;
- // Check if the radii are big enough to draw the arc, scale radii if not.
- // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
- SkScalar radiiScale = squareX / squareRx + squareY / squareRy;
- if (radiiScale > 1) {
- radiiScale = SkScalarSqrt(radiiScale);
- rx *= radiiScale;
- ry *= radiiScale;
- }
- pointTransform.setScale(1 / rx, 1 / ry);
- pointTransform.preRotate(-angle);
- SkPoint unitPts[2];
- pointTransform.mapPoints(unitPts, srcPts, (int) SK_ARRAY_COUNT(unitPts));
- SkVector delta = unitPts[1] - unitPts[0];
- SkScalar d = delta.fX * delta.fX + delta.fY * delta.fY;
- SkScalar scaleFactorSquared = SkTMax(1 / d - 0.25f, 0.f);
- SkScalar scaleFactor = SkScalarSqrt(scaleFactorSquared);
- if (SkToBool(arcSweep) != SkToBool(arcLarge)) { // flipped from the original implementation
- scaleFactor = -scaleFactor;
- }
- delta.scale(scaleFactor);
- SkPoint centerPoint = unitPts[0] + unitPts[1];
- centerPoint *= 0.5f;
- centerPoint.offset(-delta.fY, delta.fX);
- unitPts[0] -= centerPoint;
- unitPts[1] -= centerPoint;
- SkScalar theta1 = SkScalarATan2(unitPts[0].fY, unitPts[0].fX);
- SkScalar theta2 = SkScalarATan2(unitPts[1].fY, unitPts[1].fX);
- SkScalar thetaArc = theta2 - theta1;
- if (thetaArc < 0 && !arcSweep) { // arcSweep flipped from the original implementation
- thetaArc += SK_ScalarPI * 2;
- } else if (thetaArc > 0 && arcSweep) { // arcSweep flipped from the original implementation
- thetaArc -= SK_ScalarPI * 2;
- }
- pointTransform.setRotate(angle);
- pointTransform.preScale(rx, ry);
- // the arc may be slightly bigger than 1/4 circle, so allow up to 1/3rd
- int segments = SkScalarCeilToInt(SkScalarAbs(thetaArc / (2 * SK_ScalarPI / 3)));
- SkScalar thetaWidth = thetaArc / segments;
- SkScalar t = SkScalarTan(0.5f * thetaWidth);
- if (!SkScalarIsFinite(t)) {
- return *this;
- }
- SkScalar startTheta = theta1;
- SkScalar w = SkScalarSqrt(SK_ScalarHalf + SkScalarCos(thetaWidth) * SK_ScalarHalf);
- auto scalar_is_integer = [](SkScalar scalar) -> bool {
- return scalar == SkScalarFloorToScalar(scalar);
- };
- bool expectIntegers = SkScalarNearlyZero(SK_ScalarPI/2 - SkScalarAbs(thetaWidth)) &&
- scalar_is_integer(rx) && scalar_is_integer(ry) &&
- scalar_is_integer(x) && scalar_is_integer(y);
- for (int i = 0; i < segments; ++i) {
- SkScalar endTheta = startTheta + thetaWidth,
- sinEndTheta = SkScalarSinSnapToZero(endTheta),
- cosEndTheta = SkScalarCosSnapToZero(endTheta);
- unitPts[1].set(cosEndTheta, sinEndTheta);
- unitPts[1] += centerPoint;
- unitPts[0] = unitPts[1];
- unitPts[0].offset(t * sinEndTheta, -t * cosEndTheta);
- SkPoint mapped[2];
- pointTransform.mapPoints(mapped, unitPts, (int) SK_ARRAY_COUNT(unitPts));
- /*
- Computing the arc width introduces rounding errors that cause arcs to start
- outside their marks. A round rect may lose convexity as a result. If the input
- values are on integers, place the conic on integers as well.
- */
- if (expectIntegers) {
- SkScalar* mappedScalars = &mapped[0].fX;
- for (unsigned index = 0; index < sizeof(mapped) / sizeof(SkScalar); ++index) {
- mappedScalars[index] = SkScalarRoundToScalar(mappedScalars[index]);
- }
- }
- this->conicTo(mapped[0], mapped[1], w);
- startTheta = endTheta;
- }
- return *this;
- }
- SkPath& SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc,
- SkPath::Direction sweep, SkScalar dx, SkScalar dy) {
- SkPoint currentPoint;
- this->getLastPt(¤tPoint);
- return this->arcTo(rx, ry, xAxisRotate, largeArc, sweep,
- currentPoint.fX + dx, currentPoint.fY + dy);
- }
- SkPath& SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
- if (oval.isEmpty() || 0 == sweepAngle) {
- return *this;
- }
- const SkScalar kFullCircleAngle = SkIntToScalar(360);
- if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
- // We can treat the arc as an oval if it begins at one of our legal starting positions.
- // See SkPath::addOval() docs.
- SkScalar startOver90 = startAngle / 90.f;
- SkScalar startOver90I = SkScalarRoundToScalar(startOver90);
- SkScalar error = startOver90 - startOver90I;
- if (SkScalarNearlyEqual(error, 0)) {
- // Index 1 is at startAngle == 0.
- SkScalar startIndex = std::fmod(startOver90I + 1.f, 4.f);
- startIndex = startIndex < 0 ? startIndex + 4.f : startIndex;
- return this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction,
- (unsigned) startIndex);
- }
- }
- return this->arcTo(oval, startAngle, sweepAngle, true);
- }
- /*
- Need to handle the case when the angle is sharp, and our computed end-points
- for the arc go behind pt1 and/or p2...
- */
- SkPath& SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) {
- if (radius == 0) {
- return this->lineTo(x1, y1);
- }
- // need to know our prev pt so we can construct tangent vectors
- SkPoint start;
- this->getLastPt(&start);
- // need double precision for these calcs.
- SkDVector befored, afterd;
- befored.set({x1 - start.fX, y1 - start.fY}).normalize();
- afterd.set({x2 - x1, y2 - y1}).normalize();
- double cosh = befored.dot(afterd);
- double sinh = befored.cross(afterd);
- if (!befored.isFinite() || !afterd.isFinite() || SkScalarNearlyZero(SkDoubleToScalar(sinh))) {
- return this->lineTo(x1, y1);
- }
- // safe to convert back to floats now
- SkVector before = befored.asSkVector();
- SkVector after = afterd.asSkVector();
- SkScalar dist = SkScalarAbs(SkDoubleToScalar(radius * (1 - cosh) / sinh));
- SkScalar xx = x1 - dist * before.fX;
- SkScalar yy = y1 - dist * before.fY;
- after.setLength(dist);
- this->lineTo(xx, yy);
- SkScalar weight = SkScalarSqrt(SkDoubleToScalar(SK_ScalarHalf + cosh * 0.5));
- return this->conicTo(x1, y1, x1 + after.fX, y1 + after.fY, weight);
- }
- ///////////////////////////////////////////////////////////////////////////////
- SkPath& SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
- SkMatrix matrix;
- matrix.setTranslate(dx, dy);
- return this->addPath(path, matrix, mode);
- }
- SkPath& SkPath::addPath(const SkPath& srcPath, const SkMatrix& matrix, AddPathMode mode) {
- // Detect if we're trying to add ourself
- const SkPath* src = &srcPath;
- SkTLazy<SkPath> tmp;
- if (this == src) {
- src = tmp.set(srcPath);
- }
- SkPathRef::Editor(&fPathRef, src->countVerbs(), src->countPoints());
- RawIter iter(*src);
- SkPoint pts[4];
- Verb verb;
- SkMatrixPriv::MapPtsProc proc = SkMatrixPriv::GetMapPtsProc(matrix);
- bool firstVerb = true;
- while ((verb = iter.next(pts)) != kDone_Verb) {
- switch (verb) {
- case kMove_Verb:
- proc(matrix, &pts[0], &pts[0], 1);
- if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) {
- injectMoveToIfNeeded(); // In case last contour is closed
- SkPoint lastPt;
- // don't add lineTo if it is degenerate
- if (fLastMoveToIndex < 0 || !this->getLastPt(&lastPt) || lastPt != pts[0]) {
- this->lineTo(pts[0]);
- }
- } else {
- this->moveTo(pts[0]);
- }
- break;
- case kLine_Verb:
- proc(matrix, &pts[1], &pts[1], 1);
- this->lineTo(pts[1]);
- break;
- case kQuad_Verb:
- proc(matrix, &pts[1], &pts[1], 2);
- this->quadTo(pts[1], pts[2]);
- break;
- case kConic_Verb:
- proc(matrix, &pts[1], &pts[1], 2);
- this->conicTo(pts[1], pts[2], iter.conicWeight());
- break;
- case kCubic_Verb:
- proc(matrix, &pts[1], &pts[1], 3);
- this->cubicTo(pts[1], pts[2], pts[3]);
- break;
- case kClose_Verb:
- this->close();
- break;
- default:
- SkDEBUGFAIL("unknown verb");
- }
- firstVerb = false;
- }
- return *this;
- }
- ///////////////////////////////////////////////////////////////////////////////
- static int pts_in_verb(unsigned verb) {
- static const uint8_t gPtsInVerb[] = {
- 1, // kMove
- 1, // kLine
- 2, // kQuad
- 2, // kConic
- 3, // kCubic
- 0, // kClose
- 0 // kDone
- };
- SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
- return gPtsInVerb[verb];
- }
- // ignore the last point of the 1st contour
- SkPath& SkPath::reversePathTo(const SkPath& path) {
- const uint8_t* verbs = path.fPathRef->verbsMemBegin(); // points at the last verb
- if (!verbs) { // empty path returns nullptr
- return *this;
- }
- const uint8_t* verbsEnd = path.fPathRef->verbs() - 1; // points just past the first verb
- SkASSERT(verbsEnd[0] == kMove_Verb);
- const SkPoint* pts = path.fPathRef->pointsEnd() - 1;
- const SkScalar* conicWeights = path.fPathRef->conicWeightsEnd();
- while (verbs < verbsEnd) {
- uint8_t v = *verbs++;
- pts -= pts_in_verb(v);
- switch (v) {
- case kMove_Verb:
- // if the path has multiple contours, stop after reversing the last
- return *this;
- case kLine_Verb:
- this->lineTo(pts[0]);
- break;
- case kQuad_Verb:
- this->quadTo(pts[1], pts[0]);
- break;
- case kConic_Verb:
- this->conicTo(pts[1], pts[0], *--conicWeights);
- break;
- case kCubic_Verb:
- this->cubicTo(pts[2], pts[1], pts[0]);
- break;
- case kClose_Verb:
- SkASSERT(verbs - path.fPathRef->verbsMemBegin() == 1);
- break;
- default:
- SkDEBUGFAIL("bad verb");
- break;
- }
- }
- return *this;
- }
- SkPath& SkPath::reverseAddPath(const SkPath& srcPath) {
- // Detect if we're trying to add ourself
- const SkPath* src = &srcPath;
- SkTLazy<SkPath> tmp;
- if (this == src) {
- src = tmp.set(srcPath);
- }
- SkPathRef::Editor ed(&fPathRef, src->countVerbs(), src->countPoints());
- const SkPoint* pts = src->fPathRef->pointsEnd();
- // we will iterate through src's verbs backwards
- const uint8_t* verbs = src->fPathRef->verbsMemBegin(); // points at the last verb
- const uint8_t* verbsEnd = src->fPathRef->verbs(); // points just past the first verb
- const SkScalar* conicWeights = src->fPathRef->conicWeightsEnd();
- bool needMove = true;
- bool needClose = false;
- while (verbs < verbsEnd) {
- uint8_t v = *(verbs++);
- int n = pts_in_verb(v);
- if (needMove) {
- --pts;
- this->moveTo(pts->fX, pts->fY);
- needMove = false;
- }
- pts -= n;
- switch (v) {
- case kMove_Verb:
- if (needClose) {
- this->close();
- needClose = false;
- }
- needMove = true;
- pts += 1; // so we see the point in "if (needMove)" above
- break;
- case kLine_Verb:
- this->lineTo(pts[0]);
- break;
- case kQuad_Verb:
- this->quadTo(pts[1], pts[0]);
- break;
- case kConic_Verb:
- this->conicTo(pts[1], pts[0], *--conicWeights);
- break;
- case kCubic_Verb:
- this->cubicTo(pts[2], pts[1], pts[0]);
- break;
- case kClose_Verb:
- needClose = true;
- break;
- default:
- SkDEBUGFAIL("unexpected verb");
- }
- }
- return *this;
- }
- ///////////////////////////////////////////////////////////////////////////////
- void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
- SkMatrix matrix;
- matrix.setTranslate(dx, dy);
- this->transform(matrix, dst);
- }
- static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
- int level = 2) {
- if (--level >= 0) {
- SkPoint tmp[7];
- SkChopCubicAtHalf(pts, tmp);
- subdivide_cubic_to(path, &tmp[0], level);
- subdivide_cubic_to(path, &tmp[3], level);
- } else {
- path->cubicTo(pts[1], pts[2], pts[3]);
- }
- }
- void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
- if (matrix.isIdentity()) {
- if (dst != nullptr && dst != this) {
- *dst = *this;
- }
- return;
- }
- SkDEBUGCODE(this->validate();)
- if (dst == nullptr) {
- dst = (SkPath*)this;
- }
- if (matrix.hasPerspective()) {
- SkPath tmp;
- tmp.fFillType = fFillType;
- SkPath::Iter iter(*this, false);
- SkPoint pts[4];
- SkPath::Verb verb;
- while ((verb = iter.next(pts, false)) != kDone_Verb) {
- switch (verb) {
- case kMove_Verb:
- tmp.moveTo(pts[0]);
- break;
- case kLine_Verb:
- tmp.lineTo(pts[1]);
- break;
- case kQuad_Verb:
- // promote the quad to a conic
- tmp.conicTo(pts[1], pts[2],
- SkConic::TransformW(pts, SK_Scalar1, matrix));
- break;
- case kConic_Verb:
- tmp.conicTo(pts[1], pts[2],
- SkConic::TransformW(pts, iter.conicWeight(), matrix));
- break;
- case kCubic_Verb:
- subdivide_cubic_to(&tmp, pts);
- break;
- case kClose_Verb:
- tmp.close();
- break;
- default:
- SkDEBUGFAIL("unknown verb");
- break;
- }
- }
- dst->swap(tmp);
- SkPathRef::Editor ed(&dst->fPathRef);
- matrix.mapPoints(ed.points(), ed.pathRef()->countPoints());
- dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
- } else {
- Convexity convexity = this->getConvexityOrUnknown();
- SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
- if (this != dst) {
- dst->fLastMoveToIndex = fLastMoveToIndex;
- dst->fFillType = fFillType;
- dst->fIsVolatile = fIsVolatile;
- }
- // Due to finite/fragile float numerics, we can't assume that a convex path remains
- // convex after a transformation, so mark it as unknown here.
- // However, some transformations are thought to be safe:
- // axis-aligned values under scale/translate.
- //
- // See skbug.com/8606
- // If we can land a robust convex scan-converter, we may be able to relax/remove this
- // check, and keep convex paths marked as such after a general transform...
- //
- if (matrix.isScaleTranslate() && SkPathPriv::IsAxisAligned(*this)) {
- dst->setConvexity(convexity);
- } else {
- dst->setConvexity(kUnknown_Convexity);
- }
- if (this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
- dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
- } else {
- SkScalar det2x2 =
- matrix.get(SkMatrix::kMScaleX) * matrix.get(SkMatrix::kMScaleY) -
- matrix.get(SkMatrix::kMSkewX) * matrix.get(SkMatrix::kMSkewY);
- if (det2x2 < 0) {
- dst->setFirstDirection(
- SkPathPriv::OppositeFirstDirection(
- (SkPathPriv::FirstDirection)this->getFirstDirection()));
- } else if (det2x2 > 0) {
- dst->setFirstDirection(this->getFirstDirection());
- } else {
- dst->setFirstDirection(SkPathPriv::kUnknown_FirstDirection);
- }
- }
- SkDEBUGCODE(dst->validate();)
- }
- }
- ///////////////////////////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////////
- SkPath::Iter::Iter() {
- #ifdef SK_DEBUG
- fPts = nullptr;
- fConicWeights = nullptr;
- fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
- fForceClose = fCloseLine = false;
- fSegmentState = kEmptyContour_SegmentState;
- #endif
- // need to init enough to make next() harmlessly return kDone_Verb
- fVerbs = nullptr;
- fVerbStop = nullptr;
- fNeedClose = false;
- }
- SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
- this->setPath(path, forceClose);
- }
- void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
- fPts = path.fPathRef->points();
- fVerbs = path.fPathRef->verbs();
- fVerbStop = path.fPathRef->verbsMemBegin();
- fConicWeights = path.fPathRef->conicWeights();
- if (fConicWeights) {
- fConicWeights -= 1; // begin one behind
- }
- fLastPt.fX = fLastPt.fY = 0;
- fMoveTo.fX = fMoveTo.fY = 0;
- fForceClose = SkToU8(forceClose);
- fNeedClose = false;
- fSegmentState = kEmptyContour_SegmentState;
- }
- bool SkPath::Iter::isClosedContour() const {
- if (fVerbs == nullptr || fVerbs == fVerbStop) {
- return false;
- }
- if (fForceClose) {
- return true;
- }
- const uint8_t* verbs = fVerbs;
- const uint8_t* stop = fVerbStop;
- if (kMove_Verb == *(verbs - 1)) {
- verbs -= 1; // skip the initial moveto
- }
- while (verbs > stop) {
- // verbs points one beyond the current verb, decrement first.
- unsigned v = *(--verbs);
- if (kMove_Verb == v) {
- break;
- }
- if (kClose_Verb == v) {
- return true;
- }
- }
- return false;
- }
- SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
- SkASSERT(pts);
- if (fLastPt != fMoveTo) {
- // A special case: if both points are NaN, SkPoint::operation== returns
- // false, but the iterator expects that they are treated as the same.
- // (consider SkPoint is a 2-dimension float point).
- if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
- SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
- return kClose_Verb;
- }
- pts[0] = fLastPt;
- pts[1] = fMoveTo;
- fLastPt = fMoveTo;
- fCloseLine = true;
- return kLine_Verb;
- } else {
- pts[0] = fMoveTo;
- return kClose_Verb;
- }
- }
- const SkPoint& SkPath::Iter::cons_moveTo() {
- if (fSegmentState == kAfterMove_SegmentState) {
- // Set the first return pt to the move pt
- fSegmentState = kAfterPrimitive_SegmentState;
- return fMoveTo;
- }
- SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
- // Set the first return pt to the last pt of the previous primitive.
- return fPts[-1];
- }
- void SkPath::Iter::consumeDegenerateSegments(bool exact) {
- // We need to step over anything that will not move the current draw point
- // forward before the next move is seen
- const uint8_t* lastMoveVerb = nullptr;
- const SkPoint* lastMovePt = nullptr;
- const SkScalar* lastMoveWeight = nullptr;
- SkPoint lastPt = fLastPt;
- while (fVerbs != fVerbStop) {
- unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb
- switch (verb) {
- case kMove_Verb:
- // Keep a record of this most recent move
- lastMoveVerb = fVerbs;
- lastMovePt = fPts;
- lastMoveWeight = fConicWeights;
- lastPt = fPts[0];
- fVerbs--;
- fPts++;
- break;
- case kClose_Verb:
- // A close when we are in a segment is always valid except when it
- // follows a move which follows a segment.
- if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) {
- return;
- }
- // A close at any other time must be ignored
- fVerbs--;
- break;
- case kLine_Verb:
- if (!IsLineDegenerate(lastPt, fPts[0], exact)) {
- if (lastMoveVerb) {
- fVerbs = lastMoveVerb;
- fPts = lastMovePt;
- fConicWeights = lastMoveWeight;
- return;
- }
- return;
- }
- // Ignore this line and continue
- fVerbs--;
- fPts++;
- break;
- case kConic_Verb:
- case kQuad_Verb:
- if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1], exact)) {
- if (lastMoveVerb) {
- fVerbs = lastMoveVerb;
- fPts = lastMovePt;
- fConicWeights = lastMoveWeight;
- return;
- }
- return;
- }
- // Ignore this line and continue
- fVerbs--;
- fPts += 2;
- fConicWeights += (kConic_Verb == verb);
- break;
- case kCubic_Verb:
- if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2], exact)) {
- if (lastMoveVerb) {
- fVerbs = lastMoveVerb;
- fPts = lastMovePt;
- fConicWeights = lastMoveWeight;
- return;
- }
- return;
- }
- // Ignore this line and continue
- fVerbs--;
- fPts += 3;
- break;
- default:
- SkDEBUGFAIL("Should never see kDone_Verb");
- }
- }
- }
- SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
- SkASSERT(ptsParam);
- if (fVerbs == fVerbStop) {
- // Close the curve if requested and if there is some curve to close
- if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
- if (kLine_Verb == this->autoClose(ptsParam)) {
- return kLine_Verb;
- }
- fNeedClose = false;
- return kClose_Verb;
- }
- return kDone_Verb;
- }
- // fVerbs is one beyond the current verb, decrement first
- unsigned verb = *(--fVerbs);
- const SkPoint* SK_RESTRICT srcPts = fPts;
- SkPoint* SK_RESTRICT pts = ptsParam;
- switch (verb) {
- case kMove_Verb:
- if (fNeedClose) {
- fVerbs++; // move back one verb
- verb = this->autoClose(pts);
- if (verb == kClose_Verb) {
- fNeedClose = false;
- }
- return (Verb)verb;
- }
- if (fVerbs == fVerbStop) { // might be a trailing moveto
- return kDone_Verb;
- }
- fMoveTo = *srcPts;
- pts[0] = *srcPts;
- srcPts += 1;
- fSegmentState = kAfterMove_SegmentState;
- fLastPt = fMoveTo;
- fNeedClose = fForceClose;
- break;
- case kLine_Verb:
- pts[0] = this->cons_moveTo();
- pts[1] = srcPts[0];
- fLastPt = srcPts[0];
- fCloseLine = false;
- srcPts += 1;
- break;
- case kConic_Verb:
- fConicWeights += 1;
- // fall-through
- case kQuad_Verb:
- pts[0] = this->cons_moveTo();
- memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
- fLastPt = srcPts[1];
- srcPts += 2;
- break;
- case kCubic_Verb:
- pts[0] = this->cons_moveTo();
- memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
- fLastPt = srcPts[2];
- srcPts += 3;
- break;
- case kClose_Verb:
- verb = this->autoClose(pts);
- if (verb == kLine_Verb) {
- fVerbs++; // move back one verb
- } else {
- fNeedClose = false;
- fSegmentState = kEmptyContour_SegmentState;
- }
- fLastPt = fMoveTo;
- break;
- }
- fPts = srcPts;
- return (Verb)verb;
- }
- ///////////////////////////////////////////////////////////////////////////////
- #include "include/core/SkStream.h"
- #include "include/core/SkString.h"
- #include "src/core/SkStringUtils.h"
- static void append_params(SkString* str, const char label[], const SkPoint pts[],
- int count, SkScalarAsStringType strType, SkScalar conicWeight = -12345) {
- str->append(label);
- str->append("(");
- const SkScalar* values = &pts[0].fX;
- count *= 2;
- for (int i = 0; i < count; ++i) {
- SkAppendScalar(str, values[i], strType);
- if (i < count - 1) {
- str->append(", ");
- }
- }
- if (conicWeight != -12345) {
- str->append(", ");
- SkAppendScalar(str, conicWeight, strType);
- }
- str->append(");");
- if (kHex_SkScalarAsStringType == strType) {
- str->append(" // ");
- for (int i = 0; i < count; ++i) {
- SkAppendScalarDec(str, values[i]);
- if (i < count - 1) {
- str->append(", ");
- }
- }
- if (conicWeight >= 0) {
- str->append(", ");
- SkAppendScalarDec(str, conicWeight);
- }
- }
- str->append("\n");
- }
- void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
- SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
- Iter iter(*this, forceClose);
- SkPoint pts[4];
- Verb verb;
- SkString builder;
- char const * const gFillTypeStrs[] = {
- "Winding",
- "EvenOdd",
- "InverseWinding",
- "InverseEvenOdd",
- };
- builder.printf("path.setFillType(SkPath::k%s_FillType);\n",
- gFillTypeStrs[(int) this->getFillType()]);
- while ((verb = iter.next(pts, false)) != kDone_Verb) {
- switch (verb) {
- case kMove_Verb:
- append_params(&builder, "path.moveTo", &pts[0], 1, asType);
- break;
- case kLine_Verb:
- append_params(&builder, "path.lineTo", &pts[1], 1, asType);
- break;
- case kQuad_Verb:
- append_params(&builder, "path.quadTo", &pts[1], 2, asType);
- break;
- case kConic_Verb:
- append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight());
- break;
- case kCubic_Verb:
- append_params(&builder, "path.cubicTo", &pts[1], 3, asType);
- break;
- case kClose_Verb:
- builder.append("path.close();\n");
- break;
- default:
- SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb);
- verb = kDone_Verb; // stop the loop
- break;
- }
- if (!wStream && builder.size()) {
- SkDebugf("%s", builder.c_str());
- builder.reset();
- }
- }
- if (wStream) {
- wStream->writeText(builder.c_str());
- }
- }
- void SkPath::dump() const {
- this->dump(nullptr, false, false);
- }
- void SkPath::dumpHex() const {
- this->dump(nullptr, false, true);
- }
- bool SkPath::isValidImpl() const {
- if ((fFillType & ~3) != 0) {
- return false;
- }
- #ifdef SK_DEBUG_PATH
- if (!fBoundsIsDirty) {
- SkRect bounds;
- bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
- if (SkToBool(fIsFinite) != isFinite) {
- return false;
- }
- if (fPathRef->countPoints() <= 1) {
- // if we're empty, fBounds may be empty but translated, so we can't
- // necessarily compare to bounds directly
- // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
- // be [2, 2, 2, 2]
- if (!bounds.isEmpty() || !fBounds.isEmpty()) {
- return false;
- }
- } else {
- if (bounds.isEmpty()) {
- if (!fBounds.isEmpty()) {
- return false;
- }
- } else {
- if (!fBounds.isEmpty()) {
- if (!fBounds.contains(bounds)) {
- return false;
- }
- }
- }
- }
- }
- #endif // SK_DEBUG_PATH
- return true;
- }
- ///////////////////////////////////////////////////////////////////////////////
- #ifdef SK_LEGACY_PATH_CONVEXITY // for rebaselining Chrome
- static int sign(SkScalar x) { return x < 0; }
- #define kValueNeverReturnedBySign 2
- enum DirChange {
- kLeft_DirChange,
- kRight_DirChange,
- kStraight_DirChange,
- kBackwards_DirChange,
- kInvalid_DirChange
- };
- static bool almost_equal(SkScalar compA, SkScalar compB) {
- // The error epsilon was empirically derived; worse case round rects
- // with a mid point outset by 2x float epsilon in tests had an error
- // of 12.
- const int epsilon = 16;
- if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
- return false;
- }
- // no need to check for small numbers because SkPath::Iter has removed degenerate values
- int aBits = SkFloatAs2sCompliment(compA);
- int bBits = SkFloatAs2sCompliment(compB);
- return aBits < bBits + epsilon && bBits < aBits + epsilon;
- }
- // only valid for a single contour
- struct Convexicator {
- Convexicator()
- : fPtCount(0)
- , fConvexity(SkPath::kConvex_Convexity)
- , fFirstDirection(SkPathPriv::kUnknown_FirstDirection)
- , fIsFinite(true)
- , fIsCurve(false)
- , fBackwards(false) {
- fExpectedDir = kInvalid_DirChange;
- // warnings
- fPriorPt.set(0,0);
- fLastPt.set(0, 0);
- fCurrPt.set(0, 0);
- fLastVec.set(0, 0);
- fFirstVec.set(0, 0);
- fDx = fDy = 0;
- fSx = fSy = kValueNeverReturnedBySign;
- }
- SkPath::Convexity getConvexity() const { return fConvexity; }
- /** The direction returned is only valid if the path is determined convex */
- SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; }
- void addPt(const SkPoint& pt) {
- if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) {
- return;
- }
- if (0 == fPtCount) {
- fCurrPt = pt;
- ++fPtCount;
- } else {
- SkVector vec = pt - fCurrPt;
- SkScalar lengthSqd = SkPointPriv::LengthSqd(vec);
- if (!SkScalarIsFinite(lengthSqd)) {
- fIsFinite = false;
- } else if (lengthSqd) {
- fPriorPt = fLastPt;
- fLastPt = fCurrPt;
- fCurrPt = pt;
- if (++fPtCount == 2) {
- fFirstVec = fLastVec = vec;
- } else {
- SkASSERT(fPtCount > 2);
- this->addVec(vec);
- }
- int sx = sign(vec.fX);
- int sy = sign(vec.fY);
- fDx += (sx != fSx);
- fDy += (sy != fSy);
- fSx = sx;
- fSy = sy;
- if (fDx > 3 || fDy > 3) {
- fConvexity = SkPath::kConcave_Convexity;
- }
- }
- }
- }
- void close() {
- if (fPtCount > 2) {
- this->addVec(fFirstVec);
- }
- }
- DirChange directionChange(const SkVector& curVec) {
- SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
- SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
- SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
- largest = SkTMax(largest, -smallest);
- if (!almost_equal(largest, largest + cross)) {
- int sign = SkScalarSignAsInt(cross);
- if (sign) {
- return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
- }
- }
- if (cross) {
- double dLastVecX = SkScalarToDouble(fLastPt.fX) - SkScalarToDouble(fPriorPt.fX);
- double dLastVecY = SkScalarToDouble(fLastPt.fY) - SkScalarToDouble(fPriorPt.fY);
- double dCurrVecX = SkScalarToDouble(fCurrPt.fX) - SkScalarToDouble(fLastPt.fX);
- double dCurrVecY = SkScalarToDouble(fCurrPt.fY) - SkScalarToDouble(fLastPt.fY);
- double dCross = dLastVecX * dCurrVecY - dLastVecY * dCurrVecX;
- if (!approximately_zero_when_compared_to(dCross, SkScalarToDouble(largest))) {
- int sign = SkScalarSignAsInt(SkDoubleToScalar(dCross));
- if (sign) {
- return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
- }
- }
- }
- if (!SkScalarNearlyZero(SkPointPriv::LengthSqd(fLastVec),
- SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
- !SkScalarNearlyZero(SkPointPriv::LengthSqd(curVec),
- SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
- fLastVec.dot(curVec) < 0.0f) {
- return kBackwards_DirChange;
- }
- return kStraight_DirChange;
- }
- bool hasBackwards() const {
- return fBackwards;
- }
- bool isFinite() const {
- return fIsFinite;
- }
- void setCurve(bool isCurve) {
- fIsCurve = isCurve;
- }
- private:
- void addVec(const SkVector& vec) {
- SkASSERT(vec.fX || vec.fY);
- DirChange dir = this->directionChange(vec);
- switch (dir) {
- case kLeft_DirChange: // fall through
- case kRight_DirChange:
- if (kInvalid_DirChange == fExpectedDir) {
- fExpectedDir = dir;
- fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection
- : SkPathPriv::kCCW_FirstDirection;
- } else if (dir != fExpectedDir) {
- fConvexity = SkPath::kConcave_Convexity;
- fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
- }
- fLastVec = vec;
- break;
- case kStraight_DirChange:
- break;
- case kBackwards_DirChange:
- if (fIsCurve) {
- // If any of the subsequent dir is non-backward, it'll be concave.
- // Otherwise, it's still convex.
- fExpectedDir = dir;
- }
- fLastVec = vec;
- fBackwards = true;
- break;
- case kInvalid_DirChange:
- SK_ABORT("Use of invalid direction change flag");
- break;
- }
- }
- SkPoint fPriorPt;
- SkPoint fLastPt;
- SkPoint fCurrPt;
- // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product
- // value with the current vec is deemed to be of a significant value.
- SkVector fLastVec, fFirstVec;
- int fPtCount; // non-degenerate points
- DirChange fExpectedDir;
- SkPath::Convexity fConvexity;
- SkPathPriv::FirstDirection fFirstDirection;
- int fDx, fDy, fSx, fSy;
- bool fIsFinite;
- bool fIsCurve;
- bool fBackwards;
- };
- SkPath::Convexity SkPath::internalGetConvexity() const {
- // Sometimes we think we need to calculate convexity but another thread already did.
- auto c = this->getConvexityOrUnknown();
- if (c != kUnknown_Convexity) {
- return c;
- }
- SkPoint pts[4];
- SkPath::Verb verb;
- SkPath::Iter iter(*this, true);
- int contourCount = 0;
- int count;
- Convexicator state;
- if (!isFinite()) {
- return kUnknown_Convexity;
- }
- while ((verb = iter.next(pts, false, false)) != SkPath::kDone_Verb) {
- switch (verb) {
- case kMove_Verb:
- if (++contourCount > 1) {
- this->setConvexity(kConcave_Convexity);
- return kConcave_Convexity;
- }
- pts[1] = pts[0];
- // fall through
- case kLine_Verb:
- count = 1;
- state.setCurve(false);
- break;
- case kQuad_Verb:
- // fall through
- case kConic_Verb:
- // fall through
- case kCubic_Verb:
- count = 2 + (kCubic_Verb == verb);
- // As an additional enhancement, this could set curve true only
- // if the curve is nonlinear
- state.setCurve(true);
- break;
- case kClose_Verb:
- state.setCurve(false);
- state.close();
- count = 0;
- break;
- default:
- SkDEBUGFAIL("bad verb");
- this->setConvexity(kConcave_Convexity);
- return kConcave_Convexity;
- }
- for (int i = 1; i <= count; i++) {
- state.addPt(pts[i]);
- }
- // early exit
- if (!state.isFinite()) {
- return kUnknown_Convexity;
- }
- if (kConcave_Convexity == state.getConvexity()) {
- this->setConvexity(kConcave_Convexity);
- return kConcave_Convexity;
- }
- }
- this->setConvexity(state.getConvexity());
- if (this->getConvexityOrUnknown() == kConvex_Convexity &&
- this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
- if (state.getFirstDirection() == SkPathPriv::kUnknown_FirstDirection
- && !this->getBounds().isEmpty()
- && !state.hasBackwards()) {
- this->setConvexity(Convexity::kConcave_Convexity);
- } else {
- this->setFirstDirection(state.getFirstDirection());
- }
- }
- return this->getConvexityOrUnknown();
- }
- #else
- static int sign(SkScalar x) { return x < 0; }
- #define kValueNeverReturnedBySign 2
- enum DirChange {
- kUnknown_DirChange,
- kLeft_DirChange,
- kRight_DirChange,
- kStraight_DirChange,
- kBackwards_DirChange, // if double back, allow simple lines to be convex
- kInvalid_DirChange
- };
- static bool almost_equal(SkScalar compA, SkScalar compB) {
- // The error epsilon was empirically derived; worse case round rects
- // with a mid point outset by 2x float epsilon in tests had an error
- // of 12.
- const int epsilon = 16;
- if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
- return false;
- }
- // no need to check for small numbers because SkPath::Iter has removed degenerate values
- int aBits = SkFloatAs2sCompliment(compA);
- int bBits = SkFloatAs2sCompliment(compB);
- return aBits < bBits + epsilon && bBits < aBits + epsilon;
- }
- // only valid for a single contour
- struct Convexicator {
- /** The direction returned is only valid if the path is determined convex */
- SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; }
- void setMovePt(const SkPoint& pt) {
- fPriorPt = fLastPt = fCurrPt = pt;
- }
- bool addPt(const SkPoint& pt) {
- if (fCurrPt == pt) {
- return true;
- }
- fCurrPt = pt;
- if (fPriorPt == fLastPt) { // should only be true for first non-zero vector
- fLastVec = fCurrPt - fLastPt;
- fFirstPt = pt;
- } else if (!this->addVec(fCurrPt - fLastPt)) {
- return false;
- }
- fPriorPt = fLastPt;
- fLastPt = fCurrPt;
- return true;
- }
- static SkPath::Convexity BySign(const SkPoint points[], int count) {
- const SkPoint* last = points + count;
- SkPoint currPt = *points++;
- SkPoint firstPt = currPt;
- int dxes = 0;
- int dyes = 0;
- int lastSx = kValueNeverReturnedBySign;
- int lastSy = kValueNeverReturnedBySign;
- for (int outerLoop = 0; outerLoop < 2; ++outerLoop ) {
- while (points != last) {
- SkVector vec = *points - currPt;
- if (!vec.isZero()) {
- // give up if vector construction failed
- if (!vec.isFinite()) {
- return SkPath::kUnknown_Convexity;
- }
- int sx = sign(vec.fX);
- int sy = sign(vec.fY);
- dxes += (sx != lastSx);
- dyes += (sy != lastSy);
- if (dxes > 3 || dyes > 3) {
- return SkPath::kConcave_Convexity;
- }
- lastSx = sx;
- lastSy = sy;
- }
- currPt = *points++;
- if (outerLoop) {
- break;
- }
- }
- points = &firstPt;
- }
- return SkPath::kConvex_Convexity; // that is, it may be convex, don't know yet
- }
- bool close() {
- return this->addPt(fFirstPt);
- }
- bool isFinite() const {
- return fIsFinite;
- }
- int reversals() const {
- return fReversals;
- }
- private:
- DirChange directionChange(const SkVector& curVec) {
- SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
- if (!SkScalarIsFinite(cross)) {
- return kUnknown_DirChange;
- }
- SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
- SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
- largest = SkTMax(largest, -smallest);
- if (almost_equal(largest, largest + cross)) {
- return fLastVec.dot(curVec) < 0 ? kBackwards_DirChange : kStraight_DirChange;
- }
- return 1 == SkScalarSignAsInt(cross) ? kRight_DirChange : kLeft_DirChange;
- }
- bool addVec(const SkVector& curVec) {
- DirChange dir = this->directionChange(curVec);
- switch (dir) {
- case kLeft_DirChange: // fall through
- case kRight_DirChange:
- if (kInvalid_DirChange == fExpectedDir) {
- fExpectedDir = dir;
- fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection
- : SkPathPriv::kCCW_FirstDirection;
- } else if (dir != fExpectedDir) {
- fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
- return false;
- }
- fLastVec = curVec;
- break;
- case kStraight_DirChange:
- break;
- case kBackwards_DirChange:
- // allow path to reverse direction twice
- // Given path.moveTo(0, 0); path.lineTo(1, 1);
- // - 1st reversal: direction change formed by line (0,0 1,1), line (1,1 0,0)
- // - 2nd reversal: direction change formed by line (1,1 0,0), line (0,0 1,1)
- fLastVec = curVec;
- return ++fReversals < 3;
- case kUnknown_DirChange:
- return (fIsFinite = false);
- case kInvalid_DirChange:
- SK_ABORT("Use of invalid direction change flag");
- break;
- }
- return true;
- }
- SkPoint fFirstPt {0, 0};
- SkPoint fPriorPt {0, 0};
- SkPoint fLastPt {0, 0};
- SkPoint fCurrPt {0, 0};
- SkVector fLastVec {0, 0};
- DirChange fExpectedDir { kInvalid_DirChange };
- SkPathPriv::FirstDirection fFirstDirection { SkPathPriv::kUnknown_FirstDirection };
- int fReversals { 0 };
- bool fIsFinite { true };
- };
- SkPath::Convexity SkPath::internalGetConvexity() const {
- SkPoint pts[4];
- SkPath::Verb verb;
- SkPath::Iter iter(*this, true);
- auto setComputedConvexity = [=](Convexity convexity){
- SkASSERT(kUnknown_Convexity != convexity);
- this->setConvexity(convexity);
- return convexity;
- };
- // Check to see if path changes direction more than three times as quick concave test
- int pointCount = this->countPoints();
- // last moveTo index may exceed point count if data comes from fuzzer (via SkImageFilter)
- if (0 < fLastMoveToIndex && fLastMoveToIndex < pointCount) {
- pointCount = fLastMoveToIndex;
- }
- if (pointCount > 3) {
- const SkPoint* points = fPathRef->points();
- const SkPoint* last = &points[pointCount];
- // only consider the last of the initial move tos
- while (SkPath::kMove_Verb == iter.next(pts, false, false)) {
- ++points;
- }
- --points;
- SkPath::Convexity convexity = Convexicator::BySign(points, (int) (last - points));
- if (SkPath::kConcave_Convexity == convexity) {
- return setComputedConvexity(SkPath::kConcave_Convexity);
- } else if (SkPath::kUnknown_Convexity == convexity) {
- return SkPath::kUnknown_Convexity;
- }
- iter.setPath(*this, true);
- } else if (!this->isFinite()) {
- return kUnknown_Convexity;
- }
- int contourCount = 0;
- int count;
- Convexicator state;
- auto setFail = [=](){
- if (!state.isFinite()) {
- return SkPath::kUnknown_Convexity;
- }
- return setComputedConvexity(SkPath::kConcave_Convexity);
- };
- while ((verb = iter.next(pts, false, false)) != SkPath::kDone_Verb) {
- switch (verb) {
- case kMove_Verb:
- if (++contourCount > 1) {
- return setComputedConvexity(kConcave_Convexity);
- }
- state.setMovePt(pts[0]);
- count = 0;
- break;
- case kLine_Verb:
- count = 1;
- break;
- case kQuad_Verb:
- // fall through
- case kConic_Verb:
- count = 2;
- break;
- case kCubic_Verb:
- count = 3;
- break;
- case kClose_Verb:
- if (!state.close()) {
- return setFail();
- }
- count = 0;
- break;
- default:
- SkDEBUGFAIL("bad verb");
- return setComputedConvexity(kConcave_Convexity);
- }
- for (int i = 1; i <= count; i++) {
- if (!state.addPt(pts[i])) {
- return setFail();
- }
- }
- }
- if (this->getFirstDirection() == SkPathPriv::kUnknown_FirstDirection) {
- if (state.getFirstDirection() == SkPathPriv::kUnknown_FirstDirection
- && !this->getBounds().isEmpty()) {
- return setComputedConvexity(state.reversals() < 3 ?
- kConvex_Convexity : kConcave_Convexity);
- }
- this->setFirstDirection(state.getFirstDirection());
- }
- return setComputedConvexity(kConvex_Convexity);
- }
- bool SkPathPriv::IsConvex(const SkPoint points[], int count) {
- SkPath::Convexity convexity = Convexicator::BySign(points, count);
- if (SkPath::kConvex_Convexity != convexity) {
- return false;
- }
- Convexicator state;
- state.setMovePt(points[0]);
- for (int i = 1; i < count; i++) {
- if (!state.addPt(points[i])) {
- return false;
- }
- }
- if (!state.addPt(points[0])) {
- return false;
- }
- if (!state.close()) {
- return false;
- }
- return state.getFirstDirection() != SkPathPriv::kUnknown_FirstDirection
- || state.reversals() < 3;
- }
- #endif
- ///////////////////////////////////////////////////////////////////////////////
- class ContourIter {
- public:
- ContourIter(const SkPathRef& pathRef);
- bool done() const { return fDone; }
- // if !done() then these may be called
- int count() const { return fCurrPtCount; }
- const SkPoint* pts() const { return fCurrPt; }
- void next();
- private:
- int fCurrPtCount;
- const SkPoint* fCurrPt;
- const uint8_t* fCurrVerb;
- const uint8_t* fStopVerbs;
- const SkScalar* fCurrConicWeight;
- bool fDone;
- SkDEBUGCODE(int fContourCounter;)
- };
- ContourIter::ContourIter(const SkPathRef& pathRef) {
- fStopVerbs = pathRef.verbsMemBegin();
- fDone = false;
- fCurrPt = pathRef.points();
- fCurrVerb = pathRef.verbs();
- fCurrConicWeight = pathRef.conicWeights();
- fCurrPtCount = 0;
- SkDEBUGCODE(fContourCounter = 0;)
- this->next();
- }
- void ContourIter::next() {
- if (fCurrVerb <= fStopVerbs) {
- fDone = true;
- }
- if (fDone) {
- return;
- }
- // skip pts of prev contour
- fCurrPt += fCurrPtCount;
- SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
- int ptCount = 1; // moveTo
- const uint8_t* verbs = fCurrVerb;
- for (--verbs; verbs > fStopVerbs; --verbs) {
- switch (verbs[~0]) {
- case SkPath::kMove_Verb:
- goto CONTOUR_END;
- case SkPath::kLine_Verb:
- ptCount += 1;
- break;
- case SkPath::kConic_Verb:
- fCurrConicWeight += 1;
- // fall-through
- case SkPath::kQuad_Verb:
- ptCount += 2;
- break;
- case SkPath::kCubic_Verb:
- ptCount += 3;
- break;
- case SkPath::kClose_Verb:
- break;
- default:
- SkDEBUGFAIL("unexpected verb");
- break;
- }
- }
- CONTOUR_END:
- fCurrPtCount = ptCount;
- fCurrVerb = verbs;
- SkDEBUGCODE(++fContourCounter;)
- }
- // returns cross product of (p1 - p0) and (p2 - p0)
- static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
- SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
- // We may get 0 when the above subtracts underflow. We expect this to be
- // very rare and lazily promote to double.
- if (0 == cross) {
- double p0x = SkScalarToDouble(p0.fX);
- double p0y = SkScalarToDouble(p0.fY);
- double p1x = SkScalarToDouble(p1.fX);
- double p1y = SkScalarToDouble(p1.fY);
- double p2x = SkScalarToDouble(p2.fX);
- double p2y = SkScalarToDouble(p2.fY);
- cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
- (p1y - p0y) * (p2x - p0x));
- }
- return cross;
- }
- // Returns the first pt with the maximum Y coordinate
- static int find_max_y(const SkPoint pts[], int count) {
- SkASSERT(count > 0);
- SkScalar max = pts[0].fY;
- int firstIndex = 0;
- for (int i = 1; i < count; ++i) {
- SkScalar y = pts[i].fY;
- if (y > max) {
- max = y;
- firstIndex = i;
- }
- }
- return firstIndex;
- }
- static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
- int i = index;
- for (;;) {
- i = (i + inc) % n;
- if (i == index) { // we wrapped around, so abort
- break;
- }
- if (pts[index] != pts[i]) { // found a different point, success!
- break;
- }
- }
- return i;
- }
- /**
- * Starting at index, and moving forward (incrementing), find the xmin and
- * xmax of the contiguous points that have the same Y.
- */
- static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
- int* maxIndexPtr) {
- const SkScalar y = pts[index].fY;
- SkScalar min = pts[index].fX;
- SkScalar max = min;
- int minIndex = index;
- int maxIndex = index;
- for (int i = index + 1; i < n; ++i) {
- if (pts[i].fY != y) {
- break;
- }
- SkScalar x = pts[i].fX;
- if (x < min) {
- min = x;
- minIndex = i;
- } else if (x > max) {
- max = x;
- maxIndex = i;
- }
- }
- *maxIndexPtr = maxIndex;
- return minIndex;
- }
- static void crossToDir(SkScalar cross, SkPathPriv::FirstDirection* dir) {
- *dir = cross > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
- }
- /*
- * We loop through all contours, and keep the computed cross-product of the
- * contour that contained the global y-max. If we just look at the first
- * contour, we may find one that is wound the opposite way (correctly) since
- * it is the interior of a hole (e.g. 'o'). Thus we must find the contour
- * that is outer most (or at least has the global y-max) before we can consider
- * its cross product.
- */
- bool SkPathPriv::CheapComputeFirstDirection(const SkPath& path, FirstDirection* dir) {
- auto d = path.getFirstDirection();
- if (d != kUnknown_FirstDirection) {
- *dir = static_cast<FirstDirection>(d);
- return true;
- }
- // We don't want to pay the cost for computing convexity if it is unknown,
- // so we call getConvexityOrUnknown() instead of isConvex().
- if (path.getConvexityOrUnknown() == SkPath::kConvex_Convexity) {
- SkASSERT(path.getFirstDirection() == kUnknown_FirstDirection);
- *dir = static_cast<FirstDirection>(path.getFirstDirection());
- return false;
- }
- ContourIter iter(*path.fPathRef.get());
- // initialize with our logical y-min
- SkScalar ymax = path.getBounds().fTop;
- SkScalar ymaxCross = 0;
- for (; !iter.done(); iter.next()) {
- int n = iter.count();
- if (n < 3) {
- continue;
- }
- const SkPoint* pts = iter.pts();
- SkScalar cross = 0;
- int index = find_max_y(pts, n);
- if (pts[index].fY < ymax) {
- continue;
- }
- // If there is more than 1 distinct point at the y-max, we take the
- // x-min and x-max of them and just subtract to compute the dir.
- if (pts[(index + 1) % n].fY == pts[index].fY) {
- int maxIndex;
- int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
- if (minIndex == maxIndex) {
- goto TRY_CROSSPROD;
- }
- SkASSERT(pts[minIndex].fY == pts[index].fY);
- SkASSERT(pts[maxIndex].fY == pts[index].fY);
- SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
- // we just subtract the indices, and let that auto-convert to
- // SkScalar, since we just want - or + to signal the direction.
- cross = minIndex - maxIndex;
- } else {
- TRY_CROSSPROD:
- // Find a next and prev index to use for the cross-product test,
- // but we try to find pts that form non-zero vectors from pts[index]
- //
- // Its possible that we can't find two non-degenerate vectors, so
- // we have to guard our search (e.g. all the pts could be in the
- // same place).
- // we pass n - 1 instead of -1 so we don't foul up % operator by
- // passing it a negative LH argument.
- int prev = find_diff_pt(pts, index, n, n - 1);
- if (prev == index) {
- // completely degenerate, skip to next contour
- continue;
- }
- int next = find_diff_pt(pts, index, n, 1);
- SkASSERT(next != index);
- cross = cross_prod(pts[prev], pts[index], pts[next]);
- // if we get a zero and the points are horizontal, then we look at the spread in
- // x-direction. We really should continue to walk away from the degeneracy until
- // there is a divergence.
- if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
- // construct the subtract so we get the correct Direction below
- cross = pts[index].fX - pts[next].fX;
- }
- }
- if (cross) {
- // record our best guess so far
- ymax = pts[index].fY;
- ymaxCross = cross;
- }
- }
- if (ymaxCross) {
- crossToDir(ymaxCross, dir);
- path.setFirstDirection(*dir);
- return true;
- } else {
- return false;
- }
- }
- ///////////////////////////////////////////////////////////////////////////////
- static bool between(SkScalar a, SkScalar b, SkScalar c) {
- SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
- || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
- return (a - b) * (c - b) <= 0;
- }
- static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
- SkScalar t) {
- SkScalar A = c3 + 3*(c1 - c2) - c0;
- SkScalar B = 3*(c2 - c1 - c1 + c0);
- SkScalar C = 3*(c1 - c0);
- SkScalar D = c0;
- return poly_eval(A, B, C, D, t);
- }
- template <size_t N> static void find_minmax(const SkPoint pts[],
- SkScalar* minPtr, SkScalar* maxPtr) {
- SkScalar min, max;
- min = max = pts[0].fX;
- for (size_t i = 1; i < N; ++i) {
- min = SkMinScalar(min, pts[i].fX);
- max = SkMaxScalar(max, pts[i].fX);
- }
- *minPtr = min;
- *maxPtr = max;
- }
- static bool checkOnCurve(SkScalar x, SkScalar y, const SkPoint& start, const SkPoint& end) {
- if (start.fY == end.fY) {
- return between(start.fX, x, end.fX) && x != end.fX;
- } else {
- return x == start.fX && y == start.fY;
- }
- }
- static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
- SkScalar y0 = pts[0].fY;
- SkScalar y3 = pts[3].fY;
- int dir = 1;
- if (y0 > y3) {
- using std::swap;
- swap(y0, y3);
- dir = -1;
- }
- if (y < y0 || y > y3) {
- return 0;
- }
- if (checkOnCurve(x, y, pts[0], pts[3])) {
- *onCurveCount += 1;
- return 0;
- }
- if (y == y3) {
- return 0;
- }
- // quickreject or quickaccept
- SkScalar min, max;
- find_minmax<4>(pts, &min, &max);
- if (x < min) {
- return 0;
- }
- if (x > max) {
- return dir;
- }
- // compute the actual x(t) value
- SkScalar t;
- if (!SkCubicClipper::ChopMonoAtY(pts, y, &t)) {
- return 0;
- }
- SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
- if (SkScalarNearlyEqual(xt, x)) {
- if (x != pts[3].fX || y != pts[3].fY) { // don't test end points; they're start points
- *onCurveCount += 1;
- return 0;
- }
- }
- return xt < x ? dir : 0;
- }
- static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
- SkPoint dst[10];
- int n = SkChopCubicAtYExtrema(pts, dst);
- int w = 0;
- for (int i = 0; i <= n; ++i) {
- w += winding_mono_cubic(&dst[i * 3], x, y, onCurveCount);
- }
- return w;
- }
- static double conic_eval_numerator(const SkScalar src[], SkScalar w, SkScalar t) {
- SkASSERT(src);
- SkASSERT(t >= 0 && t <= 1);
- SkScalar src2w = src[2] * w;
- SkScalar C = src[0];
- SkScalar A = src[4] - 2 * src2w + C;
- SkScalar B = 2 * (src2w - C);
- return poly_eval(A, B, C, t);
- }
- static double conic_eval_denominator(SkScalar w, SkScalar t) {
- SkScalar B = 2 * (w - 1);
- SkScalar C = 1;
- SkScalar A = -B;
- return poly_eval(A, B, C, t);
- }
- static int winding_mono_conic(const SkConic& conic, SkScalar x, SkScalar y, int* onCurveCount) {
- const SkPoint* pts = conic.fPts;
- SkScalar y0 = pts[0].fY;
- SkScalar y2 = pts[2].fY;
- int dir = 1;
- if (y0 > y2) {
- using std::swap;
- swap(y0, y2);
- dir = -1;
- }
- if (y < y0 || y > y2) {
- return 0;
- }
- if (checkOnCurve(x, y, pts[0], pts[2])) {
- *onCurveCount += 1;
- return 0;
- }
- if (y == y2) {
- return 0;
- }
- SkScalar roots[2];
- SkScalar A = pts[2].fY;
- SkScalar B = pts[1].fY * conic.fW - y * conic.fW + y;
- SkScalar C = pts[0].fY;
- A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept)
- B -= C; // B = b*w - w * yCept + yCept - a
- C -= y;
- int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
- SkASSERT(n <= 1);
- SkScalar xt;
- if (0 == n) {
- // zero roots are returned only when y0 == y
- // Need [0] if dir == 1
- // and [2] if dir == -1
- xt = pts[1 - dir].fX;
- } else {
- SkScalar t = roots[0];
- xt = conic_eval_numerator(&pts[0].fX, conic.fW, t) / conic_eval_denominator(conic.fW, t);
- }
- if (SkScalarNearlyEqual(xt, x)) {
- if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points
- *onCurveCount += 1;
- return 0;
- }
- }
- return xt < x ? dir : 0;
- }
- static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
- // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
- if (y0 == y1) {
- return true;
- }
- if (y0 < y1) {
- return y1 <= y2;
- } else {
- return y1 >= y2;
- }
- }
- static int winding_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight,
- int* onCurveCount) {
- SkConic conic(pts, weight);
- SkConic chopped[2];
- // If the data points are very large, the conic may not be monotonic but may also
- // fail to chop. Then, the chopper does not split the original conic in two.
- bool isMono = is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY) || !conic.chopAtYExtrema(chopped);
- int w = winding_mono_conic(isMono ? conic : chopped[0], x, y, onCurveCount);
- if (!isMono) {
- w += winding_mono_conic(chopped[1], x, y, onCurveCount);
- }
- return w;
- }
- static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
- SkScalar y0 = pts[0].fY;
- SkScalar y2 = pts[2].fY;
- int dir = 1;
- if (y0 > y2) {
- using std::swap;
- swap(y0, y2);
- dir = -1;
- }
- if (y < y0 || y > y2) {
- return 0;
- }
- if (checkOnCurve(x, y, pts[0], pts[2])) {
- *onCurveCount += 1;
- return 0;
- }
- if (y == y2) {
- return 0;
- }
- // bounds check on X (not required. is it faster?)
- #if 0
- if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
- return 0;
- }
- #endif
- SkScalar roots[2];
- int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
- 2 * (pts[1].fY - pts[0].fY),
- pts[0].fY - y,
- roots);
- SkASSERT(n <= 1);
- SkScalar xt;
- if (0 == n) {
- // zero roots are returned only when y0 == y
- // Need [0] if dir == 1
- // and [2] if dir == -1
- xt = pts[1 - dir].fX;
- } else {
- SkScalar t = roots[0];
- SkScalar C = pts[0].fX;
- SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
- SkScalar B = 2 * (pts[1].fX - C);
- xt = poly_eval(A, B, C, t);
- }
- if (SkScalarNearlyEqual(xt, x)) {
- if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points
- *onCurveCount += 1;
- return 0;
- }
- }
- return xt < x ? dir : 0;
- }
- static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
- SkPoint dst[5];
- int n = 0;
- if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
- n = SkChopQuadAtYExtrema(pts, dst);
- pts = dst;
- }
- int w = winding_mono_quad(pts, x, y, onCurveCount);
- if (n > 0) {
- w += winding_mono_quad(&pts[2], x, y, onCurveCount);
- }
- return w;
- }
- static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
- SkScalar x0 = pts[0].fX;
- SkScalar y0 = pts[0].fY;
- SkScalar x1 = pts[1].fX;
- SkScalar y1 = pts[1].fY;
- SkScalar dy = y1 - y0;
- int dir = 1;
- if (y0 > y1) {
- using std::swap;
- swap(y0, y1);
- dir = -1;
- }
- if (y < y0 || y > y1) {
- return 0;
- }
- if (checkOnCurve(x, y, pts[0], pts[1])) {
- *onCurveCount += 1;
- return 0;
- }
- if (y == y1) {
- return 0;
- }
- SkScalar cross = (x1 - x0) * (y - pts[0].fY) - dy * (x - x0);
- if (!cross) {
- // zero cross means the point is on the line, and since the case where
- // y of the query point is at the end point is handled above, we can be
- // sure that we're on the line (excluding the end point) here
- if (x != x1 || y != pts[1].fY) {
- *onCurveCount += 1;
- }
- dir = 0;
- } else if (SkScalarSignAsInt(cross) == dir) {
- dir = 0;
- }
- return dir;
- }
- static void tangent_cubic(const SkPoint pts[], SkScalar x, SkScalar y,
- SkTDArray<SkVector>* tangents) {
- if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)
- && !between(pts[2].fY, y, pts[3].fY)) {
- return;
- }
- if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)
- && !between(pts[2].fX, x, pts[3].fX)) {
- return;
- }
- SkPoint dst[10];
- int n = SkChopCubicAtYExtrema(pts, dst);
- for (int i = 0; i <= n; ++i) {
- SkPoint* c = &dst[i * 3];
- SkScalar t;
- if (!SkCubicClipper::ChopMonoAtY(c, y, &t)) {
- continue;
- }
- SkScalar xt = eval_cubic_pts(c[0].fX, c[1].fX, c[2].fX, c[3].fX, t);
- if (!SkScalarNearlyEqual(x, xt)) {
- continue;
- }
- SkVector tangent;
- SkEvalCubicAt(c, t, nullptr, &tangent, nullptr);
- tangents->push_back(tangent);
- }
- }
- static void tangent_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w,
- SkTDArray<SkVector>* tangents) {
- if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
- return;
- }
- if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
- return;
- }
- SkScalar roots[2];
- SkScalar A = pts[2].fY;
- SkScalar B = pts[1].fY * w - y * w + y;
- SkScalar C = pts[0].fY;
- A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept)
- B -= C; // B = b*w - w * yCept + yCept - a
- C -= y;
- int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
- for (int index = 0; index < n; ++index) {
- SkScalar t = roots[index];
- SkScalar xt = conic_eval_numerator(&pts[0].fX, w, t) / conic_eval_denominator(w, t);
- if (!SkScalarNearlyEqual(x, xt)) {
- continue;
- }
- SkConic conic(pts, w);
- tangents->push_back(conic.evalTangentAt(t));
- }
- }
- static void tangent_quad(const SkPoint pts[], SkScalar x, SkScalar y,
- SkTDArray<SkVector>* tangents) {
- if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
- return;
- }
- if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
- return;
- }
- SkScalar roots[2];
- int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
- 2 * (pts[1].fY - pts[0].fY),
- pts[0].fY - y,
- roots);
- for (int index = 0; index < n; ++index) {
- SkScalar t = roots[index];
- SkScalar C = pts[0].fX;
- SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
- SkScalar B = 2 * (pts[1].fX - C);
- SkScalar xt = poly_eval(A, B, C, t);
- if (!SkScalarNearlyEqual(x, xt)) {
- continue;
- }
- tangents->push_back(SkEvalQuadTangentAt(pts, t));
- }
- }
- static void tangent_line(const SkPoint pts[], SkScalar x, SkScalar y,
- SkTDArray<SkVector>* tangents) {
- SkScalar y0 = pts[0].fY;
- SkScalar y1 = pts[1].fY;
- if (!between(y0, y, y1)) {
- return;
- }
- SkScalar x0 = pts[0].fX;
- SkScalar x1 = pts[1].fX;
- if (!between(x0, x, x1)) {
- return;
- }
- SkScalar dx = x1 - x0;
- SkScalar dy = y1 - y0;
- if (!SkScalarNearlyEqual((x - x0) * dy, dx * (y - y0))) {
- return;
- }
- SkVector v;
- v.set(dx, dy);
- tangents->push_back(v);
- }
- static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
- return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
- }
- bool SkPath::contains(SkScalar x, SkScalar y) const {
- bool isInverse = this->isInverseFillType();
- if (this->isEmpty()) {
- return isInverse;
- }
- if (!contains_inclusive(this->getBounds(), x, y)) {
- return isInverse;
- }
- SkPath::Iter iter(*this, true);
- bool done = false;
- int w = 0;
- int onCurveCount = 0;
- do {
- SkPoint pts[4];
- switch (iter.next(pts, false)) {
- case SkPath::kMove_Verb:
- case SkPath::kClose_Verb:
- break;
- case SkPath::kLine_Verb:
- w += winding_line(pts, x, y, &onCurveCount);
- break;
- case SkPath::kQuad_Verb:
- w += winding_quad(pts, x, y, &onCurveCount);
- break;
- case SkPath::kConic_Verb:
- w += winding_conic(pts, x, y, iter.conicWeight(), &onCurveCount);
- break;
- case SkPath::kCubic_Verb:
- w += winding_cubic(pts, x, y, &onCurveCount);
- break;
- case SkPath::kDone_Verb:
- done = true;
- break;
- }
- } while (!done);
- bool evenOddFill = SkPath::kEvenOdd_FillType == this->getFillType()
- || SkPath::kInverseEvenOdd_FillType == this->getFillType();
- if (evenOddFill) {
- w &= 1;
- }
- if (w) {
- return !isInverse;
- }
- if (onCurveCount <= 1) {
- return SkToBool(onCurveCount) ^ isInverse;
- }
- if ((onCurveCount & 1) || evenOddFill) {
- return SkToBool(onCurveCount & 1) ^ isInverse;
- }
- // If the point touches an even number of curves, and the fill is winding, check for
- // coincidence. Count coincidence as places where the on curve points have identical tangents.
- iter.setPath(*this, true);
- done = false;
- SkTDArray<SkVector> tangents;
- do {
- SkPoint pts[4];
- int oldCount = tangents.count();
- switch (iter.next(pts, false)) {
- case SkPath::kMove_Verb:
- case SkPath::kClose_Verb:
- break;
- case SkPath::kLine_Verb:
- tangent_line(pts, x, y, &tangents);
- break;
- case SkPath::kQuad_Verb:
- tangent_quad(pts, x, y, &tangents);
- break;
- case SkPath::kConic_Verb:
- tangent_conic(pts, x, y, iter.conicWeight(), &tangents);
- break;
- case SkPath::kCubic_Verb:
- tangent_cubic(pts, x, y, &tangents);
- break;
- case SkPath::kDone_Verb:
- done = true;
- break;
- }
- if (tangents.count() > oldCount) {
- int last = tangents.count() - 1;
- const SkVector& tangent = tangents[last];
- if (SkScalarNearlyZero(SkPointPriv::LengthSqd(tangent))) {
- tangents.remove(last);
- } else {
- for (int index = 0; index < last; ++index) {
- const SkVector& test = tangents[index];
- if (SkScalarNearlyZero(test.cross(tangent))
- && SkScalarSignAsInt(tangent.fX * test.fX) <= 0
- && SkScalarSignAsInt(tangent.fY * test.fY) <= 0) {
- tangents.remove(last);
- tangents.removeShuffle(index);
- break;
- }
- }
- }
- }
- } while (!done);
- return SkToBool(tangents.count()) ^ isInverse;
- }
- int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
- SkScalar w, SkPoint pts[], int pow2) {
- const SkConic conic(p0, p1, p2, w);
- return conic.chopIntoQuadsPOW2(pts, pow2);
- }
- bool SkPathPriv::IsSimpleClosedRect(const SkPath& path, SkRect* rect, SkPath::Direction* direction,
- unsigned* start) {
- if (path.getSegmentMasks() != SkPath::kLine_SegmentMask) {
- return false;
- }
- SkPath::RawIter iter(path);
- SkPoint verbPts[4];
- SkPath::Verb v;
- SkPoint rectPts[5];
- int rectPtCnt = 0;
- while ((v = iter.next(verbPts)) != SkPath::kDone_Verb) {
- switch (v) {
- case SkPath::kMove_Verb:
- if (0 != rectPtCnt) {
- return false;
- }
- rectPts[0] = verbPts[0];
- ++rectPtCnt;
- break;
- case SkPath::kLine_Verb:
- if (5 == rectPtCnt) {
- return false;
- }
- rectPts[rectPtCnt] = verbPts[1];
- ++rectPtCnt;
- break;
- case SkPath::kClose_Verb:
- if (4 == rectPtCnt) {
- rectPts[4] = rectPts[0];
- rectPtCnt = 5;
- }
- break;
- default:
- return false;
- }
- }
- if (rectPtCnt < 5) {
- return false;
- }
- if (rectPts[0] != rectPts[4]) {
- return false;
- }
- // Check for two cases of rectangles: pts 0 and 3 form a vertical edge or a horizontal edge (
- // and pts 1 and 2 the opposite vertical or horizontal edge).
- bool vec03IsVertical;
- if (rectPts[0].fX == rectPts[3].fX && rectPts[1].fX == rectPts[2].fX &&
- rectPts[0].fY == rectPts[1].fY && rectPts[3].fY == rectPts[2].fY) {
- // Make sure it has non-zero width and height
- if (rectPts[0].fX == rectPts[1].fX || rectPts[0].fY == rectPts[3].fY) {
- return false;
- }
- vec03IsVertical = true;
- } else if (rectPts[0].fY == rectPts[3].fY && rectPts[1].fY == rectPts[2].fY &&
- rectPts[0].fX == rectPts[1].fX && rectPts[3].fX == rectPts[2].fX) {
- // Make sure it has non-zero width and height
- if (rectPts[0].fY == rectPts[1].fY || rectPts[0].fX == rectPts[3].fX) {
- return false;
- }
- vec03IsVertical = false;
- } else {
- return false;
- }
- // Set sortFlags so that it has the low bit set if pt index 0 is on right edge and second bit
- // set if it is on the bottom edge.
- unsigned sortFlags =
- ((rectPts[0].fX < rectPts[2].fX) ? 0b00 : 0b01) |
- ((rectPts[0].fY < rectPts[2].fY) ? 0b00 : 0b10);
- switch (sortFlags) {
- case 0b00:
- rect->set(rectPts[0].fX, rectPts[0].fY, rectPts[2].fX, rectPts[2].fY);
- *direction = vec03IsVertical ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
- *start = 0;
- break;
- case 0b01:
- rect->set(rectPts[2].fX, rectPts[0].fY, rectPts[0].fX, rectPts[2].fY);
- *direction = vec03IsVertical ? SkPath::kCCW_Direction : SkPath::kCW_Direction;
- *start = 1;
- break;
- case 0b10:
- rect->set(rectPts[0].fX, rectPts[2].fY, rectPts[2].fX, rectPts[0].fY);
- *direction = vec03IsVertical ? SkPath::kCCW_Direction : SkPath::kCW_Direction;
- *start = 3;
- break;
- case 0b11:
- rect->set(rectPts[2].fX, rectPts[2].fY, rectPts[0].fX, rectPts[0].fY);
- *direction = vec03IsVertical ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
- *start = 2;
- break;
- }
- return true;
- }
- bool SkPathPriv::DrawArcIsConvex(SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) {
- if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) {
- // This gets converted to an oval.
- return true;
- }
- if (useCenter) {
- // This is a pie wedge. It's convex if the angle is <= 180.
- return SkScalarAbs(sweepAngle) <= 180.f;
- }
- // When the angle exceeds 360 this wraps back on top of itself. Otherwise it is a circle clipped
- // to a secant, i.e. convex.
- return SkScalarAbs(sweepAngle) <= 360.f;
- }
- void SkPathPriv::CreateDrawArcPath(SkPath* path, const SkRect& oval, SkScalar startAngle,
- SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) {
- SkASSERT(!oval.isEmpty());
- SkASSERT(sweepAngle);
- path->reset();
- path->setIsVolatile(true);
- path->setFillType(SkPath::kWinding_FillType);
- if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) {
- path->addOval(oval);
- SkASSERT(path->isConvex() && DrawArcIsConvex(sweepAngle, false, isFillNoPathEffect));
- return;
- }
- if (useCenter) {
- path->moveTo(oval.centerX(), oval.centerY());
- }
- auto firstDir =
- sweepAngle > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
- bool convex = DrawArcIsConvex(sweepAngle, useCenter, isFillNoPathEffect);
- // Arc to mods at 360 and drawArc is not supposed to.
- bool forceMoveTo = !useCenter;
- while (sweepAngle <= -360.f) {
- path->arcTo(oval, startAngle, -180.f, forceMoveTo);
- startAngle -= 180.f;
- path->arcTo(oval, startAngle, -180.f, false);
- startAngle -= 180.f;
- forceMoveTo = false;
- sweepAngle += 360.f;
- }
- while (sweepAngle >= 360.f) {
- path->arcTo(oval, startAngle, 180.f, forceMoveTo);
- startAngle += 180.f;
- path->arcTo(oval, startAngle, 180.f, false);
- startAngle += 180.f;
- forceMoveTo = false;
- sweepAngle -= 360.f;
- }
- path->arcTo(oval, startAngle, sweepAngle, forceMoveTo);
- if (useCenter) {
- path->close();
- }
- path->setConvexity(convex ? SkPath::kConvex_Convexity : SkPath::kConcave_Convexity);
- path->setFirstDirection(firstDir);
- }
- ///////////////////////////////////////////////////////////////////////////////////////////////////
- #include "include/private/SkNx.h"
- static int compute_quad_extremas(const SkPoint src[3], SkPoint extremas[3]) {
- SkScalar ts[2];
- int n = SkFindQuadExtrema(src[0].fX, src[1].fX, src[2].fX, ts);
- n += SkFindQuadExtrema(src[0].fY, src[1].fY, src[2].fY, &ts[n]);
- SkASSERT(n >= 0 && n <= 2);
- for (int i = 0; i < n; ++i) {
- extremas[i] = SkEvalQuadAt(src, ts[i]);
- }
- extremas[n] = src[2];
- return n + 1;
- }
- static int compute_conic_extremas(const SkPoint src[3], SkScalar w, SkPoint extremas[3]) {
- SkConic conic(src[0], src[1], src[2], w);
- SkScalar ts[2];
- int n = conic.findXExtrema(ts);
- n += conic.findYExtrema(&ts[n]);
- SkASSERT(n >= 0 && n <= 2);
- for (int i = 0; i < n; ++i) {
- extremas[i] = conic.evalAt(ts[i]);
- }
- extremas[n] = src[2];
- return n + 1;
- }
- static int compute_cubic_extremas(const SkPoint src[4], SkPoint extremas[5]) {
- SkScalar ts[4];
- int n = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, src[3].fX, ts);
- n += SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, src[3].fY, &ts[n]);
- SkASSERT(n >= 0 && n <= 4);
- for (int i = 0; i < n; ++i) {
- SkEvalCubicAt(src, ts[i], &extremas[i], nullptr, nullptr);
- }
- extremas[n] = src[3];
- return n + 1;
- }
- SkRect SkPath::computeTightBounds() const {
- if (0 == this->countVerbs()) {
- return SkRect::MakeEmpty();
- }
- if (this->getSegmentMasks() == SkPath::kLine_SegmentMask) {
- return this->getBounds();
- }
- SkPoint extremas[5]; // big enough to hold worst-case curve type (cubic) extremas + 1
- SkPoint pts[4];
- SkPath::RawIter iter(*this);
- // initial with the first MoveTo, so we don't have to check inside the switch
- Sk2s min, max;
- min = max = from_point(this->getPoint(0));
- for (;;) {
- int count = 0;
- switch (iter.next(pts)) {
- case SkPath::kMove_Verb:
- extremas[0] = pts[0];
- count = 1;
- break;
- case SkPath::kLine_Verb:
- extremas[0] = pts[1];
- count = 1;
- break;
- case SkPath::kQuad_Verb:
- count = compute_quad_extremas(pts, extremas);
- break;
- case SkPath::kConic_Verb:
- count = compute_conic_extremas(pts, iter.conicWeight(), extremas);
- break;
- case SkPath::kCubic_Verb:
- count = compute_cubic_extremas(pts, extremas);
- break;
- case SkPath::kClose_Verb:
- break;
- case SkPath::kDone_Verb:
- goto DONE;
- }
- for (int i = 0; i < count; ++i) {
- Sk2s tmp = from_point(extremas[i]);
- min = Sk2s::Min(min, tmp);
- max = Sk2s::Max(max, tmp);
- }
- }
- DONE:
- SkRect bounds;
- min.store((SkPoint*)&bounds.fLeft);
- max.store((SkPoint*)&bounds.fRight);
- return bounds;
- }
- bool SkPath::IsLineDegenerate(const SkPoint& p1, const SkPoint& p2, bool exact) {
- return exact ? p1 == p2 : SkPointPriv::EqualsWithinTolerance(p1, p2);
- }
- bool SkPath::IsQuadDegenerate(const SkPoint& p1, const SkPoint& p2,
- const SkPoint& p3, bool exact) {
- return exact ? p1 == p2 && p2 == p3 : SkPointPriv::EqualsWithinTolerance(p1, p2) &&
- SkPointPriv::EqualsWithinTolerance(p2, p3);
- }
- bool SkPath::IsCubicDegenerate(const SkPoint& p1, const SkPoint& p2,
- const SkPoint& p3, const SkPoint& p4, bool exact) {
- return exact ? p1 == p2 && p2 == p3 && p3 == p4 :
- SkPointPriv::EqualsWithinTolerance(p1, p2) &&
- SkPointPriv::EqualsWithinTolerance(p2, p3) &&
- SkPointPriv::EqualsWithinTolerance(p3, p4);
- }
|