GrTessellator.cpp 91 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403
  1. /*
  2. * Copyright 2015 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 "src/gpu/GrTessellator.h"
  8. #include "src/gpu/GrDefaultGeoProcFactory.h"
  9. #include "src/gpu/GrVertexWriter.h"
  10. #include "src/gpu/geometry/GrPathUtils.h"
  11. #include "include/core/SkPath.h"
  12. #include "src/core/SkArenaAlloc.h"
  13. #include "src/core/SkGeometry.h"
  14. #include "src/core/SkPointPriv.h"
  15. #include <algorithm>
  16. #include <cstdio>
  17. #include <queue>
  18. #include <unordered_map>
  19. #include <utility>
  20. /*
  21. * There are six stages to the basic algorithm:
  22. *
  23. * 1) Linearize the path contours into piecewise linear segments (path_to_contours()).
  24. * 2) Build a mesh of edges connecting the vertices (build_edges()).
  25. * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
  26. * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplify()).
  27. * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
  28. * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_triangles()).
  29. *
  30. * For screenspace antialiasing, the algorithm is modified as follows:
  31. *
  32. * Run steps 1-5 above to produce polygons.
  33. * 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()).
  34. * 5c) Simplify boundaries to remove "pointy" vertices that cause inversions (simplify_boundary()).
  35. * 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find
  36. * new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a new
  37. * antialiased mesh from those vertices (stroke_boundary()).
  38. * Run steps 3-6 above on the new mesh, and produce antialiased triangles.
  39. *
  40. * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
  41. * of vertices (and the necessity of inserting new vertices on intersection).
  42. *
  43. * Stages (4) and (5) use an active edge list -- a list of all edges for which the
  44. * sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
  45. * left-to-right based on the point where both edges are active (when both top vertices
  46. * have been seen, so the "lower" top vertex of the two). If the top vertices are equal
  47. * (shared), it's sorted based on the last point where both edges are active, so the
  48. * "upper" bottom vertex.
  49. *
  50. * The most complex step is the simplification (4). It's based on the Bentley-Ottman
  51. * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
  52. * not exact and may violate the mesh topology or active edge list ordering. We
  53. * accommodate this by adjusting the topology of the mesh and AEL to match the intersection
  54. * points. This occurs in two ways:
  55. *
  56. * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
  57. * neighbouring edges at the top or bottom vertex. This is handled by merging the
  58. * edges (merge_collinear_edges()).
  59. * B) Intersections may cause an edge to violate the left-to-right ordering of the
  60. * active edge list. This is handled during merging or splitting by rewind()ing the
  61. * active edge list to the vertex before potential violations occur.
  62. *
  63. * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
  64. * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
  65. * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
  66. * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
  67. * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
  68. * insertions and removals was greater than the cost of infrequent O(N) lookups with the
  69. * linked list implementation. With the latter, all removals are O(1), and most insertions
  70. * are O(1), since we know the adjacent edge in the active edge list based on the topology.
  71. * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
  72. * frequent. There may be other data structures worth investigating, however.
  73. *
  74. * Note that the orientation of the line sweep algorithms is determined by the aspect ratio of the
  75. * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y
  76. * coordinate, and secondarily by increasing X coordinate. When the path is wider than it is tall,
  77. * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so
  78. * that the "left" and "right" orientation in the code remains correct (edges to the left are
  79. * increasing in Y; edges to the right are decreasing in Y). That is, the setting rotates 90
  80. * degrees counterclockwise, rather that transposing.
  81. */
  82. #define LOGGING_ENABLED 0
  83. #if LOGGING_ENABLED
  84. #define LOG printf
  85. #else
  86. #define LOG(...)
  87. #endif
  88. namespace {
  89. const int kArenaChunkSize = 16 * 1024;
  90. const float kCosMiterAngle = 0.97f; // Corresponds to an angle of ~14 degrees.
  91. struct Vertex;
  92. struct Edge;
  93. struct Event;
  94. struct Poly;
  95. template <class T, T* T::*Prev, T* T::*Next>
  96. void list_insert(T* t, T* prev, T* next, T** head, T** tail) {
  97. t->*Prev = prev;
  98. t->*Next = next;
  99. if (prev) {
  100. prev->*Next = t;
  101. } else if (head) {
  102. *head = t;
  103. }
  104. if (next) {
  105. next->*Prev = t;
  106. } else if (tail) {
  107. *tail = t;
  108. }
  109. }
  110. template <class T, T* T::*Prev, T* T::*Next>
  111. void list_remove(T* t, T** head, T** tail) {
  112. if (t->*Prev) {
  113. t->*Prev->*Next = t->*Next;
  114. } else if (head) {
  115. *head = t->*Next;
  116. }
  117. if (t->*Next) {
  118. t->*Next->*Prev = t->*Prev;
  119. } else if (tail) {
  120. *tail = t->*Prev;
  121. }
  122. t->*Prev = t->*Next = nullptr;
  123. }
  124. /**
  125. * Vertices are used in three ways: first, the path contours are converted into a
  126. * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
  127. * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
  128. * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
  129. * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
  130. * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
  131. * an individual Vertex from the path mesh may belong to multiple
  132. * MonotonePolys, so the original Vertices cannot be re-used.
  133. */
  134. struct Vertex {
  135. Vertex(const SkPoint& point, uint8_t alpha)
  136. : fPoint(point), fPrev(nullptr), fNext(nullptr)
  137. , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
  138. , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
  139. , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
  140. , fPartner(nullptr)
  141. , fAlpha(alpha)
  142. , fSynthetic(false)
  143. #if LOGGING_ENABLED
  144. , fID (-1.0f)
  145. #endif
  146. {}
  147. SkPoint fPoint; // Vertex position
  148. Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
  149. Vertex* fNext; // "
  150. Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
  151. Edge* fLastEdgeAbove; // "
  152. Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
  153. Edge* fLastEdgeBelow; // "
  154. Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
  155. Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
  156. Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
  157. uint8_t fAlpha;
  158. bool fSynthetic; // Is this a synthetic vertex?
  159. #if LOGGING_ENABLED
  160. float fID; // Identifier used for logging.
  161. #endif
  162. };
  163. /***************************************************************************************/
  164. typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
  165. bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
  166. return a.fX < b.fX || (a.fX == b.fX && a.fY > b.fY);
  167. }
  168. bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
  169. return a.fY < b.fY || (a.fY == b.fY && a.fX < b.fX);
  170. }
  171. struct Comparator {
  172. enum class Direction { kVertical, kHorizontal };
  173. Comparator(Direction direction) : fDirection(direction) {}
  174. bool sweep_lt(const SkPoint& a, const SkPoint& b) const {
  175. return fDirection == Direction::kHorizontal ? sweep_lt_horiz(a, b) : sweep_lt_vert(a, b);
  176. }
  177. Direction fDirection;
  178. };
  179. inline void* emit_vertex(Vertex* v, bool emitCoverage, void* data) {
  180. GrVertexWriter verts{data};
  181. verts.write(v->fPoint);
  182. if (emitCoverage) {
  183. verts.write(GrNormalizeByteToFloat(v->fAlpha));
  184. }
  185. return verts.fPtr;
  186. }
  187. void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, bool emitCoverage, void* data) {
  188. LOG("emit_triangle %g (%g, %g) %d\n", v0->fID, v0->fPoint.fX, v0->fPoint.fY, v0->fAlpha);
  189. LOG(" %g (%g, %g) %d\n", v1->fID, v1->fPoint.fX, v1->fPoint.fY, v1->fAlpha);
  190. LOG(" %g (%g, %g) %d\n", v2->fID, v2->fPoint.fX, v2->fPoint.fY, v2->fAlpha);
  191. #if TESSELLATOR_WIREFRAME
  192. data = emit_vertex(v0, emitCoverage, data);
  193. data = emit_vertex(v1, emitCoverage, data);
  194. data = emit_vertex(v1, emitCoverage, data);
  195. data = emit_vertex(v2, emitCoverage, data);
  196. data = emit_vertex(v2, emitCoverage, data);
  197. data = emit_vertex(v0, emitCoverage, data);
  198. #else
  199. data = emit_vertex(v0, emitCoverage, data);
  200. data = emit_vertex(v1, emitCoverage, data);
  201. data = emit_vertex(v2, emitCoverage, data);
  202. #endif
  203. return data;
  204. }
  205. struct VertexList {
  206. VertexList() : fHead(nullptr), fTail(nullptr) {}
  207. VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
  208. Vertex* fHead;
  209. Vertex* fTail;
  210. void insert(Vertex* v, Vertex* prev, Vertex* next) {
  211. list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail);
  212. }
  213. void append(Vertex* v) {
  214. insert(v, fTail, nullptr);
  215. }
  216. void append(const VertexList& list) {
  217. if (!list.fHead) {
  218. return;
  219. }
  220. if (fTail) {
  221. fTail->fNext = list.fHead;
  222. list.fHead->fPrev = fTail;
  223. } else {
  224. fHead = list.fHead;
  225. }
  226. fTail = list.fTail;
  227. }
  228. void prepend(Vertex* v) {
  229. insert(v, nullptr, fHead);
  230. }
  231. void remove(Vertex* v) {
  232. list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail);
  233. }
  234. void close() {
  235. if (fHead && fTail) {
  236. fTail->fNext = fHead;
  237. fHead->fPrev = fTail;
  238. }
  239. }
  240. };
  241. // Round to nearest quarter-pixel. This is used for screenspace tessellation.
  242. inline void round(SkPoint* p) {
  243. p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
  244. p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
  245. }
  246. inline SkScalar double_to_clamped_scalar(double d) {
  247. return SkDoubleToScalar(std::min((double) SK_ScalarMax, std::max(d, (double) -SK_ScalarMax)));
  248. }
  249. // A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
  250. struct Line {
  251. Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
  252. Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
  253. Line(const SkPoint& p, const SkPoint& q)
  254. : fA(static_cast<double>(q.fY) - p.fY) // a = dY
  255. , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
  256. , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
  257. static_cast<double>(p.fX) * q.fY) {}
  258. double dist(const SkPoint& p) const {
  259. return fA * p.fX + fB * p.fY + fC;
  260. }
  261. Line operator*(double v) const {
  262. return Line(fA * v, fB * v, fC * v);
  263. }
  264. double magSq() const {
  265. return fA * fA + fB * fB;
  266. }
  267. void normalize() {
  268. double len = sqrt(this->magSq());
  269. if (len == 0.0) {
  270. return;
  271. }
  272. double scale = 1.0f / len;
  273. fA *= scale;
  274. fB *= scale;
  275. fC *= scale;
  276. }
  277. bool nearParallel(const Line& o) const {
  278. return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001;
  279. }
  280. // Compute the intersection of two (infinite) Lines.
  281. bool intersect(const Line& other, SkPoint* point) const {
  282. double denom = fA * other.fB - fB * other.fA;
  283. if (denom == 0.0) {
  284. return false;
  285. }
  286. double scale = 1.0 / denom;
  287. point->fX = double_to_clamped_scalar((fB * other.fC - other.fB * fC) * scale);
  288. point->fY = double_to_clamped_scalar((other.fA * fC - fA * other.fC) * scale);
  289. round(point);
  290. return point->isFinite();
  291. }
  292. double fA, fB, fC;
  293. };
  294. /**
  295. * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
  296. * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
  297. * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
  298. * point). For speed, that case is only tested by the callers that require it. Edges also handle
  299. * checking for intersection with other edges. Currently, this converts the edges to the
  300. * parametric form, in order to avoid doing a division until an intersection has been confirmed.
  301. * This is slightly slower in the "found" case, but a lot faster in the "not found" case.
  302. *
  303. * The coefficients of the line equation stored in double precision to avoid catastrphic
  304. * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
  305. * correct in float, since it's a polynomial of degree 2. The intersect() function, being
  306. * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
  307. * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
  308. * this file).
  309. */
  310. struct Edge {
  311. enum class Type { kInner, kOuter, kConnector };
  312. Edge(Vertex* top, Vertex* bottom, int winding, Type type)
  313. : fWinding(winding)
  314. , fTop(top)
  315. , fBottom(bottom)
  316. , fType(type)
  317. , fLeft(nullptr)
  318. , fRight(nullptr)
  319. , fPrevEdgeAbove(nullptr)
  320. , fNextEdgeAbove(nullptr)
  321. , fPrevEdgeBelow(nullptr)
  322. , fNextEdgeBelow(nullptr)
  323. , fLeftPoly(nullptr)
  324. , fRightPoly(nullptr)
  325. , fLeftPolyPrev(nullptr)
  326. , fLeftPolyNext(nullptr)
  327. , fRightPolyPrev(nullptr)
  328. , fRightPolyNext(nullptr)
  329. , fUsedInLeftPoly(false)
  330. , fUsedInRightPoly(false)
  331. , fLine(top, bottom) {
  332. }
  333. int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
  334. Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
  335. Vertex* fBottom; // The bottom vertex in vertex-sort-order.
  336. Type fType;
  337. Edge* fLeft; // The linked list of edges in the active edge list.
  338. Edge* fRight; // "
  339. Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
  340. Edge* fNextEdgeAbove; // "
  341. Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
  342. Edge* fNextEdgeBelow; // "
  343. Poly* fLeftPoly; // The Poly to the left of this edge, if any.
  344. Poly* fRightPoly; // The Poly to the right of this edge, if any.
  345. Edge* fLeftPolyPrev;
  346. Edge* fLeftPolyNext;
  347. Edge* fRightPolyPrev;
  348. Edge* fRightPolyNext;
  349. bool fUsedInLeftPoly;
  350. bool fUsedInRightPoly;
  351. Line fLine;
  352. double dist(const SkPoint& p) const {
  353. return fLine.dist(p);
  354. }
  355. bool isRightOf(Vertex* v) const {
  356. return fLine.dist(v->fPoint) < 0.0;
  357. }
  358. bool isLeftOf(Vertex* v) const {
  359. return fLine.dist(v->fPoint) > 0.0;
  360. }
  361. void recompute() {
  362. fLine = Line(fTop, fBottom);
  363. }
  364. bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const {
  365. LOG("intersecting %g -> %g with %g -> %g\n",
  366. fTop->fID, fBottom->fID,
  367. other.fTop->fID, other.fBottom->fID);
  368. if (fTop == other.fTop || fBottom == other.fBottom) {
  369. return false;
  370. }
  371. double denom = fLine.fA * other.fLine.fB - fLine.fB * other.fLine.fA;
  372. if (denom == 0.0) {
  373. return false;
  374. }
  375. double dx = static_cast<double>(other.fTop->fPoint.fX) - fTop->fPoint.fX;
  376. double dy = static_cast<double>(other.fTop->fPoint.fY) - fTop->fPoint.fY;
  377. double sNumer = dy * other.fLine.fB + dx * other.fLine.fA;
  378. double tNumer = dy * fLine.fB + dx * fLine.fA;
  379. // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
  380. // This saves us doing the divide below unless absolutely necessary.
  381. if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
  382. : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
  383. return false;
  384. }
  385. double s = sNumer / denom;
  386. SkASSERT(s >= 0.0 && s <= 1.0);
  387. p->fX = SkDoubleToScalar(fTop->fPoint.fX - s * fLine.fB);
  388. p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fLine.fA);
  389. if (alpha) {
  390. if (fType == Type::kConnector) {
  391. *alpha = (1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha;
  392. } else if (other.fType == Type::kConnector) {
  393. double t = tNumer / denom;
  394. *alpha = (1.0 - t) * other.fTop->fAlpha + t * other.fBottom->fAlpha;
  395. } else if (fType == Type::kOuter && other.fType == Type::kOuter) {
  396. *alpha = 0;
  397. } else {
  398. *alpha = 255;
  399. }
  400. }
  401. return true;
  402. }
  403. };
  404. struct SSEdge;
  405. struct SSVertex {
  406. SSVertex(Vertex* v) : fVertex(v), fPrev(nullptr), fNext(nullptr) {}
  407. Vertex* fVertex;
  408. SSEdge* fPrev;
  409. SSEdge* fNext;
  410. };
  411. struct SSEdge {
  412. SSEdge(Edge* edge, SSVertex* prev, SSVertex* next)
  413. : fEdge(edge), fEvent(nullptr), fPrev(prev), fNext(next) {
  414. }
  415. Edge* fEdge;
  416. Event* fEvent;
  417. SSVertex* fPrev;
  418. SSVertex* fNext;
  419. };
  420. typedef std::unordered_map<Vertex*, SSVertex*> SSVertexMap;
  421. typedef std::vector<SSEdge*> SSEdgeList;
  422. struct EdgeList {
  423. EdgeList() : fHead(nullptr), fTail(nullptr) {}
  424. Edge* fHead;
  425. Edge* fTail;
  426. void insert(Edge* edge, Edge* prev, Edge* next) {
  427. list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
  428. }
  429. void append(Edge* e) {
  430. insert(e, fTail, nullptr);
  431. }
  432. void remove(Edge* edge) {
  433. list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
  434. }
  435. void removeAll() {
  436. while (fHead) {
  437. this->remove(fHead);
  438. }
  439. }
  440. void close() {
  441. if (fHead && fTail) {
  442. fTail->fRight = fHead;
  443. fHead->fLeft = fTail;
  444. }
  445. }
  446. bool contains(Edge* edge) const {
  447. return edge->fLeft || edge->fRight || fHead == edge;
  448. }
  449. };
  450. struct EventList;
  451. struct Event {
  452. Event(SSEdge* edge, const SkPoint& point, uint8_t alpha)
  453. : fEdge(edge), fPoint(point), fAlpha(alpha) {
  454. }
  455. SSEdge* fEdge;
  456. SkPoint fPoint;
  457. uint8_t fAlpha;
  458. void apply(VertexList* mesh, Comparator& c, EventList* events, SkArenaAlloc& alloc);
  459. };
  460. struct EventComparator {
  461. enum class Op { kLessThan, kGreaterThan };
  462. EventComparator(Op op) : fOp(op) {}
  463. bool operator() (Event* const &e1, Event* const &e2) {
  464. return fOp == Op::kLessThan ? e1->fAlpha < e2->fAlpha
  465. : e1->fAlpha > e2->fAlpha;
  466. }
  467. Op fOp;
  468. };
  469. typedef std::priority_queue<Event*, std::vector<Event*>, EventComparator> EventPQ;
  470. struct EventList : EventPQ {
  471. EventList(EventComparator comparison) : EventPQ(comparison) {
  472. }
  473. };
  474. void create_event(SSEdge* e, EventList* events, SkArenaAlloc& alloc) {
  475. Vertex* prev = e->fPrev->fVertex;
  476. Vertex* next = e->fNext->fVertex;
  477. if (prev == next || !prev->fPartner || !next->fPartner) {
  478. return;
  479. }
  480. Edge bisector1(prev, prev->fPartner, 1, Edge::Type::kConnector);
  481. Edge bisector2(next, next->fPartner, 1, Edge::Type::kConnector);
  482. SkPoint p;
  483. uint8_t alpha;
  484. if (bisector1.intersect(bisector2, &p, &alpha)) {
  485. LOG("found edge event for %g, %g (original %g -> %g), will collapse to %g,%g alpha %d\n",
  486. prev->fID, next->fID, e->fEdge->fTop->fID, e->fEdge->fBottom->fID, p.fX, p.fY, alpha);
  487. e->fEvent = alloc.make<Event>(e, p, alpha);
  488. events->push(e->fEvent);
  489. }
  490. }
  491. void create_event(SSEdge* edge, Vertex* v, SSEdge* other, Vertex* dest, EventList* events,
  492. Comparator& c, SkArenaAlloc& alloc) {
  493. if (!v->fPartner) {
  494. return;
  495. }
  496. Vertex* top = edge->fEdge->fTop;
  497. Vertex* bottom = edge->fEdge->fBottom;
  498. if (!top || !bottom ) {
  499. return;
  500. }
  501. Line line = edge->fEdge->fLine;
  502. line.fC = -(dest->fPoint.fX * line.fA + dest->fPoint.fY * line.fB);
  503. Edge bisector(v, v->fPartner, 1, Edge::Type::kConnector);
  504. SkPoint p;
  505. uint8_t alpha = dest->fAlpha;
  506. if (line.intersect(bisector.fLine, &p) && !c.sweep_lt(p, top->fPoint) &&
  507. c.sweep_lt(p, bottom->fPoint)) {
  508. LOG("found p edge event for %g, %g (original %g -> %g), will collapse to %g,%g alpha %d\n",
  509. dest->fID, v->fID, top->fID, bottom->fID, p.fX, p.fY, alpha);
  510. edge->fEvent = alloc.make<Event>(edge, p, alpha);
  511. events->push(edge->fEvent);
  512. }
  513. }
  514. /***************************************************************************************/
  515. struct Poly {
  516. Poly(Vertex* v, int winding)
  517. : fFirstVertex(v)
  518. , fWinding(winding)
  519. , fHead(nullptr)
  520. , fTail(nullptr)
  521. , fNext(nullptr)
  522. , fPartner(nullptr)
  523. , fCount(0)
  524. {
  525. #if LOGGING_ENABLED
  526. static int gID = 0;
  527. fID = gID++;
  528. LOG("*** created Poly %d\n", fID);
  529. #endif
  530. }
  531. typedef enum { kLeft_Side, kRight_Side } Side;
  532. struct MonotonePoly {
  533. MonotonePoly(Edge* edge, Side side)
  534. : fSide(side)
  535. , fFirstEdge(nullptr)
  536. , fLastEdge(nullptr)
  537. , fPrev(nullptr)
  538. , fNext(nullptr) {
  539. this->addEdge(edge);
  540. }
  541. Side fSide;
  542. Edge* fFirstEdge;
  543. Edge* fLastEdge;
  544. MonotonePoly* fPrev;
  545. MonotonePoly* fNext;
  546. void addEdge(Edge* edge) {
  547. if (fSide == kRight_Side) {
  548. SkASSERT(!edge->fUsedInRightPoly);
  549. list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
  550. edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
  551. edge->fUsedInRightPoly = true;
  552. } else {
  553. SkASSERT(!edge->fUsedInLeftPoly);
  554. list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
  555. edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
  556. edge->fUsedInLeftPoly = true;
  557. }
  558. }
  559. void* emit(bool emitCoverage, void* data) {
  560. Edge* e = fFirstEdge;
  561. VertexList vertices;
  562. vertices.append(e->fTop);
  563. int count = 1;
  564. while (e != nullptr) {
  565. if (kRight_Side == fSide) {
  566. vertices.append(e->fBottom);
  567. e = e->fRightPolyNext;
  568. } else {
  569. vertices.prepend(e->fBottom);
  570. e = e->fLeftPolyNext;
  571. }
  572. count++;
  573. }
  574. Vertex* first = vertices.fHead;
  575. Vertex* v = first->fNext;
  576. while (v != vertices.fTail) {
  577. SkASSERT(v && v->fPrev && v->fNext);
  578. Vertex* prev = v->fPrev;
  579. Vertex* curr = v;
  580. Vertex* next = v->fNext;
  581. if (count == 3) {
  582. return emit_triangle(prev, curr, next, emitCoverage, data);
  583. }
  584. double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
  585. double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
  586. double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
  587. double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
  588. if (ax * by - ay * bx >= 0.0) {
  589. data = emit_triangle(prev, curr, next, emitCoverage, data);
  590. v->fPrev->fNext = v->fNext;
  591. v->fNext->fPrev = v->fPrev;
  592. count--;
  593. if (v->fPrev == first) {
  594. v = v->fNext;
  595. } else {
  596. v = v->fPrev;
  597. }
  598. } else {
  599. v = v->fNext;
  600. }
  601. }
  602. return data;
  603. }
  604. };
  605. Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc) {
  606. LOG("addEdge (%g -> %g) to poly %d, %s side\n",
  607. e->fTop->fID, e->fBottom->fID, fID, side == kLeft_Side ? "left" : "right");
  608. Poly* partner = fPartner;
  609. Poly* poly = this;
  610. if (side == kRight_Side) {
  611. if (e->fUsedInRightPoly) {
  612. return this;
  613. }
  614. } else {
  615. if (e->fUsedInLeftPoly) {
  616. return this;
  617. }
  618. }
  619. if (partner) {
  620. fPartner = partner->fPartner = nullptr;
  621. }
  622. if (!fTail) {
  623. fHead = fTail = alloc.make<MonotonePoly>(e, side);
  624. fCount += 2;
  625. } else if (e->fBottom == fTail->fLastEdge->fBottom) {
  626. return poly;
  627. } else if (side == fTail->fSide) {
  628. fTail->addEdge(e);
  629. fCount++;
  630. } else {
  631. e = alloc.make<Edge>(fTail->fLastEdge->fBottom, e->fBottom, 1, Edge::Type::kInner);
  632. fTail->addEdge(e);
  633. fCount++;
  634. if (partner) {
  635. partner->addEdge(e, side, alloc);
  636. poly = partner;
  637. } else {
  638. MonotonePoly* m = alloc.make<MonotonePoly>(e, side);
  639. m->fPrev = fTail;
  640. fTail->fNext = m;
  641. fTail = m;
  642. }
  643. }
  644. return poly;
  645. }
  646. void* emit(bool emitCoverage, void *data) {
  647. if (fCount < 3) {
  648. return data;
  649. }
  650. LOG("emit() %d, size %d\n", fID, fCount);
  651. for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) {
  652. data = m->emit(emitCoverage, data);
  653. }
  654. return data;
  655. }
  656. Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
  657. Vertex* fFirstVertex;
  658. int fWinding;
  659. MonotonePoly* fHead;
  660. MonotonePoly* fTail;
  661. Poly* fNext;
  662. Poly* fPartner;
  663. int fCount;
  664. #if LOGGING_ENABLED
  665. int fID;
  666. #endif
  667. };
  668. /***************************************************************************************/
  669. bool coincident(const SkPoint& a, const SkPoint& b) {
  670. return a == b;
  671. }
  672. Poly* new_poly(Poly** head, Vertex* v, int winding, SkArenaAlloc& alloc) {
  673. Poly* poly = alloc.make<Poly>(v, winding);
  674. poly->fNext = *head;
  675. *head = poly;
  676. return poly;
  677. }
  678. void append_point_to_contour(const SkPoint& p, VertexList* contour, SkArenaAlloc& alloc) {
  679. Vertex* v = alloc.make<Vertex>(p, 255);
  680. #if LOGGING_ENABLED
  681. static float gID = 0.0f;
  682. v->fID = gID++;
  683. #endif
  684. contour->append(v);
  685. }
  686. SkScalar quad_error_at(const SkPoint pts[3], SkScalar t, SkScalar u) {
  687. SkQuadCoeff quad(pts);
  688. SkPoint p0 = to_point(quad.eval(t - 0.5f * u));
  689. SkPoint mid = to_point(quad.eval(t));
  690. SkPoint p1 = to_point(quad.eval(t + 0.5f * u));
  691. if (!p0.isFinite() || !mid.isFinite() || !p1.isFinite()) {
  692. return 0;
  693. }
  694. return SkPointPriv::DistanceToLineSegmentBetweenSqd(mid, p0, p1);
  695. }
  696. void append_quadratic_to_contour(const SkPoint pts[3], SkScalar toleranceSqd, VertexList* contour,
  697. SkArenaAlloc& alloc) {
  698. SkQuadCoeff quad(pts);
  699. Sk2s aa = quad.fA * quad.fA;
  700. SkScalar denom = 2.0f * (aa[0] + aa[1]);
  701. Sk2s ab = quad.fA * quad.fB;
  702. SkScalar t = denom ? (-ab[0] - ab[1]) / denom : 0.0f;
  703. int nPoints = 1;
  704. SkScalar u = 1.0f;
  705. // Test possible subdivision values only at the point of maximum curvature.
  706. // If it passes the flatness metric there, it'll pass everywhere.
  707. while (nPoints < GrPathUtils::kMaxPointsPerCurve) {
  708. u = 1.0f / nPoints;
  709. if (quad_error_at(pts, t, u) < toleranceSqd) {
  710. break;
  711. }
  712. nPoints++;
  713. }
  714. for (int j = 1; j <= nPoints; j++) {
  715. append_point_to_contour(to_point(quad.eval(j * u)), contour, alloc);
  716. }
  717. }
  718. void generate_cubic_points(const SkPoint& p0,
  719. const SkPoint& p1,
  720. const SkPoint& p2,
  721. const SkPoint& p3,
  722. SkScalar tolSqd,
  723. VertexList* contour,
  724. int pointsLeft,
  725. SkArenaAlloc& alloc) {
  726. SkScalar d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3);
  727. SkScalar d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3);
  728. if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) ||
  729. !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
  730. append_point_to_contour(p3, contour, alloc);
  731. return;
  732. }
  733. const SkPoint q[] = {
  734. { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
  735. { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
  736. { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
  737. };
  738. const SkPoint r[] = {
  739. { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
  740. { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
  741. };
  742. const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
  743. pointsLeft >>= 1;
  744. generate_cubic_points(p0, q[0], r[0], s, tolSqd, contour, pointsLeft, alloc);
  745. generate_cubic_points(s, r[1], q[2], p3, tolSqd, contour, pointsLeft, alloc);
  746. }
  747. // Stage 1: convert the input path to a set of linear contours (linked list of Vertices).
  748. void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
  749. VertexList* contours, SkArenaAlloc& alloc, bool *isLinear) {
  750. SkScalar toleranceSqd = tolerance * tolerance;
  751. SkPoint pts[4];
  752. *isLinear = true;
  753. VertexList* contour = contours;
  754. SkPath::Iter iter(path, false);
  755. if (path.isInverseFillType()) {
  756. SkPoint quad[4];
  757. clipBounds.toQuad(quad);
  758. for (int i = 3; i >= 0; i--) {
  759. append_point_to_contour(quad[i], contours, alloc);
  760. }
  761. contour++;
  762. }
  763. SkAutoConicToQuads converter;
  764. SkPath::Verb verb;
  765. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  766. switch (verb) {
  767. case SkPath::kConic_Verb: {
  768. SkScalar weight = iter.conicWeight();
  769. const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd);
  770. for (int i = 0; i < converter.countQuads(); ++i) {
  771. append_quadratic_to_contour(quadPts, toleranceSqd, contour, alloc);
  772. quadPts += 2;
  773. }
  774. *isLinear = false;
  775. break;
  776. }
  777. case SkPath::kMove_Verb:
  778. if (contour->fHead) {
  779. contour++;
  780. }
  781. append_point_to_contour(pts[0], contour, alloc);
  782. break;
  783. case SkPath::kLine_Verb: {
  784. append_point_to_contour(pts[1], contour, alloc);
  785. break;
  786. }
  787. case SkPath::kQuad_Verb: {
  788. append_quadratic_to_contour(pts, toleranceSqd, contour, alloc);
  789. *isLinear = false;
  790. break;
  791. }
  792. case SkPath::kCubic_Verb: {
  793. int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance);
  794. generate_cubic_points(pts[0], pts[1], pts[2], pts[3], toleranceSqd, contour,
  795. pointsLeft, alloc);
  796. *isLinear = false;
  797. break;
  798. }
  799. case SkPath::kClose_Verb:
  800. case SkPath::kDone_Verb:
  801. break;
  802. }
  803. }
  804. }
  805. inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
  806. switch (fillType) {
  807. case SkPath::kWinding_FillType:
  808. return winding != 0;
  809. case SkPath::kEvenOdd_FillType:
  810. return (winding & 1) != 0;
  811. case SkPath::kInverseWinding_FillType:
  812. return winding == 1;
  813. case SkPath::kInverseEvenOdd_FillType:
  814. return (winding & 1) == 1;
  815. default:
  816. SkASSERT(false);
  817. return false;
  818. }
  819. }
  820. inline bool apply_fill_type(SkPath::FillType fillType, Poly* poly) {
  821. return poly && apply_fill_type(fillType, poly->fWinding);
  822. }
  823. Edge* new_edge(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc) {
  824. int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
  825. Vertex* top = winding < 0 ? next : prev;
  826. Vertex* bottom = winding < 0 ? prev : next;
  827. return alloc.make<Edge>(top, bottom, winding, type);
  828. }
  829. void remove_edge(Edge* edge, EdgeList* edges) {
  830. LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
  831. SkASSERT(edges->contains(edge));
  832. edges->remove(edge);
  833. }
  834. void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
  835. LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
  836. SkASSERT(!edges->contains(edge));
  837. Edge* next = prev ? prev->fRight : edges->fHead;
  838. edges->insert(edge, prev, next);
  839. }
  840. void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
  841. if (v->fFirstEdgeAbove && v->fLastEdgeAbove) {
  842. *left = v->fFirstEdgeAbove->fLeft;
  843. *right = v->fLastEdgeAbove->fRight;
  844. return;
  845. }
  846. Edge* next = nullptr;
  847. Edge* prev;
  848. for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) {
  849. if (prev->isLeftOf(v)) {
  850. break;
  851. }
  852. next = prev;
  853. }
  854. *left = prev;
  855. *right = next;
  856. }
  857. void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
  858. if (edge->fTop->fPoint == edge->fBottom->fPoint ||
  859. c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
  860. return;
  861. }
  862. LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
  863. Edge* prev = nullptr;
  864. Edge* next;
  865. for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
  866. if (next->isRightOf(edge->fTop)) {
  867. break;
  868. }
  869. prev = next;
  870. }
  871. list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
  872. edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
  873. }
  874. void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
  875. if (edge->fTop->fPoint == edge->fBottom->fPoint ||
  876. c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
  877. return;
  878. }
  879. LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
  880. Edge* prev = nullptr;
  881. Edge* next;
  882. for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
  883. if (next->isRightOf(edge->fBottom)) {
  884. break;
  885. }
  886. prev = next;
  887. }
  888. list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
  889. edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
  890. }
  891. void remove_edge_above(Edge* edge) {
  892. SkASSERT(edge->fTop && edge->fBottom);
  893. LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
  894. edge->fBottom->fID);
  895. list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
  896. edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
  897. }
  898. void remove_edge_below(Edge* edge) {
  899. SkASSERT(edge->fTop && edge->fBottom);
  900. LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
  901. edge->fTop->fID);
  902. list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
  903. edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
  904. }
  905. void disconnect(Edge* edge)
  906. {
  907. remove_edge_above(edge);
  908. remove_edge_below(edge);
  909. }
  910. void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c);
  911. void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, Comparator& c) {
  912. if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) {
  913. return;
  914. }
  915. Vertex* v = *current;
  916. LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID);
  917. while (v != dst) {
  918. v = v->fPrev;
  919. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  920. remove_edge(e, activeEdges);
  921. }
  922. Edge* leftEdge = v->fLeftEnclosingEdge;
  923. for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
  924. insert_edge(e, leftEdge, activeEdges);
  925. leftEdge = e;
  926. }
  927. }
  928. *current = v;
  929. }
  930. void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
  931. remove_edge_below(edge);
  932. edge->fTop = v;
  933. edge->recompute();
  934. insert_edge_below(edge, v, c);
  935. rewind(activeEdges, current, edge->fTop, c);
  936. merge_collinear_edges(edge, activeEdges, current, c);
  937. }
  938. void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
  939. remove_edge_above(edge);
  940. edge->fBottom = v;
  941. edge->recompute();
  942. insert_edge_above(edge, v, c);
  943. rewind(activeEdges, current, edge->fTop, c);
  944. merge_collinear_edges(edge, activeEdges, current, c);
  945. }
  946. void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
  947. Comparator& c) {
  948. if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
  949. LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
  950. edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
  951. edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
  952. rewind(activeEdges, current, edge->fTop, c);
  953. other->fWinding += edge->fWinding;
  954. disconnect(edge);
  955. edge->fTop = edge->fBottom = nullptr;
  956. } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
  957. rewind(activeEdges, current, edge->fTop, c);
  958. other->fWinding += edge->fWinding;
  959. set_bottom(edge, other->fTop, activeEdges, current, c);
  960. } else {
  961. rewind(activeEdges, current, other->fTop, c);
  962. edge->fWinding += other->fWinding;
  963. set_bottom(other, edge->fTop, activeEdges, current, c);
  964. }
  965. }
  966. void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
  967. Comparator& c) {
  968. if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
  969. LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
  970. edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
  971. edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
  972. rewind(activeEdges, current, edge->fTop, c);
  973. other->fWinding += edge->fWinding;
  974. disconnect(edge);
  975. edge->fTop = edge->fBottom = nullptr;
  976. } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
  977. rewind(activeEdges, current, other->fTop, c);
  978. edge->fWinding += other->fWinding;
  979. set_top(other, edge->fBottom, activeEdges, current, c);
  980. } else {
  981. rewind(activeEdges, current, edge->fTop, c);
  982. other->fWinding += edge->fWinding;
  983. set_top(edge, other->fBottom, activeEdges, current, c);
  984. }
  985. }
  986. bool top_collinear(Edge* left, Edge* right) {
  987. if (!left || !right) {
  988. return false;
  989. }
  990. return left->fTop->fPoint == right->fTop->fPoint ||
  991. !left->isLeftOf(right->fTop) || !right->isRightOf(left->fTop);
  992. }
  993. bool bottom_collinear(Edge* left, Edge* right) {
  994. if (!left || !right) {
  995. return false;
  996. }
  997. return left->fBottom->fPoint == right->fBottom->fPoint ||
  998. !left->isLeftOf(right->fBottom) || !right->isRightOf(left->fBottom);
  999. }
  1000. void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
  1001. for (;;) {
  1002. if (top_collinear(edge->fPrevEdgeAbove, edge)) {
  1003. merge_edges_above(edge->fPrevEdgeAbove, edge, activeEdges, current, c);
  1004. } else if (top_collinear(edge, edge->fNextEdgeAbove)) {
  1005. merge_edges_above(edge->fNextEdgeAbove, edge, activeEdges, current, c);
  1006. } else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) {
  1007. merge_edges_below(edge->fPrevEdgeBelow, edge, activeEdges, current, c);
  1008. } else if (bottom_collinear(edge, edge->fNextEdgeBelow)) {
  1009. merge_edges_below(edge->fNextEdgeBelow, edge, activeEdges, current, c);
  1010. } else {
  1011. break;
  1012. }
  1013. }
  1014. SkASSERT(!top_collinear(edge->fPrevEdgeAbove, edge));
  1015. SkASSERT(!top_collinear(edge, edge->fNextEdgeAbove));
  1016. SkASSERT(!bottom_collinear(edge->fPrevEdgeBelow, edge));
  1017. SkASSERT(!bottom_collinear(edge, edge->fNextEdgeBelow));
  1018. }
  1019. bool split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c,
  1020. SkArenaAlloc& alloc) {
  1021. if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) {
  1022. return false;
  1023. }
  1024. LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
  1025. edge->fTop->fID, edge->fBottom->fID,
  1026. v->fID, v->fPoint.fX, v->fPoint.fY);
  1027. Vertex* top;
  1028. Vertex* bottom;
  1029. int winding = edge->fWinding;
  1030. if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
  1031. top = v;
  1032. bottom = edge->fTop;
  1033. set_top(edge, v, activeEdges, current, c);
  1034. } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
  1035. top = edge->fBottom;
  1036. bottom = v;
  1037. set_bottom(edge, v, activeEdges, current, c);
  1038. } else {
  1039. top = v;
  1040. bottom = edge->fBottom;
  1041. set_bottom(edge, v, activeEdges, current, c);
  1042. }
  1043. Edge* newEdge = alloc.make<Edge>(top, bottom, winding, edge->fType);
  1044. insert_edge_below(newEdge, top, c);
  1045. insert_edge_above(newEdge, bottom, c);
  1046. merge_collinear_edges(newEdge, activeEdges, current, c);
  1047. return true;
  1048. }
  1049. bool intersect_edge_pair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, Comparator& c, SkArenaAlloc& alloc) {
  1050. if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) {
  1051. return false;
  1052. }
  1053. if (left->fTop == right->fTop || left->fBottom == right->fBottom) {
  1054. return false;
  1055. }
  1056. if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
  1057. if (!left->isLeftOf(right->fTop)) {
  1058. rewind(activeEdges, current, right->fTop, c);
  1059. return split_edge(left, right->fTop, activeEdges, current, c, alloc);
  1060. }
  1061. } else {
  1062. if (!right->isRightOf(left->fTop)) {
  1063. rewind(activeEdges, current, left->fTop, c);
  1064. return split_edge(right, left->fTop, activeEdges, current, c, alloc);
  1065. }
  1066. }
  1067. if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
  1068. if (!left->isLeftOf(right->fBottom)) {
  1069. rewind(activeEdges, current, right->fBottom, c);
  1070. return split_edge(left, right->fBottom, activeEdges, current, c, alloc);
  1071. }
  1072. } else {
  1073. if (!right->isRightOf(left->fBottom)) {
  1074. rewind(activeEdges, current, left->fBottom, c);
  1075. return split_edge(right, left->fBottom, activeEdges, current, c, alloc);
  1076. }
  1077. }
  1078. return false;
  1079. }
  1080. Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc,
  1081. int winding_scale = 1) {
  1082. if (!prev || !next || prev->fPoint == next->fPoint) {
  1083. return nullptr;
  1084. }
  1085. Edge* edge = new_edge(prev, next, type, c, alloc);
  1086. insert_edge_below(edge, edge->fTop, c);
  1087. insert_edge_above(edge, edge->fBottom, c);
  1088. edge->fWinding *= winding_scale;
  1089. merge_collinear_edges(edge, nullptr, nullptr, c);
  1090. return edge;
  1091. }
  1092. void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c,
  1093. SkArenaAlloc& alloc) {
  1094. LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY,
  1095. src->fID, dst->fID);
  1096. dst->fAlpha = SkTMax(src->fAlpha, dst->fAlpha);
  1097. if (src->fPartner) {
  1098. src->fPartner->fPartner = dst;
  1099. }
  1100. while (Edge* edge = src->fFirstEdgeAbove) {
  1101. set_bottom(edge, dst, nullptr, nullptr, c);
  1102. }
  1103. while (Edge* edge = src->fFirstEdgeBelow) {
  1104. set_top(edge, dst, nullptr, nullptr, c);
  1105. }
  1106. mesh->remove(src);
  1107. dst->fSynthetic = true;
  1108. }
  1109. Vertex* create_sorted_vertex(const SkPoint& p, uint8_t alpha, VertexList* mesh,
  1110. Vertex* reference, Comparator& c, SkArenaAlloc& alloc) {
  1111. Vertex* prevV = reference;
  1112. while (prevV && c.sweep_lt(p, prevV->fPoint)) {
  1113. prevV = prevV->fPrev;
  1114. }
  1115. Vertex* nextV = prevV ? prevV->fNext : mesh->fHead;
  1116. while (nextV && c.sweep_lt(nextV->fPoint, p)) {
  1117. prevV = nextV;
  1118. nextV = nextV->fNext;
  1119. }
  1120. Vertex* v;
  1121. if (prevV && coincident(prevV->fPoint, p)) {
  1122. v = prevV;
  1123. } else if (nextV && coincident(nextV->fPoint, p)) {
  1124. v = nextV;
  1125. } else {
  1126. v = alloc.make<Vertex>(p, alpha);
  1127. #if LOGGING_ENABLED
  1128. if (!prevV) {
  1129. v->fID = mesh->fHead->fID - 1.0f;
  1130. } else if (!nextV) {
  1131. v->fID = mesh->fTail->fID + 1.0f;
  1132. } else {
  1133. v->fID = (prevV->fID + nextV->fID) * 0.5f;
  1134. }
  1135. #endif
  1136. mesh->insert(v, prevV, nextV);
  1137. }
  1138. return v;
  1139. }
  1140. // If an edge's top and bottom points differ only by 1/2 machine epsilon in the primary
  1141. // sort criterion, it may not be possible to split correctly, since there is no point which is
  1142. // below the top and above the bottom. This function detects that case.
  1143. bool nearly_flat(Comparator& c, Edge* edge) {
  1144. SkPoint diff = edge->fBottom->fPoint - edge->fTop->fPoint;
  1145. float primaryDiff = c.fDirection == Comparator::Direction::kHorizontal ? diff.fX : diff.fY;
  1146. return fabs(primaryDiff) < std::numeric_limits<float>::epsilon() && primaryDiff != 0.0f;
  1147. }
  1148. SkPoint clamp(SkPoint p, SkPoint min, SkPoint max, Comparator& c) {
  1149. if (c.sweep_lt(p, min)) {
  1150. return min;
  1151. } else if (c.sweep_lt(max, p)) {
  1152. return max;
  1153. } else {
  1154. return p;
  1155. }
  1156. }
  1157. void compute_bisector(Edge* edge1, Edge* edge2, Vertex* v, SkArenaAlloc& alloc) {
  1158. Line line1 = edge1->fLine;
  1159. Line line2 = edge2->fLine;
  1160. line1.normalize();
  1161. line2.normalize();
  1162. double cosAngle = line1.fA * line2.fA + line1.fB * line2.fB;
  1163. if (cosAngle > 0.999) {
  1164. return;
  1165. }
  1166. line1.fC += edge1->fWinding > 0 ? -1 : 1;
  1167. line2.fC += edge2->fWinding > 0 ? -1 : 1;
  1168. SkPoint p;
  1169. if (line1.intersect(line2, &p)) {
  1170. uint8_t alpha = edge1->fType == Edge::Type::kOuter ? 255 : 0;
  1171. v->fPartner = alloc.make<Vertex>(p, alpha);
  1172. LOG("computed bisector (%g,%g) alpha %d for vertex %g\n", p.fX, p.fY, alpha, v->fID);
  1173. }
  1174. }
  1175. bool check_for_intersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
  1176. VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
  1177. if (!left || !right) {
  1178. return false;
  1179. }
  1180. SkPoint p;
  1181. uint8_t alpha;
  1182. if (left->intersect(*right, &p, &alpha) && p.isFinite()) {
  1183. Vertex* v;
  1184. LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
  1185. Vertex* top = *current;
  1186. // If the intersection point is above the current vertex, rewind to the vertex above the
  1187. // intersection.
  1188. while (top && c.sweep_lt(p, top->fPoint)) {
  1189. top = top->fPrev;
  1190. }
  1191. if (!nearly_flat(c, left)) {
  1192. p = clamp(p, left->fTop->fPoint, left->fBottom->fPoint, c);
  1193. }
  1194. if (!nearly_flat(c, right)) {
  1195. p = clamp(p, right->fTop->fPoint, right->fBottom->fPoint, c);
  1196. }
  1197. if (p == left->fTop->fPoint) {
  1198. v = left->fTop;
  1199. } else if (p == left->fBottom->fPoint) {
  1200. v = left->fBottom;
  1201. } else if (p == right->fTop->fPoint) {
  1202. v = right->fTop;
  1203. } else if (p == right->fBottom->fPoint) {
  1204. v = right->fBottom;
  1205. } else {
  1206. v = create_sorted_vertex(p, alpha, mesh, top, c, alloc);
  1207. if (left->fTop->fPartner) {
  1208. v->fSynthetic = true;
  1209. compute_bisector(left, right, v, alloc);
  1210. }
  1211. }
  1212. rewind(activeEdges, current, top ? top : v, c);
  1213. split_edge(left, v, activeEdges, current, c, alloc);
  1214. split_edge(right, v, activeEdges, current, c, alloc);
  1215. v->fAlpha = SkTMax(v->fAlpha, alpha);
  1216. return true;
  1217. }
  1218. return intersect_edge_pair(left, right, activeEdges, current, c, alloc);
  1219. }
  1220. void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) {
  1221. for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
  1222. SkASSERT(contour->fHead);
  1223. Vertex* prev = contour->fTail;
  1224. if (approximate) {
  1225. round(&prev->fPoint);
  1226. }
  1227. for (Vertex* v = contour->fHead; v;) {
  1228. if (approximate) {
  1229. round(&v->fPoint);
  1230. }
  1231. Vertex* next = v->fNext;
  1232. Vertex* nextWrap = next ? next : contour->fHead;
  1233. if (coincident(prev->fPoint, v->fPoint)) {
  1234. LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY);
  1235. contour->remove(v);
  1236. } else if (!v->fPoint.isFinite()) {
  1237. LOG("vertex %g,%g non-finite; removing\n", v->fPoint.fX, v->fPoint.fY);
  1238. contour->remove(v);
  1239. } else if (Line(prev->fPoint, nextWrap->fPoint).dist(v->fPoint) == 0.0) {
  1240. LOG("vertex %g,%g collinear; removing\n", v->fPoint.fX, v->fPoint.fY);
  1241. contour->remove(v);
  1242. } else {
  1243. prev = v;
  1244. }
  1245. v = next;
  1246. }
  1247. }
  1248. }
  1249. bool merge_coincident_vertices(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
  1250. if (!mesh->fHead) {
  1251. return false;
  1252. }
  1253. bool merged = false;
  1254. for (Vertex* v = mesh->fHead->fNext; v;) {
  1255. Vertex* next = v->fNext;
  1256. if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) {
  1257. v->fPoint = v->fPrev->fPoint;
  1258. }
  1259. if (coincident(v->fPrev->fPoint, v->fPoint)) {
  1260. merge_vertices(v, v->fPrev, mesh, c, alloc);
  1261. merged = true;
  1262. }
  1263. v = next;
  1264. }
  1265. return merged;
  1266. }
  1267. // Stage 2: convert the contours to a mesh of edges connecting the vertices.
  1268. void build_edges(VertexList* contours, int contourCnt, VertexList* mesh, Comparator& c,
  1269. SkArenaAlloc& alloc) {
  1270. for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
  1271. Vertex* prev = contour->fTail;
  1272. for (Vertex* v = contour->fHead; v;) {
  1273. Vertex* next = v->fNext;
  1274. connect(prev, v, Edge::Type::kInner, c, alloc);
  1275. mesh->append(v);
  1276. prev = v;
  1277. v = next;
  1278. }
  1279. }
  1280. }
  1281. void connect_partners(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
  1282. for (Vertex* outer = mesh->fHead; outer; outer = outer->fNext) {
  1283. if (Vertex* inner = outer->fPartner) {
  1284. if ((inner->fPrev || inner->fNext) && (outer->fPrev || outer->fNext)) {
  1285. // Connector edges get zero winding, since they're only structural (i.e., to ensure
  1286. // no 0-0-0 alpha triangles are produced), and shouldn't affect the poly winding
  1287. // number.
  1288. connect(outer, inner, Edge::Type::kConnector, c, alloc, 0);
  1289. inner->fPartner = outer->fPartner = nullptr;
  1290. }
  1291. }
  1292. }
  1293. }
  1294. template <CompareFunc sweep_lt>
  1295. void sorted_merge(VertexList* front, VertexList* back, VertexList* result) {
  1296. Vertex* a = front->fHead;
  1297. Vertex* b = back->fHead;
  1298. while (a && b) {
  1299. if (sweep_lt(a->fPoint, b->fPoint)) {
  1300. front->remove(a);
  1301. result->append(a);
  1302. a = front->fHead;
  1303. } else {
  1304. back->remove(b);
  1305. result->append(b);
  1306. b = back->fHead;
  1307. }
  1308. }
  1309. result->append(*front);
  1310. result->append(*back);
  1311. }
  1312. void sorted_merge(VertexList* front, VertexList* back, VertexList* result, Comparator& c) {
  1313. if (c.fDirection == Comparator::Direction::kHorizontal) {
  1314. sorted_merge<sweep_lt_horiz>(front, back, result);
  1315. } else {
  1316. sorted_merge<sweep_lt_vert>(front, back, result);
  1317. }
  1318. #if LOGGING_ENABLED
  1319. float id = 0.0f;
  1320. for (Vertex* v = result->fHead; v; v = v->fNext) {
  1321. v->fID = id++;
  1322. }
  1323. #endif
  1324. }
  1325. // Stage 3: sort the vertices by increasing sweep direction.
  1326. template <CompareFunc sweep_lt>
  1327. void merge_sort(VertexList* vertices) {
  1328. Vertex* slow = vertices->fHead;
  1329. if (!slow) {
  1330. return;
  1331. }
  1332. Vertex* fast = slow->fNext;
  1333. if (!fast) {
  1334. return;
  1335. }
  1336. do {
  1337. fast = fast->fNext;
  1338. if (fast) {
  1339. fast = fast->fNext;
  1340. slow = slow->fNext;
  1341. }
  1342. } while (fast);
  1343. VertexList front(vertices->fHead, slow);
  1344. VertexList back(slow->fNext, vertices->fTail);
  1345. front.fTail->fNext = back.fHead->fPrev = nullptr;
  1346. merge_sort<sweep_lt>(&front);
  1347. merge_sort<sweep_lt>(&back);
  1348. vertices->fHead = vertices->fTail = nullptr;
  1349. sorted_merge<sweep_lt>(&front, &back, vertices);
  1350. }
  1351. void dump_mesh(const VertexList& mesh) {
  1352. #if LOGGING_ENABLED
  1353. for (Vertex* v = mesh.fHead; v; v = v->fNext) {
  1354. LOG("vertex %g (%g, %g) alpha %d", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
  1355. if (Vertex* p = v->fPartner) {
  1356. LOG(", partner %g (%g, %g) alpha %d\n", p->fID, p->fPoint.fX, p->fPoint.fY, p->fAlpha);
  1357. } else {
  1358. LOG(", null partner\n");
  1359. }
  1360. for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
  1361. LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
  1362. }
  1363. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  1364. LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
  1365. }
  1366. }
  1367. #endif
  1368. }
  1369. void dump_skel(const SSEdgeList& ssEdges) {
  1370. #if LOGGING_ENABLED
  1371. for (SSEdge* edge : ssEdges) {
  1372. if (edge->fEdge) {
  1373. LOG("skel edge %g -> %g",
  1374. edge->fPrev->fVertex->fID,
  1375. edge->fNext->fVertex->fID);
  1376. if (edge->fEdge->fTop && edge->fEdge->fBottom) {
  1377. LOG(" (original %g -> %g)\n",
  1378. edge->fEdge->fTop->fID,
  1379. edge->fEdge->fBottom->fID);
  1380. } else {
  1381. LOG("\n");
  1382. }
  1383. }
  1384. }
  1385. #endif
  1386. }
  1387. #ifdef SK_DEBUG
  1388. void validate_edge_pair(Edge* left, Edge* right, Comparator& c) {
  1389. if (!left || !right) {
  1390. return;
  1391. }
  1392. if (left->fTop == right->fTop) {
  1393. SkASSERT(left->isLeftOf(right->fBottom));
  1394. SkASSERT(right->isRightOf(left->fBottom));
  1395. } else if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
  1396. SkASSERT(left->isLeftOf(right->fTop));
  1397. } else {
  1398. SkASSERT(right->isRightOf(left->fTop));
  1399. }
  1400. if (left->fBottom == right->fBottom) {
  1401. SkASSERT(left->isLeftOf(right->fTop));
  1402. SkASSERT(right->isRightOf(left->fTop));
  1403. } else if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
  1404. SkASSERT(left->isLeftOf(right->fBottom));
  1405. } else {
  1406. SkASSERT(right->isRightOf(left->fBottom));
  1407. }
  1408. }
  1409. void validate_edge_list(EdgeList* edges, Comparator& c) {
  1410. Edge* left = edges->fHead;
  1411. if (!left) {
  1412. return;
  1413. }
  1414. for (Edge* right = left->fRight; right; right = right->fRight) {
  1415. validate_edge_pair(left, right, c);
  1416. left = right;
  1417. }
  1418. }
  1419. #endif
  1420. // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
  1421. bool connected(Vertex* v) {
  1422. return v->fFirstEdgeAbove || v->fFirstEdgeBelow;
  1423. }
  1424. bool simplify(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
  1425. LOG("simplifying complex polygons\n");
  1426. EdgeList activeEdges;
  1427. bool found = false;
  1428. for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
  1429. if (!connected(v)) {
  1430. continue;
  1431. }
  1432. Edge* leftEnclosingEdge;
  1433. Edge* rightEnclosingEdge;
  1434. bool restartChecks;
  1435. do {
  1436. LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
  1437. restartChecks = false;
  1438. find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
  1439. v->fLeftEnclosingEdge = leftEnclosingEdge;
  1440. v->fRightEnclosingEdge = rightEnclosingEdge;
  1441. if (v->fFirstEdgeBelow) {
  1442. for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
  1443. if (check_for_intersection(leftEnclosingEdge, edge, &activeEdges, &v, mesh, c,
  1444. alloc)) {
  1445. restartChecks = true;
  1446. break;
  1447. }
  1448. if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, &v, mesh, c,
  1449. alloc)) {
  1450. restartChecks = true;
  1451. break;
  1452. }
  1453. }
  1454. } else {
  1455. if (check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
  1456. &activeEdges, &v, mesh, c, alloc)) {
  1457. restartChecks = true;
  1458. }
  1459. }
  1460. found = found || restartChecks;
  1461. } while (restartChecks);
  1462. #ifdef SK_DEBUG
  1463. validate_edge_list(&activeEdges, c);
  1464. #endif
  1465. for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
  1466. remove_edge(e, &activeEdges);
  1467. }
  1468. Edge* leftEdge = leftEnclosingEdge;
  1469. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  1470. insert_edge(e, leftEdge, &activeEdges);
  1471. leftEdge = e;
  1472. }
  1473. }
  1474. SkASSERT(!activeEdges.fHead && !activeEdges.fTail);
  1475. return found;
  1476. }
  1477. // Stage 5: Tessellate the simplified mesh into monotone polygons.
  1478. Poly* tessellate(const VertexList& vertices, SkArenaAlloc& alloc) {
  1479. LOG("\ntessellating simple polygons\n");
  1480. EdgeList activeEdges;
  1481. Poly* polys = nullptr;
  1482. for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) {
  1483. if (!connected(v)) {
  1484. continue;
  1485. }
  1486. #if LOGGING_ENABLED
  1487. LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
  1488. #endif
  1489. Edge* leftEnclosingEdge;
  1490. Edge* rightEnclosingEdge;
  1491. find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
  1492. Poly* leftPoly;
  1493. Poly* rightPoly;
  1494. if (v->fFirstEdgeAbove) {
  1495. leftPoly = v->fFirstEdgeAbove->fLeftPoly;
  1496. rightPoly = v->fLastEdgeAbove->fRightPoly;
  1497. } else {
  1498. leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullptr;
  1499. rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nullptr;
  1500. }
  1501. #if LOGGING_ENABLED
  1502. LOG("edges above:\n");
  1503. for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
  1504. LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
  1505. e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
  1506. }
  1507. LOG("edges below:\n");
  1508. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  1509. LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
  1510. e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
  1511. }
  1512. #endif
  1513. if (v->fFirstEdgeAbove) {
  1514. if (leftPoly) {
  1515. leftPoly = leftPoly->addEdge(v->fFirstEdgeAbove, Poly::kRight_Side, alloc);
  1516. }
  1517. if (rightPoly) {
  1518. rightPoly = rightPoly->addEdge(v->fLastEdgeAbove, Poly::kLeft_Side, alloc);
  1519. }
  1520. for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
  1521. Edge* rightEdge = e->fNextEdgeAbove;
  1522. remove_edge(e, &activeEdges);
  1523. if (e->fRightPoly) {
  1524. e->fRightPoly->addEdge(e, Poly::kLeft_Side, alloc);
  1525. }
  1526. if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != e->fRightPoly) {
  1527. rightEdge->fLeftPoly->addEdge(e, Poly::kRight_Side, alloc);
  1528. }
  1529. }
  1530. remove_edge(v->fLastEdgeAbove, &activeEdges);
  1531. if (!v->fFirstEdgeBelow) {
  1532. if (leftPoly && rightPoly && leftPoly != rightPoly) {
  1533. SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartner == nullptr);
  1534. rightPoly->fPartner = leftPoly;
  1535. leftPoly->fPartner = rightPoly;
  1536. }
  1537. }
  1538. }
  1539. if (v->fFirstEdgeBelow) {
  1540. if (!v->fFirstEdgeAbove) {
  1541. if (leftPoly && rightPoly) {
  1542. if (leftPoly == rightPoly) {
  1543. if (leftPoly->fTail && leftPoly->fTail->fSide == Poly::kLeft_Side) {
  1544. leftPoly = new_poly(&polys, leftPoly->lastVertex(),
  1545. leftPoly->fWinding, alloc);
  1546. leftEnclosingEdge->fRightPoly = leftPoly;
  1547. } else {
  1548. rightPoly = new_poly(&polys, rightPoly->lastVertex(),
  1549. rightPoly->fWinding, alloc);
  1550. rightEnclosingEdge->fLeftPoly = rightPoly;
  1551. }
  1552. }
  1553. Edge* join = alloc.make<Edge>(leftPoly->lastVertex(), v, 1, Edge::Type::kInner);
  1554. leftPoly = leftPoly->addEdge(join, Poly::kRight_Side, alloc);
  1555. rightPoly = rightPoly->addEdge(join, Poly::kLeft_Side, alloc);
  1556. }
  1557. }
  1558. Edge* leftEdge = v->fFirstEdgeBelow;
  1559. leftEdge->fLeftPoly = leftPoly;
  1560. insert_edge(leftEdge, leftEnclosingEdge, &activeEdges);
  1561. for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
  1562. rightEdge = rightEdge->fNextEdgeBelow) {
  1563. insert_edge(rightEdge, leftEdge, &activeEdges);
  1564. int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0;
  1565. winding += leftEdge->fWinding;
  1566. if (winding != 0) {
  1567. Poly* poly = new_poly(&polys, v, winding, alloc);
  1568. leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
  1569. }
  1570. leftEdge = rightEdge;
  1571. }
  1572. v->fLastEdgeBelow->fRightPoly = rightPoly;
  1573. }
  1574. #if LOGGING_ENABLED
  1575. LOG("\nactive edges:\n");
  1576. for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
  1577. LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
  1578. e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
  1579. }
  1580. #endif
  1581. }
  1582. return polys;
  1583. }
  1584. void remove_non_boundary_edges(const VertexList& mesh, SkPath::FillType fillType,
  1585. SkArenaAlloc& alloc) {
  1586. LOG("removing non-boundary edges\n");
  1587. EdgeList activeEdges;
  1588. for (Vertex* v = mesh.fHead; v != nullptr; v = v->fNext) {
  1589. if (!connected(v)) {
  1590. continue;
  1591. }
  1592. Edge* leftEnclosingEdge;
  1593. Edge* rightEnclosingEdge;
  1594. find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
  1595. bool prevFilled = leftEnclosingEdge &&
  1596. apply_fill_type(fillType, leftEnclosingEdge->fWinding);
  1597. for (Edge* e = v->fFirstEdgeAbove; e;) {
  1598. Edge* next = e->fNextEdgeAbove;
  1599. remove_edge(e, &activeEdges);
  1600. bool filled = apply_fill_type(fillType, e->fWinding);
  1601. if (filled == prevFilled) {
  1602. disconnect(e);
  1603. }
  1604. prevFilled = filled;
  1605. e = next;
  1606. }
  1607. Edge* prev = leftEnclosingEdge;
  1608. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  1609. if (prev) {
  1610. e->fWinding += prev->fWinding;
  1611. }
  1612. insert_edge(e, prev, &activeEdges);
  1613. prev = e;
  1614. }
  1615. }
  1616. }
  1617. // Note: this is the normal to the edge, but not necessarily unit length.
  1618. void get_edge_normal(const Edge* e, SkVector* normal) {
  1619. normal->set(SkDoubleToScalar(e->fLine.fA),
  1620. SkDoubleToScalar(e->fLine.fB));
  1621. }
  1622. // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions
  1623. // and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
  1624. // invert on stroking.
  1625. void simplify_boundary(EdgeList* boundary, Comparator& c, SkArenaAlloc& alloc) {
  1626. Edge* prevEdge = boundary->fTail;
  1627. SkVector prevNormal;
  1628. get_edge_normal(prevEdge, &prevNormal);
  1629. for (Edge* e = boundary->fHead; e != nullptr;) {
  1630. Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom;
  1631. Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop;
  1632. double distPrev = e->dist(prev->fPoint);
  1633. double distNext = prevEdge->dist(next->fPoint);
  1634. SkVector normal;
  1635. get_edge_normal(e, &normal);
  1636. constexpr double kQuarterPixelSq = 0.25f * 0.25f;
  1637. if (prev == next) {
  1638. remove_edge(prevEdge, boundary);
  1639. remove_edge(e, boundary);
  1640. prevEdge = boundary->fTail;
  1641. e = boundary->fHead;
  1642. if (prevEdge) {
  1643. get_edge_normal(prevEdge, &prevNormal);
  1644. }
  1645. } else if (prevNormal.dot(normal) < 0.0 &&
  1646. (distPrev * distPrev <= kQuarterPixelSq || distNext * distNext <= kQuarterPixelSq)) {
  1647. Edge* join = new_edge(prev, next, Edge::Type::kInner, c, alloc);
  1648. if (prev->fPoint != next->fPoint) {
  1649. join->fLine.normalize();
  1650. join->fLine = join->fLine * join->fWinding;
  1651. }
  1652. insert_edge(join, e, boundary);
  1653. remove_edge(prevEdge, boundary);
  1654. remove_edge(e, boundary);
  1655. if (join->fLeft && join->fRight) {
  1656. prevEdge = join->fLeft;
  1657. e = join;
  1658. } else {
  1659. prevEdge = boundary->fTail;
  1660. e = boundary->fHead; // join->fLeft ? join->fLeft : join;
  1661. }
  1662. get_edge_normal(prevEdge, &prevNormal);
  1663. } else {
  1664. prevEdge = e;
  1665. prevNormal = normal;
  1666. e = e->fRight;
  1667. }
  1668. }
  1669. }
  1670. void ss_connect(Vertex* v, Vertex* dest, Comparator& c, SkArenaAlloc& alloc) {
  1671. if (v == dest) {
  1672. return;
  1673. }
  1674. LOG("ss_connecting vertex %g to vertex %g\n", v->fID, dest->fID);
  1675. if (v->fSynthetic) {
  1676. connect(v, dest, Edge::Type::kConnector, c, alloc, 0);
  1677. } else if (v->fPartner) {
  1678. LOG("setting %g's partner to %g ", v->fPartner->fID, dest->fID);
  1679. LOG("and %g's partner to null\n", v->fID);
  1680. v->fPartner->fPartner = dest;
  1681. v->fPartner = nullptr;
  1682. }
  1683. }
  1684. void Event::apply(VertexList* mesh, Comparator& c, EventList* events, SkArenaAlloc& alloc) {
  1685. if (!fEdge) {
  1686. return;
  1687. }
  1688. Vertex* prev = fEdge->fPrev->fVertex;
  1689. Vertex* next = fEdge->fNext->fVertex;
  1690. SSEdge* prevEdge = fEdge->fPrev->fPrev;
  1691. SSEdge* nextEdge = fEdge->fNext->fNext;
  1692. if (!prevEdge || !nextEdge || !prevEdge->fEdge || !nextEdge->fEdge) {
  1693. return;
  1694. }
  1695. Vertex* dest = create_sorted_vertex(fPoint, fAlpha, mesh, prev, c, alloc);
  1696. dest->fSynthetic = true;
  1697. SSVertex* ssv = alloc.make<SSVertex>(dest);
  1698. LOG("collapsing %g, %g (original edge %g -> %g) to %g (%g, %g) alpha %d\n",
  1699. prev->fID, next->fID, fEdge->fEdge->fTop->fID, fEdge->fEdge->fBottom->fID,
  1700. dest->fID, fPoint.fX, fPoint.fY, fAlpha);
  1701. fEdge->fEdge = nullptr;
  1702. ss_connect(prev, dest, c, alloc);
  1703. ss_connect(next, dest, c, alloc);
  1704. prevEdge->fNext = nextEdge->fPrev = ssv;
  1705. ssv->fPrev = prevEdge;
  1706. ssv->fNext = nextEdge;
  1707. if (!prevEdge->fEdge || !nextEdge->fEdge) {
  1708. return;
  1709. }
  1710. if (prevEdge->fEvent) {
  1711. prevEdge->fEvent->fEdge = nullptr;
  1712. }
  1713. if (nextEdge->fEvent) {
  1714. nextEdge->fEvent->fEdge = nullptr;
  1715. }
  1716. if (prevEdge->fPrev == nextEdge->fNext) {
  1717. ss_connect(prevEdge->fPrev->fVertex, dest, c, alloc);
  1718. prevEdge->fEdge = nextEdge->fEdge = nullptr;
  1719. } else {
  1720. compute_bisector(prevEdge->fEdge, nextEdge->fEdge, dest, alloc);
  1721. SkASSERT(prevEdge != fEdge && nextEdge != fEdge);
  1722. if (dest->fPartner) {
  1723. create_event(prevEdge, events, alloc);
  1724. create_event(nextEdge, events, alloc);
  1725. } else {
  1726. create_event(prevEdge, prevEdge->fPrev->fVertex, nextEdge, dest, events, c, alloc);
  1727. create_event(nextEdge, nextEdge->fNext->fVertex, prevEdge, dest, events, c, alloc);
  1728. }
  1729. }
  1730. }
  1731. bool is_overlap_edge(Edge* e) {
  1732. if (e->fType == Edge::Type::kOuter) {
  1733. return e->fWinding != 0 && e->fWinding != 1;
  1734. } else if (e->fType == Edge::Type::kInner) {
  1735. return e->fWinding != 0 && e->fWinding != -2;
  1736. } else {
  1737. return false;
  1738. }
  1739. }
  1740. // This is a stripped-down version of tessellate() which computes edges which
  1741. // join two filled regions, which represent overlap regions, and collapses them.
  1742. bool collapse_overlap_regions(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc,
  1743. EventComparator comp) {
  1744. LOG("\nfinding overlap regions\n");
  1745. EdgeList activeEdges;
  1746. EventList events(comp);
  1747. SSVertexMap ssVertices;
  1748. SSEdgeList ssEdges;
  1749. for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
  1750. if (!connected(v)) {
  1751. continue;
  1752. }
  1753. Edge* leftEnclosingEdge;
  1754. Edge* rightEnclosingEdge;
  1755. find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
  1756. for (Edge* e = v->fLastEdgeAbove; e && e != leftEnclosingEdge;) {
  1757. Edge* prev = e->fPrevEdgeAbove ? e->fPrevEdgeAbove : leftEnclosingEdge;
  1758. remove_edge(e, &activeEdges);
  1759. bool leftOverlap = prev && is_overlap_edge(prev);
  1760. bool rightOverlap = is_overlap_edge(e);
  1761. bool isOuterBoundary = e->fType == Edge::Type::kOuter &&
  1762. (!prev || prev->fWinding == 0 || e->fWinding == 0);
  1763. if (prev) {
  1764. e->fWinding -= prev->fWinding;
  1765. }
  1766. if (leftOverlap && rightOverlap) {
  1767. LOG("found interior overlap edge %g -> %g, disconnecting\n",
  1768. e->fTop->fID, e->fBottom->fID);
  1769. disconnect(e);
  1770. } else if (leftOverlap || rightOverlap) {
  1771. LOG("found overlap edge %g -> %g%s\n", e->fTop->fID, e->fBottom->fID,
  1772. isOuterBoundary ? ", is outer boundary" : "");
  1773. Vertex* prevVertex = e->fWinding < 0 ? e->fBottom : e->fTop;
  1774. Vertex* nextVertex = e->fWinding < 0 ? e->fTop : e->fBottom;
  1775. SSVertex* ssPrev = ssVertices[prevVertex];
  1776. if (!ssPrev) {
  1777. ssPrev = ssVertices[prevVertex] = alloc.make<SSVertex>(prevVertex);
  1778. }
  1779. SSVertex* ssNext = ssVertices[nextVertex];
  1780. if (!ssNext) {
  1781. ssNext = ssVertices[nextVertex] = alloc.make<SSVertex>(nextVertex);
  1782. }
  1783. SSEdge* ssEdge = alloc.make<SSEdge>(e, ssPrev, ssNext);
  1784. ssEdges.push_back(ssEdge);
  1785. // SkASSERT(!ssPrev->fNext && !ssNext->fPrev);
  1786. ssPrev->fNext = ssNext->fPrev = ssEdge;
  1787. create_event(ssEdge, &events, alloc);
  1788. if (!isOuterBoundary) {
  1789. disconnect(e);
  1790. }
  1791. }
  1792. e = prev;
  1793. }
  1794. Edge* prev = leftEnclosingEdge;
  1795. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  1796. if (prev) {
  1797. e->fWinding += prev->fWinding;
  1798. }
  1799. insert_edge(e, prev, &activeEdges);
  1800. prev = e;
  1801. }
  1802. }
  1803. bool complex = events.size() > 0;
  1804. LOG("\ncollapsing overlap regions\n");
  1805. LOG("skeleton before:\n");
  1806. dump_skel(ssEdges);
  1807. while (events.size() > 0) {
  1808. Event* event = events.top();
  1809. events.pop();
  1810. event->apply(mesh, c, &events, alloc);
  1811. }
  1812. LOG("skeleton after:\n");
  1813. dump_skel(ssEdges);
  1814. for (SSEdge* edge : ssEdges) {
  1815. if (Edge* e = edge->fEdge) {
  1816. connect(edge->fPrev->fVertex, edge->fNext->fVertex, e->fType, c, alloc, 0);
  1817. }
  1818. }
  1819. return complex;
  1820. }
  1821. bool inversion(Vertex* prev, Vertex* next, Edge* origEdge, Comparator& c) {
  1822. if (!prev || !next) {
  1823. return true;
  1824. }
  1825. int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
  1826. return winding != origEdge->fWinding;
  1827. }
  1828. // Stage 5d: Displace edges by half a pixel inward and outward along their normals. Intersect to
  1829. // find new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
  1830. // new antialiased mesh from those vertices.
  1831. void stroke_boundary(EdgeList* boundary, VertexList* innerMesh, VertexList* outerMesh,
  1832. Comparator& c, SkArenaAlloc& alloc) {
  1833. LOG("\nstroking boundary\n");
  1834. // A boundary with fewer than 3 edges is degenerate.
  1835. if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) {
  1836. return;
  1837. }
  1838. Edge* prevEdge = boundary->fTail;
  1839. Vertex* prevV = prevEdge->fWinding > 0 ? prevEdge->fTop : prevEdge->fBottom;
  1840. SkVector prevNormal;
  1841. get_edge_normal(prevEdge, &prevNormal);
  1842. double radius = 0.5;
  1843. Line prevInner(prevEdge->fLine);
  1844. prevInner.fC -= radius;
  1845. Line prevOuter(prevEdge->fLine);
  1846. prevOuter.fC += radius;
  1847. VertexList innerVertices;
  1848. VertexList outerVertices;
  1849. bool innerInversion = true;
  1850. bool outerInversion = true;
  1851. for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
  1852. Vertex* v = e->fWinding > 0 ? e->fTop : e->fBottom;
  1853. SkVector normal;
  1854. get_edge_normal(e, &normal);
  1855. Line inner(e->fLine);
  1856. inner.fC -= radius;
  1857. Line outer(e->fLine);
  1858. outer.fC += radius;
  1859. SkPoint innerPoint, outerPoint;
  1860. LOG("stroking vertex %g (%g, %g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
  1861. if (!prevEdge->fLine.nearParallel(e->fLine) && prevInner.intersect(inner, &innerPoint) &&
  1862. prevOuter.intersect(outer, &outerPoint)) {
  1863. float cosAngle = normal.dot(prevNormal);
  1864. if (cosAngle < -kCosMiterAngle) {
  1865. Vertex* nextV = e->fWinding > 0 ? e->fBottom : e->fTop;
  1866. // This is a pointy vertex whose angle is smaller than the threshold; miter it.
  1867. Line bisector(innerPoint, outerPoint);
  1868. Line tangent(v->fPoint, v->fPoint + SkPoint::Make(bisector.fA, bisector.fB));
  1869. if (tangent.fA == 0 && tangent.fB == 0) {
  1870. continue;
  1871. }
  1872. tangent.normalize();
  1873. Line innerTangent(tangent);
  1874. Line outerTangent(tangent);
  1875. innerTangent.fC -= 0.5;
  1876. outerTangent.fC += 0.5;
  1877. SkPoint innerPoint1, innerPoint2, outerPoint1, outerPoint2;
  1878. if (prevNormal.cross(normal) > 0) {
  1879. // Miter inner points
  1880. if (!innerTangent.intersect(prevInner, &innerPoint1) ||
  1881. !innerTangent.intersect(inner, &innerPoint2) ||
  1882. !outerTangent.intersect(bisector, &outerPoint)) {
  1883. continue;
  1884. }
  1885. Line prevTangent(prevV->fPoint,
  1886. prevV->fPoint + SkVector::Make(prevOuter.fA, prevOuter.fB));
  1887. Line nextTangent(nextV->fPoint,
  1888. nextV->fPoint + SkVector::Make(outer.fA, outer.fB));
  1889. if (prevTangent.dist(outerPoint) > 0) {
  1890. bisector.intersect(prevTangent, &outerPoint);
  1891. }
  1892. if (nextTangent.dist(outerPoint) < 0) {
  1893. bisector.intersect(nextTangent, &outerPoint);
  1894. }
  1895. outerPoint1 = outerPoint2 = outerPoint;
  1896. } else {
  1897. // Miter outer points
  1898. if (!outerTangent.intersect(prevOuter, &outerPoint1) ||
  1899. !outerTangent.intersect(outer, &outerPoint2)) {
  1900. continue;
  1901. }
  1902. Line prevTangent(prevV->fPoint,
  1903. prevV->fPoint + SkVector::Make(prevInner.fA, prevInner.fB));
  1904. Line nextTangent(nextV->fPoint,
  1905. nextV->fPoint + SkVector::Make(inner.fA, inner.fB));
  1906. if (prevTangent.dist(innerPoint) > 0) {
  1907. bisector.intersect(prevTangent, &innerPoint);
  1908. }
  1909. if (nextTangent.dist(innerPoint) < 0) {
  1910. bisector.intersect(nextTangent, &innerPoint);
  1911. }
  1912. innerPoint1 = innerPoint2 = innerPoint;
  1913. }
  1914. if (!innerPoint1.isFinite() || !innerPoint2.isFinite() ||
  1915. !outerPoint1.isFinite() || !outerPoint2.isFinite()) {
  1916. continue;
  1917. }
  1918. LOG("inner (%g, %g), (%g, %g), ",
  1919. innerPoint1.fX, innerPoint1.fY, innerPoint2.fX, innerPoint2.fY);
  1920. LOG("outer (%g, %g), (%g, %g)\n",
  1921. outerPoint1.fX, outerPoint1.fY, outerPoint2.fX, outerPoint2.fY);
  1922. Vertex* innerVertex1 = alloc.make<Vertex>(innerPoint1, 255);
  1923. Vertex* innerVertex2 = alloc.make<Vertex>(innerPoint2, 255);
  1924. Vertex* outerVertex1 = alloc.make<Vertex>(outerPoint1, 0);
  1925. Vertex* outerVertex2 = alloc.make<Vertex>(outerPoint2, 0);
  1926. innerVertex1->fPartner = outerVertex1;
  1927. innerVertex2->fPartner = outerVertex2;
  1928. outerVertex1->fPartner = innerVertex1;
  1929. outerVertex2->fPartner = innerVertex2;
  1930. if (!inversion(innerVertices.fTail, innerVertex1, prevEdge, c)) {
  1931. innerInversion = false;
  1932. }
  1933. if (!inversion(outerVertices.fTail, outerVertex1, prevEdge, c)) {
  1934. outerInversion = false;
  1935. }
  1936. innerVertices.append(innerVertex1);
  1937. innerVertices.append(innerVertex2);
  1938. outerVertices.append(outerVertex1);
  1939. outerVertices.append(outerVertex2);
  1940. } else {
  1941. LOG("inner (%g, %g), ", innerPoint.fX, innerPoint.fY);
  1942. LOG("outer (%g, %g)\n", outerPoint.fX, outerPoint.fY);
  1943. Vertex* innerVertex = alloc.make<Vertex>(innerPoint, 255);
  1944. Vertex* outerVertex = alloc.make<Vertex>(outerPoint, 0);
  1945. innerVertex->fPartner = outerVertex;
  1946. outerVertex->fPartner = innerVertex;
  1947. if (!inversion(innerVertices.fTail, innerVertex, prevEdge, c)) {
  1948. innerInversion = false;
  1949. }
  1950. if (!inversion(outerVertices.fTail, outerVertex, prevEdge, c)) {
  1951. outerInversion = false;
  1952. }
  1953. innerVertices.append(innerVertex);
  1954. outerVertices.append(outerVertex);
  1955. }
  1956. }
  1957. prevInner = inner;
  1958. prevOuter = outer;
  1959. prevV = v;
  1960. prevEdge = e;
  1961. prevNormal = normal;
  1962. }
  1963. if (!inversion(innerVertices.fTail, innerVertices.fHead, prevEdge, c)) {
  1964. innerInversion = false;
  1965. }
  1966. if (!inversion(outerVertices.fTail, outerVertices.fHead, prevEdge, c)) {
  1967. outerInversion = false;
  1968. }
  1969. // Outer edges get 1 winding, and inner edges get -2 winding. This ensures that the interior
  1970. // is always filled (1 + -2 = -1 for normal cases, 1 + 2 = 3 for thin features where the
  1971. // interior inverts).
  1972. // For total inversion cases, the shape has now reversed handedness, so invert the winding
  1973. // so it will be detected during collapse_overlap_regions().
  1974. int innerWinding = innerInversion ? 2 : -2;
  1975. int outerWinding = outerInversion ? -1 : 1;
  1976. for (Vertex* v = innerVertices.fHead; v && v->fNext; v = v->fNext) {
  1977. connect(v, v->fNext, Edge::Type::kInner, c, alloc, innerWinding);
  1978. }
  1979. connect(innerVertices.fTail, innerVertices.fHead, Edge::Type::kInner, c, alloc, innerWinding);
  1980. for (Vertex* v = outerVertices.fHead; v && v->fNext; v = v->fNext) {
  1981. connect(v, v->fNext, Edge::Type::kOuter, c, alloc, outerWinding);
  1982. }
  1983. connect(outerVertices.fTail, outerVertices.fHead, Edge::Type::kOuter, c, alloc, outerWinding);
  1984. innerMesh->append(innerVertices);
  1985. outerMesh->append(outerVertices);
  1986. }
  1987. void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, SkArenaAlloc& alloc) {
  1988. LOG("\nextracting boundary\n");
  1989. bool down = apply_fill_type(fillType, e->fWinding);
  1990. Vertex* start = down ? e->fTop : e->fBottom;
  1991. do {
  1992. e->fWinding = down ? 1 : -1;
  1993. Edge* next;
  1994. e->fLine.normalize();
  1995. e->fLine = e->fLine * e->fWinding;
  1996. boundary->append(e);
  1997. if (down) {
  1998. // Find outgoing edge, in clockwise order.
  1999. if ((next = e->fNextEdgeAbove)) {
  2000. down = false;
  2001. } else if ((next = e->fBottom->fLastEdgeBelow)) {
  2002. down = true;
  2003. } else if ((next = e->fPrevEdgeAbove)) {
  2004. down = false;
  2005. }
  2006. } else {
  2007. // Find outgoing edge, in counter-clockwise order.
  2008. if ((next = e->fPrevEdgeBelow)) {
  2009. down = true;
  2010. } else if ((next = e->fTop->fFirstEdgeAbove)) {
  2011. down = false;
  2012. } else if ((next = e->fNextEdgeBelow)) {
  2013. down = true;
  2014. }
  2015. }
  2016. disconnect(e);
  2017. e = next;
  2018. } while (e && (down ? e->fTop : e->fBottom) != start);
  2019. }
  2020. // Stage 5b: Extract boundaries from mesh, simplify and stroke them into a new mesh.
  2021. void extract_boundaries(const VertexList& inMesh, VertexList* innerVertices,
  2022. VertexList* outerVertices, SkPath::FillType fillType,
  2023. Comparator& c, SkArenaAlloc& alloc) {
  2024. remove_non_boundary_edges(inMesh, fillType, alloc);
  2025. for (Vertex* v = inMesh.fHead; v; v = v->fNext) {
  2026. while (v->fFirstEdgeBelow) {
  2027. EdgeList boundary;
  2028. extract_boundary(&boundary, v->fFirstEdgeBelow, fillType, alloc);
  2029. simplify_boundary(&boundary, c, alloc);
  2030. stroke_boundary(&boundary, innerVertices, outerVertices, c, alloc);
  2031. }
  2032. }
  2033. }
  2034. // This is a driver function that calls stages 2-5 in turn.
  2035. void contours_to_mesh(VertexList* contours, int contourCnt, bool antialias,
  2036. VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
  2037. #if LOGGING_ENABLED
  2038. for (int i = 0; i < contourCnt; ++i) {
  2039. Vertex* v = contours[i].fHead;
  2040. SkASSERT(v);
  2041. LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
  2042. for (v = v->fNext; v; v = v->fNext) {
  2043. LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
  2044. }
  2045. }
  2046. #endif
  2047. sanitize_contours(contours, contourCnt, antialias);
  2048. build_edges(contours, contourCnt, mesh, c, alloc);
  2049. }
  2050. void sort_mesh(VertexList* vertices, Comparator& c, SkArenaAlloc& alloc) {
  2051. if (!vertices || !vertices->fHead) {
  2052. return;
  2053. }
  2054. // Sort vertices in Y (secondarily in X).
  2055. if (c.fDirection == Comparator::Direction::kHorizontal) {
  2056. merge_sort<sweep_lt_horiz>(vertices);
  2057. } else {
  2058. merge_sort<sweep_lt_vert>(vertices);
  2059. }
  2060. #if LOGGING_ENABLED
  2061. for (Vertex* v = vertices->fHead; v != nullptr; v = v->fNext) {
  2062. static float gID = 0.0f;
  2063. v->fID = gID++;
  2064. }
  2065. #endif
  2066. }
  2067. Poly* contours_to_polys(VertexList* contours, int contourCnt, SkPath::FillType fillType,
  2068. const SkRect& pathBounds, bool antialias, VertexList* outerMesh,
  2069. SkArenaAlloc& alloc) {
  2070. Comparator c(pathBounds.width() > pathBounds.height() ? Comparator::Direction::kHorizontal
  2071. : Comparator::Direction::kVertical);
  2072. VertexList mesh;
  2073. contours_to_mesh(contours, contourCnt, antialias, &mesh, c, alloc);
  2074. sort_mesh(&mesh, c, alloc);
  2075. merge_coincident_vertices(&mesh, c, alloc);
  2076. simplify(&mesh, c, alloc);
  2077. LOG("\nsimplified mesh:\n");
  2078. dump_mesh(mesh);
  2079. if (antialias) {
  2080. VertexList innerMesh;
  2081. extract_boundaries(mesh, &innerMesh, outerMesh, fillType, c, alloc);
  2082. sort_mesh(&innerMesh, c, alloc);
  2083. sort_mesh(outerMesh, c, alloc);
  2084. merge_coincident_vertices(&innerMesh, c, alloc);
  2085. bool was_complex = merge_coincident_vertices(outerMesh, c, alloc);
  2086. was_complex = simplify(&innerMesh, c, alloc) || was_complex;
  2087. was_complex = simplify(outerMesh, c, alloc) || was_complex;
  2088. LOG("\ninner mesh before:\n");
  2089. dump_mesh(innerMesh);
  2090. LOG("\nouter mesh before:\n");
  2091. dump_mesh(*outerMesh);
  2092. EventComparator eventLT(EventComparator::Op::kLessThan);
  2093. EventComparator eventGT(EventComparator::Op::kGreaterThan);
  2094. was_complex = collapse_overlap_regions(&innerMesh, c, alloc, eventLT) || was_complex;
  2095. was_complex = collapse_overlap_regions(outerMesh, c, alloc, eventGT) || was_complex;
  2096. if (was_complex) {
  2097. LOG("found complex mesh; taking slow path\n");
  2098. VertexList aaMesh;
  2099. LOG("\ninner mesh after:\n");
  2100. dump_mesh(innerMesh);
  2101. LOG("\nouter mesh after:\n");
  2102. dump_mesh(*outerMesh);
  2103. connect_partners(outerMesh, c, alloc);
  2104. connect_partners(&innerMesh, c, alloc);
  2105. sorted_merge(&innerMesh, outerMesh, &aaMesh, c);
  2106. merge_coincident_vertices(&aaMesh, c, alloc);
  2107. simplify(&aaMesh, c, alloc);
  2108. LOG("combined and simplified mesh:\n");
  2109. dump_mesh(aaMesh);
  2110. outerMesh->fHead = outerMesh->fTail = nullptr;
  2111. return tessellate(aaMesh, alloc);
  2112. } else {
  2113. LOG("no complex polygons; taking fast path\n");
  2114. return tessellate(innerMesh, alloc);
  2115. }
  2116. } else {
  2117. return tessellate(mesh, alloc);
  2118. }
  2119. }
  2120. // Stage 6: Triangulate the monotone polygons into a vertex buffer.
  2121. void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, bool emitCoverage, void* data) {
  2122. for (Poly* poly = polys; poly; poly = poly->fNext) {
  2123. if (apply_fill_type(fillType, poly)) {
  2124. data = poly->emit(emitCoverage, data);
  2125. }
  2126. }
  2127. return data;
  2128. }
  2129. Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
  2130. int contourCnt, SkArenaAlloc& alloc, bool antialias, bool* isLinear,
  2131. VertexList* outerMesh) {
  2132. SkPath::FillType fillType = path.getFillType();
  2133. if (SkPath::IsInverseFillType(fillType)) {
  2134. contourCnt++;
  2135. }
  2136. std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]);
  2137. path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinear);
  2138. return contours_to_polys(contours.get(), contourCnt, path.getFillType(), path.getBounds(),
  2139. antialias, outerMesh, alloc);
  2140. }
  2141. int get_contour_count(const SkPath& path, SkScalar tolerance) {
  2142. int contourCnt;
  2143. int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tolerance);
  2144. if (maxPts <= 0) {
  2145. return 0;
  2146. }
  2147. return contourCnt;
  2148. }
  2149. int64_t count_points(Poly* polys, SkPath::FillType fillType) {
  2150. int64_t count = 0;
  2151. for (Poly* poly = polys; poly; poly = poly->fNext) {
  2152. if (apply_fill_type(fillType, poly) && poly->fCount >= 3) {
  2153. count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3);
  2154. }
  2155. }
  2156. return count;
  2157. }
  2158. int64_t count_outer_mesh_points(const VertexList& outerMesh) {
  2159. int64_t count = 0;
  2160. for (Vertex* v = outerMesh.fHead; v; v = v->fNext) {
  2161. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  2162. count += TESSELLATOR_WIREFRAME ? 12 : 6;
  2163. }
  2164. }
  2165. return count;
  2166. }
  2167. void* outer_mesh_to_triangles(const VertexList& outerMesh, bool emitCoverage, void* data) {
  2168. for (Vertex* v = outerMesh.fHead; v; v = v->fNext) {
  2169. for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
  2170. Vertex* v0 = e->fTop;
  2171. Vertex* v1 = e->fBottom;
  2172. Vertex* v2 = e->fBottom->fPartner;
  2173. Vertex* v3 = e->fTop->fPartner;
  2174. data = emit_triangle(v0, v1, v2, emitCoverage, data);
  2175. data = emit_triangle(v0, v2, v3, emitCoverage, data);
  2176. }
  2177. }
  2178. return data;
  2179. }
  2180. } // namespace
  2181. namespace GrTessellator {
  2182. // Stage 6: Triangulate the monotone polygons into a vertex buffer.
  2183. int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
  2184. VertexAllocator* vertexAllocator, bool antialias, bool* isLinear) {
  2185. int contourCnt = get_contour_count(path, tolerance);
  2186. if (contourCnt <= 0) {
  2187. *isLinear = true;
  2188. return 0;
  2189. }
  2190. SkArenaAlloc alloc(kArenaChunkSize);
  2191. VertexList outerMesh;
  2192. Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, antialias,
  2193. isLinear, &outerMesh);
  2194. SkPath::FillType fillType = antialias ? SkPath::kWinding_FillType : path.getFillType();
  2195. int64_t count64 = count_points(polys, fillType);
  2196. if (antialias) {
  2197. count64 += count_outer_mesh_points(outerMesh);
  2198. }
  2199. if (0 == count64 || count64 > SK_MaxS32) {
  2200. return 0;
  2201. }
  2202. int count = count64;
  2203. void* verts = vertexAllocator->lock(count);
  2204. if (!verts) {
  2205. SkDebugf("Could not allocate vertices\n");
  2206. return 0;
  2207. }
  2208. LOG("emitting %d verts\n", count);
  2209. void* end = polys_to_triangles(polys, fillType, antialias, verts);
  2210. end = outer_mesh_to_triangles(outerMesh, true, end);
  2211. int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts))
  2212. / vertexAllocator->stride());
  2213. SkASSERT(actualCount <= count);
  2214. vertexAllocator->unlock(actualCount);
  2215. return actualCount;
  2216. }
  2217. int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
  2218. GrTessellator::WindingVertex** verts) {
  2219. int contourCnt = get_contour_count(path, tolerance);
  2220. if (contourCnt <= 0) {
  2221. *verts = nullptr;
  2222. return 0;
  2223. }
  2224. SkArenaAlloc alloc(kArenaChunkSize);
  2225. bool isLinear;
  2226. Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, false, &isLinear,
  2227. nullptr);
  2228. SkPath::FillType fillType = path.getFillType();
  2229. int64_t count64 = count_points(polys, fillType);
  2230. if (0 == count64 || count64 > SK_MaxS32) {
  2231. *verts = nullptr;
  2232. return 0;
  2233. }
  2234. int count = count64;
  2235. *verts = new GrTessellator::WindingVertex[count];
  2236. GrTessellator::WindingVertex* vertsEnd = *verts;
  2237. SkPoint* points = new SkPoint[count];
  2238. SkPoint* pointsEnd = points;
  2239. for (Poly* poly = polys; poly; poly = poly->fNext) {
  2240. if (apply_fill_type(fillType, poly)) {
  2241. SkPoint* start = pointsEnd;
  2242. pointsEnd = static_cast<SkPoint*>(poly->emit(false, pointsEnd));
  2243. while (start != pointsEnd) {
  2244. vertsEnd->fPos = *start;
  2245. vertsEnd->fWinding = poly->fWinding;
  2246. ++start;
  2247. ++vertsEnd;
  2248. }
  2249. }
  2250. }
  2251. int actualCount = static_cast<int>(vertsEnd - *verts);
  2252. SkASSERT(actualCount <= count);
  2253. SkASSERT(pointsEnd - points == actualCount);
  2254. delete[] points;
  2255. return actualCount;
  2256. }
  2257. } // namespace