PathOpsConicIntersectionTest.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353
  1. /*
  2. * Copyright 2015 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "src/core/SkGeometry.h"
  8. #include "src/pathops/SkIntersections.h"
  9. #include "tests/PathOpsTestCommon.h"
  10. #include "tests/Test.h"
  11. /*
  12. manually compute the intersection of a pair of circles and see if the conic intersection matches
  13. given two circles
  14. construct a line connecting their centers
  15. */
  16. static const ConicPts testSet[] = {
  17. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  18. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  19. {{{{5.1114602088928223, 628.77813720703125},
  20. {10.834027290344238, 988.964111328125},
  21. {163.40835571289062, 988.964111328125}}}, 0.72944212f},
  22. {{{{163.40835571289062, 988.964111328125},
  23. {5, 988.964111328125},
  24. {5, 614.7423095703125}}}, 0.707106769f},
  25. {{{{11.17222976684570312, -8.103978157043457031},
  26. {22.91432571411132812, -10.37866020202636719},
  27. {23.7764129638671875, -7.725424289703369141}}}, 1.00862849f},
  28. {{{{-1.545085430145263672, -4.755282402038574219},
  29. {22.23132705688476562, -12.48070907592773438},
  30. {23.7764129638671875, -7.725427150726318359}}}, 0.707106769f},
  31. {{{{-4,1}, {-4,5}, {0,5}}}, 0.707106769f},
  32. {{{{-3,4}, {-3,1}, {0,1}}}, 0.707106769f},
  33. {{{{0, 0}, {0, 1}, {1, 1}}}, 0.5f},
  34. {{{{1, 0}, {0, 0}, {0, 1}}}, 0.5f},
  35. };
  36. const int testSetCount = (int) SK_ARRAY_COUNT(testSet);
  37. static void chopCompare(const SkConic chopped[2], const SkDConic dChopped[2]) {
  38. SkASSERT(roughly_equal(chopped[0].fW, dChopped[0].fWeight));
  39. SkASSERT(roughly_equal(chopped[1].fW, dChopped[1].fWeight));
  40. for (int cIndex = 0; cIndex < 2; ++cIndex) {
  41. for (int pIndex = 0; pIndex < 3; ++pIndex) {
  42. SkDPoint up;
  43. up.set(chopped[cIndex].fPts[pIndex]);
  44. SkASSERT(dChopped[cIndex].fPts[pIndex].approximatelyEqual(up));
  45. }
  46. }
  47. #if DEBUG_VISUALIZE_CONICS
  48. dChopped[0].dump();
  49. dChopped[1].dump();
  50. #endif
  51. }
  52. #include "include/core/SkBitmap.h"
  53. #include "include/core/SkCanvas.h"
  54. #include "include/core/SkImageEncoder.h"
  55. #include "include/core/SkPaint.h"
  56. #include "include/core/SkString.h"
  57. #include "src/pathops/SkPathOpsRect.h"
  58. #define DEBUG_VISUALIZE_CONICS 0
  59. #if DEBUG_VISUALIZE_CONICS
  60. static void writePng(const SkConic& c, const SkConic ch[2], const char* name) {
  61. const int scale = 10;
  62. SkConic conic, chopped[2];
  63. for (int index = 0; index < 3; ++index) {
  64. conic.fPts[index].fX = c.fPts[index].fX * scale;
  65. conic.fPts[index].fY = c.fPts[index].fY * scale;
  66. for (int chIndex = 0; chIndex < 2; ++chIndex) {
  67. chopped[chIndex].fPts[index].fX = ch[chIndex].fPts[index].fX * scale;
  68. chopped[chIndex].fPts[index].fY = ch[chIndex].fPts[index].fY * scale;
  69. }
  70. }
  71. conic.fW = c.fW;
  72. chopped[0].fW = ch[0].fW;
  73. chopped[1].fW = ch[1].fW;
  74. SkBitmap bitmap;
  75. SkRect bounds;
  76. conic.computeTightBounds(&bounds);
  77. bounds.outset(10, 10);
  78. bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
  79. SkScalarRoundToInt(bounds.width()), SkScalarRoundToInt(bounds.height())));
  80. SkCanvas canvas(bitmap);
  81. SkPaint paint;
  82. paint.setAntiAlias(true);
  83. paint.setStyle(SkPaint::kStroke_Style);
  84. canvas.translate(-bounds.fLeft, -bounds.fTop);
  85. canvas.drawColor(SK_ColorWHITE);
  86. SkPath path;
  87. path.moveTo(conic.fPts[0]);
  88. path.conicTo(conic.fPts[1], conic.fPts[2], conic.fW);
  89. paint.setARGB(0x80, 0xFF, 0, 0);
  90. canvas.drawPath(path, paint);
  91. path.reset();
  92. path.moveTo(chopped[0].fPts[0]);
  93. path.conicTo(chopped[0].fPts[1], chopped[0].fPts[2], chopped[0].fW);
  94. path.moveTo(chopped[1].fPts[0]);
  95. path.conicTo(chopped[1].fPts[1], chopped[1].fPts[2], chopped[1].fW);
  96. paint.setARGB(0x80, 0, 0, 0xFF);
  97. canvas.drawPath(path, paint);
  98. SkString filename("c:\\Users\\caryclark\\Documents\\");
  99. filename.appendf("%s.png", name);
  100. ToolUtils::EncodeImageToFile(filename.c_str(), bitmap, SkEncodedImageFormat::kPNG, 100);
  101. }
  102. static void writeDPng(const SkDConic& dC, const char* name) {
  103. const int scale = 5;
  104. SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
  105. {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
  106. {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
  107. SkBitmap bitmap;
  108. SkDRect bounds;
  109. bounds.setBounds(dConic);
  110. bounds.fLeft -= 10;
  111. bounds.fTop -= 10;
  112. bounds.fRight += 10;
  113. bounds.fBottom += 10;
  114. bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
  115. SkScalarRoundToInt(SkDoubleToScalar(bounds.width())),
  116. SkScalarRoundToInt(SkDoubleToScalar(bounds.height()))));
  117. SkCanvas canvas(bitmap);
  118. SkPaint paint;
  119. paint.setAntiAlias(true);
  120. paint.setStyle(SkPaint::kStroke_Style);
  121. canvas.translate(SkDoubleToScalar(-bounds.fLeft), SkDoubleToScalar(-bounds.fTop));
  122. canvas.drawColor(SK_ColorWHITE);
  123. SkPath path;
  124. path.moveTo(dConic.fPts[0].asSkPoint());
  125. path.conicTo(dConic.fPts[1].asSkPoint(), dConic.fPts[2].asSkPoint(), dConic.fWeight);
  126. paint.setARGB(0x80, 0xFF, 0, 0);
  127. canvas.drawPath(path, paint);
  128. path.reset();
  129. const int chops = 2;
  130. for (int tIndex = 0; tIndex < chops; ++tIndex) {
  131. SkDConic chopped = dConic.subDivide(tIndex / (double) chops,
  132. (tIndex + 1) / (double) chops);
  133. path.moveTo(chopped.fPts[0].asSkPoint());
  134. path.conicTo(chopped.fPts[1].asSkPoint(), chopped.fPts[2].asSkPoint(), chopped.fWeight);
  135. }
  136. paint.setARGB(0x80, 0, 0, 0xFF);
  137. canvas.drawPath(path, paint);
  138. SkString filename("c:\\Users\\caryclark\\Documents\\");
  139. filename.appendf("%s.png", name);
  140. ToolUtils::EncodeImageToFile(filename.c_str(), bitmap, SkEncodedImageFormat::kPNG, 100);
  141. }
  142. #endif
  143. static void chopBothWays(const SkDConic& dConic, double t, const char* name) {
  144. SkConic conic;
  145. for (int index = 0; index < 3; ++index) {
  146. conic.fPts[index] = dConic.fPts[index].asSkPoint();
  147. }
  148. conic.fW = dConic.fWeight;
  149. SkConic chopped[2];
  150. SkDConic dChopped[2];
  151. if (!conic.chopAt(SkDoubleToScalar(t), chopped)) {
  152. return;
  153. }
  154. dChopped[0] = dConic.subDivide(0, t);
  155. dChopped[1] = dConic.subDivide(t, 1);
  156. #if DEBUG_VISUALIZE_CONICS
  157. dConic.dump();
  158. #endif
  159. chopCompare(chopped, dChopped);
  160. #if DEBUG_VISUALIZE_CONICS
  161. writePng(conic, chopped, name);
  162. #endif
  163. }
  164. #if DEBUG_VISUALIZE_CONICS
  165. const SkDConic frame0[] = {
  166. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  167. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  168. };
  169. const SkDConic frame1[] = {
  170. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  171. {{{{306.58801299999999, -227.983994}, {212.46499600000001, -262.24200400000001}, {95.551200899999998, 58.976398500000002}}}, 0.707107008f},
  172. {{{{377.21899400000001, -141.98100299999999}, {237.77799285476553, -166.56830755921084}, {134.08399674208422, -155.06258330544892}}}, 0.788580656f},
  173. {{{{134.08399674208422, -155.06258330544892}, {30.390000629402859, -143.55685905168704}, {23.185499199999999, -102.697998}}}, 0.923879623f},
  174. };
  175. const SkDConic frame2[] = {
  176. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  177. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  178. {{{{205.78973252799028, -158.12538713371103}, {143.97848953841861, -74.076645245042371}, {95.551200899999998, 58.976398500000002}}}, 0.923879623f},
  179. {{{{377.21899400000001, -141.98100299999999}, {237.77799285476553, -166.56830755921084}, {134.08399674208422, -155.06258330544892}}}, 0.788580656f},
  180. };
  181. const SkDConic frame3[] = {
  182. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  183. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  184. {{{{205.78973252799028, -158.12538713371103}, {143.97848953841861, -74.076645245042371}, {95.551200899999998, 58.976398500000002}}}, 0.923879623f},
  185. {{{{252.08225670812539, -156.90491625851064}, {185.93099479842493, -160.81544543232982}, {134.08399674208422, -155.06258330544892}}}, 0.835816324f},
  186. };
  187. const SkDConic frame4[] = {
  188. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  189. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  190. {{{{205.78973252799028, -158.12538713371103}, {174.88411103320448, -116.10101618937664}, {145.19509369736275, -56.857102571363754}}}, 0.871667147f},
  191. {{{{252.08225670812539, -156.90491625851064}, {185.93099479842493, -160.81544543232982}, {134.08399674208422, -155.06258330544892}}}, 0.835816324f},
  192. };
  193. const SkDConic frame5[] = {
  194. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  195. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  196. {{{{205.78973252799028, -158.12538713371103}, {174.88411103320448, -116.10101618937664}, {145.19509369736275, -56.857102571363754}}}, 0.871667147f},
  197. {{{{252.08225670812539, -156.90491625851064}, {219.70109133058406, -158.81912754088933}, {190.17095392508796, -158.38373974664466}}}, 0.858306944f},
  198. };
  199. const SkDConic frame6[] = {
  200. {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
  201. {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
  202. {{{{205.78973252799028, -158.12538713371103}, {190.33692178059735, -137.11320166154385}, {174.87004877564593, -111.2132534799228}}}, 0.858117759f},
  203. {{{{252.08225670812539, -156.90491625851064}, {219.70109133058406, -158.81912754088933}, {190.17095392508796, -158.38373974664466}}}, 0.858306944f},
  204. };
  205. const SkDConic* frames[] = {
  206. frame0, frame1, frame2, frame3, frame4, frame5, frame6
  207. };
  208. const int frameSizes[] = { (int) SK_ARRAY_COUNT(frame0), (int) SK_ARRAY_COUNT(frame1),
  209. (int) SK_ARRAY_COUNT(frame2), (int) SK_ARRAY_COUNT(frame3),
  210. (int) SK_ARRAY_COUNT(frame4), (int) SK_ARRAY_COUNT(frame5),
  211. (int) SK_ARRAY_COUNT(frame6),
  212. };
  213. static void writeFrames() {
  214. const int scale = 5;
  215. for (int index = 0; index < (int) SK_ARRAY_COUNT(frameSizes); ++index) {
  216. SkDRect bounds;
  217. bool boundsSet = false;
  218. int frameSize = frameSizes[index];
  219. for (int fIndex = 0; fIndex < frameSize; ++fIndex) {
  220. const SkDConic& dC = frames[index][fIndex];
  221. SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
  222. {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
  223. {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
  224. SkDRect dBounds;
  225. dBounds.setBounds(dConic);
  226. if (!boundsSet) {
  227. bounds = dBounds;
  228. boundsSet = true;
  229. } else {
  230. bounds.add((SkDPoint&) dBounds.fLeft);
  231. bounds.add((SkDPoint&) dBounds.fRight);
  232. }
  233. }
  234. bounds.fLeft -= 10;
  235. bounds.fTop -= 10;
  236. bounds.fRight += 10;
  237. bounds.fBottom += 10;
  238. SkBitmap bitmap;
  239. bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
  240. SkScalarRoundToInt(SkDoubleToScalar(bounds.width())),
  241. SkScalarRoundToInt(SkDoubleToScalar(bounds.height()))));
  242. SkCanvas canvas(bitmap);
  243. SkPaint paint;
  244. paint.setAntiAlias(true);
  245. paint.setStyle(SkPaint::kStroke_Style);
  246. canvas.translate(SkDoubleToScalar(-bounds.fLeft), SkDoubleToScalar(-bounds.fTop));
  247. canvas.drawColor(SK_ColorWHITE);
  248. for (int fIndex = 0; fIndex < frameSize; ++fIndex) {
  249. const SkDConic& dC = frames[index][fIndex];
  250. SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
  251. {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
  252. {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
  253. SkPath path;
  254. path.moveTo(dConic.fPts[0].asSkPoint());
  255. path.conicTo(dConic.fPts[1].asSkPoint(), dConic.fPts[2].asSkPoint(), dConic.fWeight);
  256. if (fIndex < 2) {
  257. paint.setARGB(0x80, 0xFF, 0, 0);
  258. } else {
  259. paint.setARGB(0x80, 0, 0, 0xFF);
  260. }
  261. canvas.drawPath(path, paint);
  262. }
  263. SkString filename("c:\\Users\\caryclark\\Documents\\");
  264. filename.appendf("f%d.png", index);
  265. ToolUtils::EncodeImageToFile(filename.c_str(), bitmap, SkEncodedImageFormat::kPNG, 100);
  266. }
  267. }
  268. #endif
  269. static void oneOff(skiatest::Reporter* reporter, const ConicPts& conic1, const ConicPts& conic2,
  270. bool coin) {
  271. #if DEBUG_VISUALIZE_CONICS
  272. writeFrames();
  273. #endif
  274. SkDConic c1, c2;
  275. c1.debugSet(conic1.fPts.fPts, conic1.fWeight);
  276. c2.debugSet(conic2.fPts.fPts, conic2.fWeight);
  277. chopBothWays(c1, 0.5, "c1");
  278. chopBothWays(c2, 0.5, "c2");
  279. #if DEBUG_VISUALIZE_CONICS
  280. writeDPng(c1, "d1");
  281. writeDPng(c2, "d2");
  282. #endif
  283. SkASSERT(ValidConic(c1));
  284. SkASSERT(ValidConic(c2));
  285. SkIntersections intersections;
  286. intersections.intersect(c1, c2);
  287. if (coin && intersections.used() != 2) {
  288. SkDebugf("");
  289. }
  290. REPORTER_ASSERT(reporter, !coin || intersections.used() == 2);
  291. double tt1, tt2;
  292. SkDPoint xy1, xy2;
  293. for (int pt3 = 0; pt3 < intersections.used(); ++pt3) {
  294. tt1 = intersections[0][pt3];
  295. xy1 = c1.ptAtT(tt1);
  296. tt2 = intersections[1][pt3];
  297. xy2 = c2.ptAtT(tt2);
  298. const SkDPoint& iPt = intersections.pt(pt3);
  299. REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt));
  300. REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt));
  301. REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
  302. }
  303. reporter->bumpTestCount();
  304. }
  305. static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
  306. const ConicPts& c1 = testSet[outer];
  307. const ConicPts& c2 = testSet[inner];
  308. oneOff(reporter, c1, c2, false);
  309. }
  310. static void oneOffTests(skiatest::Reporter* reporter) {
  311. for (int outer = 0; outer < testSetCount - 1; ++outer) {
  312. for (int inner = outer + 1; inner < testSetCount; ++inner) {
  313. oneOff(reporter, outer, inner);
  314. }
  315. }
  316. }
  317. DEF_TEST(PathOpsConicIntersectionOneOff, reporter) {
  318. oneOff(reporter, 0, 1);
  319. }
  320. DEF_TEST(PathOpsConicIntersection, reporter) {
  321. oneOffTests(reporter);
  322. }