PathOpsTestCommon.cpp 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331
  1. /*
  2. * Copyright 2012 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/core/SkTSort.h"
  8. #include "src/pathops/SkPathOpsBounds.h"
  9. #include "src/pathops/SkPathOpsConic.h"
  10. #include "src/pathops/SkPathOpsCubic.h"
  11. #include "src/pathops/SkPathOpsLine.h"
  12. #include "src/pathops/SkPathOpsQuad.h"
  13. #include "src/pathops/SkPathOpsTSect.h"
  14. #include "src/pathops/SkReduceOrder.h"
  15. #include "tests/PathOpsTestCommon.h"
  16. #include <utility>
  17. static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
  18. const double adjust = sqrt(3.) / 36;
  19. SkDCubic sub;
  20. const SkDCubic* cPtr;
  21. if (start == 0) {
  22. cPtr = &cubic;
  23. } else {
  24. // OPTIMIZE: special-case half-split ?
  25. sub = cubic.subDivide(start, 1);
  26. cPtr = &sub;
  27. }
  28. const SkDCubic& c = *cPtr;
  29. double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX;
  30. double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY;
  31. double dist = sqrt(dx * dx + dy * dy);
  32. double tDiv3 = precision / (adjust * dist);
  33. double t = SkDCubeRoot(tDiv3);
  34. if (start > 0) {
  35. t = start + (1 - start) * t;
  36. }
  37. return t;
  38. }
  39. static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) {
  40. double tDiv = calc_t_div(cubic, precision, 0);
  41. if (tDiv >= 1) {
  42. return true;
  43. }
  44. if (tDiv >= 0.5) {
  45. ts->push_back(0.5);
  46. return true;
  47. }
  48. return false;
  49. }
  50. static void addTs(const SkDCubic& cubic, double precision, double start, double end,
  51. SkTArray<double, true>* ts) {
  52. double tDiv = calc_t_div(cubic, precision, 0);
  53. double parts = ceil(1.0 / tDiv);
  54. for (double index = 0; index < parts; ++index) {
  55. double newT = start + (index / parts) * (end - start);
  56. if (newT > 0 && newT < 1) {
  57. ts->push_back(newT);
  58. }
  59. }
  60. }
  61. static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) {
  62. SkReduceOrder reducer;
  63. int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics);
  64. if (order < 3) {
  65. return;
  66. }
  67. double inflectT[5];
  68. int inflections = cubic->findInflections(inflectT);
  69. SkASSERT(inflections <= 2);
  70. if (!cubic->endsAreExtremaInXOrY()) {
  71. inflections += cubic->findMaxCurvature(&inflectT[inflections]);
  72. SkASSERT(inflections <= 5);
  73. }
  74. SkTQSort<double>(inflectT, &inflectT[inflections - 1]);
  75. // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
  76. // own subroutine?
  77. while (inflections && approximately_less_than_zero(inflectT[0])) {
  78. memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
  79. }
  80. int start = 0;
  81. int next = 1;
  82. while (next < inflections) {
  83. if (!approximately_equal(inflectT[start], inflectT[next])) {
  84. ++start;
  85. ++next;
  86. continue;
  87. }
  88. memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start));
  89. }
  90. while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) {
  91. --inflections;
  92. }
  93. SkDCubicPair pair;
  94. if (inflections == 1) {
  95. pair = cubic->chopAt(inflectT[0]);
  96. int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics);
  97. if (orderP1 < 2) {
  98. --inflections;
  99. } else {
  100. int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics);
  101. if (orderP2 < 2) {
  102. --inflections;
  103. }
  104. }
  105. }
  106. if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) {
  107. return;
  108. }
  109. if (inflections == 1) {
  110. pair = cubic->chopAt(inflectT[0]);
  111. addTs(pair.first(), precision, 0, inflectT[0], ts);
  112. addTs(pair.second(), precision, inflectT[0], 1, ts);
  113. return;
  114. }
  115. if (inflections > 1) {
  116. SkDCubic part = cubic->subDivide(0, inflectT[0]);
  117. addTs(part, precision, 0, inflectT[0], ts);
  118. int last = inflections - 1;
  119. for (int idx = 0; idx < last; ++idx) {
  120. part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]);
  121. addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
  122. }
  123. part = cubic->subDivide(inflectT[last], 1);
  124. addTs(part, precision, inflectT[last], 1, ts);
  125. return;
  126. }
  127. addTs(*cubic, precision, 0, 1, ts);
  128. }
  129. void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) {
  130. SkTArray<double, true> ts;
  131. toQuadraticTs(&cubic, precision, &ts);
  132. if (ts.count() <= 0) {
  133. SkDQuad quad = cubic.toQuad();
  134. quads.push_back(quad);
  135. return;
  136. }
  137. double tStart = 0;
  138. for (int i1 = 0; i1 <= ts.count(); ++i1) {
  139. const double tEnd = i1 < ts.count() ? ts[i1] : 1;
  140. SkDRect bounds;
  141. bounds.setBounds(cubic);
  142. SkDCubic part = cubic.subDivide(tStart, tEnd);
  143. SkDQuad quad = part.toQuad();
  144. if (quad[1].fX < bounds.fLeft) {
  145. quad[1].fX = bounds.fLeft;
  146. } else if (quad[1].fX > bounds.fRight) {
  147. quad[1].fX = bounds.fRight;
  148. }
  149. if (quad[1].fY < bounds.fTop) {
  150. quad[1].fY = bounds.fTop;
  151. } else if (quad[1].fY > bounds.fBottom) {
  152. quad[1].fY = bounds.fBottom;
  153. }
  154. quads.push_back(quad);
  155. tStart = tEnd;
  156. }
  157. }
  158. void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) {
  159. quadPath->reset();
  160. SkDCubic cubic;
  161. SkTArray<SkDQuad, true> quads;
  162. SkPath::RawIter iter(cubicPath);
  163. uint8_t verb;
  164. SkPoint pts[4];
  165. while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
  166. switch (verb) {
  167. case SkPath::kMove_Verb:
  168. quadPath->moveTo(pts[0].fX, pts[0].fY);
  169. continue;
  170. case SkPath::kLine_Verb:
  171. quadPath->lineTo(pts[1].fX, pts[1].fY);
  172. break;
  173. case SkPath::kQuad_Verb:
  174. quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
  175. break;
  176. case SkPath::kCubic_Verb:
  177. quads.reset();
  178. cubic.set(pts);
  179. CubicToQuads(cubic, cubic.calcPrecision(), quads);
  180. for (int index = 0; index < quads.count(); ++index) {
  181. SkPoint qPts[2] = {
  182. quads[index][1].asSkPoint(),
  183. quads[index][2].asSkPoint()
  184. };
  185. quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY);
  186. }
  187. break;
  188. case SkPath::kClose_Verb:
  189. quadPath->close();
  190. break;
  191. default:
  192. SkDEBUGFAIL("bad verb");
  193. return;
  194. }
  195. }
  196. }
  197. void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) {
  198. simplePath->reset();
  199. SkDCubic cubic;
  200. SkPath::RawIter iter(cubicPath);
  201. uint8_t verb;
  202. SkPoint pts[4];
  203. while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
  204. switch (verb) {
  205. case SkPath::kMove_Verb:
  206. simplePath->moveTo(pts[0].fX, pts[0].fY);
  207. continue;
  208. case SkPath::kLine_Verb:
  209. simplePath->lineTo(pts[1].fX, pts[1].fY);
  210. break;
  211. case SkPath::kQuad_Verb:
  212. simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
  213. break;
  214. case SkPath::kCubic_Verb: {
  215. cubic.set(pts);
  216. double tInflects[2];
  217. int inflections = cubic.findInflections(tInflects);
  218. if (inflections > 1 && tInflects[0] > tInflects[1]) {
  219. using std::swap;
  220. swap(tInflects[0], tInflects[1]);
  221. }
  222. double lo = 0;
  223. for (int index = 0; index <= inflections; ++index) {
  224. double hi = index < inflections ? tInflects[index] : 1;
  225. SkDCubic part = cubic.subDivide(lo, hi);
  226. SkPoint cPts[3];
  227. cPts[0] = part[1].asSkPoint();
  228. cPts[1] = part[2].asSkPoint();
  229. cPts[2] = part[3].asSkPoint();
  230. simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY,
  231. cPts[2].fX, cPts[2].fY);
  232. lo = hi;
  233. }
  234. break;
  235. }
  236. case SkPath::kClose_Verb:
  237. simplePath->close();
  238. break;
  239. default:
  240. SkDEBUGFAIL("bad verb");
  241. return;
  242. }
  243. }
  244. }
  245. bool ValidBounds(const SkPathOpsBounds& bounds) {
  246. if (SkScalarIsNaN(bounds.fLeft)) {
  247. return false;
  248. }
  249. if (SkScalarIsNaN(bounds.fTop)) {
  250. return false;
  251. }
  252. if (SkScalarIsNaN(bounds.fRight)) {
  253. return false;
  254. }
  255. return !SkScalarIsNaN(bounds.fBottom);
  256. }
  257. bool ValidConic(const SkDConic& conic) {
  258. for (int index = 0; index < SkDConic::kPointCount; ++index) {
  259. if (!ValidPoint(conic[index])) {
  260. return false;
  261. }
  262. }
  263. if (SkDoubleIsNaN(conic.fWeight)) {
  264. return false;
  265. }
  266. return true;
  267. }
  268. bool ValidCubic(const SkDCubic& cubic) {
  269. for (int index = 0; index < 4; ++index) {
  270. if (!ValidPoint(cubic[index])) {
  271. return false;
  272. }
  273. }
  274. return true;
  275. }
  276. bool ValidLine(const SkDLine& line) {
  277. for (int index = 0; index < 2; ++index) {
  278. if (!ValidPoint(line[index])) {
  279. return false;
  280. }
  281. }
  282. return true;
  283. }
  284. bool ValidPoint(const SkDPoint& pt) {
  285. if (SkDoubleIsNaN(pt.fX)) {
  286. return false;
  287. }
  288. return !SkDoubleIsNaN(pt.fY);
  289. }
  290. bool ValidPoints(const SkPoint* pts, int count) {
  291. for (int index = 0; index < count; ++index) {
  292. if (SkScalarIsNaN(pts[index].fX)) {
  293. return false;
  294. }
  295. if (SkScalarIsNaN(pts[index].fY)) {
  296. return false;
  297. }
  298. }
  299. return true;
  300. }
  301. bool ValidQuad(const SkDQuad& quad) {
  302. for (int index = 0; index < 3; ++index) {
  303. if (!ValidPoint(quad[index])) {
  304. return false;
  305. }
  306. }
  307. return true;
  308. }
  309. bool ValidVector(const SkDVector& v) {
  310. if (SkDoubleIsNaN(v.fX)) {
  311. return false;
  312. }
  313. return !SkDoubleIsNaN(v.fY);
  314. }