SkPolyUtils.cpp 65 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838
  1. /*
  2. * Copyright 2017 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/utils/SkPolyUtils.h"
  8. #include <limits>
  9. #include "include/private/SkNx.h"
  10. #include "include/private/SkTArray.h"
  11. #include "include/private/SkTemplates.h"
  12. #include "src/core/SkPointPriv.h"
  13. #include "src/core/SkTDPQueue.h"
  14. #include "src/core/SkTInternalLList.h"
  15. //////////////////////////////////////////////////////////////////////////////////
  16. // Helper data structures and functions
  17. struct OffsetSegment {
  18. SkPoint fP0;
  19. SkVector fV;
  20. };
  21. constexpr SkScalar kCrossTolerance = SK_ScalarNearlyZero * SK_ScalarNearlyZero;
  22. // Computes perpDot for point p compared to segment defined by origin p0 and vector v.
  23. // A positive value means the point is to the left of the segment,
  24. // negative is to the right, 0 is collinear.
  25. static int compute_side(const SkPoint& p0, const SkVector& v, const SkPoint& p) {
  26. SkVector w = p - p0;
  27. SkScalar perpDot = v.cross(w);
  28. if (!SkScalarNearlyZero(perpDot, kCrossTolerance)) {
  29. return ((perpDot > 0) ? 1 : -1);
  30. }
  31. return 0;
  32. }
  33. // Returns 1 for cw, -1 for ccw and 0 if zero signed area (either degenerate or self-intersecting)
  34. int SkGetPolygonWinding(const SkPoint* polygonVerts, int polygonSize) {
  35. if (polygonSize < 3) {
  36. return 0;
  37. }
  38. // compute area and use sign to determine winding
  39. SkScalar quadArea = 0;
  40. SkVector v0 = polygonVerts[1] - polygonVerts[0];
  41. for (int curr = 2; curr < polygonSize; ++curr) {
  42. SkVector v1 = polygonVerts[curr] - polygonVerts[0];
  43. quadArea += v0.cross(v1);
  44. v0 = v1;
  45. }
  46. if (SkScalarNearlyZero(quadArea, kCrossTolerance)) {
  47. return 0;
  48. }
  49. // 1 == ccw, -1 == cw
  50. return (quadArea > 0) ? 1 : -1;
  51. }
  52. // Compute difference vector to offset p0-p1 'offset' units in direction specified by 'side'
  53. bool compute_offset_vector(const SkPoint& p0, const SkPoint& p1, SkScalar offset, int side,
  54. SkPoint* vector) {
  55. SkASSERT(side == -1 || side == 1);
  56. // if distances are equal, can just outset by the perpendicular
  57. SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX);
  58. if (!perp.setLength(offset*side)) {
  59. return false;
  60. }
  61. *vector = perp;
  62. return true;
  63. }
  64. // check interval to see if intersection is in segment
  65. static inline bool outside_interval(SkScalar numer, SkScalar denom, bool denomPositive) {
  66. return (denomPositive && (numer < 0 || numer > denom)) ||
  67. (!denomPositive && (numer > 0 || numer < denom));
  68. }
  69. // Compute the intersection 'p' between segments s0 and s1, if any.
  70. // 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'.
  71. // Returns false if there is no intersection.
  72. static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s1,
  73. SkPoint* p, SkScalar* s, SkScalar* t) {
  74. const SkVector& v0 = s0.fV;
  75. const SkVector& v1 = s1.fV;
  76. SkVector w = s1.fP0 - s0.fP0;
  77. SkScalar denom = v0.cross(v1);
  78. bool denomPositive = (denom > 0);
  79. SkScalar sNumer, tNumer;
  80. if (SkScalarNearlyZero(denom, kCrossTolerance)) {
  81. // segments are parallel, but not collinear
  82. if (!SkScalarNearlyZero(w.cross(v0), kCrossTolerance) ||
  83. !SkScalarNearlyZero(w.cross(v1), kCrossTolerance)) {
  84. return false;
  85. }
  86. // Check for zero-length segments
  87. if (!SkPointPriv::CanNormalize(v0.fX, v0.fY)) {
  88. // Both are zero-length
  89. if (!SkPointPriv::CanNormalize(v1.fX, v1.fY)) {
  90. // Check if they're the same point
  91. if (!SkPointPriv::CanNormalize(w.fX, w.fY)) {
  92. *p = s0.fP0;
  93. *s = 0;
  94. *t = 0;
  95. return true;
  96. } else {
  97. return false;
  98. }
  99. }
  100. // Otherwise project segment0's origin onto segment1
  101. tNumer = v1.dot(-w);
  102. denom = v1.dot(v1);
  103. if (outside_interval(tNumer, denom, true)) {
  104. return false;
  105. }
  106. sNumer = 0;
  107. } else {
  108. // Project segment1's endpoints onto segment0
  109. sNumer = v0.dot(w);
  110. denom = v0.dot(v0);
  111. tNumer = 0;
  112. if (outside_interval(sNumer, denom, true)) {
  113. // The first endpoint doesn't lie on segment0
  114. // If segment1 is degenerate, then there's no collision
  115. if (!SkPointPriv::CanNormalize(v1.fX, v1.fY)) {
  116. return false;
  117. }
  118. // Otherwise try the other one
  119. SkScalar oldSNumer = sNumer;
  120. sNumer = v0.dot(w + v1);
  121. tNumer = denom;
  122. if (outside_interval(sNumer, denom, true)) {
  123. // it's possible that segment1's interval surrounds segment0
  124. // this is false if params have the same signs, and in that case no collision
  125. if (sNumer*oldSNumer > 0) {
  126. return false;
  127. }
  128. // otherwise project segment0's endpoint onto segment1 instead
  129. sNumer = 0;
  130. tNumer = v1.dot(-w);
  131. denom = v1.dot(v1);
  132. }
  133. }
  134. }
  135. } else {
  136. sNumer = w.cross(v1);
  137. if (outside_interval(sNumer, denom, denomPositive)) {
  138. return false;
  139. }
  140. tNumer = w.cross(v0);
  141. if (outside_interval(tNumer, denom, denomPositive)) {
  142. return false;
  143. }
  144. }
  145. SkScalar localS = sNumer/denom;
  146. SkScalar localT = tNumer/denom;
  147. *p = s0.fP0 + v0*localS;
  148. *s = localS;
  149. *t = localT;
  150. return true;
  151. }
  152. bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) {
  153. if (polygonSize < 3) {
  154. return false;
  155. }
  156. SkScalar lastArea = 0;
  157. SkScalar lastPerpDot = 0;
  158. int prevIndex = polygonSize - 1;
  159. int currIndex = 0;
  160. int nextIndex = 1;
  161. SkPoint origin = polygonVerts[0];
  162. SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex];
  163. SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
  164. SkVector w0 = polygonVerts[currIndex] - origin;
  165. SkVector w1 = polygonVerts[nextIndex] - origin;
  166. for (int i = 0; i < polygonSize; ++i) {
  167. if (!polygonVerts[i].isFinite()) {
  168. return false;
  169. }
  170. // Check that winding direction is always the same (otherwise we have a reflex vertex)
  171. SkScalar perpDot = v0.cross(v1);
  172. if (lastPerpDot*perpDot < 0) {
  173. return false;
  174. }
  175. if (0 != perpDot) {
  176. lastPerpDot = perpDot;
  177. }
  178. // If the signed area ever flips it's concave
  179. // TODO: see if we can verify convexity only with signed area
  180. SkScalar quadArea = w0.cross(w1);
  181. if (quadArea*lastArea < 0) {
  182. return false;
  183. }
  184. if (0 != quadArea) {
  185. lastArea = quadArea;
  186. }
  187. prevIndex = currIndex;
  188. currIndex = nextIndex;
  189. nextIndex = (currIndex + 1) % polygonSize;
  190. v0 = v1;
  191. v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
  192. w0 = w1;
  193. w1 = polygonVerts[nextIndex] - origin;
  194. }
  195. return true;
  196. }
  197. struct OffsetEdge {
  198. OffsetEdge* fPrev;
  199. OffsetEdge* fNext;
  200. OffsetSegment fOffset;
  201. SkPoint fIntersection;
  202. SkScalar fTValue;
  203. uint16_t fIndex;
  204. uint16_t fEnd;
  205. void init(uint16_t start = 0, uint16_t end = 0) {
  206. fIntersection = fOffset.fP0;
  207. fTValue = SK_ScalarMin;
  208. fIndex = start;
  209. fEnd = end;
  210. }
  211. // special intersection check that looks for endpoint intersection
  212. bool checkIntersection(const OffsetEdge* that,
  213. SkPoint* p, SkScalar* s, SkScalar* t) {
  214. if (this->fEnd == that->fIndex) {
  215. SkPoint p1 = this->fOffset.fP0 + this->fOffset.fV;
  216. if (SkPointPriv::EqualsWithinTolerance(p1, that->fOffset.fP0)) {
  217. *p = p1;
  218. *s = SK_Scalar1;
  219. *t = 0;
  220. return true;
  221. }
  222. }
  223. return compute_intersection(this->fOffset, that->fOffset, p, s, t);
  224. }
  225. // computes the line intersection and then the "distance" from that to this
  226. // this is really a signed squared distance, where negative means that
  227. // the intersection lies inside this->fOffset
  228. SkScalar computeCrossingDistance(const OffsetEdge* that) {
  229. const OffsetSegment& s0 = this->fOffset;
  230. const OffsetSegment& s1 = that->fOffset;
  231. const SkVector& v0 = s0.fV;
  232. const SkVector& v1 = s1.fV;
  233. SkScalar denom = v0.cross(v1);
  234. if (SkScalarNearlyZero(denom, kCrossTolerance)) {
  235. // segments are parallel
  236. return SK_ScalarMax;
  237. }
  238. SkVector w = s1.fP0 - s0.fP0;
  239. SkScalar localS = w.cross(v1) / denom;
  240. if (localS < 0) {
  241. localS = -localS;
  242. } else {
  243. localS -= SK_Scalar1;
  244. }
  245. localS *= SkScalarAbs(localS);
  246. localS *= v0.dot(v0);
  247. return localS;
  248. }
  249. };
  250. static void remove_node(const OffsetEdge* node, OffsetEdge** head) {
  251. // remove from linked list
  252. node->fPrev->fNext = node->fNext;
  253. node->fNext->fPrev = node->fPrev;
  254. if (node == *head) {
  255. *head = (node->fNext == node) ? nullptr : node->fNext;
  256. }
  257. }
  258. //////////////////////////////////////////////////////////////////////////////////
  259. // The objective here is to inset all of the edges by the given distance, and then
  260. // remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
  261. // we should only be making left-hand turns (for cw polygons, we use the winding
  262. // parameter to reverse this). We detect this by checking whether the second intersection
  263. // on an edge is closer to its tail than the first one.
  264. //
  265. // We might also have the case that there is no intersection between two neighboring inset edges.
  266. // In this case, one edge will lie to the right of the other and should be discarded along with
  267. // its previous intersection (if any).
  268. //
  269. // Note: the assumption is that inputPolygon is convex and has no coincident points.
  270. //
  271. bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
  272. SkScalar inset, SkTDArray<SkPoint>* insetPolygon) {
  273. if (inputPolygonSize < 3) {
  274. return false;
  275. }
  276. // restrict this to match other routines
  277. // practically we don't want anything bigger than this anyway
  278. if (inputPolygonSize > std::numeric_limits<uint16_t>::max()) {
  279. return false;
  280. }
  281. // can't inset by a negative or non-finite amount
  282. if (inset < -SK_ScalarNearlyZero || !SkScalarIsFinite(inset)) {
  283. return false;
  284. }
  285. // insetting close to zero just returns the original poly
  286. if (inset <= SK_ScalarNearlyZero) {
  287. for (int i = 0; i < inputPolygonSize; ++i) {
  288. *insetPolygon->push() = inputPolygonVerts[i];
  289. }
  290. return true;
  291. }
  292. // get winding direction
  293. int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
  294. if (0 == winding) {
  295. return false;
  296. }
  297. // set up
  298. SkAutoSTMalloc<64, OffsetEdge> edgeData(inputPolygonSize);
  299. int prev = inputPolygonSize - 1;
  300. for (int curr = 0; curr < inputPolygonSize; prev = curr, ++curr) {
  301. int next = (curr + 1) % inputPolygonSize;
  302. if (!inputPolygonVerts[curr].isFinite()) {
  303. return false;
  304. }
  305. // check for convexity just to be sure
  306. if (compute_side(inputPolygonVerts[prev], inputPolygonVerts[curr] - inputPolygonVerts[prev],
  307. inputPolygonVerts[next])*winding < 0) {
  308. return false;
  309. }
  310. SkVector v = inputPolygonVerts[next] - inputPolygonVerts[curr];
  311. SkVector perp = SkVector::Make(-v.fY, v.fX);
  312. perp.setLength(inset*winding);
  313. edgeData[curr].fPrev = &edgeData[prev];
  314. edgeData[curr].fNext = &edgeData[next];
  315. edgeData[curr].fOffset.fP0 = inputPolygonVerts[curr] + perp;
  316. edgeData[curr].fOffset.fV = v;
  317. edgeData[curr].init();
  318. }
  319. OffsetEdge* head = &edgeData[0];
  320. OffsetEdge* currEdge = head;
  321. OffsetEdge* prevEdge = currEdge->fPrev;
  322. int insetVertexCount = inputPolygonSize;
  323. unsigned int iterations = 0;
  324. unsigned int maxIterations = inputPolygonSize * inputPolygonSize;
  325. while (head && prevEdge != currEdge) {
  326. ++iterations;
  327. // we should check each edge against each other edge at most once
  328. if (iterations > maxIterations) {
  329. return false;
  330. }
  331. SkScalar s, t;
  332. SkPoint intersection;
  333. if (compute_intersection(prevEdge->fOffset, currEdge->fOffset,
  334. &intersection, &s, &t)) {
  335. // if new intersection is further back on previous inset from the prior intersection
  336. if (s < prevEdge->fTValue) {
  337. // no point in considering this one again
  338. remove_node(prevEdge, &head);
  339. --insetVertexCount;
  340. // go back one segment
  341. prevEdge = prevEdge->fPrev;
  342. // we've already considered this intersection, we're done
  343. } else if (currEdge->fTValue > SK_ScalarMin &&
  344. SkPointPriv::EqualsWithinTolerance(intersection,
  345. currEdge->fIntersection,
  346. 1.0e-6f)) {
  347. break;
  348. } else {
  349. // add intersection
  350. currEdge->fIntersection = intersection;
  351. currEdge->fTValue = t;
  352. // go to next segment
  353. prevEdge = currEdge;
  354. currEdge = currEdge->fNext;
  355. }
  356. } else {
  357. // if prev to right side of curr
  358. int side = winding*compute_side(currEdge->fOffset.fP0,
  359. currEdge->fOffset.fV,
  360. prevEdge->fOffset.fP0);
  361. if (side < 0 &&
  362. side == winding*compute_side(currEdge->fOffset.fP0,
  363. currEdge->fOffset.fV,
  364. prevEdge->fOffset.fP0 + prevEdge->fOffset.fV)) {
  365. // no point in considering this one again
  366. remove_node(prevEdge, &head);
  367. --insetVertexCount;
  368. // go back one segment
  369. prevEdge = prevEdge->fPrev;
  370. } else {
  371. // move to next segment
  372. remove_node(currEdge, &head);
  373. --insetVertexCount;
  374. currEdge = currEdge->fNext;
  375. }
  376. }
  377. }
  378. // store all the valid intersections that aren't nearly coincident
  379. // TODO: look at the main algorithm and see if we can detect these better
  380. insetPolygon->reset();
  381. if (!head) {
  382. return false;
  383. }
  384. static constexpr SkScalar kCleanupTolerance = 0.01f;
  385. if (insetVertexCount >= 0) {
  386. insetPolygon->setReserve(insetVertexCount);
  387. }
  388. int currIndex = 0;
  389. *insetPolygon->push() = head->fIntersection;
  390. currEdge = head->fNext;
  391. while (currEdge != head) {
  392. if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
  393. (*insetPolygon)[currIndex],
  394. kCleanupTolerance)) {
  395. *insetPolygon->push() = currEdge->fIntersection;
  396. currIndex++;
  397. }
  398. currEdge = currEdge->fNext;
  399. }
  400. // make sure the first and last points aren't coincident
  401. if (currIndex >= 1 &&
  402. SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex],
  403. kCleanupTolerance)) {
  404. insetPolygon->pop();
  405. }
  406. return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->count());
  407. }
  408. ///////////////////////////////////////////////////////////////////////////////////////////
  409. // compute the number of points needed for a circular join when offsetting a reflex vertex
  410. bool SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar offset,
  411. SkScalar* rotSin, SkScalar* rotCos, int* n) {
  412. const SkScalar kRecipPixelsPerArcSegment = 0.25f;
  413. SkScalar rCos = v1.dot(v2);
  414. if (!SkScalarIsFinite(rCos)) {
  415. return false;
  416. }
  417. SkScalar rSin = v1.cross(v2);
  418. if (!SkScalarIsFinite(rSin)) {
  419. return false;
  420. }
  421. SkScalar theta = SkScalarATan2(rSin, rCos);
  422. SkScalar floatSteps = SkScalarAbs(offset*theta*kRecipPixelsPerArcSegment);
  423. // limit the number of steps to at most max uint16_t (that's all we can index)
  424. // knock one value off the top to account for rounding
  425. if (floatSteps >= std::numeric_limits<uint16_t>::max()) {
  426. return false;
  427. }
  428. int steps = SkScalarRoundToInt(floatSteps);
  429. SkScalar dTheta = steps > 0 ? theta / steps : 0;
  430. *rotSin = SkScalarSin(dTheta);
  431. *rotCos = SkScalarCos(dTheta);
  432. *n = steps;
  433. return true;
  434. }
  435. ///////////////////////////////////////////////////////////////////////////////////////////
  436. // a point is "left" to another if its x-coord is less, or if equal, its y-coord is greater
  437. static bool left(const SkPoint& p0, const SkPoint& p1) {
  438. return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY > p1.fY);
  439. }
  440. // a point is "right" to another if its x-coord is greater, or if equal, its y-coord is less
  441. static bool right(const SkPoint& p0, const SkPoint& p1) {
  442. return p0.fX > p1.fX || (!(p0.fX < p1.fX) && p0.fY < p1.fY);
  443. }
  444. struct Vertex {
  445. static bool Left(const Vertex& qv0, const Vertex& qv1) {
  446. return left(qv0.fPosition, qv1.fPosition);
  447. }
  448. // packed to fit into 16 bytes (one cache line)
  449. SkPoint fPosition;
  450. uint16_t fIndex; // index in unsorted polygon
  451. uint16_t fPrevIndex; // indices for previous and next vertex in unsorted polygon
  452. uint16_t fNextIndex;
  453. uint16_t fFlags;
  454. };
  455. enum VertexFlags {
  456. kPrevLeft_VertexFlag = 0x1,
  457. kNextLeft_VertexFlag = 0x2,
  458. };
  459. struct ActiveEdge {
  460. ActiveEdge() : fChild{ nullptr, nullptr }, fAbove(nullptr), fBelow(nullptr), fRed(false) {}
  461. ActiveEdge(const SkPoint& p0, const SkVector& v, uint16_t index0, uint16_t index1)
  462. : fSegment({ p0, v })
  463. , fIndex0(index0)
  464. , fIndex1(index1)
  465. , fAbove(nullptr)
  466. , fBelow(nullptr)
  467. , fRed(true) {
  468. fChild[0] = nullptr;
  469. fChild[1] = nullptr;
  470. }
  471. // Returns true if "this" is above "that", assuming this->p0 is to the left of that->p0
  472. // This is only used to verify the edgelist -- the actual test for insertion/deletion is much
  473. // simpler because we can make certain assumptions then.
  474. bool aboveIfLeft(const ActiveEdge* that) const {
  475. const SkPoint& p0 = this->fSegment.fP0;
  476. const SkPoint& q0 = that->fSegment.fP0;
  477. SkASSERT(p0.fX <= q0.fX);
  478. SkVector d = q0 - p0;
  479. const SkVector& v = this->fSegment.fV;
  480. const SkVector& w = that->fSegment.fV;
  481. // The idea here is that if the vector between the origins of the two segments (d)
  482. // rotates counterclockwise up to the vector representing the "this" segment (v),
  483. // then we know that "this" is above "that". If the result is clockwise we say it's below.
  484. if (this->fIndex0 != that->fIndex0) {
  485. SkScalar cross = d.cross(v);
  486. if (cross > kCrossTolerance) {
  487. return true;
  488. } else if (cross < -kCrossTolerance) {
  489. return false;
  490. }
  491. } else if (this->fIndex1 == that->fIndex1) {
  492. return false;
  493. }
  494. // At this point either the two origins are nearly equal or the origin of "that"
  495. // lies on dv. So then we try the same for the vector from the tail of "this"
  496. // to the head of "that". Again, ccw means "this" is above "that".
  497. // d = that.P1 - this.P0
  498. // = that.fP0 + that.fV - this.fP0
  499. // = that.fP0 - this.fP0 + that.fV
  500. // = old_d + that.fV
  501. d += w;
  502. SkScalar cross = d.cross(v);
  503. if (cross > kCrossTolerance) {
  504. return true;
  505. } else if (cross < -kCrossTolerance) {
  506. return false;
  507. }
  508. // If the previous check fails, the two segments are nearly collinear
  509. // First check y-coord of first endpoints
  510. if (p0.fX < q0.fX) {
  511. return (p0.fY >= q0.fY);
  512. } else if (p0.fY > q0.fY) {
  513. return true;
  514. } else if (p0.fY < q0.fY) {
  515. return false;
  516. }
  517. // The first endpoints are the same, so check the other endpoint
  518. SkPoint p1 = p0 + v;
  519. SkPoint q1 = q0 + w;
  520. if (p1.fX < q1.fX) {
  521. return (p1.fY >= q1.fY);
  522. } else {
  523. return (p1.fY > q1.fY);
  524. }
  525. }
  526. // same as leftAndAbove(), but generalized
  527. bool above(const ActiveEdge* that) const {
  528. const SkPoint& p0 = this->fSegment.fP0;
  529. const SkPoint& q0 = that->fSegment.fP0;
  530. if (right(p0, q0)) {
  531. return !that->aboveIfLeft(this);
  532. } else {
  533. return this->aboveIfLeft(that);
  534. }
  535. }
  536. bool intersect(const SkPoint& q0, const SkVector& w, uint16_t index0, uint16_t index1) const {
  537. // check first to see if these edges are neighbors in the polygon
  538. if (this->fIndex0 == index0 || this->fIndex1 == index0 ||
  539. this->fIndex0 == index1 || this->fIndex1 == index1) {
  540. return false;
  541. }
  542. // We don't need the exact intersection point so we can do a simpler test here.
  543. const SkPoint& p0 = this->fSegment.fP0;
  544. const SkVector& v = this->fSegment.fV;
  545. SkPoint p1 = p0 + v;
  546. SkPoint q1 = q0 + w;
  547. // We assume some x-overlap due to how the edgelist works
  548. // This allows us to simplify our test
  549. // We need some slop here because storing the vector and recomputing the second endpoint
  550. // doesn't necessary give us the original result in floating point.
  551. // TODO: Store vector as double? Store endpoint as well?
  552. SkASSERT(q0.fX <= p1.fX + SK_ScalarNearlyZero);
  553. // if each segment straddles the other (i.e., the endpoints have different sides)
  554. // then they intersect
  555. bool result;
  556. if (p0.fX < q0.fX) {
  557. if (q1.fX < p1.fX) {
  558. result = (compute_side(p0, v, q0)*compute_side(p0, v, q1) < 0);
  559. } else {
  560. result = (compute_side(p0, v, q0)*compute_side(q0, w, p1) > 0);
  561. }
  562. } else {
  563. if (p1.fX < q1.fX) {
  564. result = (compute_side(q0, w, p0)*compute_side(q0, w, p1) < 0);
  565. } else {
  566. result = (compute_side(q0, w, p0)*compute_side(p0, v, q1) > 0);
  567. }
  568. }
  569. return result;
  570. }
  571. bool intersect(const ActiveEdge* edge) {
  572. return this->intersect(edge->fSegment.fP0, edge->fSegment.fV, edge->fIndex0, edge->fIndex1);
  573. }
  574. bool lessThan(const ActiveEdge* that) const {
  575. SkASSERT(!this->above(this));
  576. SkASSERT(!that->above(that));
  577. SkASSERT(!(this->above(that) && that->above(this)));
  578. return this->above(that);
  579. }
  580. bool equals(uint16_t index0, uint16_t index1) const {
  581. return (this->fIndex0 == index0 && this->fIndex1 == index1);
  582. }
  583. OffsetSegment fSegment;
  584. uint16_t fIndex0; // indices for previous and next vertex in polygon
  585. uint16_t fIndex1;
  586. ActiveEdge* fChild[2];
  587. ActiveEdge* fAbove;
  588. ActiveEdge* fBelow;
  589. int32_t fRed;
  590. };
  591. class ActiveEdgeList {
  592. public:
  593. ActiveEdgeList(int maxEdges) {
  594. fAllocation = (char*) sk_malloc_throw(sizeof(ActiveEdge)*maxEdges);
  595. fCurrFree = 0;
  596. fMaxFree = maxEdges;
  597. }
  598. ~ActiveEdgeList() {
  599. fTreeHead.fChild[1] = nullptr;
  600. sk_free(fAllocation);
  601. }
  602. bool insert(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
  603. SkVector v = p1 - p0;
  604. if (!v.isFinite()) {
  605. return false;
  606. }
  607. // empty tree case -- easy
  608. if (!fTreeHead.fChild[1]) {
  609. ActiveEdge* root = fTreeHead.fChild[1] = this->allocate(p0, v, index0, index1);
  610. SkASSERT(root);
  611. if (!root) {
  612. return false;
  613. }
  614. root->fRed = false;
  615. return true;
  616. }
  617. // set up helpers
  618. ActiveEdge* top = &fTreeHead;
  619. ActiveEdge *grandparent = nullptr;
  620. ActiveEdge *parent = nullptr;
  621. ActiveEdge *curr = top->fChild[1];
  622. int dir = 0;
  623. int last = 0; // ?
  624. // predecessor and successor, for intersection check
  625. ActiveEdge* pred = nullptr;
  626. ActiveEdge* succ = nullptr;
  627. // search down the tree
  628. while (true) {
  629. if (!curr) {
  630. // check for intersection with predecessor and successor
  631. if ((pred && pred->intersect(p0, v, index0, index1)) ||
  632. (succ && succ->intersect(p0, v, index0, index1))) {
  633. return false;
  634. }
  635. // insert new node at bottom
  636. parent->fChild[dir] = curr = this->allocate(p0, v, index0, index1);
  637. SkASSERT(curr);
  638. if (!curr) {
  639. return false;
  640. }
  641. curr->fAbove = pred;
  642. curr->fBelow = succ;
  643. if (pred) {
  644. pred->fBelow = curr;
  645. }
  646. if (succ) {
  647. succ->fAbove = curr;
  648. }
  649. if (IsRed(parent)) {
  650. int dir2 = (top->fChild[1] == grandparent);
  651. if (curr == parent->fChild[last]) {
  652. top->fChild[dir2] = SingleRotation(grandparent, !last);
  653. } else {
  654. top->fChild[dir2] = DoubleRotation(grandparent, !last);
  655. }
  656. }
  657. break;
  658. } else if (IsRed(curr->fChild[0]) && IsRed(curr->fChild[1])) {
  659. // color flip
  660. curr->fRed = true;
  661. curr->fChild[0]->fRed = false;
  662. curr->fChild[1]->fRed = false;
  663. if (IsRed(parent)) {
  664. int dir2 = (top->fChild[1] == grandparent);
  665. if (curr == parent->fChild[last]) {
  666. top->fChild[dir2] = SingleRotation(grandparent, !last);
  667. } else {
  668. top->fChild[dir2] = DoubleRotation(grandparent, !last);
  669. }
  670. }
  671. }
  672. last = dir;
  673. int side;
  674. // check to see if segment is above or below
  675. if (curr->fIndex0 == index0) {
  676. side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
  677. } else {
  678. side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
  679. }
  680. if (0 == side) {
  681. return false;
  682. }
  683. dir = (side < 0);
  684. if (0 == dir) {
  685. succ = curr;
  686. } else {
  687. pred = curr;
  688. }
  689. // update helpers
  690. if (grandparent) {
  691. top = grandparent;
  692. }
  693. grandparent = parent;
  694. parent = curr;
  695. curr = curr->fChild[dir];
  696. }
  697. // update root and make it black
  698. fTreeHead.fChild[1]->fRed = false;
  699. SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
  700. return true;
  701. }
  702. // replaces edge p0p1 with p1p2
  703. bool replace(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
  704. uint16_t index0, uint16_t index1, uint16_t index2) {
  705. if (!fTreeHead.fChild[1]) {
  706. return false;
  707. }
  708. SkVector v = p2 - p1;
  709. ActiveEdge* curr = &fTreeHead;
  710. ActiveEdge* found = nullptr;
  711. int dir = 1;
  712. // search
  713. while (curr->fChild[dir] != nullptr) {
  714. // update helpers
  715. curr = curr->fChild[dir];
  716. // save found node
  717. if (curr->equals(index0, index1)) {
  718. found = curr;
  719. break;
  720. } else {
  721. // check to see if segment is above or below
  722. int side;
  723. if (curr->fIndex1 == index1) {
  724. side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
  725. } else {
  726. side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
  727. }
  728. if (0 == side) {
  729. return false;
  730. }
  731. dir = (side < 0);
  732. }
  733. }
  734. if (!found) {
  735. return false;
  736. }
  737. // replace if found
  738. ActiveEdge* pred = found->fAbove;
  739. ActiveEdge* succ = found->fBelow;
  740. // check deletion and insert intersection cases
  741. if (pred && (pred->intersect(found) || pred->intersect(p1, v, index1, index2))) {
  742. return false;
  743. }
  744. if (succ && (succ->intersect(found) || succ->intersect(p1, v, index1, index2))) {
  745. return false;
  746. }
  747. found->fSegment.fP0 = p1;
  748. found->fSegment.fV = v;
  749. found->fIndex0 = index1;
  750. found->fIndex1 = index2;
  751. // above and below should stay the same
  752. SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
  753. return true;
  754. }
  755. bool remove(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
  756. if (!fTreeHead.fChild[1]) {
  757. return false;
  758. }
  759. ActiveEdge* curr = &fTreeHead;
  760. ActiveEdge* parent = nullptr;
  761. ActiveEdge* grandparent = nullptr;
  762. ActiveEdge* found = nullptr;
  763. int dir = 1;
  764. // search and push a red node down
  765. while (curr->fChild[dir] != nullptr) {
  766. int last = dir;
  767. // update helpers
  768. grandparent = parent;
  769. parent = curr;
  770. curr = curr->fChild[dir];
  771. // save found node
  772. if (curr->equals(index0, index1)) {
  773. found = curr;
  774. dir = 0;
  775. } else {
  776. // check to see if segment is above or below
  777. int side;
  778. if (curr->fIndex1 == index1) {
  779. side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
  780. } else {
  781. side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
  782. }
  783. if (0 == side) {
  784. return false;
  785. }
  786. dir = (side < 0);
  787. }
  788. // push the red node down
  789. if (!IsRed(curr) && !IsRed(curr->fChild[dir])) {
  790. if (IsRed(curr->fChild[!dir])) {
  791. parent = parent->fChild[last] = SingleRotation(curr, dir);
  792. } else {
  793. ActiveEdge *s = parent->fChild[!last];
  794. if (s != NULL) {
  795. if (!IsRed(s->fChild[!last]) && !IsRed(s->fChild[last])) {
  796. // color flip
  797. parent->fRed = false;
  798. s->fRed = true;
  799. curr->fRed = true;
  800. } else {
  801. int dir2 = (grandparent->fChild[1] == parent);
  802. if (IsRed(s->fChild[last])) {
  803. grandparent->fChild[dir2] = DoubleRotation(parent, last);
  804. } else if (IsRed(s->fChild[!last])) {
  805. grandparent->fChild[dir2] = SingleRotation(parent, last);
  806. }
  807. // ensure correct coloring
  808. curr->fRed = grandparent->fChild[dir2]->fRed = true;
  809. grandparent->fChild[dir2]->fChild[0]->fRed = false;
  810. grandparent->fChild[dir2]->fChild[1]->fRed = false;
  811. }
  812. }
  813. }
  814. }
  815. }
  816. // replace and remove if found
  817. if (found) {
  818. ActiveEdge* pred = found->fAbove;
  819. ActiveEdge* succ = found->fBelow;
  820. if ((pred && pred->intersect(found)) || (succ && succ->intersect(found))) {
  821. return false;
  822. }
  823. if (found != curr) {
  824. found->fSegment = curr->fSegment;
  825. found->fIndex0 = curr->fIndex0;
  826. found->fIndex1 = curr->fIndex1;
  827. found->fAbove = curr->fAbove;
  828. pred = found->fAbove;
  829. // we don't need to set found->fBelow here
  830. } else {
  831. if (succ) {
  832. succ->fAbove = pred;
  833. }
  834. }
  835. if (pred) {
  836. pred->fBelow = curr->fBelow;
  837. }
  838. parent->fChild[parent->fChild[1] == curr] = curr->fChild[!curr->fChild[0]];
  839. // no need to delete
  840. curr->fAbove = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
  841. curr->fBelow = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
  842. if (fTreeHead.fChild[1]) {
  843. fTreeHead.fChild[1]->fRed = false;
  844. }
  845. }
  846. // update root and make it black
  847. if (fTreeHead.fChild[1]) {
  848. fTreeHead.fChild[1]->fRed = false;
  849. }
  850. SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
  851. return true;
  852. }
  853. private:
  854. // allocator
  855. ActiveEdge * allocate(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
  856. if (fCurrFree >= fMaxFree) {
  857. return nullptr;
  858. }
  859. char* bytes = fAllocation + sizeof(ActiveEdge)*fCurrFree;
  860. ++fCurrFree;
  861. return new(bytes) ActiveEdge(p0, p1, index0, index1);
  862. }
  863. ///////////////////////////////////////////////////////////////////////////////////
  864. // Red-black tree methods
  865. ///////////////////////////////////////////////////////////////////////////////////
  866. static bool IsRed(const ActiveEdge* node) {
  867. return node && node->fRed;
  868. }
  869. static ActiveEdge* SingleRotation(ActiveEdge* node, int dir) {
  870. ActiveEdge* tmp = node->fChild[!dir];
  871. node->fChild[!dir] = tmp->fChild[dir];
  872. tmp->fChild[dir] = node;
  873. node->fRed = true;
  874. tmp->fRed = false;
  875. return tmp;
  876. }
  877. static ActiveEdge* DoubleRotation(ActiveEdge* node, int dir) {
  878. node->fChild[!dir] = SingleRotation(node->fChild[!dir], !dir);
  879. return SingleRotation(node, dir);
  880. }
  881. // returns black link count
  882. static int VerifyTree(const ActiveEdge* tree) {
  883. if (!tree) {
  884. return 1;
  885. }
  886. const ActiveEdge* left = tree->fChild[0];
  887. const ActiveEdge* right = tree->fChild[1];
  888. // no consecutive red links
  889. if (IsRed(tree) && (IsRed(left) || IsRed(right))) {
  890. SkASSERT(false);
  891. return 0;
  892. }
  893. // check secondary links
  894. if (tree->fAbove) {
  895. SkASSERT(tree->fAbove->fBelow == tree);
  896. SkASSERT(tree->fAbove->lessThan(tree));
  897. }
  898. if (tree->fBelow) {
  899. SkASSERT(tree->fBelow->fAbove == tree);
  900. SkASSERT(tree->lessThan(tree->fBelow));
  901. }
  902. // violates binary tree order
  903. if ((left && tree->lessThan(left)) || (right && right->lessThan(tree))) {
  904. SkASSERT(false);
  905. return 0;
  906. }
  907. int leftCount = VerifyTree(left);
  908. int rightCount = VerifyTree(right);
  909. // return black link count
  910. if (leftCount != 0 && rightCount != 0) {
  911. // black height mismatch
  912. if (leftCount != rightCount) {
  913. SkASSERT(false);
  914. return 0;
  915. }
  916. return IsRed(tree) ? leftCount : leftCount + 1;
  917. } else {
  918. return 0;
  919. }
  920. }
  921. ActiveEdge fTreeHead;
  922. char* fAllocation;
  923. int fCurrFree;
  924. int fMaxFree;
  925. };
  926. // Here we implement a sweep line algorithm to determine whether the provided points
  927. // represent a simple polygon, i.e., the polygon is non-self-intersecting.
  928. // We first insert the vertices into a priority queue sorting horizontally from left to right.
  929. // Then as we pop the vertices from the queue we generate events which indicate that an edge
  930. // should be added or removed from an edge list. If any intersections are detected in the edge
  931. // list, then we know the polygon is self-intersecting and hence not simple.
  932. bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
  933. if (polygonSize < 3) {
  934. return false;
  935. }
  936. // If it's convex, it's simple
  937. if (SkIsConvexPolygon(polygon, polygonSize)) {
  938. return true;
  939. }
  940. // practically speaking, it takes too long to process large polygons
  941. if (polygonSize > 2048) {
  942. return false;
  943. }
  944. SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize);
  945. for (int i = 0; i < polygonSize; ++i) {
  946. Vertex newVertex;
  947. if (!polygon[i].isFinite()) {
  948. return false;
  949. }
  950. newVertex.fPosition = polygon[i];
  951. newVertex.fIndex = i;
  952. newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
  953. newVertex.fNextIndex = (i + 1) % polygonSize;
  954. newVertex.fFlags = 0;
  955. if (left(polygon[newVertex.fPrevIndex], polygon[i])) {
  956. newVertex.fFlags |= kPrevLeft_VertexFlag;
  957. }
  958. if (left(polygon[newVertex.fNextIndex], polygon[i])) {
  959. newVertex.fFlags |= kNextLeft_VertexFlag;
  960. }
  961. vertexQueue.insert(newVertex);
  962. }
  963. // pop each vertex from the queue and generate events depending on
  964. // where it lies relative to its neighboring edges
  965. ActiveEdgeList sweepLine(polygonSize);
  966. while (vertexQueue.count() > 0) {
  967. const Vertex& v = vertexQueue.peek();
  968. // both to the right -- insert both
  969. if (v.fFlags == 0) {
  970. if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) {
  971. break;
  972. }
  973. if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) {
  974. break;
  975. }
  976. // both to the left -- remove both
  977. } else if (v.fFlags == (kPrevLeft_VertexFlag | kNextLeft_VertexFlag)) {
  978. if (!sweepLine.remove(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex)) {
  979. break;
  980. }
  981. if (!sweepLine.remove(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex)) {
  982. break;
  983. }
  984. // one to left and right -- replace one with another
  985. } else {
  986. if (v.fFlags & kPrevLeft_VertexFlag) {
  987. if (!sweepLine.replace(polygon[v.fPrevIndex], v.fPosition, polygon[v.fNextIndex],
  988. v.fPrevIndex, v.fIndex, v.fNextIndex)) {
  989. break;
  990. }
  991. } else {
  992. SkASSERT(v.fFlags & kNextLeft_VertexFlag);
  993. if (!sweepLine.replace(polygon[v.fNextIndex], v.fPosition, polygon[v.fPrevIndex],
  994. v.fNextIndex, v.fIndex, v.fPrevIndex)) {
  995. break;
  996. }
  997. }
  998. }
  999. vertexQueue.pop();
  1000. }
  1001. return (vertexQueue.count() == 0);
  1002. }
  1003. ///////////////////////////////////////////////////////////////////////////////////////////
  1004. // helper function for SkOffsetSimplePolygon
  1005. static void setup_offset_edge(OffsetEdge* currEdge,
  1006. const SkPoint& endpoint0, const SkPoint& endpoint1,
  1007. uint16_t startIndex, uint16_t endIndex) {
  1008. currEdge->fOffset.fP0 = endpoint0;
  1009. currEdge->fOffset.fV = endpoint1 - endpoint0;
  1010. currEdge->init(startIndex, endIndex);
  1011. }
  1012. static bool is_reflex_vertex(const SkPoint* inputPolygonVerts, int winding, SkScalar offset,
  1013. uint16_t prevIndex, uint16_t currIndex, uint16_t nextIndex) {
  1014. int side = compute_side(inputPolygonVerts[prevIndex],
  1015. inputPolygonVerts[currIndex] - inputPolygonVerts[prevIndex],
  1016. inputPolygonVerts[nextIndex]);
  1017. // if reflex point, we need to add extra edges
  1018. return (side*winding*offset < 0);
  1019. }
  1020. bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
  1021. const SkRect& bounds, SkScalar offset,
  1022. SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) {
  1023. if (inputPolygonSize < 3) {
  1024. return false;
  1025. }
  1026. // need to be able to represent all the vertices in the 16-bit indices
  1027. if (inputPolygonSize >= std::numeric_limits<uint16_t>::max()) {
  1028. return false;
  1029. }
  1030. if (!SkScalarIsFinite(offset)) {
  1031. return false;
  1032. }
  1033. // can't inset more than the half bounds of the polygon
  1034. if (offset > SkTMin(SkTAbs(SK_ScalarHalf*bounds.width()),
  1035. SkTAbs(SK_ScalarHalf*bounds.height()))) {
  1036. return false;
  1037. }
  1038. // offsetting close to zero just returns the original poly
  1039. if (SkScalarNearlyZero(offset)) {
  1040. for (int i = 0; i < inputPolygonSize; ++i) {
  1041. *offsetPolygon->push() = inputPolygonVerts[i];
  1042. if (polygonIndices) {
  1043. *polygonIndices->push() = i;
  1044. }
  1045. }
  1046. return true;
  1047. }
  1048. // get winding direction
  1049. int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
  1050. if (0 == winding) {
  1051. return false;
  1052. }
  1053. // build normals
  1054. SkAutoSTMalloc<64, SkVector> normals(inputPolygonSize);
  1055. unsigned int numEdges = 0;
  1056. for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
  1057. currIndex < inputPolygonSize;
  1058. prevIndex = currIndex, ++currIndex) {
  1059. if (!inputPolygonVerts[currIndex].isFinite()) {
  1060. return false;
  1061. }
  1062. int nextIndex = (currIndex + 1) % inputPolygonSize;
  1063. if (!compute_offset_vector(inputPolygonVerts[currIndex], inputPolygonVerts[nextIndex],
  1064. offset, winding, &normals[currIndex])) {
  1065. return false;
  1066. }
  1067. if (currIndex > 0) {
  1068. // if reflex point, we need to add extra edges
  1069. if (is_reflex_vertex(inputPolygonVerts, winding, offset,
  1070. prevIndex, currIndex, nextIndex)) {
  1071. SkScalar rotSin, rotCos;
  1072. int numSteps;
  1073. if (!SkComputeRadialSteps(normals[prevIndex], normals[currIndex], offset,
  1074. &rotSin, &rotCos, &numSteps)) {
  1075. return false;
  1076. }
  1077. numEdges += SkTMax(numSteps, 1);
  1078. }
  1079. }
  1080. numEdges++;
  1081. }
  1082. // finish up the edge counting
  1083. if (is_reflex_vertex(inputPolygonVerts, winding, offset, inputPolygonSize-1, 0, 1)) {
  1084. SkScalar rotSin, rotCos;
  1085. int numSteps;
  1086. if (!SkComputeRadialSteps(normals[inputPolygonSize-1], normals[0], offset,
  1087. &rotSin, &rotCos, &numSteps)) {
  1088. return false;
  1089. }
  1090. numEdges += SkTMax(numSteps, 1);
  1091. }
  1092. // Make sure we don't overflow the max array count.
  1093. // We shouldn't overflow numEdges, as SkComputeRadialSteps returns a max of 2^16-1,
  1094. // and we have a max of 2^16-1 original vertices.
  1095. if (numEdges > (unsigned int)std::numeric_limits<int32_t>::max()) {
  1096. return false;
  1097. }
  1098. // build initial offset edge list
  1099. SkSTArray<64, OffsetEdge> edgeData(numEdges);
  1100. OffsetEdge* prevEdge = nullptr;
  1101. for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
  1102. currIndex < inputPolygonSize;
  1103. prevIndex = currIndex, ++currIndex) {
  1104. int nextIndex = (currIndex + 1) % inputPolygonSize;
  1105. // if reflex point, fill in curve
  1106. if (is_reflex_vertex(inputPolygonVerts, winding, offset,
  1107. prevIndex, currIndex, nextIndex)) {
  1108. SkScalar rotSin, rotCos;
  1109. int numSteps;
  1110. SkVector prevNormal = normals[prevIndex];
  1111. if (!SkComputeRadialSteps(prevNormal, normals[currIndex], offset,
  1112. &rotSin, &rotCos, &numSteps)) {
  1113. return false;
  1114. }
  1115. auto currEdge = edgeData.push_back_n(SkTMax(numSteps, 1));
  1116. for (int i = 0; i < numSteps - 1; ++i) {
  1117. SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin,
  1118. prevNormal.fY*rotCos + prevNormal.fX*rotSin);
  1119. setup_offset_edge(currEdge,
  1120. inputPolygonVerts[currIndex] + prevNormal,
  1121. inputPolygonVerts[currIndex] + currNormal,
  1122. currIndex, currIndex);
  1123. prevNormal = currNormal;
  1124. currEdge->fPrev = prevEdge;
  1125. if (prevEdge) {
  1126. prevEdge->fNext = currEdge;
  1127. }
  1128. prevEdge = currEdge;
  1129. ++currEdge;
  1130. }
  1131. setup_offset_edge(currEdge,
  1132. inputPolygonVerts[currIndex] + prevNormal,
  1133. inputPolygonVerts[currIndex] + normals[currIndex],
  1134. currIndex, currIndex);
  1135. currEdge->fPrev = prevEdge;
  1136. if (prevEdge) {
  1137. prevEdge->fNext = currEdge;
  1138. }
  1139. prevEdge = currEdge;
  1140. }
  1141. // Add the edge
  1142. auto currEdge = edgeData.push_back_n(1);
  1143. setup_offset_edge(currEdge,
  1144. inputPolygonVerts[currIndex] + normals[currIndex],
  1145. inputPolygonVerts[nextIndex] + normals[currIndex],
  1146. currIndex, nextIndex);
  1147. currEdge->fPrev = prevEdge;
  1148. if (prevEdge) {
  1149. prevEdge->fNext = currEdge;
  1150. }
  1151. prevEdge = currEdge;
  1152. }
  1153. // close up the linked list
  1154. SkASSERT(prevEdge);
  1155. prevEdge->fNext = &edgeData[0];
  1156. edgeData[0].fPrev = prevEdge;
  1157. // now clip edges
  1158. SkASSERT(edgeData.count() == (int)numEdges);
  1159. auto head = &edgeData[0];
  1160. auto currEdge = head;
  1161. unsigned int offsetVertexCount = numEdges;
  1162. unsigned long long iterations = 0;
  1163. unsigned long long maxIterations = (unsigned long long)(numEdges) * numEdges;
  1164. while (head && prevEdge != currEdge && offsetVertexCount > 0) {
  1165. ++iterations;
  1166. // we should check each edge against each other edge at most once
  1167. if (iterations > maxIterations) {
  1168. return false;
  1169. }
  1170. SkScalar s, t;
  1171. SkPoint intersection;
  1172. if (prevEdge->checkIntersection(currEdge, &intersection, &s, &t)) {
  1173. // if new intersection is further back on previous inset from the prior intersection
  1174. if (s < prevEdge->fTValue) {
  1175. // no point in considering this one again
  1176. remove_node(prevEdge, &head);
  1177. --offsetVertexCount;
  1178. // go back one segment
  1179. prevEdge = prevEdge->fPrev;
  1180. // we've already considered this intersection, we're done
  1181. } else if (currEdge->fTValue > SK_ScalarMin &&
  1182. SkPointPriv::EqualsWithinTolerance(intersection,
  1183. currEdge->fIntersection,
  1184. 1.0e-6f)) {
  1185. break;
  1186. } else {
  1187. // add intersection
  1188. currEdge->fIntersection = intersection;
  1189. currEdge->fTValue = t;
  1190. currEdge->fIndex = prevEdge->fEnd;
  1191. // go to next segment
  1192. prevEdge = currEdge;
  1193. currEdge = currEdge->fNext;
  1194. }
  1195. } else {
  1196. // If there is no intersection, we want to minimize the distance between
  1197. // the point where the segment lines cross and the segments themselves.
  1198. OffsetEdge* prevPrevEdge = prevEdge->fPrev;
  1199. OffsetEdge* currNextEdge = currEdge->fNext;
  1200. SkScalar dist0 = currEdge->computeCrossingDistance(prevPrevEdge);
  1201. SkScalar dist1 = prevEdge->computeCrossingDistance(currNextEdge);
  1202. // if both lead to direct collision
  1203. if (dist0 < 0 && dist1 < 0) {
  1204. // check first to see if either represent parts of one contour
  1205. SkPoint p1 = prevPrevEdge->fOffset.fP0 + prevPrevEdge->fOffset.fV;
  1206. bool prevSameContour = SkPointPriv::EqualsWithinTolerance(p1,
  1207. prevEdge->fOffset.fP0);
  1208. p1 = currEdge->fOffset.fP0 + currEdge->fOffset.fV;
  1209. bool currSameContour = SkPointPriv::EqualsWithinTolerance(p1,
  1210. currNextEdge->fOffset.fP0);
  1211. // want to step along contour to find intersections rather than jump to new one
  1212. if (currSameContour && !prevSameContour) {
  1213. remove_node(currEdge, &head);
  1214. currEdge = currNextEdge;
  1215. --offsetVertexCount;
  1216. continue;
  1217. } else if (prevSameContour && !currSameContour) {
  1218. remove_node(prevEdge, &head);
  1219. prevEdge = prevPrevEdge;
  1220. --offsetVertexCount;
  1221. continue;
  1222. }
  1223. }
  1224. // otherwise minimize collision distance along segment
  1225. if (dist0 < dist1) {
  1226. remove_node(prevEdge, &head);
  1227. prevEdge = prevPrevEdge;
  1228. } else {
  1229. remove_node(currEdge, &head);
  1230. currEdge = currNextEdge;
  1231. }
  1232. --offsetVertexCount;
  1233. }
  1234. }
  1235. // store all the valid intersections that aren't nearly coincident
  1236. // TODO: look at the main algorithm and see if we can detect these better
  1237. offsetPolygon->reset();
  1238. if (!head || offsetVertexCount == 0 ||
  1239. offsetVertexCount >= std::numeric_limits<uint16_t>::max()) {
  1240. return false;
  1241. }
  1242. static constexpr SkScalar kCleanupTolerance = 0.01f;
  1243. offsetPolygon->setReserve(offsetVertexCount);
  1244. int currIndex = 0;
  1245. *offsetPolygon->push() = head->fIntersection;
  1246. if (polygonIndices) {
  1247. *polygonIndices->push() = head->fIndex;
  1248. }
  1249. currEdge = head->fNext;
  1250. while (currEdge != head) {
  1251. if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
  1252. (*offsetPolygon)[currIndex],
  1253. kCleanupTolerance)) {
  1254. *offsetPolygon->push() = currEdge->fIntersection;
  1255. if (polygonIndices) {
  1256. *polygonIndices->push() = currEdge->fIndex;
  1257. }
  1258. currIndex++;
  1259. }
  1260. currEdge = currEdge->fNext;
  1261. }
  1262. // make sure the first and last points aren't coincident
  1263. if (currIndex >= 1 &&
  1264. SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex],
  1265. kCleanupTolerance)) {
  1266. offsetPolygon->pop();
  1267. if (polygonIndices) {
  1268. polygonIndices->pop();
  1269. }
  1270. }
  1271. // check winding of offset polygon (it should be same as the original polygon)
  1272. SkScalar offsetWinding = SkGetPolygonWinding(offsetPolygon->begin(), offsetPolygon->count());
  1273. return (winding*offsetWinding > 0 &&
  1274. SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->count()));
  1275. }
  1276. //////////////////////////////////////////////////////////////////////////////////////////
  1277. struct TriangulationVertex {
  1278. SK_DECLARE_INTERNAL_LLIST_INTERFACE(TriangulationVertex);
  1279. enum class VertexType { kConvex, kReflex };
  1280. SkPoint fPosition;
  1281. VertexType fVertexType;
  1282. uint16_t fIndex;
  1283. uint16_t fPrevIndex;
  1284. uint16_t fNextIndex;
  1285. };
  1286. static void compute_triangle_bounds(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
  1287. SkRect* bounds) {
  1288. Sk4s min, max;
  1289. min = max = Sk4s(p0.fX, p0.fY, p0.fX, p0.fY);
  1290. Sk4s xy(p1.fX, p1.fY, p2.fX, p2.fY);
  1291. min = Sk4s::Min(min, xy);
  1292. max = Sk4s::Max(max, xy);
  1293. bounds->set(SkTMin(min[0], min[2]), SkTMin(min[1], min[3]),
  1294. SkTMax(max[0], max[2]), SkTMax(max[1], max[3]));
  1295. }
  1296. // test to see if point p is in triangle p0p1p2.
  1297. // for now assuming strictly inside -- if on the edge it's outside
  1298. static bool point_in_triangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
  1299. const SkPoint& p) {
  1300. SkVector v0 = p1 - p0;
  1301. SkVector v1 = p2 - p1;
  1302. SkScalar n = v0.cross(v1);
  1303. SkVector w0 = p - p0;
  1304. if (n*v0.cross(w0) < SK_ScalarNearlyZero) {
  1305. return false;
  1306. }
  1307. SkVector w1 = p - p1;
  1308. if (n*v1.cross(w1) < SK_ScalarNearlyZero) {
  1309. return false;
  1310. }
  1311. SkVector v2 = p0 - p2;
  1312. SkVector w2 = p - p2;
  1313. if (n*v2.cross(w2) < SK_ScalarNearlyZero) {
  1314. return false;
  1315. }
  1316. return true;
  1317. }
  1318. // Data structure to track reflex vertices and check whether any are inside a given triangle
  1319. class ReflexHash {
  1320. public:
  1321. bool init(const SkRect& bounds, int vertexCount) {
  1322. fBounds = bounds;
  1323. fNumVerts = 0;
  1324. SkScalar width = bounds.width();
  1325. SkScalar height = bounds.height();
  1326. if (!SkScalarIsFinite(width) || !SkScalarIsFinite(height)) {
  1327. return false;
  1328. }
  1329. // We want vertexCount grid cells, roughly distributed to match the bounds ratio
  1330. SkScalar hCount = SkScalarSqrt(sk_ieee_float_divide(vertexCount*width, height));
  1331. if (!SkScalarIsFinite(hCount)) {
  1332. return false;
  1333. }
  1334. fHCount = SkTMax(SkTMin(SkScalarRoundToInt(hCount), vertexCount), 1);
  1335. fVCount = vertexCount/fHCount;
  1336. fGridConversion.set(sk_ieee_float_divide(fHCount - 0.001f, width),
  1337. sk_ieee_float_divide(fVCount - 0.001f, height));
  1338. if (!fGridConversion.isFinite()) {
  1339. return false;
  1340. }
  1341. fGrid.setCount(fHCount*fVCount);
  1342. for (int i = 0; i < fGrid.count(); ++i) {
  1343. fGrid[i].reset();
  1344. }
  1345. return true;
  1346. }
  1347. void add(TriangulationVertex* v) {
  1348. int index = hash(v);
  1349. fGrid[index].addToTail(v);
  1350. ++fNumVerts;
  1351. }
  1352. void remove(TriangulationVertex* v) {
  1353. int index = hash(v);
  1354. fGrid[index].remove(v);
  1355. --fNumVerts;
  1356. }
  1357. bool checkTriangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
  1358. uint16_t ignoreIndex0, uint16_t ignoreIndex1) const {
  1359. if (!fNumVerts) {
  1360. return false;
  1361. }
  1362. SkRect triBounds;
  1363. compute_triangle_bounds(p0, p1, p2, &triBounds);
  1364. int h0 = (triBounds.fLeft - fBounds.fLeft)*fGridConversion.fX;
  1365. int h1 = (triBounds.fRight - fBounds.fLeft)*fGridConversion.fX;
  1366. int v0 = (triBounds.fTop - fBounds.fTop)*fGridConversion.fY;
  1367. int v1 = (triBounds.fBottom - fBounds.fTop)*fGridConversion.fY;
  1368. for (int v = v0; v <= v1; ++v) {
  1369. for (int h = h0; h <= h1; ++h) {
  1370. int i = v * fHCount + h;
  1371. for (SkTInternalLList<TriangulationVertex>::Iter reflexIter = fGrid[i].begin();
  1372. reflexIter != fGrid[i].end(); ++reflexIter) {
  1373. TriangulationVertex* reflexVertex = *reflexIter;
  1374. if (reflexVertex->fIndex != ignoreIndex0 &&
  1375. reflexVertex->fIndex != ignoreIndex1 &&
  1376. point_in_triangle(p0, p1, p2, reflexVertex->fPosition)) {
  1377. return true;
  1378. }
  1379. }
  1380. }
  1381. }
  1382. return false;
  1383. }
  1384. private:
  1385. int hash(TriangulationVertex* vert) const {
  1386. int h = (vert->fPosition.fX - fBounds.fLeft)*fGridConversion.fX;
  1387. int v = (vert->fPosition.fY - fBounds.fTop)*fGridConversion.fY;
  1388. SkASSERT(v*fHCount + h >= 0);
  1389. return v*fHCount + h;
  1390. }
  1391. SkRect fBounds;
  1392. int fHCount;
  1393. int fVCount;
  1394. int fNumVerts;
  1395. // converts distance from the origin to a grid location (when cast to int)
  1396. SkVector fGridConversion;
  1397. SkTDArray<SkTInternalLList<TriangulationVertex>> fGrid;
  1398. };
  1399. // Check to see if a reflex vertex has become a convex vertex after clipping an ear
  1400. static void reclassify_vertex(TriangulationVertex* p, const SkPoint* polygonVerts,
  1401. int winding, ReflexHash* reflexHash,
  1402. SkTInternalLList<TriangulationVertex>* convexList) {
  1403. if (TriangulationVertex::VertexType::kReflex == p->fVertexType) {
  1404. SkVector v0 = p->fPosition - polygonVerts[p->fPrevIndex];
  1405. SkVector v1 = polygonVerts[p->fNextIndex] - p->fPosition;
  1406. if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
  1407. p->fVertexType = TriangulationVertex::VertexType::kConvex;
  1408. reflexHash->remove(p);
  1409. p->fPrev = p->fNext = nullptr;
  1410. convexList->addToTail(p);
  1411. }
  1412. }
  1413. }
  1414. bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, int polygonSize,
  1415. SkTDArray<uint16_t>* triangleIndices) {
  1416. if (polygonSize < 3) {
  1417. return false;
  1418. }
  1419. // need to be able to represent all the vertices in the 16-bit indices
  1420. if (polygonSize >= std::numeric_limits<uint16_t>::max()) {
  1421. return false;
  1422. }
  1423. // get bounds
  1424. SkRect bounds;
  1425. if (!bounds.setBoundsCheck(polygonVerts, polygonSize)) {
  1426. return false;
  1427. }
  1428. // get winding direction
  1429. // TODO: we do this for all the polygon routines -- might be better to have the client
  1430. // compute it and pass it in
  1431. int winding = SkGetPolygonWinding(polygonVerts, polygonSize);
  1432. if (0 == winding) {
  1433. return false;
  1434. }
  1435. // Set up vertices
  1436. SkAutoSTMalloc<64, TriangulationVertex> triangulationVertices(polygonSize);
  1437. int prevIndex = polygonSize - 1;
  1438. SkVector v0 = polygonVerts[0] - polygonVerts[prevIndex];
  1439. for (int currIndex = 0; currIndex < polygonSize; ++currIndex) {
  1440. int nextIndex = (currIndex + 1) % polygonSize;
  1441. SkDEBUGCODE(memset(&triangulationVertices[currIndex], 0, sizeof(TriangulationVertex)));
  1442. triangulationVertices[currIndex].fPosition = polygonVerts[currIndex];
  1443. triangulationVertices[currIndex].fIndex = currIndex;
  1444. triangulationVertices[currIndex].fPrevIndex = prevIndex;
  1445. triangulationVertices[currIndex].fNextIndex = nextIndex;
  1446. SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
  1447. if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
  1448. triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kConvex;
  1449. } else {
  1450. triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kReflex;
  1451. }
  1452. prevIndex = currIndex;
  1453. v0 = v1;
  1454. }
  1455. // Classify initial vertices into a list of convex vertices and a hash of reflex vertices
  1456. // TODO: possibly sort the convexList in some way to get better triangles
  1457. SkTInternalLList<TriangulationVertex> convexList;
  1458. ReflexHash reflexHash;
  1459. if (!reflexHash.init(bounds, polygonSize)) {
  1460. return false;
  1461. }
  1462. prevIndex = polygonSize - 1;
  1463. for (int currIndex = 0; currIndex < polygonSize; prevIndex = currIndex, ++currIndex) {
  1464. TriangulationVertex::VertexType currType = triangulationVertices[currIndex].fVertexType;
  1465. if (TriangulationVertex::VertexType::kConvex == currType) {
  1466. int nextIndex = (currIndex + 1) % polygonSize;
  1467. TriangulationVertex::VertexType prevType = triangulationVertices[prevIndex].fVertexType;
  1468. TriangulationVertex::VertexType nextType = triangulationVertices[nextIndex].fVertexType;
  1469. // We prioritize clipping vertices with neighboring reflex vertices.
  1470. // The intent here is that it will cull reflex vertices more quickly.
  1471. if (TriangulationVertex::VertexType::kReflex == prevType ||
  1472. TriangulationVertex::VertexType::kReflex == nextType) {
  1473. convexList.addToHead(&triangulationVertices[currIndex]);
  1474. } else {
  1475. convexList.addToTail(&triangulationVertices[currIndex]);
  1476. }
  1477. } else {
  1478. // We treat near collinear vertices as reflex
  1479. reflexHash.add(&triangulationVertices[currIndex]);
  1480. }
  1481. }
  1482. // The general concept: We are trying to find three neighboring vertices where
  1483. // no other vertex lies inside the triangle (an "ear"). If we find one, we clip
  1484. // that ear off, and then repeat on the new polygon. Once we get down to three vertices
  1485. // we have triangulated the entire polygon.
  1486. // In the worst case this is an n^2 algorithm. We can cut down the search space somewhat by
  1487. // noting that only convex vertices can be potential ears, and we only need to check whether
  1488. // any reflex vertices lie inside the ear.
  1489. triangleIndices->setReserve(triangleIndices->count() + 3 * (polygonSize - 2));
  1490. int vertexCount = polygonSize;
  1491. while (vertexCount > 3) {
  1492. bool success = false;
  1493. TriangulationVertex* earVertex = nullptr;
  1494. TriangulationVertex* p0 = nullptr;
  1495. TriangulationVertex* p2 = nullptr;
  1496. // find a convex vertex to clip
  1497. for (SkTInternalLList<TriangulationVertex>::Iter convexIter = convexList.begin();
  1498. convexIter != convexList.end(); ++convexIter) {
  1499. earVertex = *convexIter;
  1500. SkASSERT(TriangulationVertex::VertexType::kReflex != earVertex->fVertexType);
  1501. p0 = &triangulationVertices[earVertex->fPrevIndex];
  1502. p2 = &triangulationVertices[earVertex->fNextIndex];
  1503. // see if any reflex vertices are inside the ear
  1504. bool failed = reflexHash.checkTriangle(p0->fPosition, earVertex->fPosition,
  1505. p2->fPosition, p0->fIndex, p2->fIndex);
  1506. if (failed) {
  1507. continue;
  1508. }
  1509. // found one we can clip
  1510. success = true;
  1511. break;
  1512. }
  1513. // If we can't find any ears to clip, this probably isn't a simple polygon
  1514. if (!success) {
  1515. return false;
  1516. }
  1517. // add indices
  1518. auto indices = triangleIndices->append(3);
  1519. indices[0] = indexMap[p0->fIndex];
  1520. indices[1] = indexMap[earVertex->fIndex];
  1521. indices[2] = indexMap[p2->fIndex];
  1522. // clip the ear
  1523. convexList.remove(earVertex);
  1524. --vertexCount;
  1525. // reclassify reflex verts
  1526. p0->fNextIndex = earVertex->fNextIndex;
  1527. reclassify_vertex(p0, polygonVerts, winding, &reflexHash, &convexList);
  1528. p2->fPrevIndex = earVertex->fPrevIndex;
  1529. reclassify_vertex(p2, polygonVerts, winding, &reflexHash, &convexList);
  1530. }
  1531. // output indices
  1532. for (SkTInternalLList<TriangulationVertex>::Iter vertexIter = convexList.begin();
  1533. vertexIter != convexList.end(); ++vertexIter) {
  1534. TriangulationVertex* vertex = *vertexIter;
  1535. *triangleIndices->push() = indexMap[vertex->fIndex];
  1536. }
  1537. return true;
  1538. }
  1539. ///////////
  1540. static double crs(SkVector a, SkVector b) {
  1541. return a.fX * b.fY - a.fY * b.fX;
  1542. }
  1543. static int sign(SkScalar v) {
  1544. return v < 0 ? -1 : (v > 0);
  1545. }
  1546. struct SignTracker {
  1547. int fSign;
  1548. int fSignChanges;
  1549. void reset() {
  1550. fSign = 0;
  1551. fSignChanges = 0;
  1552. }
  1553. void init(int s) {
  1554. SkASSERT(fSignChanges == 0);
  1555. SkASSERT(s == 1 || s == -1 || s == 0);
  1556. fSign = s;
  1557. fSignChanges = 1;
  1558. }
  1559. void update(int s) {
  1560. if (s) {
  1561. if (fSign != s) {
  1562. fSignChanges += 1;
  1563. fSign = s;
  1564. }
  1565. }
  1566. }
  1567. };
  1568. struct ConvexTracker {
  1569. SkVector fFirst, fPrev;
  1570. SignTracker fDSign, fCSign;
  1571. int fVecCounter;
  1572. bool fIsConcave;
  1573. ConvexTracker() { this->reset(); }
  1574. void reset() {
  1575. fPrev = {0, 0};
  1576. fDSign.reset();
  1577. fCSign.reset();
  1578. fVecCounter = 0;
  1579. fIsConcave = false;
  1580. }
  1581. void addVec(SkPoint p1, SkPoint p0) {
  1582. this->addVec(p1 - p0);
  1583. }
  1584. void addVec(SkVector v) {
  1585. if (v.fX == 0 && v.fY == 0) {
  1586. return;
  1587. }
  1588. fVecCounter += 1;
  1589. if (fVecCounter == 1) {
  1590. fFirst = fPrev = v;
  1591. fDSign.update(sign(v.fX));
  1592. return;
  1593. }
  1594. SkScalar d = v.fX;
  1595. SkScalar c = crs(fPrev, v);
  1596. int sign_c;
  1597. if (c) {
  1598. sign_c = sign(c);
  1599. } else {
  1600. if (d >= 0) {
  1601. sign_c = fCSign.fSign;
  1602. } else {
  1603. sign_c = -fCSign.fSign;
  1604. }
  1605. }
  1606. fDSign.update(sign(d));
  1607. fCSign.update(sign_c);
  1608. fPrev = v;
  1609. if (fDSign.fSignChanges > 3 || fCSign.fSignChanges > 1) {
  1610. fIsConcave = true;
  1611. }
  1612. }
  1613. void finalCross() {
  1614. this->addVec(fFirst);
  1615. }
  1616. };
  1617. bool SkIsPolyConvex_experimental(const SkPoint pts[], int count) {
  1618. if (count <= 3) {
  1619. return true;
  1620. }
  1621. ConvexTracker tracker;
  1622. for (int i = 0; i < count - 1; ++i) {
  1623. tracker.addVec(pts[i + 1], pts[i]);
  1624. if (tracker.fIsConcave) {
  1625. return false;
  1626. }
  1627. }
  1628. tracker.addVec(pts[0], pts[count - 1]);
  1629. tracker.finalCross();
  1630. return !tracker.fIsConcave;
  1631. }