SkPathOpsDebug.cpp 113 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147
  1. /*
  2. * Copyright 2013 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/core/SkPath.h"
  8. #include "include/core/SkString.h"
  9. #include "include/private/SkMutex.h"
  10. #include "src/core/SkOSFile.h"
  11. #include "src/pathops/SkOpCoincidence.h"
  12. #include "src/pathops/SkOpContour.h"
  13. #include "src/pathops/SkPathOpsDebug.h"
  14. #include <utility>
  15. #if DEBUG_DUMP_VERIFY
  16. bool SkPathOpsDebug::gDumpOp; // set to true to write op to file before a crash
  17. bool SkPathOpsDebug::gVerifyOp; // set to true to compare result against regions
  18. #endif
  19. bool SkPathOpsDebug::gRunFail; // set to true to check for success on tests known to fail
  20. bool SkPathOpsDebug::gVeryVerbose; // set to true to run extensive checking tests
  21. #undef FAIL_IF
  22. #define FAIL_IF(cond, coin) \
  23. do { if (cond) log->record(SkPathOpsDebug::kFail_Glitch, coin); } while (false)
  24. #undef FAIL_WITH_NULL_IF
  25. #define FAIL_WITH_NULL_IF(cond, span) \
  26. do { if (cond) log->record(SkPathOpsDebug::kFail_Glitch, span); } while (false)
  27. #undef RETURN_FALSE_IF
  28. #define RETURN_FALSE_IF(cond, span) \
  29. do { if (cond) log->record(SkPathOpsDebug::kReturnFalse_Glitch, span); \
  30. } while (false)
  31. class SkCoincidentSpans;
  32. #if DEBUG_SORT
  33. int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
  34. int SkPathOpsDebug::gSortCount;
  35. #endif
  36. #if DEBUG_ACTIVE_OP
  37. const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor", "rdiff"};
  38. #endif
  39. #if defined SK_DEBUG || !FORCE_RELEASE
  40. int SkPathOpsDebug::gContourID = 0;
  41. int SkPathOpsDebug::gSegmentID = 0;
  42. bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
  43. const SkOpSpanBase* span) {
  44. for (int index = 0; index < chaseArray.count(); ++index) {
  45. const SkOpSpanBase* entry = chaseArray[index];
  46. if (entry == span) {
  47. return true;
  48. }
  49. }
  50. return false;
  51. }
  52. #endif
  53. #if DEBUG_ACTIVE_SPANS
  54. SkString SkPathOpsDebug::gActiveSpans;
  55. #endif
  56. #if DEBUG_COIN
  57. SkPathOpsDebug::CoinDict SkPathOpsDebug::gCoinSumChangedDict;
  58. SkPathOpsDebug::CoinDict SkPathOpsDebug::gCoinSumVisitedDict;
  59. static const int kGlitchType_Count = SkPathOpsDebug::kUnalignedTail_Glitch + 1;
  60. struct SpanGlitch {
  61. const SkOpSpanBase* fBase;
  62. const SkOpSpanBase* fSuspect;
  63. const SkOpSegment* fSegment;
  64. const SkOpSegment* fOppSegment;
  65. const SkOpPtT* fCoinSpan;
  66. const SkOpPtT* fEndSpan;
  67. const SkOpPtT* fOppSpan;
  68. const SkOpPtT* fOppEndSpan;
  69. double fStartT;
  70. double fEndT;
  71. double fOppStartT;
  72. double fOppEndT;
  73. SkPoint fPt;
  74. SkPathOpsDebug::GlitchType fType;
  75. void dumpType() const;
  76. };
  77. struct SkPathOpsDebug::GlitchLog {
  78. void init(const SkOpGlobalState* state) {
  79. fGlobalState = state;
  80. }
  81. SpanGlitch* recordCommon(GlitchType type) {
  82. SpanGlitch* glitch = fGlitches.push();
  83. glitch->fBase = nullptr;
  84. glitch->fSuspect = nullptr;
  85. glitch->fSegment = nullptr;
  86. glitch->fOppSegment = nullptr;
  87. glitch->fCoinSpan = nullptr;
  88. glitch->fEndSpan = nullptr;
  89. glitch->fOppSpan = nullptr;
  90. glitch->fOppEndSpan = nullptr;
  91. glitch->fStartT = SK_ScalarNaN;
  92. glitch->fEndT = SK_ScalarNaN;
  93. glitch->fOppStartT = SK_ScalarNaN;
  94. glitch->fOppEndT = SK_ScalarNaN;
  95. glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
  96. glitch->fType = type;
  97. return glitch;
  98. }
  99. void record(GlitchType type, const SkOpSpanBase* base,
  100. const SkOpSpanBase* suspect = NULL) {
  101. SpanGlitch* glitch = recordCommon(type);
  102. glitch->fBase = base;
  103. glitch->fSuspect = suspect;
  104. }
  105. void record(GlitchType type, const SkOpSpanBase* base,
  106. const SkOpPtT* ptT) {
  107. SpanGlitch* glitch = recordCommon(type);
  108. glitch->fBase = base;
  109. glitch->fCoinSpan = ptT;
  110. }
  111. void record(GlitchType type, const SkCoincidentSpans* coin,
  112. const SkCoincidentSpans* opp = NULL) {
  113. SpanGlitch* glitch = recordCommon(type);
  114. glitch->fCoinSpan = coin->coinPtTStart();
  115. glitch->fEndSpan = coin->coinPtTEnd();
  116. if (opp) {
  117. glitch->fOppSpan = opp->coinPtTStart();
  118. glitch->fOppEndSpan = opp->coinPtTEnd();
  119. }
  120. }
  121. void record(GlitchType type, const SkOpSpanBase* base,
  122. const SkOpSegment* seg, double t, SkPoint pt) {
  123. SpanGlitch* glitch = recordCommon(type);
  124. glitch->fBase = base;
  125. glitch->fSegment = seg;
  126. glitch->fStartT = t;
  127. glitch->fPt = pt;
  128. }
  129. void record(GlitchType type, const SkOpSpanBase* base, double t,
  130. SkPoint pt) {
  131. SpanGlitch* glitch = recordCommon(type);
  132. glitch->fBase = base;
  133. glitch->fStartT = t;
  134. glitch->fPt = pt;
  135. }
  136. void record(GlitchType type, const SkCoincidentSpans* coin,
  137. const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
  138. SpanGlitch* glitch = recordCommon(type);
  139. glitch->fCoinSpan = coin->coinPtTStart();
  140. glitch->fEndSpan = coin->coinPtTEnd();
  141. glitch->fEndSpan = endSpan;
  142. glitch->fOppSpan = coinSpan;
  143. glitch->fOppEndSpan = endSpan;
  144. }
  145. void record(GlitchType type, const SkCoincidentSpans* coin,
  146. const SkOpSpanBase* base) {
  147. SpanGlitch* glitch = recordCommon(type);
  148. glitch->fBase = base;
  149. glitch->fCoinSpan = coin->coinPtTStart();
  150. glitch->fEndSpan = coin->coinPtTEnd();
  151. }
  152. void record(GlitchType type, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
  153. const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
  154. SpanGlitch* glitch = recordCommon(type);
  155. glitch->fCoinSpan = ptTS;
  156. glitch->fEndSpan = ptTE;
  157. glitch->fOppSpan = oPtTS;
  158. glitch->fOppEndSpan = oPtTE;
  159. }
  160. void record(GlitchType type, const SkOpSegment* seg, double startT,
  161. double endT, const SkOpSegment* oppSeg, double oppStartT, double oppEndT) {
  162. SpanGlitch* glitch = recordCommon(type);
  163. glitch->fSegment = seg;
  164. glitch->fStartT = startT;
  165. glitch->fEndT = endT;
  166. glitch->fOppSegment = oppSeg;
  167. glitch->fOppStartT = oppStartT;
  168. glitch->fOppEndT = oppEndT;
  169. }
  170. void record(GlitchType type, const SkOpSegment* seg,
  171. const SkOpSpan* span) {
  172. SpanGlitch* glitch = recordCommon(type);
  173. glitch->fSegment = seg;
  174. glitch->fBase = span;
  175. }
  176. void record(GlitchType type, double t, const SkOpSpanBase* span) {
  177. SpanGlitch* glitch = recordCommon(type);
  178. glitch->fStartT = t;
  179. glitch->fBase = span;
  180. }
  181. void record(GlitchType type, const SkOpSegment* seg) {
  182. SpanGlitch* glitch = recordCommon(type);
  183. glitch->fSegment = seg;
  184. }
  185. void record(GlitchType type, const SkCoincidentSpans* coin,
  186. const SkOpPtT* ptT) {
  187. SpanGlitch* glitch = recordCommon(type);
  188. glitch->fCoinSpan = coin->coinPtTStart();
  189. glitch->fEndSpan = ptT;
  190. }
  191. SkTDArray<SpanGlitch> fGlitches;
  192. const SkOpGlobalState* fGlobalState;
  193. };
  194. void SkPathOpsDebug::CoinDict::add(const SkPathOpsDebug::CoinDict& dict) {
  195. int count = dict.fDict.count();
  196. for (int index = 0; index < count; ++index) {
  197. this->add(dict.fDict[index]);
  198. }
  199. }
  200. void SkPathOpsDebug::CoinDict::add(const CoinDictEntry& key) {
  201. int count = fDict.count();
  202. for (int index = 0; index < count; ++index) {
  203. CoinDictEntry* entry = &fDict[index];
  204. if (entry->fIteration == key.fIteration && entry->fLineNumber == key.fLineNumber) {
  205. SkASSERT(!strcmp(entry->fFunctionName, key.fFunctionName));
  206. if (entry->fGlitchType == kUninitialized_Glitch) {
  207. entry->fGlitchType = key.fGlitchType;
  208. }
  209. return;
  210. }
  211. }
  212. *fDict.append() = key;
  213. }
  214. #endif
  215. #if DEBUG_COIN
  216. static void missing_coincidence(SkPathOpsDebug::GlitchLog* glitches, const SkOpContourHead* contourList) {
  217. const SkOpContour* contour = contourList;
  218. // bool result = false;
  219. do {
  220. /* result |= */ contour->debugMissingCoincidence(glitches);
  221. } while ((contour = contour->next()));
  222. return;
  223. }
  224. static void move_multiples(SkPathOpsDebug::GlitchLog* glitches, const SkOpContourHead* contourList) {
  225. const SkOpContour* contour = contourList;
  226. do {
  227. if (contour->debugMoveMultiples(glitches), false) {
  228. return;
  229. }
  230. } while ((contour = contour->next()));
  231. return;
  232. }
  233. static void move_nearby(SkPathOpsDebug::GlitchLog* glitches, const SkOpContourHead* contourList) {
  234. const SkOpContour* contour = contourList;
  235. do {
  236. contour->debugMoveNearby(glitches);
  237. } while ((contour = contour->next()));
  238. }
  239. #endif
  240. #if DEBUG_COIN
  241. void SkOpGlobalState::debugAddToCoinChangedDict() {
  242. #if DEBUG_COINCIDENCE
  243. SkPathOpsDebug::CheckHealth(fContourHead);
  244. #endif
  245. // see if next coincident operation makes a change; if so, record it
  246. SkPathOpsDebug::GlitchLog glitches;
  247. const char* funcName = fCoinDictEntry.fFunctionName;
  248. if (!strcmp("calc_angles", funcName)) {
  249. ;
  250. } else if (!strcmp("missing_coincidence", funcName)) {
  251. missing_coincidence(&glitches, fContourHead);
  252. } else if (!strcmp("move_multiples", funcName)) {
  253. move_multiples(&glitches, fContourHead);
  254. } else if (!strcmp("move_nearby", funcName)) {
  255. move_nearby(&glitches, fContourHead);
  256. } else if (!strcmp("addExpanded", funcName)) {
  257. fCoincidence->debugAddExpanded(&glitches);
  258. } else if (!strcmp("addMissing", funcName)) {
  259. bool added;
  260. fCoincidence->debugAddMissing(&glitches, &added);
  261. } else if (!strcmp("addEndMovedSpans", funcName)) {
  262. fCoincidence->debugAddEndMovedSpans(&glitches);
  263. } else if (!strcmp("correctEnds", funcName)) {
  264. fCoincidence->debugCorrectEnds(&glitches);
  265. } else if (!strcmp("expand", funcName)) {
  266. fCoincidence->debugExpand(&glitches);
  267. } else if (!strcmp("findOverlaps", funcName)) {
  268. ;
  269. } else if (!strcmp("mark", funcName)) {
  270. fCoincidence->debugMark(&glitches);
  271. } else if (!strcmp("apply", funcName)) {
  272. ;
  273. } else {
  274. SkASSERT(0); // add missing case
  275. }
  276. if (glitches.fGlitches.count()) {
  277. fCoinDictEntry.fGlitchType = glitches.fGlitches[0].fType;
  278. }
  279. fCoinChangedDict.add(fCoinDictEntry);
  280. }
  281. #endif
  282. void SkPathOpsDebug::ShowActiveSpans(SkOpContourHead* contourList) {
  283. #if DEBUG_ACTIVE_SPANS
  284. SkString str;
  285. SkOpContour* contour = contourList;
  286. do {
  287. contour->debugShowActiveSpans(&str);
  288. } while ((contour = contour->next()));
  289. if (!gActiveSpans.equals(str)) {
  290. const char* s = str.c_str();
  291. const char* end;
  292. while ((end = strchr(s, '\n'))) {
  293. SkDebugf("%.*s", end - s + 1, s);
  294. s = end + 1;
  295. }
  296. gActiveSpans.set(str);
  297. }
  298. #endif
  299. }
  300. #if DEBUG_COINCIDENCE || DEBUG_COIN
  301. void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList) {
  302. #if DEBUG_COINCIDENCE
  303. contourList->globalState()->debugSetCheckHealth(true);
  304. #endif
  305. #if DEBUG_COIN
  306. GlitchLog glitches;
  307. const SkOpContour* contour = contourList;
  308. const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
  309. coincidence->debugCheckValid(&glitches); // don't call validate; spans may be inconsistent
  310. do {
  311. contour->debugCheckHealth(&glitches);
  312. contour->debugMissingCoincidence(&glitches);
  313. } while ((contour = contour->next()));
  314. bool added;
  315. coincidence->debugAddMissing(&glitches, &added);
  316. coincidence->debugExpand(&glitches);
  317. coincidence->debugAddExpanded(&glitches);
  318. coincidence->debugMark(&glitches);
  319. unsigned mask = 0;
  320. for (int index = 0; index < glitches.fGlitches.count(); ++index) {
  321. const SpanGlitch& glitch = glitches.fGlitches[index];
  322. mask |= 1 << glitch.fType;
  323. }
  324. for (int index = 0; index < kGlitchType_Count; ++index) {
  325. SkDebugf(mask & (1 << index) ? "x" : "-");
  326. }
  327. SkDebugf(" %s\n", contourList->globalState()->debugCoinDictEntry().fFunctionName);
  328. for (int index = 0; index < glitches.fGlitches.count(); ++index) {
  329. const SpanGlitch& glitch = glitches.fGlitches[index];
  330. SkDebugf("%02d: ", index);
  331. if (glitch.fBase) {
  332. SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(),
  333. glitch.fBase->debugID());
  334. }
  335. if (glitch.fSuspect) {
  336. SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(),
  337. glitch.fSuspect->debugID());
  338. }
  339. if (glitch.fSegment) {
  340. SkDebugf(" segment=%d", glitch.fSegment->debugID());
  341. }
  342. if (glitch.fCoinSpan) {
  343. SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(),
  344. glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID());
  345. }
  346. if (glitch.fEndSpan) {
  347. SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
  348. }
  349. if (glitch.fOppSpan) {
  350. SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(),
  351. glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID());
  352. }
  353. if (glitch.fOppEndSpan) {
  354. SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
  355. }
  356. if (!SkScalarIsNaN(glitch.fStartT)) {
  357. SkDebugf(" startT=%g", glitch.fStartT);
  358. }
  359. if (!SkScalarIsNaN(glitch.fEndT)) {
  360. SkDebugf(" endT=%g", glitch.fEndT);
  361. }
  362. if (glitch.fOppSegment) {
  363. SkDebugf(" segment=%d", glitch.fOppSegment->debugID());
  364. }
  365. if (!SkScalarIsNaN(glitch.fOppStartT)) {
  366. SkDebugf(" oppStartT=%g", glitch.fOppStartT);
  367. }
  368. if (!SkScalarIsNaN(glitch.fOppEndT)) {
  369. SkDebugf(" oppEndT=%g", glitch.fOppEndT);
  370. }
  371. if (!SkScalarIsNaN(glitch.fPt.fX) || !SkScalarIsNaN(glitch.fPt.fY)) {
  372. SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY);
  373. }
  374. DumpGlitchType(glitch.fType);
  375. SkDebugf("\n");
  376. }
  377. #if DEBUG_COINCIDENCE
  378. contourList->globalState()->debugSetCheckHealth(false);
  379. #endif
  380. #if 01 && DEBUG_ACTIVE_SPANS
  381. // SkDebugf("active after %s:\n", id);
  382. ShowActiveSpans(contourList);
  383. #endif
  384. #endif
  385. }
  386. #endif
  387. #if DEBUG_COIN
  388. void SkPathOpsDebug::DumpGlitchType(GlitchType glitchType) {
  389. switch (glitchType) {
  390. case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
  391. case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
  392. case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
  393. case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;
  394. case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
  395. case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
  396. case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
  397. case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break;
  398. case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break;
  399. case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break;
  400. case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break;
  401. case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break;
  402. case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break;
  403. case kCorrectEnd_Glitch: SkDebugf(" CorrectEnd"); break;
  404. case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break;
  405. case kExpandCoin_Glitch: SkDebugf(" ExpandCoin"); break;
  406. case kFail_Glitch: SkDebugf(" Fail"); break;
  407. case kMarkCoinEnd_Glitch: SkDebugf(" MarkCoinEnd"); break;
  408. case kMarkCoinInsert_Glitch: SkDebugf(" MarkCoinInsert"); break;
  409. case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break;
  410. case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break;
  411. case kMergeMatches_Glitch: SkDebugf(" MergeMatches"); break;
  412. case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break;
  413. case kMissingDone_Glitch: SkDebugf(" MissingDone"); break;
  414. case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break;
  415. case kMoveMultiple_Glitch: SkDebugf(" MoveMultiple"); break;
  416. case kMoveNearbyClearAll_Glitch: SkDebugf(" MoveNearbyClearAll"); break;
  417. case kMoveNearbyClearAll2_Glitch: SkDebugf(" MoveNearbyClearAll2"); break;
  418. case kMoveNearbyMerge_Glitch: SkDebugf(" MoveNearbyMerge"); break;
  419. case kMoveNearbyMergeFinal_Glitch: SkDebugf(" MoveNearbyMergeFinal"); break;
  420. case kMoveNearbyRelease_Glitch: SkDebugf(" MoveNearbyRelease"); break;
  421. case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break;
  422. case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break;
  423. case kReturnFalse_Glitch: SkDebugf(" ReturnFalse"); break;
  424. case kUnaligned_Glitch: SkDebugf(" Unaligned"); break;
  425. case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break;
  426. case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break;
  427. case kUninitialized_Glitch: break;
  428. default: SkASSERT(0);
  429. }
  430. }
  431. #endif
  432. #if defined SK_DEBUG || !FORCE_RELEASE
  433. void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
  434. size_t len = strlen(str);
  435. bool num = false;
  436. for (size_t idx = 0; idx < len; ++idx) {
  437. if (num && str[idx] == 'e') {
  438. if (len + 2 >= bufferLen) {
  439. return;
  440. }
  441. memmove(&str[idx + 2], &str[idx + 1], len - idx);
  442. str[idx] = '*';
  443. str[idx + 1] = '^';
  444. ++len;
  445. }
  446. num = str[idx] >= '0' && str[idx] <= '9';
  447. }
  448. }
  449. bool SkPathOpsDebug::ValidWind(int wind) {
  450. return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
  451. }
  452. void SkPathOpsDebug::WindingPrintf(int wind) {
  453. if (wind == SK_MinS32) {
  454. SkDebugf("?");
  455. } else {
  456. SkDebugf("%d", wind);
  457. }
  458. }
  459. #endif // defined SK_DEBUG || !FORCE_RELEASE
  460. #if DEBUG_SHOW_TEST_NAME
  461. void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; }
  462. void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast<char*>(v); }
  463. void SkPathOpsDebug::BumpTestName(char* test) {
  464. char* num = test + strlen(test);
  465. while (num[-1] >= '0' && num[-1] <= '9') {
  466. --num;
  467. }
  468. if (num[0] == '\0') {
  469. return;
  470. }
  471. int dec = atoi(num);
  472. if (dec == 0) {
  473. return;
  474. }
  475. ++dec;
  476. SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
  477. }
  478. #endif
  479. static void show_function_header(const char* functionName) {
  480. SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
  481. if (strcmp("skphealth_com76", functionName) == 0) {
  482. SkDebugf("found it\n");
  483. }
  484. }
  485. static const char* gOpStrs[] = {
  486. "kDifference_SkPathOp",
  487. "kIntersect_SkPathOp",
  488. "kUnion_SkPathOp",
  489. "kXOR_PathOp",
  490. "kReverseDifference_SkPathOp",
  491. };
  492. const char* SkPathOpsDebug::OpStr(SkPathOp op) {
  493. return gOpStrs[op];
  494. }
  495. static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
  496. SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
  497. SkDebugf("}\n");
  498. }
  499. void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
  500. const char* testName) {
  501. static SkMutex& mutex = *(new SkMutex);
  502. SkAutoMutexExclusive ac(mutex);
  503. show_function_header(testName);
  504. ShowOnePath(a, "path", true);
  505. ShowOnePath(b, "pathB", true);
  506. show_op(shapeOp, "path", "pathB");
  507. }
  508. #include "src/pathops/SkIntersectionHelper.h"
  509. #include "src/pathops/SkIntersections.h"
  510. #include "src/pathops/SkPathOpsTypes.h"
  511. #if DEBUG_COIN
  512. void SkOpGlobalState::debugAddToGlobalCoinDicts() {
  513. static SkMutex& mutex = *(new SkMutex);
  514. SkAutoMutexExclusive ac(mutex);
  515. SkPathOpsDebug::gCoinSumChangedDict.add(fCoinChangedDict);
  516. SkPathOpsDebug::gCoinSumVisitedDict.add(fCoinVisitedDict);
  517. }
  518. #endif
  519. #if DEBUG_T_SECT_LOOP_COUNT
  520. void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
  521. const SkIntersectionHelper& wn) {
  522. for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
  523. SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
  524. if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
  525. continue;
  526. }
  527. fDebugLoopCount[index] = i->debugLoopCount(looper);
  528. fDebugWorstVerb[index * 2] = wt.segment()->verb();
  529. fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
  530. sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
  531. memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
  532. (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
  533. memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
  534. (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
  535. fDebugWorstWeight[index * 2] = wt.weight();
  536. fDebugWorstWeight[index * 2 + 1] = wn.weight();
  537. }
  538. i->debugResetLoopCount();
  539. }
  540. void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
  541. for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
  542. if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
  543. continue;
  544. }
  545. fDebugLoopCount[index] = local->fDebugLoopCount[index];
  546. fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
  547. fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
  548. memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
  549. sizeof(SkPoint) * 8);
  550. fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
  551. fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
  552. }
  553. local->debugResetLoopCounts();
  554. }
  555. static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
  556. if (!verb) {
  557. return;
  558. }
  559. const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
  560. SkDebugf("%s: {{", verbs[verb]);
  561. int ptCount = SkPathOpsVerbToPoints(verb);
  562. for (int index = 0; index <= ptCount; ++index) {
  563. SkDPoint::Dump((&pts)[index]);
  564. if (index < ptCount - 1) {
  565. SkDebugf(", ");
  566. }
  567. }
  568. SkDebugf("}");
  569. if (weight != 1) {
  570. SkDebugf(", ");
  571. if (weight == floorf(weight)) {
  572. SkDebugf("%.0f", weight);
  573. } else {
  574. SkDebugf("%1.9gf", weight);
  575. }
  576. }
  577. SkDebugf("}\n");
  578. }
  579. void SkOpGlobalState::debugLoopReport() {
  580. const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
  581. SkDebugf("\n");
  582. for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
  583. SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
  584. dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
  585. fDebugWorstWeight[index * 2]);
  586. dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
  587. fDebugWorstWeight[index * 2 + 1]);
  588. }
  589. }
  590. void SkOpGlobalState::debugResetLoopCounts() {
  591. sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
  592. sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
  593. sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
  594. sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
  595. }
  596. #endif
  597. bool SkOpGlobalState::DebugRunFail() {
  598. return SkPathOpsDebug::gRunFail;
  599. }
  600. // this is const so it can be called by const methods that overwise don't alter state
  601. #if DEBUG_VALIDATE || DEBUG_COIN
  602. void SkOpGlobalState::debugSetPhase(const char* funcName DEBUG_COIN_DECLARE_PARAMS()) const {
  603. auto writable = const_cast<SkOpGlobalState*>(this);
  604. #if DEBUG_VALIDATE
  605. writable->setPhase(phase);
  606. #endif
  607. #if DEBUG_COIN
  608. SkPathOpsDebug::CoinDictEntry* entry = &writable->fCoinDictEntry;
  609. writable->fPreviousFuncName = entry->fFunctionName;
  610. entry->fIteration = iteration;
  611. entry->fLineNumber = lineNo;
  612. entry->fGlitchType = SkPathOpsDebug::kUninitialized_Glitch;
  613. entry->fFunctionName = funcName;
  614. writable->fCoinVisitedDict.add(*entry);
  615. writable->debugAddToCoinChangedDict();
  616. #endif
  617. }
  618. #endif
  619. #if DEBUG_T_SECT_LOOP_COUNT
  620. void SkIntersections::debugBumpLoopCount(DebugLoop index) {
  621. fDebugLoopCount[index]++;
  622. }
  623. int SkIntersections::debugLoopCount(DebugLoop index) const {
  624. return fDebugLoopCount[index];
  625. }
  626. void SkIntersections::debugResetLoopCount() {
  627. sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
  628. }
  629. #endif
  630. #include "src/pathops/SkPathOpsConic.h"
  631. #include "src/pathops/SkPathOpsCubic.h"
  632. SkDCubic SkDQuad::debugToCubic() const {
  633. SkDCubic cubic;
  634. cubic[0] = fPts[0];
  635. cubic[2] = fPts[1];
  636. cubic[3] = fPts[2];
  637. cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
  638. cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
  639. cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
  640. cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
  641. return cubic;
  642. }
  643. void SkDQuad::debugSet(const SkDPoint* pts) {
  644. memcpy(fPts, pts, sizeof(fPts));
  645. SkDEBUGCODE(fDebugGlobalState = nullptr);
  646. }
  647. void SkDCubic::debugSet(const SkDPoint* pts) {
  648. memcpy(fPts, pts, sizeof(fPts));
  649. SkDEBUGCODE(fDebugGlobalState = nullptr);
  650. }
  651. void SkDConic::debugSet(const SkDPoint* pts, SkScalar weight) {
  652. fPts.debugSet(pts);
  653. fWeight = weight;
  654. }
  655. void SkDRect::debugInit() {
  656. fLeft = fTop = fRight = fBottom = SK_ScalarNaN;
  657. }
  658. #include "src/pathops/SkOpAngle.h"
  659. #include "src/pathops/SkOpSegment.h"
  660. #if DEBUG_COIN
  661. // commented-out lines keep this in sync with addT()
  662. const SkOpPtT* SkOpSegment::debugAddT(double t, SkPathOpsDebug::GlitchLog* log) const {
  663. debugValidate();
  664. SkPoint pt = this->ptAtT(t);
  665. const SkOpSpanBase* span = &fHead;
  666. do {
  667. const SkOpPtT* result = span->ptT();
  668. if (t == result->fT || this->match(result, this, t, pt)) {
  669. // span->bumpSpanAdds();
  670. return result;
  671. }
  672. if (t < result->fT) {
  673. const SkOpSpan* prev = result->span()->prev();
  674. FAIL_WITH_NULL_IF(!prev, span);
  675. // marks in global state that new op span has been allocated
  676. this->globalState()->setAllocatedOpSpan();
  677. // span->init(this, prev, t, pt);
  678. this->debugValidate();
  679. // #if DEBUG_ADD_T
  680. // SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
  681. // span->segment()->debugID(), span->debugID());
  682. // #endif
  683. // span->bumpSpanAdds();
  684. return nullptr;
  685. }
  686. FAIL_WITH_NULL_IF(span != &fTail, span);
  687. } while ((span = span->upCast()->next()));
  688. SkASSERT(0);
  689. return nullptr; // we never get here, but need this to satisfy compiler
  690. }
  691. #endif
  692. #if DEBUG_ANGLE
  693. void SkOpSegment::debugCheckAngleCoin() const {
  694. const SkOpSpanBase* base = &fHead;
  695. const SkOpSpan* span;
  696. do {
  697. const SkOpAngle* angle = base->fromAngle();
  698. if (angle && angle->debugCheckCoincidence()) {
  699. angle->debugCheckNearCoincidence();
  700. }
  701. if (base->final()) {
  702. break;
  703. }
  704. span = base->upCast();
  705. angle = span->toAngle();
  706. if (angle && angle->debugCheckCoincidence()) {
  707. angle->debugCheckNearCoincidence();
  708. }
  709. } while ((base = span->next()));
  710. }
  711. #endif
  712. #if DEBUG_COIN
  713. // this mimics the order of the checks in handle coincidence
  714. void SkOpSegment::debugCheckHealth(SkPathOpsDebug::GlitchLog* glitches) const {
  715. debugMoveMultiples(glitches);
  716. debugMoveNearby(glitches);
  717. debugMissingCoincidence(glitches);
  718. }
  719. // commented-out lines keep this in sync with clearAll()
  720. void SkOpSegment::debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const {
  721. const SkOpSpan* span = &fHead;
  722. do {
  723. this->debugClearOne(span, glitches);
  724. } while ((span = span->next()->upCastable()));
  725. this->globalState()->coincidence()->debugRelease(glitches, this);
  726. }
  727. // commented-out lines keep this in sync with clearOne()
  728. void SkOpSegment::debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const {
  729. if (span->windValue()) glitches->record(SkPathOpsDebug::kCollapsedWindValue_Glitch, span);
  730. if (span->oppValue()) glitches->record(SkPathOpsDebug::kCollapsedOppValue_Glitch, span);
  731. if (!span->done()) glitches->record(SkPathOpsDebug::kCollapsedDone_Glitch, span);
  732. }
  733. #endif
  734. SkOpAngle* SkOpSegment::debugLastAngle() {
  735. SkOpAngle* result = nullptr;
  736. SkOpSpan* span = this->head();
  737. do {
  738. if (span->toAngle()) {
  739. SkASSERT(!result);
  740. result = span->toAngle();
  741. }
  742. } while ((span = span->next()->upCastable()));
  743. SkASSERT(result);
  744. return result;
  745. }
  746. #if DEBUG_COIN
  747. // commented-out lines keep this in sync with ClearVisited
  748. void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) {
  749. // reset visited flag back to false
  750. do {
  751. const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
  752. while ((ptT = ptT->next()) != stopPtT) {
  753. const SkOpSegment* opp = ptT->segment();
  754. opp->resetDebugVisited();
  755. }
  756. } while (!span->final() && (span = span->upCast()->next()));
  757. }
  758. #endif
  759. #if DEBUG_COIN
  760. // commented-out lines keep this in sync with missingCoincidence()
  761. // look for pairs of undetected coincident curves
  762. // assumes that segments going in have visited flag clear
  763. // Even though pairs of curves correct detect coincident runs, a run may be missed
  764. // if the coincidence is a product of multiple intersections. For instance, given
  765. // curves A, B, and C:
  766. // A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
  767. // the end of C that the intersection is replaced with the end of C.
  768. // Even though A-B correctly do not detect an intersection at point 2,
  769. // the resulting run from point 1 to point 2 is coincident on A and B.
  770. void SkOpSegment::debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const {
  771. if (this->done()) {
  772. return;
  773. }
  774. const SkOpSpan* prior = nullptr;
  775. const SkOpSpanBase* spanBase = &fHead;
  776. // bool result = false;
  777. do {
  778. const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
  779. SkASSERT(ptT->span() == spanBase);
  780. while ((ptT = ptT->next()) != spanStopPtT) {
  781. if (ptT->deleted()) {
  782. continue;
  783. }
  784. const SkOpSegment* opp = ptT->span()->segment();
  785. if (opp->done()) {
  786. continue;
  787. }
  788. // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
  789. if (!opp->debugVisited()) {
  790. continue;
  791. }
  792. if (spanBase == &fHead) {
  793. continue;
  794. }
  795. if (ptT->segment() == this) {
  796. continue;
  797. }
  798. const SkOpSpan* span = spanBase->upCastable();
  799. // FIXME?: this assumes that if the opposite segment is coincident then no more
  800. // coincidence needs to be detected. This may not be true.
  801. if (span && span->segment() != opp && span->containsCoincidence(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted
  802. continue;
  803. }
  804. if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted
  805. continue;
  806. }
  807. const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
  808. // find prior span containing opp segment
  809. const SkOpSegment* priorOpp = nullptr;
  810. const SkOpSpan* priorTest = spanBase->prev();
  811. while (!priorOpp && priorTest) {
  812. priorStopPtT = priorPtT = priorTest->ptT();
  813. while ((priorPtT = priorPtT->next()) != priorStopPtT) {
  814. if (priorPtT->deleted()) {
  815. continue;
  816. }
  817. const SkOpSegment* segment = priorPtT->span()->segment();
  818. if (segment == opp) {
  819. prior = priorTest;
  820. priorOpp = opp;
  821. break;
  822. }
  823. }
  824. priorTest = priorTest->prev();
  825. }
  826. if (!priorOpp) {
  827. continue;
  828. }
  829. if (priorPtT == ptT) {
  830. continue;
  831. }
  832. const SkOpPtT* oppStart = prior->ptT();
  833. const SkOpPtT* oppEnd = spanBase->ptT();
  834. bool swapped = priorPtT->fT > ptT->fT;
  835. if (swapped) {
  836. using std::swap;
  837. swap(priorPtT, ptT);
  838. swap(oppStart, oppEnd);
  839. }
  840. const SkOpCoincidence* coincidence = this->globalState()->coincidence();
  841. const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
  842. const SkOpPtT* rootPtT = ptT->span()->ptT();
  843. const SkOpPtT* rootOppStart = oppStart->span()->ptT();
  844. const SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
  845. if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
  846. goto swapBack;
  847. }
  848. if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
  849. // mark coincidence
  850. #if DEBUG_COINCIDENCE_VERBOSE
  851. // SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
  852. // rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
  853. // rootOppEnd->debugID());
  854. #endif
  855. log->record(SkPathOpsDebug::kMissingCoin_Glitch, priorPtT, ptT, oppStart, oppEnd);
  856. // coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
  857. // }
  858. #if DEBUG_COINCIDENCE
  859. // SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
  860. #endif
  861. // result = true;
  862. }
  863. swapBack:
  864. if (swapped) {
  865. using std::swap;
  866. swap(priorPtT, ptT);
  867. }
  868. }
  869. } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
  870. DebugClearVisited(&fHead);
  871. return;
  872. }
  873. // commented-out lines keep this in sync with moveMultiples()
  874. // if a span has more than one intersection, merge the other segments' span as needed
  875. void SkOpSegment::debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const {
  876. debugValidate();
  877. const SkOpSpanBase* test = &fHead;
  878. do {
  879. int addCount = test->spanAddsCount();
  880. // SkASSERT(addCount >= 1);
  881. if (addCount <= 1) {
  882. continue;
  883. }
  884. const SkOpPtT* startPtT = test->ptT();
  885. const SkOpPtT* testPtT = startPtT;
  886. do { // iterate through all spans associated with start
  887. const SkOpSpanBase* oppSpan = testPtT->span();
  888. if (oppSpan->spanAddsCount() == addCount) {
  889. continue;
  890. }
  891. if (oppSpan->deleted()) {
  892. continue;
  893. }
  894. const SkOpSegment* oppSegment = oppSpan->segment();
  895. if (oppSegment == this) {
  896. continue;
  897. }
  898. // find range of spans to consider merging
  899. const SkOpSpanBase* oppPrev = oppSpan;
  900. const SkOpSpanBase* oppFirst = oppSpan;
  901. while ((oppPrev = oppPrev->prev())) {
  902. if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
  903. break;
  904. }
  905. if (oppPrev->spanAddsCount() == addCount) {
  906. continue;
  907. }
  908. if (oppPrev->deleted()) {
  909. continue;
  910. }
  911. oppFirst = oppPrev;
  912. }
  913. const SkOpSpanBase* oppNext = oppSpan;
  914. const SkOpSpanBase* oppLast = oppSpan;
  915. while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
  916. if (!roughly_equal(oppNext->t(), oppSpan->t())) {
  917. break;
  918. }
  919. if (oppNext->spanAddsCount() == addCount) {
  920. continue;
  921. }
  922. if (oppNext->deleted()) {
  923. continue;
  924. }
  925. oppLast = oppNext;
  926. }
  927. if (oppFirst == oppLast) {
  928. continue;
  929. }
  930. const SkOpSpanBase* oppTest = oppFirst;
  931. do {
  932. if (oppTest == oppSpan) {
  933. continue;
  934. }
  935. // check to see if the candidate meets specific criteria:
  936. // it contains spans of segments in test's loop but not including 'this'
  937. const SkOpPtT* oppStartPtT = oppTest->ptT();
  938. const SkOpPtT* oppPtT = oppStartPtT;
  939. while ((oppPtT = oppPtT->next()) != oppStartPtT) {
  940. const SkOpSegment* oppPtTSegment = oppPtT->segment();
  941. if (oppPtTSegment == this) {
  942. goto tryNextSpan;
  943. }
  944. const SkOpPtT* matchPtT = startPtT;
  945. do {
  946. if (matchPtT->segment() == oppPtTSegment) {
  947. goto foundMatch;
  948. }
  949. } while ((matchPtT = matchPtT->next()) != startPtT);
  950. goto tryNextSpan;
  951. foundMatch: // merge oppTest and oppSpan
  952. oppSegment->debugValidate();
  953. oppTest->debugMergeMatches(glitches, oppSpan);
  954. oppTest->debugAddOpp(glitches, oppSpan);
  955. oppSegment->debugValidate();
  956. goto checkNextSpan;
  957. }
  958. tryNextSpan:
  959. ;
  960. } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
  961. } while ((testPtT = testPtT->next()) != startPtT);
  962. checkNextSpan:
  963. ;
  964. } while ((test = test->final() ? nullptr : test->upCast()->next()));
  965. debugValidate();
  966. return;
  967. }
  968. // commented-out lines keep this in sync with moveNearby()
  969. // Move nearby t values and pts so they all hang off the same span. Alignment happens later.
  970. void SkOpSegment::debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const {
  971. debugValidate();
  972. // release undeleted spans pointing to this seg that are linked to the primary span
  973. const SkOpSpanBase* spanBase = &fHead;
  974. do {
  975. const SkOpPtT* ptT = spanBase->ptT();
  976. const SkOpPtT* headPtT = ptT;
  977. while ((ptT = ptT->next()) != headPtT) {
  978. const SkOpSpanBase* test = ptT->span();
  979. if (ptT->segment() == this && !ptT->deleted() && test != spanBase
  980. && test->ptT() == ptT) {
  981. if (test->final()) {
  982. if (spanBase == &fHead) {
  983. glitches->record(SkPathOpsDebug::kMoveNearbyClearAll_Glitch, this);
  984. // return;
  985. }
  986. glitches->record(SkPathOpsDebug::kMoveNearbyReleaseFinal_Glitch, spanBase, ptT);
  987. } else if (test->prev()) {
  988. glitches->record(SkPathOpsDebug::kMoveNearbyRelease_Glitch, test, headPtT);
  989. }
  990. // break;
  991. }
  992. }
  993. spanBase = spanBase->upCast()->next();
  994. } while (!spanBase->final());
  995. // This loop looks for adjacent spans which are near by
  996. spanBase = &fHead;
  997. do { // iterate through all spans associated with start
  998. const SkOpSpanBase* test = spanBase->upCast()->next();
  999. bool found;
  1000. if (!this->spansNearby(spanBase, test, &found)) {
  1001. glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test);
  1002. }
  1003. if (found) {
  1004. if (test->final()) {
  1005. if (spanBase->prev()) {
  1006. glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test);
  1007. } else {
  1008. glitches->record(SkPathOpsDebug::kMoveNearbyClearAll2_Glitch, this);
  1009. // return
  1010. }
  1011. } else {
  1012. glitches->record(SkPathOpsDebug::kMoveNearbyMerge_Glitch, spanBase);
  1013. }
  1014. }
  1015. spanBase = test;
  1016. } while (!spanBase->final());
  1017. debugValidate();
  1018. }
  1019. #endif
  1020. void SkOpSegment::debugReset() {
  1021. this->init(this->fPts, this->fWeight, this->contour(), this->verb());
  1022. }
  1023. #if DEBUG_COINCIDENCE_ORDER
  1024. void SkOpSegment::debugSetCoinT(int index, SkScalar t) const {
  1025. if (fDebugBaseMax < 0 || fDebugBaseIndex == index) {
  1026. fDebugBaseIndex = index;
  1027. fDebugBaseMin = SkTMin(t, fDebugBaseMin);
  1028. fDebugBaseMax = SkTMax(t, fDebugBaseMax);
  1029. return;
  1030. }
  1031. SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax);
  1032. if (fDebugLastMax < 0 || fDebugLastIndex == index) {
  1033. fDebugLastIndex = index;
  1034. fDebugLastMin = SkTMin(t, fDebugLastMin);
  1035. fDebugLastMax = SkTMax(t, fDebugLastMax);
  1036. return;
  1037. }
  1038. SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax);
  1039. SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0));
  1040. }
  1041. #endif
  1042. #if DEBUG_ACTIVE_SPANS
  1043. void SkOpSegment::debugShowActiveSpans(SkString* str) const {
  1044. debugValidate();
  1045. if (done()) {
  1046. return;
  1047. }
  1048. int lastId = -1;
  1049. double lastT = -1;
  1050. const SkOpSpan* span = &fHead;
  1051. do {
  1052. if (span->done()) {
  1053. continue;
  1054. }
  1055. if (lastId == this->debugID() && lastT == span->t()) {
  1056. continue;
  1057. }
  1058. lastId = this->debugID();
  1059. lastT = span->t();
  1060. str->appendf("%s id=%d", __FUNCTION__, this->debugID());
  1061. // since endpoints may have be adjusted, show actual computed curves
  1062. SkDCurve curvePart;
  1063. this->subDivide(span, span->next(), &curvePart);
  1064. const SkDPoint* pts = curvePart.fCubic.fPts;
  1065. str->appendf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY);
  1066. for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
  1067. str->appendf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY);
  1068. }
  1069. if (SkPath::kConic_Verb == fVerb) {
  1070. str->appendf(" %1.9gf", curvePart.fConic.fWeight);
  1071. }
  1072. str->appendf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t());
  1073. if (span->windSum() == SK_MinS32) {
  1074. str->appendf(" windSum=?");
  1075. } else {
  1076. str->appendf(" windSum=%d", span->windSum());
  1077. }
  1078. if (span->oppValue() && span->oppSum() == SK_MinS32) {
  1079. str->appendf(" oppSum=?");
  1080. } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
  1081. str->appendf(" oppSum=%d", span->oppSum());
  1082. }
  1083. str->appendf(" windValue=%d", span->windValue());
  1084. if (span->oppValue() || span->oppSum() != SK_MinS32) {
  1085. str->appendf(" oppValue=%d", span->oppValue());
  1086. }
  1087. str->appendf("\n");
  1088. } while ((span = span->next()->upCastable()));
  1089. }
  1090. #endif
  1091. #if DEBUG_MARK_DONE
  1092. void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
  1093. const SkPoint& pt = span->ptT()->fPt;
  1094. SkDebugf("%s id=%d", fun, this->debugID());
  1095. SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
  1096. for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
  1097. SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
  1098. }
  1099. SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
  1100. span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
  1101. if (winding == SK_MinS32) {
  1102. SkDebugf("?");
  1103. } else {
  1104. SkDebugf("%d", winding);
  1105. }
  1106. SkDebugf(" windSum=");
  1107. if (span->windSum() == SK_MinS32) {
  1108. SkDebugf("?");
  1109. } else {
  1110. SkDebugf("%d", span->windSum());
  1111. }
  1112. SkDebugf(" windValue=%d\n", span->windValue());
  1113. }
  1114. void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
  1115. int oppWinding) {
  1116. const SkPoint& pt = span->ptT()->fPt;
  1117. SkDebugf("%s id=%d", fun, this->debugID());
  1118. SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
  1119. for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
  1120. SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
  1121. }
  1122. SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
  1123. span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
  1124. if (winding == SK_MinS32) {
  1125. SkDebugf("?");
  1126. } else {
  1127. SkDebugf("%d", winding);
  1128. }
  1129. SkDebugf(" newOppSum=");
  1130. if (oppWinding == SK_MinS32) {
  1131. SkDebugf("?");
  1132. } else {
  1133. SkDebugf("%d", oppWinding);
  1134. }
  1135. SkDebugf(" oppSum=");
  1136. if (span->oppSum() == SK_MinS32) {
  1137. SkDebugf("?");
  1138. } else {
  1139. SkDebugf("%d", span->oppSum());
  1140. }
  1141. SkDebugf(" windSum=");
  1142. if (span->windSum() == SK_MinS32) {
  1143. SkDebugf("?");
  1144. } else {
  1145. SkDebugf("%d", span->windSum());
  1146. }
  1147. SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
  1148. }
  1149. #endif
  1150. // loop looking for a pair of angle parts that are too close to be sorted
  1151. /* This is called after other more simple intersection and angle sorting tests have been exhausted.
  1152. This should be rarely called -- the test below is thorough and time consuming.
  1153. This checks the distance between start points; the distance between
  1154. */
  1155. #if DEBUG_ANGLE
  1156. void SkOpAngle::debugCheckNearCoincidence() const {
  1157. const SkOpAngle* test = this;
  1158. do {
  1159. const SkOpSegment* testSegment = test->segment();
  1160. double testStartT = test->start()->t();
  1161. SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
  1162. double testEndT = test->end()->t();
  1163. SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
  1164. double testLenSq = testStartPt.distanceSquared(testEndPt);
  1165. SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
  1166. double testMidT = (testStartT + testEndT) / 2;
  1167. const SkOpAngle* next = test;
  1168. while ((next = next->fNext) != this) {
  1169. SkOpSegment* nextSegment = next->segment();
  1170. double testMidDistSq = testSegment->distSq(testMidT, next);
  1171. double testEndDistSq = testSegment->distSq(testEndT, next);
  1172. double nextStartT = next->start()->t();
  1173. SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
  1174. double distSq = testStartPt.distanceSquared(nextStartPt);
  1175. double nextEndT = next->end()->t();
  1176. double nextMidT = (nextStartT + nextEndT) / 2;
  1177. double nextMidDistSq = nextSegment->distSq(nextMidT, test);
  1178. double nextEndDistSq = nextSegment->distSq(nextEndT, test);
  1179. SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
  1180. testSegment->debugID(), nextSegment->debugID());
  1181. SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
  1182. SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
  1183. SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
  1184. SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
  1185. SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
  1186. double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
  1187. SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
  1188. SkDebugf("\n");
  1189. }
  1190. test = test->fNext;
  1191. } while (test->fNext != this);
  1192. }
  1193. #endif
  1194. #if DEBUG_ANGLE
  1195. SkString SkOpAngle::debugPart() const {
  1196. SkString result;
  1197. switch (this->segment()->verb()) {
  1198. case SkPath::kLine_Verb:
  1199. result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fPart.fCurve),
  1200. this->segment()->debugID());
  1201. break;
  1202. case SkPath::kQuad_Verb:
  1203. result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fPart.fCurve),
  1204. this->segment()->debugID());
  1205. break;
  1206. case SkPath::kConic_Verb:
  1207. result.printf(CONIC_DEBUG_STR " id=%d",
  1208. CONIC_DEBUG_DATA(fPart.fCurve, fPart.fCurve.fConic.fWeight),
  1209. this->segment()->debugID());
  1210. break;
  1211. case SkPath::kCubic_Verb:
  1212. result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fPart.fCurve),
  1213. this->segment()->debugID());
  1214. break;
  1215. default:
  1216. SkASSERT(0);
  1217. }
  1218. return result;
  1219. }
  1220. #endif
  1221. #if DEBUG_SORT
  1222. void SkOpAngle::debugLoop() const {
  1223. const SkOpAngle* first = this;
  1224. const SkOpAngle* next = this;
  1225. do {
  1226. next->dumpOne(true);
  1227. SkDebugf("\n");
  1228. next = next->fNext;
  1229. } while (next && next != first);
  1230. next = first;
  1231. do {
  1232. next->debugValidate();
  1233. next = next->fNext;
  1234. } while (next && next != first);
  1235. }
  1236. #endif
  1237. void SkOpAngle::debugValidate() const {
  1238. #if DEBUG_COINCIDENCE
  1239. if (this->globalState()->debugCheckHealth()) {
  1240. return;
  1241. }
  1242. #endif
  1243. #if DEBUG_VALIDATE
  1244. const SkOpAngle* first = this;
  1245. const SkOpAngle* next = this;
  1246. int wind = 0;
  1247. int opp = 0;
  1248. int lastXor = -1;
  1249. int lastOppXor = -1;
  1250. do {
  1251. if (next->unorderable()) {
  1252. return;
  1253. }
  1254. const SkOpSpan* minSpan = next->start()->starter(next->end());
  1255. if (minSpan->windValue() == SK_MinS32) {
  1256. return;
  1257. }
  1258. bool op = next->segment()->operand();
  1259. bool isXor = next->segment()->isXor();
  1260. bool oppXor = next->segment()->oppXor();
  1261. SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
  1262. SkASSERT(!DEBUG_LIMIT_WIND_SUM
  1263. || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
  1264. bool useXor = op ? oppXor : isXor;
  1265. SkASSERT(lastXor == -1 || lastXor == (int) useXor);
  1266. lastXor = (int) useXor;
  1267. wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
  1268. if (useXor) {
  1269. wind &= 1;
  1270. }
  1271. useXor = op ? isXor : oppXor;
  1272. SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
  1273. lastOppXor = (int) useXor;
  1274. opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
  1275. if (useXor) {
  1276. opp &= 1;
  1277. }
  1278. next = next->fNext;
  1279. } while (next && next != first);
  1280. SkASSERT(wind == 0 || !SkPathOpsDebug::gRunFail);
  1281. SkASSERT(opp == 0 || !SkPathOpsDebug::gRunFail);
  1282. #endif
  1283. }
  1284. void SkOpAngle::debugValidateNext() const {
  1285. #if !FORCE_RELEASE
  1286. const SkOpAngle* first = this;
  1287. const SkOpAngle* next = first;
  1288. SkTDArray<const SkOpAngle*>(angles);
  1289. do {
  1290. // SkASSERT_RELEASE(next->fSegment->debugContains(next));
  1291. angles.push_back(next);
  1292. next = next->next();
  1293. if (next == first) {
  1294. break;
  1295. }
  1296. SkASSERT_RELEASE(!angles.contains(next));
  1297. if (!next) {
  1298. return;
  1299. }
  1300. } while (true);
  1301. #endif
  1302. }
  1303. #ifdef SK_DEBUG
  1304. void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
  1305. const SkOpGlobalState* debugState) const {
  1306. SkASSERT(coinPtTEnd()->span() == over || !SkOpGlobalState::DebugRunFail());
  1307. SkASSERT(oppPtTEnd()->span() == outer || !SkOpGlobalState::DebugRunFail());
  1308. }
  1309. #endif
  1310. #if DEBUG_COIN
  1311. // sets the span's end to the ptT referenced by the previous-next
  1312. void SkCoincidentSpans::debugCorrectOneEnd(SkPathOpsDebug::GlitchLog* log,
  1313. const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
  1314. void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) const ) const {
  1315. const SkOpPtT* origPtT = (this->*getEnd)();
  1316. const SkOpSpanBase* origSpan = origPtT->span();
  1317. const SkOpSpan* prev = origSpan->prev();
  1318. const SkOpPtT* testPtT = prev ? prev->next()->ptT()
  1319. : origSpan->upCast()->next()->prev()->ptT();
  1320. if (origPtT != testPtT) {
  1321. log->record(SkPathOpsDebug::kCorrectEnd_Glitch, this, origPtT, testPtT);
  1322. }
  1323. }
  1324. /* Commented-out lines keep this in sync with correctEnds */
  1325. // FIXME: member pointers have fallen out of favor and can be replaced with
  1326. // an alternative approach.
  1327. // makes all span ends agree with the segment's spans that define them
  1328. void SkCoincidentSpans::debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const {
  1329. this->debugCorrectOneEnd(log, &SkCoincidentSpans::coinPtTStart, nullptr);
  1330. this->debugCorrectOneEnd(log, &SkCoincidentSpans::coinPtTEnd, nullptr);
  1331. this->debugCorrectOneEnd(log, &SkCoincidentSpans::oppPtTStart, nullptr);
  1332. this->debugCorrectOneEnd(log, &SkCoincidentSpans::oppPtTEnd, nullptr);
  1333. }
  1334. /* Commented-out lines keep this in sync with expand */
  1335. // expand the range by checking adjacent spans for coincidence
  1336. bool SkCoincidentSpans::debugExpand(SkPathOpsDebug::GlitchLog* log) const {
  1337. bool expanded = false;
  1338. const SkOpSegment* segment = coinPtTStart()->segment();
  1339. const SkOpSegment* oppSegment = oppPtTStart()->segment();
  1340. do {
  1341. const SkOpSpan* start = coinPtTStart()->span()->upCast();
  1342. const SkOpSpan* prev = start->prev();
  1343. const SkOpPtT* oppPtT;
  1344. if (!prev || !(oppPtT = prev->contains(oppSegment))) {
  1345. break;
  1346. }
  1347. double midT = (prev->t() + start->t()) / 2;
  1348. if (!segment->isClose(midT, oppSegment)) {
  1349. break;
  1350. }
  1351. if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, this, prev->ptT(), oppPtT);
  1352. expanded = true;
  1353. } while (false); // actual continues while expansion is possible
  1354. do {
  1355. const SkOpSpanBase* end = coinPtTEnd()->span();
  1356. SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
  1357. if (next && next->deleted()) {
  1358. break;
  1359. }
  1360. const SkOpPtT* oppPtT;
  1361. if (!next || !(oppPtT = next->contains(oppSegment))) {
  1362. break;
  1363. }
  1364. double midT = (end->t() + next->t()) / 2;
  1365. if (!segment->isClose(midT, oppSegment)) {
  1366. break;
  1367. }
  1368. if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, this, next->ptT(), oppPtT);
  1369. expanded = true;
  1370. } while (false); // actual continues while expansion is possible
  1371. return expanded;
  1372. }
  1373. // description below
  1374. void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log, const SkOpSpan* base, const SkOpSpanBase* testSpan) const {
  1375. const SkOpPtT* testPtT = testSpan->ptT();
  1376. const SkOpPtT* stopPtT = testPtT;
  1377. const SkOpSegment* baseSeg = base->segment();
  1378. while ((testPtT = testPtT->next()) != stopPtT) {
  1379. const SkOpSegment* testSeg = testPtT->segment();
  1380. if (testPtT->deleted()) {
  1381. continue;
  1382. }
  1383. if (testSeg == baseSeg) {
  1384. continue;
  1385. }
  1386. if (testPtT->span()->ptT() != testPtT) {
  1387. continue;
  1388. }
  1389. if (this->contains(baseSeg, testSeg, testPtT->fT)) {
  1390. continue;
  1391. }
  1392. // intersect perp with base->ptT() with testPtT->segment()
  1393. SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
  1394. const SkPoint& pt = base->pt();
  1395. SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
  1396. SkIntersections i;
  1397. (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
  1398. for (int index = 0; index < i.used(); ++index) {
  1399. double t = i[0][index];
  1400. if (!between(0, t, 1)) {
  1401. continue;
  1402. }
  1403. SkDPoint oppPt = i.pt(index);
  1404. if (!oppPt.approximatelyEqual(pt)) {
  1405. continue;
  1406. }
  1407. SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
  1408. SkOpPtT* oppStart = writableSeg->addT(t);
  1409. if (oppStart == testPtT) {
  1410. continue;
  1411. }
  1412. SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
  1413. oppStart->span()->addOpp(writableBase);
  1414. if (oppStart->deleted()) {
  1415. continue;
  1416. }
  1417. SkOpSegment* coinSeg = base->segment();
  1418. SkOpSegment* oppSeg = oppStart->segment();
  1419. double coinTs, coinTe, oppTs, oppTe;
  1420. if (Ordered(coinSeg, oppSeg)) {
  1421. coinTs = base->t();
  1422. coinTe = testSpan->t();
  1423. oppTs = oppStart->fT;
  1424. oppTe = testPtT->fT;
  1425. } else {
  1426. using std::swap;
  1427. swap(coinSeg, oppSeg);
  1428. coinTs = oppStart->fT;
  1429. coinTe = testPtT->fT;
  1430. oppTs = base->t();
  1431. oppTe = testSpan->t();
  1432. }
  1433. if (coinTs > coinTe) {
  1434. using std::swap;
  1435. swap(coinTs, coinTe);
  1436. swap(oppTs, oppTe);
  1437. }
  1438. bool added;
  1439. if (this->debugAddOrOverlap(log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added), false) {
  1440. return;
  1441. }
  1442. }
  1443. }
  1444. return;
  1445. }
  1446. // description below
  1447. void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* ptT) const {
  1448. FAIL_IF(!ptT->span()->upCastable(), ptT->span());
  1449. const SkOpSpan* base = ptT->span()->upCast();
  1450. const SkOpSpan* prev = base->prev();
  1451. FAIL_IF(!prev, ptT->span());
  1452. if (!prev->isCanceled()) {
  1453. if (this->debugAddEndMovedSpans(log, base, base->prev()), false) {
  1454. return;
  1455. }
  1456. }
  1457. if (!base->isCanceled()) {
  1458. if (this->debugAddEndMovedSpans(log, base, base->next()), false) {
  1459. return;
  1460. }
  1461. }
  1462. return;
  1463. }
  1464. /* If A is coincident with B and B includes an endpoint, and A's matching point
  1465. is not the endpoint (i.e., there's an implied line connecting B-end and A)
  1466. then assume that the same implied line may intersect another curve close to B.
  1467. Since we only care about coincidence that was undetected, look at the
  1468. ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
  1469. next door) and see if the A matching point is close enough to form another
  1470. coincident pair. If so, check for a new coincident span between B-end/A ptT loop
  1471. and the adjacent ptT loop.
  1472. */
  1473. void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log) const {
  1474. const SkCoincidentSpans* span = fHead;
  1475. if (!span) {
  1476. return;
  1477. }
  1478. // fTop = span;
  1479. // fHead = nullptr;
  1480. do {
  1481. if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
  1482. FAIL_IF(1 == span->coinPtTStart()->fT, span);
  1483. bool onEnd = span->coinPtTStart()->fT == 0;
  1484. bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
  1485. if (onEnd) {
  1486. if (!oOnEnd) { // if both are on end, any nearby intersect was already found
  1487. if (this->debugAddEndMovedSpans(log, span->oppPtTStart()), false) {
  1488. return;
  1489. }
  1490. }
  1491. } else if (oOnEnd) {
  1492. if (this->debugAddEndMovedSpans(log, span->coinPtTStart()), false) {
  1493. return;
  1494. }
  1495. }
  1496. }
  1497. if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
  1498. bool onEnd = span->coinPtTEnd()->fT == 1;
  1499. bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
  1500. if (onEnd) {
  1501. if (!oOnEnd) {
  1502. if (this->debugAddEndMovedSpans(log, span->oppPtTEnd()), false) {
  1503. return;
  1504. }
  1505. }
  1506. } else if (oOnEnd) {
  1507. if (this->debugAddEndMovedSpans(log, span->coinPtTEnd()), false) {
  1508. return;
  1509. }
  1510. }
  1511. }
  1512. } while ((span = span->next()));
  1513. // this->restoreHead();
  1514. return;
  1515. }
  1516. /* Commented-out lines keep this in sync with addExpanded */
  1517. // for each coincident pair, match the spans
  1518. // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
  1519. void SkOpCoincidence::debugAddExpanded(SkPathOpsDebug::GlitchLog* log) const {
  1520. // DEBUG_SET_PHASE();
  1521. const SkCoincidentSpans* coin = this->fHead;
  1522. if (!coin) {
  1523. return;
  1524. }
  1525. do {
  1526. const SkOpPtT* startPtT = coin->coinPtTStart();
  1527. const SkOpPtT* oStartPtT = coin->oppPtTStart();
  1528. double priorT = startPtT->fT;
  1529. double oPriorT = oStartPtT->fT;
  1530. FAIL_IF(!startPtT->contains(oStartPtT), coin);
  1531. SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
  1532. const SkOpSpanBase* start = startPtT->span();
  1533. const SkOpSpanBase* oStart = oStartPtT->span();
  1534. const SkOpSpanBase* end = coin->coinPtTEnd()->span();
  1535. const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
  1536. FAIL_IF(oEnd->deleted(), coin);
  1537. FAIL_IF(!start->upCastable(), coin);
  1538. const SkOpSpanBase* test = start->upCast()->next();
  1539. FAIL_IF(!coin->flipped() && !oStart->upCastable(), coin);
  1540. const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
  1541. FAIL_IF(!oTest, coin);
  1542. const SkOpSegment* seg = start->segment();
  1543. const SkOpSegment* oSeg = oStart->segment();
  1544. while (test != end || oTest != oEnd) {
  1545. const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
  1546. const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
  1547. if (!containedOpp || !containedThis) {
  1548. // choose the ends, or the first common pt-t list shared by both
  1549. double nextT, oNextT;
  1550. if (containedOpp) {
  1551. nextT = test->t();
  1552. oNextT = containedOpp->fT;
  1553. } else if (containedThis) {
  1554. nextT = containedThis->fT;
  1555. oNextT = oTest->t();
  1556. } else {
  1557. // iterate through until a pt-t list found that contains the other
  1558. const SkOpSpanBase* walk = test;
  1559. const SkOpPtT* walkOpp;
  1560. do {
  1561. FAIL_IF(!walk->upCastable(), coin);
  1562. walk = walk->upCast()->next();
  1563. } while (!(walkOpp = walk->ptT()->contains(oSeg))
  1564. && walk != coin->coinPtTEnd()->span());
  1565. FAIL_IF(!walkOpp, coin);
  1566. nextT = walk->t();
  1567. oNextT = walkOpp->fT;
  1568. }
  1569. // use t ranges to guess which one is missing
  1570. double startRange = nextT - priorT;
  1571. FAIL_IF(!startRange, coin);
  1572. double startPart = (test->t() - priorT) / startRange;
  1573. double oStartRange = oNextT - oPriorT;
  1574. FAIL_IF(!oStartRange, coin);
  1575. double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
  1576. FAIL_IF(startPart == oStartPart, coin);
  1577. bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
  1578. : !!containedThis;
  1579. bool startOver = false;
  1580. addToOpp ? log->record(SkPathOpsDebug::kAddExpandedCoin_Glitch,
  1581. oPriorT + oStartRange * startPart, test)
  1582. : log->record(SkPathOpsDebug::kAddExpandedCoin_Glitch,
  1583. priorT + startRange * oStartPart, oTest);
  1584. // FAIL_IF(!success, coin);
  1585. if (startOver) {
  1586. test = start;
  1587. oTest = oStart;
  1588. }
  1589. end = coin->coinPtTEnd()->span();
  1590. oEnd = coin->oppPtTEnd()->span();
  1591. }
  1592. if (test != end) {
  1593. FAIL_IF(!test->upCastable(), coin);
  1594. priorT = test->t();
  1595. test = test->upCast()->next();
  1596. }
  1597. if (oTest != oEnd) {
  1598. oPriorT = oTest->t();
  1599. oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
  1600. FAIL_IF(!oTest, coin);
  1601. }
  1602. }
  1603. } while ((coin = coin->next()));
  1604. return;
  1605. }
  1606. /* Commented-out lines keep this in sync addIfMissing() */
  1607. // note that over1s, over1e, over2s, over2e are ordered
  1608. void SkOpCoincidence::debugAddIfMissing(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s,
  1609. double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added,
  1610. const SkOpPtT* over1e, const SkOpPtT* over2e) const {
  1611. SkASSERT(tStart < tEnd);
  1612. SkASSERT(over1s->fT < over1e->fT);
  1613. SkASSERT(between(over1s->fT, tStart, over1e->fT));
  1614. SkASSERT(between(over1s->fT, tEnd, over1e->fT));
  1615. SkASSERT(over2s->fT < over2e->fT);
  1616. SkASSERT(between(over2s->fT, tStart, over2e->fT));
  1617. SkASSERT(between(over2s->fT, tEnd, over2e->fT));
  1618. SkASSERT(over1s->segment() == over1e->segment());
  1619. SkASSERT(over2s->segment() == over2e->segment());
  1620. SkASSERT(over1s->segment() == over2s->segment());
  1621. SkASSERT(over1s->segment() != coinSeg);
  1622. SkASSERT(over1s->segment() != oppSeg);
  1623. SkASSERT(coinSeg != oppSeg);
  1624. double coinTs, coinTe, oppTs, oppTe;
  1625. coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e));
  1626. coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e));
  1627. SkOpSpanBase::Collapsed result = coinSeg->collapsed(coinTs, coinTe);
  1628. if (SkOpSpanBase::Collapsed::kNo != result) {
  1629. return log->record(SkPathOpsDebug::kAddIfCollapsed_Glitch, coinSeg);
  1630. }
  1631. oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e));
  1632. oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e));
  1633. result = oppSeg->collapsed(oppTs, oppTe);
  1634. if (SkOpSpanBase::Collapsed::kNo != result) {
  1635. return log->record(SkPathOpsDebug::kAddIfCollapsed_Glitch, oppSeg);
  1636. }
  1637. if (coinTs > coinTe) {
  1638. using std::swap;
  1639. swap(coinTs, coinTe);
  1640. swap(oppTs, oppTe);
  1641. }
  1642. this->debugAddOrOverlap(log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
  1643. return;
  1644. }
  1645. /* Commented-out lines keep this in sync addOrOverlap() */
  1646. // If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
  1647. // If this is called by AddIfMissing(), a returned false indicates there was nothing to add
  1648. void SkOpCoincidence::debugAddOrOverlap(SkPathOpsDebug::GlitchLog* log,
  1649. const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
  1650. double coinTs, double coinTe, double oppTs, double oppTe, bool* added) const {
  1651. SkTDArray<SkCoincidentSpans*> overlaps;
  1652. SkOPASSERT(!fTop); // this is (correctly) reversed in addifMissing()
  1653. if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe,
  1654. &overlaps)) {
  1655. return;
  1656. }
  1657. if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
  1658. coinTe, oppTs, oppTe, &overlaps)) {
  1659. return;
  1660. }
  1661. const SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
  1662. for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
  1663. const SkCoincidentSpans* test = overlaps[index];
  1664. if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
  1665. log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->coinPtTStart());
  1666. }
  1667. if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
  1668. log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->coinPtTEnd());
  1669. }
  1670. if (overlap->flipped()
  1671. ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
  1672. : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
  1673. log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->oppPtTStart());
  1674. }
  1675. if (overlap->flipped()
  1676. ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
  1677. : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
  1678. log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->oppPtTEnd());
  1679. }
  1680. if (!fHead) { this->debugRelease(log, fHead, test);
  1681. this->debugRelease(log, fTop, test);
  1682. }
  1683. }
  1684. const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
  1685. const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
  1686. RETURN_FALSE_IF(overlap && cs && ce && overlap->contains(cs, ce), coinSeg);
  1687. RETURN_FALSE_IF(cs != ce || !cs, coinSeg);
  1688. const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
  1689. const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
  1690. RETURN_FALSE_IF(overlap && os && oe && overlap->contains(os, oe), oppSeg);
  1691. SkASSERT(true || !cs || !cs->deleted());
  1692. SkASSERT(true || !os || !os->deleted());
  1693. SkASSERT(true || !ce || !ce->deleted());
  1694. SkASSERT(true || !oe || !oe->deleted());
  1695. const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
  1696. const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
  1697. RETURN_FALSE_IF(csExisting && csExisting == ceExisting, coinSeg);
  1698. RETURN_FALSE_IF(csExisting && (csExisting == ce ||
  1699. csExisting->contains(ceExisting ? ceExisting : ce)), coinSeg);
  1700. RETURN_FALSE_IF(ceExisting && (ceExisting == cs ||
  1701. ceExisting->contains(csExisting ? csExisting : cs)), coinSeg);
  1702. const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
  1703. const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
  1704. RETURN_FALSE_IF(osExisting && osExisting == oeExisting, oppSeg);
  1705. RETURN_FALSE_IF(osExisting && (osExisting == oe ||
  1706. osExisting->contains(oeExisting ? oeExisting : oe)), oppSeg);
  1707. RETURN_FALSE_IF(oeExisting && (oeExisting == os ||
  1708. oeExisting->contains(osExisting ? osExisting : os)), oppSeg);
  1709. bool csDeleted = false, osDeleted = false, ceDeleted = false, oeDeleted = false;
  1710. this->debugValidate();
  1711. if (!cs || !os) {
  1712. if (!cs)
  1713. cs = coinSeg->debugAddT(coinTs, log);
  1714. if (!os)
  1715. os = oppSeg->debugAddT(oppTs, log);
  1716. // RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable);
  1717. if (cs && os) cs->span()->debugAddOpp(log, os->span());
  1718. // cs = csWritable;
  1719. // os = osWritable->active();
  1720. RETURN_FALSE_IF((ce && ce->deleted()) || (oe && oe->deleted()), coinSeg);
  1721. }
  1722. if (!ce || !oe) {
  1723. if (!ce)
  1724. ce = coinSeg->debugAddT(coinTe, log);
  1725. if (!oe)
  1726. oe = oppSeg->debugAddT(oppTe, log);
  1727. if (ce && oe) ce->span()->debugAddOpp(log, oe->span());
  1728. // ce = ceWritable;
  1729. // oe = oeWritable;
  1730. }
  1731. this->debugValidate();
  1732. RETURN_FALSE_IF(csDeleted, coinSeg);
  1733. RETURN_FALSE_IF(osDeleted, oppSeg);
  1734. RETURN_FALSE_IF(ceDeleted, coinSeg);
  1735. RETURN_FALSE_IF(oeDeleted, oppSeg);
  1736. RETURN_FALSE_IF(!cs || !ce || cs == ce || cs->contains(ce) || !os || !oe || os == oe || os->contains(oe), coinSeg);
  1737. bool result = true;
  1738. if (overlap) {
  1739. if (overlap->coinPtTStart()->segment() == coinSeg) {
  1740. log->record(SkPathOpsDebug::kAddMissingExtend_Glitch, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
  1741. } else {
  1742. if (oppTs > oppTe) {
  1743. using std::swap;
  1744. swap(coinTs, coinTe);
  1745. swap(oppTs, oppTe);
  1746. }
  1747. log->record(SkPathOpsDebug::kAddMissingExtend_Glitch, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
  1748. }
  1749. #if 0 && DEBUG_COINCIDENCE_VERBOSE
  1750. if (result) {
  1751. overlap->debugShow();
  1752. }
  1753. #endif
  1754. } else {
  1755. log->record(SkPathOpsDebug::kAddMissingCoin_Glitch, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
  1756. #if 0 && DEBUG_COINCIDENCE_VERBOSE
  1757. fHead->debugShow();
  1758. #endif
  1759. }
  1760. this->debugValidate();
  1761. return (void) result;
  1762. }
  1763. // Extra commented-out lines keep this in sync with addMissing()
  1764. /* detects overlaps of different coincident runs on same segment */
  1765. /* does not detect overlaps for pairs without any segments in common */
  1766. // returns true if caller should loop again
  1767. void SkOpCoincidence::debugAddMissing(SkPathOpsDebug::GlitchLog* log, bool* added) const {
  1768. const SkCoincidentSpans* outer = fHead;
  1769. *added = false;
  1770. if (!outer) {
  1771. return;
  1772. }
  1773. // fTop = outer;
  1774. // fHead = nullptr;
  1775. do {
  1776. // addifmissing can modify the list that this is walking
  1777. // save head so that walker can iterate over old data unperturbed
  1778. // addifmissing adds to head freely then add saved head in the end
  1779. const SkOpPtT* ocs = outer->coinPtTStart();
  1780. SkASSERT(!ocs->deleted());
  1781. const SkOpSegment* outerCoin = ocs->segment();
  1782. SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list
  1783. const SkOpPtT* oos = outer->oppPtTStart();
  1784. if (oos->deleted()) {
  1785. return;
  1786. }
  1787. const SkOpSegment* outerOpp = oos->segment();
  1788. SkASSERT(!outerOpp->done());
  1789. // SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
  1790. // SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
  1791. const SkCoincidentSpans* inner = outer;
  1792. while ((inner = inner->next())) {
  1793. this->debugValidate();
  1794. double overS, overE;
  1795. const SkOpPtT* ics = inner->coinPtTStart();
  1796. SkASSERT(!ics->deleted());
  1797. const SkOpSegment* innerCoin = ics->segment();
  1798. SkASSERT(!innerCoin->done());
  1799. const SkOpPtT* ios = inner->oppPtTStart();
  1800. SkASSERT(!ios->deleted());
  1801. const SkOpSegment* innerOpp = ios->segment();
  1802. SkASSERT(!innerOpp->done());
  1803. // SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
  1804. // SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
  1805. if (outerCoin == innerCoin) {
  1806. const SkOpPtT* oce = outer->coinPtTEnd();
  1807. if (oce->deleted()) {
  1808. return;
  1809. }
  1810. const SkOpPtT* ice = inner->coinPtTEnd();
  1811. SkASSERT(!ice->deleted());
  1812. if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
  1813. this->debugAddIfMissing(log, ocs->starter(oce), ics->starter(ice),
  1814. overS, overE, outerOpp, innerOpp, added,
  1815. ocs->debugEnder(oce),
  1816. ics->debugEnder(ice));
  1817. }
  1818. } else if (outerCoin == innerOpp) {
  1819. const SkOpPtT* oce = outer->coinPtTEnd();
  1820. SkASSERT(!oce->deleted());
  1821. const SkOpPtT* ioe = inner->oppPtTEnd();
  1822. SkASSERT(!ioe->deleted());
  1823. if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
  1824. this->debugAddIfMissing(log, ocs->starter(oce), ios->starter(ioe),
  1825. overS, overE, outerOpp, innerCoin, added,
  1826. ocs->debugEnder(oce),
  1827. ios->debugEnder(ioe));
  1828. }
  1829. } else if (outerOpp == innerCoin) {
  1830. const SkOpPtT* ooe = outer->oppPtTEnd();
  1831. SkASSERT(!ooe->deleted());
  1832. const SkOpPtT* ice = inner->coinPtTEnd();
  1833. SkASSERT(!ice->deleted());
  1834. SkASSERT(outerCoin != innerOpp);
  1835. if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
  1836. this->debugAddIfMissing(log, oos->starter(ooe), ics->starter(ice),
  1837. overS, overE, outerCoin, innerOpp, added,
  1838. oos->debugEnder(ooe),
  1839. ics->debugEnder(ice));
  1840. }
  1841. } else if (outerOpp == innerOpp) {
  1842. const SkOpPtT* ooe = outer->oppPtTEnd();
  1843. SkASSERT(!ooe->deleted());
  1844. const SkOpPtT* ioe = inner->oppPtTEnd();
  1845. if (ioe->deleted()) {
  1846. return;
  1847. }
  1848. SkASSERT(outerCoin != innerCoin);
  1849. if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
  1850. this->debugAddIfMissing(log, oos->starter(ooe), ios->starter(ioe),
  1851. overS, overE, outerCoin, innerCoin, added,
  1852. oos->debugEnder(ooe),
  1853. ios->debugEnder(ioe));
  1854. }
  1855. }
  1856. this->debugValidate();
  1857. }
  1858. } while ((outer = outer->next()));
  1859. // this->restoreHead();
  1860. return;
  1861. }
  1862. // Commented-out lines keep this in sync with release()
  1863. void SkOpCoincidence::debugRelease(SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkCoincidentSpans* remove) const {
  1864. const SkCoincidentSpans* head = coin;
  1865. const SkCoincidentSpans* prev = nullptr;
  1866. const SkCoincidentSpans* next;
  1867. do {
  1868. next = coin->next();
  1869. if (coin == remove) {
  1870. if (prev) {
  1871. // prev->setNext(next);
  1872. } else if (head == fHead) {
  1873. // fHead = next;
  1874. } else {
  1875. // fTop = next;
  1876. }
  1877. log->record(SkPathOpsDebug::kReleasedSpan_Glitch, coin);
  1878. }
  1879. prev = coin;
  1880. } while ((coin = next));
  1881. return;
  1882. }
  1883. void SkOpCoincidence::debugRelease(SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const {
  1884. const SkCoincidentSpans* coin = fHead;
  1885. if (!coin) {
  1886. return;
  1887. }
  1888. do {
  1889. if (coin->coinPtTStart()->segment() == deleted
  1890. || coin->coinPtTEnd()->segment() == deleted
  1891. || coin->oppPtTStart()->segment() == deleted
  1892. || coin->oppPtTEnd()->segment() == deleted) {
  1893. log->record(SkPathOpsDebug::kReleasedSpan_Glitch, coin);
  1894. }
  1895. } while ((coin = coin->next()));
  1896. }
  1897. // Commented-out lines keep this in sync with expand()
  1898. // expand the range by checking adjacent spans for coincidence
  1899. bool SkOpCoincidence::debugExpand(SkPathOpsDebug::GlitchLog* log) const {
  1900. const SkCoincidentSpans* coin = fHead;
  1901. if (!coin) {
  1902. return false;
  1903. }
  1904. bool expanded = false;
  1905. do {
  1906. if (coin->debugExpand(log)) {
  1907. // check to see if multiple spans expanded so they are now identical
  1908. const SkCoincidentSpans* test = fHead;
  1909. do {
  1910. if (coin == test) {
  1911. continue;
  1912. }
  1913. if (coin->coinPtTStart() == test->coinPtTStart()
  1914. && coin->oppPtTStart() == test->oppPtTStart()) {
  1915. if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, fHead, test->coinPtTStart());
  1916. break;
  1917. }
  1918. } while ((test = test->next()));
  1919. expanded = true;
  1920. }
  1921. } while ((coin = coin->next()));
  1922. return expanded;
  1923. }
  1924. // Commented-out lines keep this in sync with mark()
  1925. /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
  1926. void SkOpCoincidence::debugMark(SkPathOpsDebug::GlitchLog* log) const {
  1927. const SkCoincidentSpans* coin = fHead;
  1928. if (!coin) {
  1929. return;
  1930. }
  1931. do {
  1932. FAIL_IF(!coin->coinPtTStartWritable()->span()->upCastable(), coin);
  1933. const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
  1934. // SkASSERT(start->deleted());
  1935. const SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
  1936. // SkASSERT(end->deleted());
  1937. const SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
  1938. // SkASSERT(oStart->deleted());
  1939. const SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
  1940. // SkASSERT(oEnd->deleted());
  1941. bool flipped = coin->flipped();
  1942. if (flipped) {
  1943. using std::swap;
  1944. swap(oStart, oEnd);
  1945. }
  1946. /* coin and opp spans may not match up. Mark the ends, and then let the interior
  1947. get marked as many times as the spans allow */
  1948. start->debugInsertCoincidence(log, oStart->upCast());
  1949. end->debugInsertCoinEnd(log, oEnd);
  1950. const SkOpSegment* segment = start->segment();
  1951. const SkOpSegment* oSegment = oStart->segment();
  1952. const SkOpSpanBase* next = start;
  1953. const SkOpSpanBase* oNext = oStart;
  1954. bool ordered;
  1955. FAIL_IF(!coin->ordered(&ordered), coin);
  1956. while ((next = next->upCast()->next()) != end) {
  1957. FAIL_IF(!next->upCastable(), coin);
  1958. if (next->upCast()->debugInsertCoincidence(log, oSegment, flipped, ordered), false) {
  1959. return;
  1960. }
  1961. }
  1962. while ((oNext = oNext->upCast()->next()) != oEnd) {
  1963. FAIL_IF(!oNext->upCastable(), coin);
  1964. if (oNext->upCast()->debugInsertCoincidence(log, segment, flipped, ordered), false) {
  1965. return;
  1966. }
  1967. }
  1968. } while ((coin = coin->next()));
  1969. return;
  1970. }
  1971. #endif
  1972. #if DEBUG_COIN
  1973. // Commented-out lines keep this in sync with markCollapsed()
  1974. void SkOpCoincidence::debugMarkCollapsed(SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkOpPtT* test) const {
  1975. const SkCoincidentSpans* head = coin;
  1976. while (coin) {
  1977. if (coin->collapsed(test)) {
  1978. if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
  1979. log->record(SkPathOpsDebug::kCollapsedCoin_Glitch, coin);
  1980. }
  1981. if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
  1982. log->record(SkPathOpsDebug::kCollapsedCoin_Glitch, coin);
  1983. }
  1984. this->debugRelease(log, head, coin);
  1985. }
  1986. coin = coin->next();
  1987. }
  1988. }
  1989. // Commented-out lines keep this in sync with markCollapsed()
  1990. void SkOpCoincidence::debugMarkCollapsed(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* test) const {
  1991. this->debugMarkCollapsed(log, fHead, test);
  1992. this->debugMarkCollapsed(log, fTop, test);
  1993. }
  1994. #endif
  1995. void SkCoincidentSpans::debugShow() const {
  1996. SkDebugf("coinSpan - id=%d t=%1.9g tEnd=%1.9g\n", coinPtTStart()->segment()->debugID(),
  1997. coinPtTStart()->fT, coinPtTEnd()->fT);
  1998. SkDebugf("coinSpan + id=%d t=%1.9g tEnd=%1.9g\n", oppPtTStart()->segment()->debugID(),
  1999. oppPtTStart()->fT, oppPtTEnd()->fT);
  2000. }
  2001. void SkOpCoincidence::debugShowCoincidence() const {
  2002. #if DEBUG_COINCIDENCE
  2003. const SkCoincidentSpans* span = fHead;
  2004. while (span) {
  2005. span->debugShow();
  2006. span = span->next();
  2007. }
  2008. #endif
  2009. }
  2010. #if DEBUG_COIN
  2011. static void DebugCheckBetween(const SkOpSpanBase* next, const SkOpSpanBase* end,
  2012. double oStart, double oEnd, const SkOpSegment* oSegment,
  2013. SkPathOpsDebug::GlitchLog* log) {
  2014. SkASSERT(next != end);
  2015. SkASSERT(!next->contains(end) || log);
  2016. if (next->t() > end->t()) {
  2017. using std::swap;
  2018. swap(next, end);
  2019. }
  2020. do {
  2021. const SkOpPtT* ptT = next->ptT();
  2022. int index = 0;
  2023. bool somethingBetween = false;
  2024. do {
  2025. ++index;
  2026. ptT = ptT->next();
  2027. const SkOpPtT* checkPtT = next->ptT();
  2028. if (ptT == checkPtT) {
  2029. break;
  2030. }
  2031. bool looped = false;
  2032. for (int check = 0; check < index; ++check) {
  2033. if ((looped = checkPtT == ptT)) {
  2034. break;
  2035. }
  2036. checkPtT = checkPtT->next();
  2037. }
  2038. if (looped) {
  2039. SkASSERT(0);
  2040. break;
  2041. }
  2042. if (ptT->deleted()) {
  2043. continue;
  2044. }
  2045. if (ptT->segment() != oSegment) {
  2046. continue;
  2047. }
  2048. somethingBetween |= between(oStart, ptT->fT, oEnd);
  2049. } while (true);
  2050. SkASSERT(somethingBetween);
  2051. } while (next != end && (next = next->upCast()->next()));
  2052. }
  2053. static void DebugCheckOverlap(const SkCoincidentSpans* test, const SkCoincidentSpans* list,
  2054. SkPathOpsDebug::GlitchLog* log) {
  2055. if (!list) {
  2056. return;
  2057. }
  2058. const SkOpSegment* coinSeg = test->coinPtTStart()->segment();
  2059. SkASSERT(coinSeg == test->coinPtTEnd()->segment());
  2060. const SkOpSegment* oppSeg = test->oppPtTStart()->segment();
  2061. SkASSERT(oppSeg == test->oppPtTEnd()->segment());
  2062. SkASSERT(coinSeg != test->oppPtTStart()->segment());
  2063. SkDEBUGCODE(double tcs = test->coinPtTStart()->fT);
  2064. SkASSERT(between(0, tcs, 1));
  2065. SkDEBUGCODE(double tce = test->coinPtTEnd()->fT);
  2066. SkASSERT(between(0, tce, 1));
  2067. SkASSERT(tcs < tce);
  2068. double tos = test->oppPtTStart()->fT;
  2069. SkASSERT(between(0, tos, 1));
  2070. double toe = test->oppPtTEnd()->fT;
  2071. SkASSERT(between(0, toe, 1));
  2072. SkASSERT(tos != toe);
  2073. if (tos > toe) {
  2074. using std::swap;
  2075. swap(tos, toe);
  2076. }
  2077. do {
  2078. double lcs, lce, los, loe;
  2079. if (coinSeg == list->coinPtTStart()->segment()) {
  2080. if (oppSeg != list->oppPtTStart()->segment()) {
  2081. continue;
  2082. }
  2083. lcs = list->coinPtTStart()->fT;
  2084. lce = list->coinPtTEnd()->fT;
  2085. los = list->oppPtTStart()->fT;
  2086. loe = list->oppPtTEnd()->fT;
  2087. if (los > loe) {
  2088. using std::swap;
  2089. swap(los, loe);
  2090. }
  2091. } else if (coinSeg == list->oppPtTStart()->segment()) {
  2092. if (oppSeg != list->coinPtTStart()->segment()) {
  2093. continue;
  2094. }
  2095. lcs = list->oppPtTStart()->fT;
  2096. lce = list->oppPtTEnd()->fT;
  2097. if (lcs > lce) {
  2098. using std::swap;
  2099. swap(lcs, lce);
  2100. }
  2101. los = list->coinPtTStart()->fT;
  2102. loe = list->coinPtTEnd()->fT;
  2103. } else {
  2104. continue;
  2105. }
  2106. SkASSERT(tce < lcs || lce < tcs);
  2107. SkASSERT(toe < los || loe < tos);
  2108. } while ((list = list->next()));
  2109. }
  2110. static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
  2111. SkPathOpsDebug::GlitchLog* log) {
  2112. // check for overlapping coincident spans
  2113. const SkCoincidentSpans* test = head;
  2114. while (test) {
  2115. const SkCoincidentSpans* next = test->next();
  2116. DebugCheckOverlap(test, next, log);
  2117. DebugCheckOverlap(test, opt, log);
  2118. test = next;
  2119. }
  2120. }
  2121. static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
  2122. SkPathOpsDebug::GlitchLog* log) {
  2123. // look for pts inside coincident spans that are not inside the opposite spans
  2124. const SkCoincidentSpans* coin = head;
  2125. while (coin) {
  2126. SkASSERT(SkOpCoincidence::Ordered(coin->coinPtTStart()->segment(),
  2127. coin->oppPtTStart()->segment()));
  2128. SkASSERT(coin->coinPtTStart()->span()->ptT() == coin->coinPtTStart());
  2129. SkASSERT(coin->coinPtTEnd()->span()->ptT() == coin->coinPtTEnd());
  2130. SkASSERT(coin->oppPtTStart()->span()->ptT() == coin->oppPtTStart());
  2131. SkASSERT(coin->oppPtTEnd()->span()->ptT() == coin->oppPtTEnd());
  2132. coin = coin->next();
  2133. }
  2134. DebugCheckOverlapTop(head, opt, log);
  2135. }
  2136. #endif
  2137. void SkOpCoincidence::debugValidate() const {
  2138. #if DEBUG_COINCIDENCE
  2139. DebugValidate(fHead, fTop, nullptr);
  2140. DebugValidate(fTop, nullptr, nullptr);
  2141. #endif
  2142. }
  2143. #if DEBUG_COIN
  2144. static void DebugCheckBetween(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
  2145. SkPathOpsDebug::GlitchLog* log) {
  2146. // look for pts inside coincident spans that are not inside the opposite spans
  2147. const SkCoincidentSpans* coin = head;
  2148. while (coin) {
  2149. DebugCheckBetween(coin->coinPtTStart()->span(), coin->coinPtTEnd()->span(),
  2150. coin->oppPtTStart()->fT, coin->oppPtTEnd()->fT, coin->oppPtTStart()->segment(),
  2151. log);
  2152. DebugCheckBetween(coin->oppPtTStart()->span(), coin->oppPtTEnd()->span(),
  2153. coin->coinPtTStart()->fT, coin->coinPtTEnd()->fT, coin->coinPtTStart()->segment(),
  2154. log);
  2155. coin = coin->next();
  2156. }
  2157. DebugCheckOverlapTop(head, opt, log);
  2158. }
  2159. #endif
  2160. void SkOpCoincidence::debugCheckBetween() const {
  2161. #if DEBUG_COINCIDENCE
  2162. if (fGlobalState->debugCheckHealth()) {
  2163. return;
  2164. }
  2165. DebugCheckBetween(fHead, fTop, nullptr);
  2166. DebugCheckBetween(fTop, nullptr, nullptr);
  2167. #endif
  2168. }
  2169. #if DEBUG_COIN
  2170. void SkOpContour::debugCheckHealth(SkPathOpsDebug::GlitchLog* log) const {
  2171. const SkOpSegment* segment = &fHead;
  2172. do {
  2173. segment->debugCheckHealth(log);
  2174. } while ((segment = segment->next()));
  2175. }
  2176. void SkOpCoincidence::debugCheckValid(SkPathOpsDebug::GlitchLog* log) const {
  2177. #if DEBUG_VALIDATE
  2178. DebugValidate(fHead, fTop, log);
  2179. DebugValidate(fTop, nullptr, log);
  2180. #endif
  2181. }
  2182. void SkOpCoincidence::debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const {
  2183. const SkCoincidentSpans* coin = fHead;
  2184. if (!coin) {
  2185. return;
  2186. }
  2187. do {
  2188. coin->debugCorrectEnds(log);
  2189. } while ((coin = coin->next()));
  2190. }
  2191. // commmented-out lines keep this aligned with missingCoincidence()
  2192. void SkOpContour::debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const {
  2193. // SkASSERT(fCount > 0);
  2194. const SkOpSegment* segment = &fHead;
  2195. // bool result = false;
  2196. do {
  2197. if (segment->debugMissingCoincidence(log), false) {
  2198. // result = true;
  2199. }
  2200. segment = segment->next();
  2201. } while (segment);
  2202. return;
  2203. }
  2204. void SkOpContour::debugMoveMultiples(SkPathOpsDebug::GlitchLog* log) const {
  2205. SkASSERT(fCount > 0);
  2206. const SkOpSegment* segment = &fHead;
  2207. do {
  2208. if (segment->debugMoveMultiples(log), false) {
  2209. return;
  2210. }
  2211. } while ((segment = segment->next()));
  2212. return;
  2213. }
  2214. void SkOpContour::debugMoveNearby(SkPathOpsDebug::GlitchLog* log) const {
  2215. SkASSERT(fCount > 0);
  2216. const SkOpSegment* segment = &fHead;
  2217. do {
  2218. segment->debugMoveNearby(log);
  2219. } while ((segment = segment->next()));
  2220. }
  2221. #endif
  2222. #if DEBUG_COINCIDENCE_ORDER
  2223. void SkOpSegment::debugResetCoinT() const {
  2224. fDebugBaseIndex = -1;
  2225. fDebugBaseMin = 1;
  2226. fDebugBaseMax = -1;
  2227. fDebugLastIndex = -1;
  2228. fDebugLastMin = 1;
  2229. fDebugLastMax = -1;
  2230. }
  2231. #endif
  2232. void SkOpSegment::debugValidate() const {
  2233. #if DEBUG_COINCIDENCE_ORDER
  2234. {
  2235. const SkOpSpanBase* span = &fHead;
  2236. do {
  2237. span->debugResetCoinT();
  2238. } while (!span->final() && (span = span->upCast()->next()));
  2239. span = &fHead;
  2240. int index = 0;
  2241. do {
  2242. span->debugSetCoinT(index++);
  2243. } while (!span->final() && (span = span->upCast()->next()));
  2244. }
  2245. #endif
  2246. #if DEBUG_COINCIDENCE
  2247. if (this->globalState()->debugCheckHealth()) {
  2248. return;
  2249. }
  2250. #endif
  2251. #if DEBUG_VALIDATE
  2252. const SkOpSpanBase* span = &fHead;
  2253. double lastT = -1;
  2254. const SkOpSpanBase* prev = nullptr;
  2255. int count = 0;
  2256. int done = 0;
  2257. do {
  2258. if (!span->final()) {
  2259. ++count;
  2260. done += span->upCast()->done() ? 1 : 0;
  2261. }
  2262. SkASSERT(span->segment() == this);
  2263. SkASSERT(!prev || prev->upCast()->next() == span);
  2264. SkASSERT(!prev || prev == span->prev());
  2265. prev = span;
  2266. double t = span->ptT()->fT;
  2267. SkASSERT(lastT < t);
  2268. lastT = t;
  2269. span->debugValidate();
  2270. } while (!span->final() && (span = span->upCast()->next()));
  2271. SkASSERT(count == fCount);
  2272. SkASSERT(done == fDoneCount);
  2273. SkASSERT(count >= fDoneCount);
  2274. SkASSERT(span->final());
  2275. span->debugValidate();
  2276. #endif
  2277. }
  2278. #if DEBUG_COIN
  2279. // Commented-out lines keep this in sync with addOpp()
  2280. void SkOpSpanBase::debugAddOpp(SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
  2281. const SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
  2282. if (!oppPrev) {
  2283. return;
  2284. }
  2285. this->debugMergeMatches(log, opp);
  2286. this->ptT()->debugAddOpp(opp->ptT(), oppPrev);
  2287. this->debugCheckForCollapsedCoincidence(log);
  2288. }
  2289. // Commented-out lines keep this in sync with checkForCollapsedCoincidence()
  2290. void SkOpSpanBase::debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* log) const {
  2291. const SkOpCoincidence* coins = this->globalState()->coincidence();
  2292. if (coins->isEmpty()) {
  2293. return;
  2294. }
  2295. // the insert above may have put both ends of a coincident run in the same span
  2296. // for each coincident ptT in loop; see if its opposite in is also in the loop
  2297. // this implementation is the motivation for marking that a ptT is referenced by a coincident span
  2298. const SkOpPtT* head = this->ptT();
  2299. const SkOpPtT* test = head;
  2300. do {
  2301. if (!test->coincident()) {
  2302. continue;
  2303. }
  2304. coins->debugMarkCollapsed(log, test);
  2305. } while ((test = test->next()) != head);
  2306. }
  2307. #endif
  2308. bool SkOpSpanBase::debugCoinEndLoopCheck() const {
  2309. int loop = 0;
  2310. const SkOpSpanBase* next = this;
  2311. SkOpSpanBase* nextCoin;
  2312. do {
  2313. nextCoin = next->fCoinEnd;
  2314. SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
  2315. for (int check = 1; check < loop - 1; ++check) {
  2316. const SkOpSpanBase* checkCoin = this->fCoinEnd;
  2317. const SkOpSpanBase* innerCoin = checkCoin;
  2318. for (int inner = check + 1; inner < loop; ++inner) {
  2319. innerCoin = innerCoin->fCoinEnd;
  2320. if (checkCoin == innerCoin) {
  2321. SkDebugf("*** bad coincident end loop ***\n");
  2322. return false;
  2323. }
  2324. }
  2325. }
  2326. ++loop;
  2327. } while ((next = nextCoin) && next != this);
  2328. return true;
  2329. }
  2330. #if DEBUG_COIN
  2331. // Commented-out lines keep this in sync with insertCoinEnd()
  2332. void SkOpSpanBase::debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* coin) const {
  2333. if (containsCoinEnd(coin)) {
  2334. // SkASSERT(coin->containsCoinEnd(this));
  2335. return;
  2336. }
  2337. debugValidate();
  2338. // SkASSERT(this != coin);
  2339. log->record(SkPathOpsDebug::kMarkCoinEnd_Glitch, this, coin);
  2340. // coin->fCoinEnd = this->fCoinEnd;
  2341. // this->fCoinEnd = coinNext;
  2342. debugValidate();
  2343. }
  2344. // Commented-out lines keep this in sync with mergeMatches()
  2345. // Look to see if pt-t linked list contains same segment more than once
  2346. // if so, and if each pt-t is directly pointed to by spans in that segment,
  2347. // merge them
  2348. // keep the points, but remove spans so that the segment doesn't have 2 or more
  2349. // spans pointing to the same pt-t loop at different loop elements
  2350. void SkOpSpanBase::debugMergeMatches(SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
  2351. const SkOpPtT* test = &fPtT;
  2352. const SkOpPtT* testNext;
  2353. const SkOpPtT* stop = test;
  2354. do {
  2355. testNext = test->next();
  2356. if (test->deleted()) {
  2357. continue;
  2358. }
  2359. const SkOpSpanBase* testBase = test->span();
  2360. SkASSERT(testBase->ptT() == test);
  2361. const SkOpSegment* segment = test->segment();
  2362. if (segment->done()) {
  2363. continue;
  2364. }
  2365. const SkOpPtT* inner = opp->ptT();
  2366. const SkOpPtT* innerStop = inner;
  2367. do {
  2368. if (inner->segment() != segment) {
  2369. continue;
  2370. }
  2371. if (inner->deleted()) {
  2372. continue;
  2373. }
  2374. const SkOpSpanBase* innerBase = inner->span();
  2375. SkASSERT(innerBase->ptT() == inner);
  2376. // when the intersection is first detected, the span base is marked if there are
  2377. // more than one point in the intersection.
  2378. // if (!innerBase->hasMultipleHint() && !testBase->hasMultipleHint()) {
  2379. if (!zero_or_one(inner->fT)) {
  2380. log->record(SkPathOpsDebug::kMergeMatches_Glitch, innerBase, test);
  2381. } else {
  2382. SkASSERT(inner->fT != test->fT);
  2383. if (!zero_or_one(test->fT)) {
  2384. log->record(SkPathOpsDebug::kMergeMatches_Glitch, testBase, inner);
  2385. } else {
  2386. log->record(SkPathOpsDebug::kMergeMatches_Glitch, segment);
  2387. // SkDEBUGCODE(testBase->debugSetDeleted());
  2388. // test->setDeleted();
  2389. // SkDEBUGCODE(innerBase->debugSetDeleted());
  2390. // inner->setDeleted();
  2391. }
  2392. }
  2393. #ifdef SK_DEBUG // assert if another undeleted entry points to segment
  2394. const SkOpPtT* debugInner = inner;
  2395. while ((debugInner = debugInner->next()) != innerStop) {
  2396. if (debugInner->segment() != segment) {
  2397. continue;
  2398. }
  2399. if (debugInner->deleted()) {
  2400. continue;
  2401. }
  2402. SkOPASSERT(0);
  2403. }
  2404. #endif
  2405. break;
  2406. // }
  2407. break;
  2408. } while ((inner = inner->next()) != innerStop);
  2409. } while ((test = testNext) != stop);
  2410. this->debugCheckForCollapsedCoincidence(log);
  2411. }
  2412. #endif
  2413. void SkOpSpanBase::debugResetCoinT() const {
  2414. #if DEBUG_COINCIDENCE_ORDER
  2415. const SkOpPtT* ptT = &fPtT;
  2416. do {
  2417. ptT->debugResetCoinT();
  2418. ptT = ptT->next();
  2419. } while (ptT != &fPtT);
  2420. #endif
  2421. }
  2422. void SkOpSpanBase::debugSetCoinT(int index) const {
  2423. #if DEBUG_COINCIDENCE_ORDER
  2424. const SkOpPtT* ptT = &fPtT;
  2425. do {
  2426. if (!ptT->deleted()) {
  2427. ptT->debugSetCoinT(index);
  2428. }
  2429. ptT = ptT->next();
  2430. } while (ptT != &fPtT);
  2431. #endif
  2432. }
  2433. const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
  2434. const SkOpSpanBase* end = *endPtr;
  2435. SkASSERT(this->segment() == end->segment());
  2436. const SkOpSpanBase* result;
  2437. if (t() < end->t()) {
  2438. result = this;
  2439. } else {
  2440. result = end;
  2441. *endPtr = this;
  2442. }
  2443. return result->upCast();
  2444. }
  2445. void SkOpSpanBase::debugValidate() const {
  2446. #if DEBUG_COINCIDENCE
  2447. if (this->globalState()->debugCheckHealth()) {
  2448. return;
  2449. }
  2450. #endif
  2451. #if DEBUG_VALIDATE
  2452. const SkOpPtT* ptT = &fPtT;
  2453. SkASSERT(ptT->span() == this);
  2454. do {
  2455. // SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
  2456. ptT->debugValidate();
  2457. ptT = ptT->next();
  2458. } while (ptT != &fPtT);
  2459. SkASSERT(this->debugCoinEndLoopCheck());
  2460. if (!this->final()) {
  2461. SkASSERT(this->upCast()->debugCoinLoopCheck());
  2462. }
  2463. if (fFromAngle) {
  2464. fFromAngle->debugValidate();
  2465. }
  2466. if (!this->final() && this->upCast()->toAngle()) {
  2467. this->upCast()->toAngle()->debugValidate();
  2468. }
  2469. #endif
  2470. }
  2471. bool SkOpSpan::debugCoinLoopCheck() const {
  2472. int loop = 0;
  2473. const SkOpSpan* next = this;
  2474. SkOpSpan* nextCoin;
  2475. do {
  2476. nextCoin = next->fCoincident;
  2477. SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
  2478. for (int check = 1; check < loop - 1; ++check) {
  2479. const SkOpSpan* checkCoin = this->fCoincident;
  2480. const SkOpSpan* innerCoin = checkCoin;
  2481. for (int inner = check + 1; inner < loop; ++inner) {
  2482. innerCoin = innerCoin->fCoincident;
  2483. if (checkCoin == innerCoin) {
  2484. SkDebugf("*** bad coincident loop ***\n");
  2485. return false;
  2486. }
  2487. }
  2488. }
  2489. ++loop;
  2490. } while ((next = nextCoin) && next != this);
  2491. return true;
  2492. }
  2493. #if DEBUG_COIN
  2494. // Commented-out lines keep this in sync with insertCoincidence() in header
  2495. void SkOpSpan::debugInsertCoincidence(SkPathOpsDebug::GlitchLog* log, const SkOpSpan* coin) const {
  2496. if (containsCoincidence(coin)) {
  2497. // SkASSERT(coin->containsCoincidence(this));
  2498. return;
  2499. }
  2500. debugValidate();
  2501. // SkASSERT(this != coin);
  2502. log->record(SkPathOpsDebug::kMarkCoinStart_Glitch, this, coin);
  2503. // coin->fCoincident = this->fCoincident;
  2504. // this->fCoincident = coinNext;
  2505. debugValidate();
  2506. }
  2507. // Commented-out lines keep this in sync with insertCoincidence()
  2508. void SkOpSpan::debugInsertCoincidence(SkPathOpsDebug::GlitchLog* log, const SkOpSegment* segment, bool flipped, bool ordered) const {
  2509. if (this->containsCoincidence(segment)) {
  2510. return;
  2511. }
  2512. const SkOpPtT* next = &fPtT;
  2513. while ((next = next->next()) != &fPtT) {
  2514. if (next->segment() == segment) {
  2515. const SkOpSpan* span;
  2516. const SkOpSpanBase* base = next->span();
  2517. if (!ordered) {
  2518. const SkOpSpanBase* spanEnd = fNext->contains(segment)->span();
  2519. const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
  2520. FAIL_IF(!start->span()->upCastable(), this);
  2521. span = const_cast<SkOpSpan*>(start->span()->upCast());
  2522. }
  2523. else if (flipped) {
  2524. span = base->prev();
  2525. FAIL_IF(!span, this);
  2526. }
  2527. else {
  2528. FAIL_IF(!base->upCastable(), this);
  2529. span = base->upCast();
  2530. }
  2531. log->record(SkPathOpsDebug::kMarkCoinInsert_Glitch, span);
  2532. return;
  2533. }
  2534. }
  2535. #if DEBUG_COIN
  2536. log->record(SkPathOpsDebug::kMarkCoinMissing_Glitch, segment, this);
  2537. #endif
  2538. return;
  2539. }
  2540. #endif
  2541. // called only by test code
  2542. int SkIntersections::debugCoincidentUsed() const {
  2543. if (!fIsCoincident[0]) {
  2544. SkASSERT(!fIsCoincident[1]);
  2545. return 0;
  2546. }
  2547. int count = 0;
  2548. SkDEBUGCODE(int count2 = 0;)
  2549. for (int index = 0; index < fUsed; ++index) {
  2550. if (fIsCoincident[0] & (1 << index)) {
  2551. ++count;
  2552. }
  2553. #ifdef SK_DEBUG
  2554. if (fIsCoincident[1] & (1 << index)) {
  2555. ++count2;
  2556. }
  2557. #endif
  2558. }
  2559. SkASSERT(count == count2);
  2560. return count;
  2561. }
  2562. #include "src/pathops/SkOpContour.h"
  2563. // Commented-out lines keep this in sync with addOpp()
  2564. void SkOpPtT::debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const {
  2565. SkDEBUGCODE(const SkOpPtT* oldNext = this->fNext);
  2566. SkASSERT(this != opp);
  2567. // this->fNext = opp;
  2568. SkASSERT(oppPrev != oldNext);
  2569. // oppPrev->fNext = oldNext;
  2570. }
  2571. bool SkOpPtT::debugContains(const SkOpPtT* check) const {
  2572. SkASSERT(this != check);
  2573. const SkOpPtT* ptT = this;
  2574. int links = 0;
  2575. do {
  2576. ptT = ptT->next();
  2577. if (ptT == check) {
  2578. return true;
  2579. }
  2580. ++links;
  2581. const SkOpPtT* test = this;
  2582. for (int index = 0; index < links; ++index) {
  2583. if (ptT == test) {
  2584. return false;
  2585. }
  2586. test = test->next();
  2587. }
  2588. } while (true);
  2589. }
  2590. const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
  2591. SkASSERT(this->segment() != check);
  2592. const SkOpPtT* ptT = this;
  2593. int links = 0;
  2594. do {
  2595. ptT = ptT->next();
  2596. if (ptT->segment() == check) {
  2597. return ptT;
  2598. }
  2599. ++links;
  2600. const SkOpPtT* test = this;
  2601. for (int index = 0; index < links; ++index) {
  2602. if (ptT == test) {
  2603. return nullptr;
  2604. }
  2605. test = test->next();
  2606. }
  2607. } while (true);
  2608. }
  2609. const SkOpPtT* SkOpPtT::debugEnder(const SkOpPtT* end) const {
  2610. return fT < end->fT ? end : this;
  2611. }
  2612. int SkOpPtT::debugLoopLimit(bool report) const {
  2613. int loop = 0;
  2614. const SkOpPtT* next = this;
  2615. do {
  2616. for (int check = 1; check < loop - 1; ++check) {
  2617. const SkOpPtT* checkPtT = this->fNext;
  2618. const SkOpPtT* innerPtT = checkPtT;
  2619. for (int inner = check + 1; inner < loop; ++inner) {
  2620. innerPtT = innerPtT->fNext;
  2621. if (checkPtT == innerPtT) {
  2622. if (report) {
  2623. SkDebugf("*** bad ptT loop ***\n");
  2624. }
  2625. return loop;
  2626. }
  2627. }
  2628. }
  2629. // there's nothing wrong with extremely large loop counts -- but this may appear to hang
  2630. // by taking a very long time to figure out that no loop entry is a duplicate
  2631. // -- and it's likely that a large loop count is indicative of a bug somewhere
  2632. if (++loop > 1000) {
  2633. SkDebugf("*** loop count exceeds 1000 ***\n");
  2634. return 1000;
  2635. }
  2636. } while ((next = next->fNext) && next != this);
  2637. return 0;
  2638. }
  2639. const SkOpPtT* SkOpPtT::debugOppPrev(const SkOpPtT* opp) const {
  2640. return this->oppPrev(const_cast<SkOpPtT*>(opp));
  2641. }
  2642. void SkOpPtT::debugResetCoinT() const {
  2643. #if DEBUG_COINCIDENCE_ORDER
  2644. this->segment()->debugResetCoinT();
  2645. #endif
  2646. }
  2647. void SkOpPtT::debugSetCoinT(int index) const {
  2648. #if DEBUG_COINCIDENCE_ORDER
  2649. this->segment()->debugSetCoinT(index, fT);
  2650. #endif
  2651. }
  2652. void SkOpPtT::debugValidate() const {
  2653. #if DEBUG_COINCIDENCE
  2654. if (this->globalState()->debugCheckHealth()) {
  2655. return;
  2656. }
  2657. #endif
  2658. #if DEBUG_VALIDATE
  2659. SkOpPhase phase = contour()->globalState()->phase();
  2660. if (phase == SkOpPhase::kIntersecting || phase == SkOpPhase::kFixWinding) {
  2661. return;
  2662. }
  2663. SkASSERT(fNext);
  2664. SkASSERT(fNext != this);
  2665. SkASSERT(fNext->fNext);
  2666. SkASSERT(debugLoopLimit(false) == 0);
  2667. #endif
  2668. }
  2669. static void output_scalar(SkScalar num) {
  2670. if (num == (int) num) {
  2671. SkDebugf("%d", (int) num);
  2672. } else {
  2673. SkString str;
  2674. str.printf("%1.9g", num);
  2675. int width = (int) str.size();
  2676. const char* cStr = str.c_str();
  2677. while (cStr[width - 1] == '0') {
  2678. --width;
  2679. }
  2680. str.resize(width);
  2681. SkDebugf("%sf", str.c_str());
  2682. }
  2683. }
  2684. static void output_points(const SkPoint* pts, int count) {
  2685. for (int index = 0; index < count; ++index) {
  2686. output_scalar(pts[index].fX);
  2687. SkDebugf(", ");
  2688. output_scalar(pts[index].fY);
  2689. if (index + 1 < count) {
  2690. SkDebugf(", ");
  2691. }
  2692. }
  2693. }
  2694. static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
  2695. uint8_t verb;
  2696. SkPoint pts[4];
  2697. while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
  2698. switch (verb) {
  2699. case SkPath::kMove_Verb:
  2700. SkDebugf(" %s.moveTo(", pathName);
  2701. output_points(&pts[0], 1);
  2702. SkDebugf(");\n");
  2703. continue;
  2704. case SkPath::kLine_Verb:
  2705. SkDebugf(" %s.lineTo(", pathName);
  2706. output_points(&pts[1], 1);
  2707. SkDebugf(");\n");
  2708. break;
  2709. case SkPath::kQuad_Verb:
  2710. SkDebugf(" %s.quadTo(", pathName);
  2711. output_points(&pts[1], 2);
  2712. SkDebugf(");\n");
  2713. break;
  2714. case SkPath::kConic_Verb:
  2715. SkDebugf(" %s.conicTo(", pathName);
  2716. output_points(&pts[1], 2);
  2717. SkDebugf(", %1.9gf);\n", iter.conicWeight());
  2718. break;
  2719. case SkPath::kCubic_Verb:
  2720. SkDebugf(" %s.cubicTo(", pathName);
  2721. output_points(&pts[1], 3);
  2722. SkDebugf(");\n");
  2723. break;
  2724. case SkPath::kClose_Verb:
  2725. SkDebugf(" %s.close();\n", pathName);
  2726. break;
  2727. default:
  2728. SkDEBUGFAIL("bad verb");
  2729. return;
  2730. }
  2731. }
  2732. }
  2733. static const char* gFillTypeStr[] = {
  2734. "kWinding_FillType",
  2735. "kEvenOdd_FillType",
  2736. "kInverseWinding_FillType",
  2737. "kInverseEvenOdd_FillType"
  2738. };
  2739. void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
  2740. SkPath::RawIter iter(path);
  2741. #define SUPPORT_RECT_CONTOUR_DETECTION 0
  2742. #if SUPPORT_RECT_CONTOUR_DETECTION
  2743. int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
  2744. if (rectCount > 0) {
  2745. SkTDArray<SkRect> rects;
  2746. SkTDArray<SkPath::Direction> directions;
  2747. rects.setCount(rectCount);
  2748. directions.setCount(rectCount);
  2749. path.rectContours(rects.begin(), directions.begin());
  2750. for (int contour = 0; contour < rectCount; ++contour) {
  2751. const SkRect& rect = rects[contour];
  2752. SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
  2753. rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
  2754. ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
  2755. }
  2756. return;
  2757. }
  2758. #endif
  2759. SkPath::FillType fillType = path.getFillType();
  2760. SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
  2761. if (includeDeclaration) {
  2762. SkDebugf(" SkPath %s;\n", name);
  2763. }
  2764. SkDebugf(" %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
  2765. iter.setPath(path);
  2766. showPathContours(iter, name);
  2767. }
  2768. #if DEBUG_DUMP_VERIFY
  2769. #include "include/core/SkData.h"
  2770. #include "include/core/SkStream.h"
  2771. static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex) {
  2772. SkDynamicMemoryWStream wStream;
  2773. path.dump(&wStream, force, dumpAsHex);
  2774. sk_sp<SkData> data(wStream.detachAsData());
  2775. fprintf(file, "%.*s\n", (int) data->size(), (char*) data->data());
  2776. }
  2777. static int dumpID = 0;
  2778. void SkPathOpsDebug::DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
  2779. const char* testName) {
  2780. FILE* file = sk_fopen("op_dump.txt", kWrite_SkFILE_Flag);
  2781. DumpOp(file, one, two, op, testName);
  2782. }
  2783. void SkPathOpsDebug::DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
  2784. const char* testName) {
  2785. const char* name = testName ? testName : "op";
  2786. fprintf(file,
  2787. "\nstatic void %s_%d(skiatest::Reporter* reporter, const char* filename) {\n",
  2788. name, ++dumpID);
  2789. fprintf(file, " SkPath path;\n");
  2790. fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillType());
  2791. dump_path(file, one, false, true);
  2792. fprintf(file, " SkPath path1(path);\n");
  2793. fprintf(file, " path.reset();\n");
  2794. fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillType());
  2795. dump_path(file, two, false, true);
  2796. fprintf(file, " SkPath path2(path);\n");
  2797. fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
  2798. fprintf(file, "}\n\n");
  2799. fclose(file);
  2800. }
  2801. void SkPathOpsDebug::DumpSimplify(const SkPath& path, const char* testName) {
  2802. FILE* file = sk_fopen("simplify_dump.txt", kWrite_SkFILE_Flag);
  2803. DumpSimplify(file, path, testName);
  2804. }
  2805. void SkPathOpsDebug::DumpSimplify(FILE* file, const SkPath& path, const char* testName) {
  2806. const char* name = testName ? testName : "simplify";
  2807. fprintf(file,
  2808. "\nstatic void %s_%d(skiatest::Reporter* reporter, const char* filename) {\n",
  2809. name, ++dumpID);
  2810. fprintf(file, " SkPath path;\n");
  2811. fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", path.getFillType());
  2812. dump_path(file, path, false, true);
  2813. fprintf(file, " testSimplify(reporter, path, filename);\n");
  2814. fprintf(file, "}\n\n");
  2815. fclose(file);
  2816. }
  2817. #include "include/core/SkBitmap.h"
  2818. #include "include/core/SkCanvas.h"
  2819. #include "include/core/SkPaint.h"
  2820. const int bitWidth = 64;
  2821. const int bitHeight = 64;
  2822. static void debug_scale_matrix(const SkPath& one, const SkPath* two, SkMatrix& scale) {
  2823. SkRect larger = one.getBounds();
  2824. if (two) {
  2825. larger.join(two->getBounds());
  2826. }
  2827. SkScalar largerWidth = larger.width();
  2828. if (largerWidth < 4) {
  2829. largerWidth = 4;
  2830. }
  2831. SkScalar largerHeight = larger.height();
  2832. if (largerHeight < 4) {
  2833. largerHeight = 4;
  2834. }
  2835. SkScalar hScale = (bitWidth - 2) / largerWidth;
  2836. SkScalar vScale = (bitHeight - 2) / largerHeight;
  2837. scale.reset();
  2838. scale.preScale(hScale, vScale);
  2839. larger.fLeft *= hScale;
  2840. larger.fRight *= hScale;
  2841. larger.fTop *= vScale;
  2842. larger.fBottom *= vScale;
  2843. SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft
  2844. : 16000 < larger.fRight ? 16000 - larger.fRight : 0;
  2845. SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop
  2846. : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0;
  2847. scale.preTranslate(dx, dy);
  2848. }
  2849. static int debug_paths_draw_the_same(const SkPath& one, const SkPath& two, SkBitmap& bits) {
  2850. if (bits.width() == 0) {
  2851. bits.allocN32Pixels(bitWidth * 2, bitHeight);
  2852. }
  2853. SkCanvas canvas(bits);
  2854. canvas.drawColor(SK_ColorWHITE);
  2855. SkPaint paint;
  2856. canvas.save();
  2857. const SkRect& bounds1 = one.getBounds();
  2858. canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1);
  2859. canvas.drawPath(one, paint);
  2860. canvas.restore();
  2861. canvas.save();
  2862. canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1);
  2863. canvas.drawPath(two, paint);
  2864. canvas.restore();
  2865. int errors = 0;
  2866. for (int y = 0; y < bitHeight - 1; ++y) {
  2867. uint32_t* addr1 = bits.getAddr32(0, y);
  2868. uint32_t* addr2 = bits.getAddr32(0, y + 1);
  2869. uint32_t* addr3 = bits.getAddr32(bitWidth, y);
  2870. uint32_t* addr4 = bits.getAddr32(bitWidth, y + 1);
  2871. for (int x = 0; x < bitWidth - 1; ++x) {
  2872. // count 2x2 blocks
  2873. bool err = addr1[x] != addr3[x];
  2874. if (err) {
  2875. errors += addr1[x + 1] != addr3[x + 1]
  2876. && addr2[x] != addr4[x] && addr2[x + 1] != addr4[x + 1];
  2877. }
  2878. }
  2879. }
  2880. return errors;
  2881. }
  2882. void SkPathOpsDebug::ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op) {
  2883. SkDebugf("// Op did not expect failure\n");
  2884. DumpOp(stderr, one, two, op, "opTest");
  2885. fflush(stderr);
  2886. }
  2887. void SkPathOpsDebug::VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
  2888. const SkPath& result) {
  2889. SkPath pathOut, scaledPathOut;
  2890. SkRegion rgnA, rgnB, openClip, rgnOut;
  2891. openClip.setRect(-16000, -16000, 16000, 16000);
  2892. rgnA.setPath(one, openClip);
  2893. rgnB.setPath(two, openClip);
  2894. rgnOut.op(rgnA, rgnB, (SkRegion::Op) op);
  2895. rgnOut.getBoundaryPath(&pathOut);
  2896. SkMatrix scale;
  2897. debug_scale_matrix(one, &two, scale);
  2898. SkRegion scaledRgnA, scaledRgnB, scaledRgnOut;
  2899. SkPath scaledA, scaledB;
  2900. scaledA.addPath(one, scale);
  2901. scaledA.setFillType(one.getFillType());
  2902. scaledB.addPath(two, scale);
  2903. scaledB.setFillType(two.getFillType());
  2904. scaledRgnA.setPath(scaledA, openClip);
  2905. scaledRgnB.setPath(scaledB, openClip);
  2906. scaledRgnOut.op(scaledRgnA, scaledRgnB, (SkRegion::Op) op);
  2907. scaledRgnOut.getBoundaryPath(&scaledPathOut);
  2908. SkBitmap bitmap;
  2909. SkPath scaledOut;
  2910. scaledOut.addPath(result, scale);
  2911. scaledOut.setFillType(result.getFillType());
  2912. int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap);
  2913. const int MAX_ERRORS = 9;
  2914. if (errors > MAX_ERRORS) {
  2915. fprintf(stderr, "// Op did not expect errors=%d\n", errors);
  2916. DumpOp(stderr, one, two, op, "opTest");
  2917. fflush(stderr);
  2918. }
  2919. }
  2920. void SkPathOpsDebug::ReportSimplifyFail(const SkPath& path) {
  2921. SkDebugf("// Simplify did not expect failure\n");
  2922. DumpSimplify(stderr, path, "simplifyTest");
  2923. fflush(stderr);
  2924. }
  2925. void SkPathOpsDebug::VerifySimplify(const SkPath& path, const SkPath& result) {
  2926. SkPath pathOut, scaledPathOut;
  2927. SkRegion rgnA, openClip, rgnOut;
  2928. openClip.setRect(-16000, -16000, 16000, 16000);
  2929. rgnA.setPath(path, openClip);
  2930. rgnOut.getBoundaryPath(&pathOut);
  2931. SkMatrix scale;
  2932. debug_scale_matrix(path, nullptr, scale);
  2933. SkRegion scaledRgnA;
  2934. SkPath scaledA;
  2935. scaledA.addPath(path, scale);
  2936. scaledA.setFillType(path.getFillType());
  2937. scaledRgnA.setPath(scaledA, openClip);
  2938. scaledRgnA.getBoundaryPath(&scaledPathOut);
  2939. SkBitmap bitmap;
  2940. SkPath scaledOut;
  2941. scaledOut.addPath(result, scale);
  2942. scaledOut.setFillType(result.getFillType());
  2943. int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap);
  2944. const int MAX_ERRORS = 9;
  2945. if (errors > MAX_ERRORS) {
  2946. fprintf(stderr, "// Simplify did not expect errors=%d\n", errors);
  2947. DumpSimplify(stderr, path, "simplifyTest");
  2948. fflush(stderr);
  2949. }
  2950. }
  2951. #endif
  2952. // global path dumps for msvs Visual Studio 17 to use from Immediate Window
  2953. void Dump(const SkPath& path) {
  2954. path.dump();
  2955. }
  2956. void DumpHex(const SkPath& path) {
  2957. path.dumpHex();
  2958. }