GeometryTest.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392
  1. /*
  2. * Copyright 2011 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/utils/SkRandom.h"
  8. #include "src/core/SkGeometry.h"
  9. #include "src/core/SkPointPriv.h"
  10. #include "tests/Test.h"
  11. #include <array>
  12. #include <numeric>
  13. static bool nearly_equal(const SkPoint& a, const SkPoint& b) {
  14. return SkScalarNearlyEqual(a.fX, b.fX) && SkScalarNearlyEqual(a.fY, b.fY);
  15. }
  16. static void testChopCubic(skiatest::Reporter* reporter) {
  17. /*
  18. Inspired by this test, which used to assert that the tValues had dups
  19. <path stroke="#202020" d="M0,0 C0,0 1,1 2190,5130 C2190,5070 2220,5010 2205,4980" />
  20. */
  21. const SkPoint src[] = {
  22. { SkIntToScalar(2190), SkIntToScalar(5130) },
  23. { SkIntToScalar(2190), SkIntToScalar(5070) },
  24. { SkIntToScalar(2220), SkIntToScalar(5010) },
  25. { SkIntToScalar(2205), SkIntToScalar(4980) },
  26. };
  27. SkPoint dst[13];
  28. SkScalar tValues[3];
  29. // make sure we don't assert internally
  30. int count = SkChopCubicAtMaxCurvature(src, dst, tValues);
  31. if (false) { // avoid bit rot, suppress warning
  32. REPORTER_ASSERT(reporter, count);
  33. }
  34. // Make sure src and dst can be the same pointer.
  35. SkPoint pts[7];
  36. for (int i = 0; i < 7; ++i) {
  37. pts[i].set(i, i);
  38. }
  39. SkChopCubicAt(pts, pts, .5f);
  40. for (int i = 0; i < 7; ++i) {
  41. REPORTER_ASSERT(reporter, pts[i].fX == pts[i].fY);
  42. REPORTER_ASSERT(reporter, pts[i].fX == i * .5f);
  43. }
  44. }
  45. static void check_pairs(skiatest::Reporter* reporter, int index, SkScalar t, const char name[],
  46. SkScalar x0, SkScalar y0, SkScalar x1, SkScalar y1) {
  47. bool eq = SkScalarNearlyEqual(x0, x1) && SkScalarNearlyEqual(y0, y1);
  48. if (!eq) {
  49. SkDebugf("%s [%d %g] p0 [%10.8f %10.8f] p1 [%10.8f %10.8f]\n",
  50. name, index, t, x0, y0, x1, y1);
  51. REPORTER_ASSERT(reporter, eq);
  52. }
  53. }
  54. static void test_evalquadat(skiatest::Reporter* reporter) {
  55. SkRandom rand;
  56. for (int i = 0; i < 1000; ++i) {
  57. SkPoint pts[3];
  58. for (int j = 0; j < 3; ++j) {
  59. pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100);
  60. }
  61. const SkScalar dt = SK_Scalar1 / 128;
  62. SkScalar t = dt;
  63. for (int j = 1; j < 128; ++j) {
  64. SkPoint r0;
  65. SkEvalQuadAt(pts, t, &r0);
  66. SkPoint r1 = SkEvalQuadAt(pts, t);
  67. check_pairs(reporter, i, t, "quad-pos", r0.fX, r0.fY, r1.fX, r1.fY);
  68. SkVector v0;
  69. SkEvalQuadAt(pts, t, nullptr, &v0);
  70. SkVector v1 = SkEvalQuadTangentAt(pts, t);
  71. check_pairs(reporter, i, t, "quad-tan", v0.fX, v0.fY, v1.fX, v1.fY);
  72. t += dt;
  73. }
  74. }
  75. }
  76. static void test_conic_eval_pos(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) {
  77. SkPoint p0, p1;
  78. conic.evalAt(t, &p0, nullptr);
  79. p1 = conic.evalAt(t);
  80. check_pairs(reporter, 0, t, "conic-pos", p0.fX, p0.fY, p1.fX, p1.fY);
  81. }
  82. static void test_conic_eval_tan(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) {
  83. SkVector v0, v1;
  84. conic.evalAt(t, nullptr, &v0);
  85. v1 = conic.evalTangentAt(t);
  86. check_pairs(reporter, 0, t, "conic-tan", v0.fX, v0.fY, v1.fX, v1.fY);
  87. }
  88. static void test_conic(skiatest::Reporter* reporter) {
  89. SkRandom rand;
  90. for (int i = 0; i < 1000; ++i) {
  91. SkPoint pts[3];
  92. for (int j = 0; j < 3; ++j) {
  93. pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100);
  94. }
  95. for (int k = 0; k < 10; ++k) {
  96. SkScalar w = rand.nextUScalar1() * 2;
  97. SkConic conic(pts, w);
  98. const SkScalar dt = SK_Scalar1 / 128;
  99. SkScalar t = dt;
  100. for (int j = 1; j < 128; ++j) {
  101. test_conic_eval_pos(reporter, conic, t);
  102. test_conic_eval_tan(reporter, conic, t);
  103. t += dt;
  104. }
  105. }
  106. }
  107. }
  108. static void test_quad_tangents(skiatest::Reporter* reporter) {
  109. SkPoint pts[] = {
  110. {10, 20}, {10, 20}, {20, 30},
  111. {10, 20}, {15, 25}, {20, 30},
  112. {10, 20}, {20, 30}, {20, 30},
  113. };
  114. int count = (int) SK_ARRAY_COUNT(pts) / 3;
  115. for (int index = 0; index < count; ++index) {
  116. SkConic conic(&pts[index * 3], 0.707f);
  117. SkVector start = SkEvalQuadTangentAt(&pts[index * 3], 0);
  118. SkVector mid = SkEvalQuadTangentAt(&pts[index * 3], .5f);
  119. SkVector end = SkEvalQuadTangentAt(&pts[index * 3], 1);
  120. REPORTER_ASSERT(reporter, start.fX && start.fY);
  121. REPORTER_ASSERT(reporter, mid.fX && mid.fY);
  122. REPORTER_ASSERT(reporter, end.fX && end.fY);
  123. REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
  124. REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
  125. }
  126. }
  127. static void test_conic_tangents(skiatest::Reporter* reporter) {
  128. SkPoint pts[] = {
  129. { 10, 20}, {10, 20}, {20, 30},
  130. { 10, 20}, {15, 25}, {20, 30},
  131. { 10, 20}, {20, 30}, {20, 30}
  132. };
  133. int count = (int) SK_ARRAY_COUNT(pts) / 3;
  134. for (int index = 0; index < count; ++index) {
  135. SkConic conic(&pts[index * 3], 0.707f);
  136. SkVector start = conic.evalTangentAt(0);
  137. SkVector mid = conic.evalTangentAt(.5f);
  138. SkVector end = conic.evalTangentAt(1);
  139. REPORTER_ASSERT(reporter, start.fX && start.fY);
  140. REPORTER_ASSERT(reporter, mid.fX && mid.fY);
  141. REPORTER_ASSERT(reporter, end.fX && end.fY);
  142. REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
  143. REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
  144. }
  145. }
  146. static void test_this_conic_to_quad(skiatest::Reporter* r, const SkPoint pts[3], SkScalar w) {
  147. SkAutoConicToQuads quadder;
  148. const SkPoint* qpts = quadder.computeQuads(pts, w, 0.25);
  149. const int qcount = quadder.countQuads();
  150. const int pcount = qcount * 2 + 1;
  151. REPORTER_ASSERT(r, SkPointPriv::AreFinite(qpts, pcount));
  152. }
  153. /**
  154. * We need to ensure that when a conic is approximated by quads, that we always return finite
  155. * values in the quads.
  156. *
  157. * Inspired by crbug_627414
  158. */
  159. static void test_conic_to_quads(skiatest::Reporter* reporter) {
  160. const SkPoint triples[] = {
  161. { 0, 0 }, { 1, 0 }, { 1, 1 },
  162. { 0, 0 }, { 3.58732e-43f, 2.72084f }, { 3.00392f, 3.00392f },
  163. { 0, 0 }, { 100000, 0 }, { 100000, 100000 },
  164. { 0, 0 }, { 1e30f, 0 }, { 1e30f, 1e30f },
  165. };
  166. const int N = sizeof(triples) / sizeof(SkPoint);
  167. for (int i = 0; i < N; i += 3) {
  168. const SkPoint* pts = &triples[i];
  169. SkRect bounds;
  170. bounds.set(pts, 3);
  171. SkScalar w = 1e30f;
  172. do {
  173. w *= 2;
  174. test_this_conic_to_quad(reporter, pts, w);
  175. } while (SkScalarIsFinite(w));
  176. test_this_conic_to_quad(reporter, pts, SK_ScalarNaN);
  177. }
  178. }
  179. static void test_cubic_tangents(skiatest::Reporter* reporter) {
  180. SkPoint pts[] = {
  181. { 10, 20}, {10, 20}, {20, 30}, {30, 40},
  182. { 10, 20}, {15, 25}, {20, 30}, {30, 40},
  183. { 10, 20}, {20, 30}, {30, 40}, {30, 40},
  184. };
  185. int count = (int) SK_ARRAY_COUNT(pts) / 4;
  186. for (int index = 0; index < count; ++index) {
  187. SkConic conic(&pts[index * 3], 0.707f);
  188. SkVector start, mid, end;
  189. SkEvalCubicAt(&pts[index * 4], 0, nullptr, &start, nullptr);
  190. SkEvalCubicAt(&pts[index * 4], .5f, nullptr, &mid, nullptr);
  191. SkEvalCubicAt(&pts[index * 4], 1, nullptr, &end, nullptr);
  192. REPORTER_ASSERT(reporter, start.fX && start.fY);
  193. REPORTER_ASSERT(reporter, mid.fX && mid.fY);
  194. REPORTER_ASSERT(reporter, end.fX && end.fY);
  195. REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
  196. REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
  197. }
  198. }
  199. static void check_cubic_type(skiatest::Reporter* reporter,
  200. const std::array<SkPoint, 4>& bezierPoints, SkCubicType expectedType,
  201. bool undefined = false) {
  202. // Classify the cubic even if the results will be undefined: check for crashes and asserts.
  203. SkCubicType actualType = SkClassifyCubic(bezierPoints.data());
  204. if (!undefined) {
  205. REPORTER_ASSERT(reporter, actualType == expectedType);
  206. }
  207. }
  208. static void check_cubic_around_rect(skiatest::Reporter* reporter,
  209. float x1, float y1, float x2, float y2,
  210. bool undefined = false) {
  211. static constexpr SkCubicType expectations[24] = {
  212. SkCubicType::kLoop,
  213. SkCubicType::kCuspAtInfinity,
  214. SkCubicType::kLocalCusp,
  215. SkCubicType::kLocalCusp,
  216. SkCubicType::kCuspAtInfinity,
  217. SkCubicType::kLoop,
  218. SkCubicType::kCuspAtInfinity,
  219. SkCubicType::kLoop,
  220. SkCubicType::kCuspAtInfinity,
  221. SkCubicType::kLoop,
  222. SkCubicType::kLocalCusp,
  223. SkCubicType::kLocalCusp,
  224. SkCubicType::kLocalCusp,
  225. SkCubicType::kLocalCusp,
  226. SkCubicType::kLoop,
  227. SkCubicType::kCuspAtInfinity,
  228. SkCubicType::kLoop,
  229. SkCubicType::kCuspAtInfinity,
  230. SkCubicType::kLoop,
  231. SkCubicType::kCuspAtInfinity,
  232. SkCubicType::kLocalCusp,
  233. SkCubicType::kLocalCusp,
  234. SkCubicType::kCuspAtInfinity,
  235. SkCubicType::kLoop,
  236. };
  237. SkPoint points[] = {{x1, y1}, {x2, y1}, {x2, y2}, {x1, y2}};
  238. std::array<SkPoint, 4> bezier;
  239. for (int i=0; i < 4; ++i) {
  240. bezier[0] = points[i];
  241. for (int j=0; j < 3; ++j) {
  242. int jidx = (j < i) ? j : j+1;
  243. bezier[1] = points[jidx];
  244. for (int k=0, kidx=0; k < 2; ++k, ++kidx) {
  245. for (int n = 0; n < 2; ++n) {
  246. kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx;
  247. }
  248. bezier[2] = points[kidx];
  249. for (int l = 0; l < 4; ++l) {
  250. if (l != i && l != jidx && l != kidx) {
  251. bezier[3] = points[l];
  252. break;
  253. }
  254. }
  255. check_cubic_type(reporter, bezier, expectations[i*6 + j*2 + k], undefined);
  256. }
  257. }
  258. }
  259. for (int i=0; i < 4; ++i) {
  260. bezier[0] = points[i];
  261. for (int j=0; j < 3; ++j) {
  262. int jidx = (j < i) ? j : j+1;
  263. bezier[1] = points[jidx];
  264. bezier[2] = points[jidx];
  265. for (int k=0, kidx=0; k < 2; ++k, ++kidx) {
  266. for (int n = 0; n < 2; ++n) {
  267. kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx;
  268. }
  269. bezier[3] = points[kidx];
  270. check_cubic_type(reporter, bezier, SkCubicType::kSerpentine, undefined);
  271. }
  272. }
  273. }
  274. }
  275. static void test_classify_cubic(skiatest::Reporter* reporter) {
  276. check_cubic_type(reporter, {{{149.325f, 107.705f}, {149.325f, 103.783f},
  277. {151.638f, 100.127f}, {156.263f, 96.736f}}},
  278. SkCubicType::kSerpentine);
  279. check_cubic_type(reporter, {{{225.694f, 223.15f}, {209.831f, 224.837f},
  280. {195.994f, 230.237f}, {184.181f, 239.35f}}},
  281. SkCubicType::kSerpentine);
  282. check_cubic_type(reporter, {{{4.873f, 5.581f}, {5.083f, 5.2783f},
  283. {5.182f, 4.8593f}, {5.177f, 4.3242f}}},
  284. SkCubicType::kSerpentine);
  285. check_cubic_around_rect(reporter, 0, 0, 1, 1);
  286. check_cubic_around_rect(reporter,
  287. -std::numeric_limits<float>::max(),
  288. -std::numeric_limits<float>::max(),
  289. +std::numeric_limits<float>::max(),
  290. +std::numeric_limits<float>::max());
  291. check_cubic_around_rect(reporter, 1, 1,
  292. +std::numeric_limits<float>::min(),
  293. +std::numeric_limits<float>::max());
  294. check_cubic_around_rect(reporter,
  295. -std::numeric_limits<float>::min(),
  296. -std::numeric_limits<float>::min(),
  297. +std::numeric_limits<float>::min(),
  298. +std::numeric_limits<float>::min());
  299. check_cubic_around_rect(reporter, +1, -std::numeric_limits<float>::min(), -1, -1);
  300. check_cubic_around_rect(reporter,
  301. -std::numeric_limits<float>::infinity(),
  302. -std::numeric_limits<float>::infinity(),
  303. +std::numeric_limits<float>::infinity(),
  304. +std::numeric_limits<float>::infinity(),
  305. true);
  306. check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::infinity(), true);
  307. check_cubic_around_rect(reporter,
  308. -std::numeric_limits<float>::quiet_NaN(),
  309. -std::numeric_limits<float>::quiet_NaN(),
  310. +std::numeric_limits<float>::quiet_NaN(),
  311. +std::numeric_limits<float>::quiet_NaN(),
  312. true);
  313. check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::quiet_NaN(), true);
  314. }
  315. static void test_cubic_cusps(skiatest::Reporter* reporter) {
  316. std::array<SkPoint, 4> noCusps[] = {
  317. {{{0, 0}, {1, 1}, {2, 2}, {3, 3}}},
  318. {{{0, 0}, {1, 0}, {1, 1}, {0, 1}}},
  319. {{{0, 0}, {1, 0}, {2, 1}, {2, 2}}},
  320. {{{0, 0}, {1, 0}, {1, 1}, {2, 1}}},
  321. };
  322. for (auto noCusp : noCusps) {
  323. REPORTER_ASSERT(reporter, SkFindCubicCusp(noCusp.data()) < 0);
  324. }
  325. std::array<SkPoint, 4> cusps[] = {
  326. {{{0, 0}, {1, 1}, {1, 0}, {0, 1}}},
  327. {{{0, 0}, {1, 1}, {0, 1}, {1, 0}}},
  328. {{{0, 1}, {1, 0}, {0, 0}, {1, 1}}},
  329. {{{0, 1}, {1, 0}, {1, 1}, {0, 0}}},
  330. };
  331. for (auto cusp : cusps) {
  332. REPORTER_ASSERT(reporter, SkFindCubicCusp(cusp.data()) > 0);
  333. }
  334. }
  335. DEF_TEST(Geometry, reporter) {
  336. SkPoint pts[5];
  337. pts[0].set(0, 0);
  338. pts[1].set(100, 50);
  339. pts[2].set(0, 100);
  340. int count = SkChopQuadAtMaxCurvature(pts, pts); // Ensure src and dst can be the same pointer.
  341. REPORTER_ASSERT(reporter, count == 1 || count == 2);
  342. pts[0].set(0, 0);
  343. pts[1].set(3, 0);
  344. pts[2].set(3, 3);
  345. SkConvertQuadToCubic(pts, pts);
  346. const SkPoint cubic[] = {
  347. { 0, 0, }, { 2, 0, }, { 3, 1, }, { 3, 3 },
  348. };
  349. for (int i = 0; i < 4; ++i) {
  350. REPORTER_ASSERT(reporter, nearly_equal(cubic[i], pts[i]));
  351. }
  352. testChopCubic(reporter);
  353. test_evalquadat(reporter);
  354. test_conic(reporter);
  355. test_cubic_tangents(reporter);
  356. test_quad_tangents(reporter);
  357. test_conic_tangents(reporter);
  358. test_conic_to_quads(reporter);
  359. test_classify_cubic(reporter);
  360. test_cubic_cusps(reporter);
  361. }