PathOpsCubicReduceOrderTest.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262
  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/pathops/SkIntersections.h"
  8. #include "src/pathops/SkPathOpsRect.h"
  9. #include "src/pathops/SkReduceOrder.h"
  10. #include "tests/PathOpsCubicIntersectionTestData.h"
  11. #include "tests/PathOpsQuadIntersectionTestData.h"
  12. #include "tests/PathOpsTestCommon.h"
  13. #include "tests/Test.h"
  14. #if 0 // disable test until stroke reduction is supported
  15. static bool controls_inside(const SkDCubic& cubic) {
  16. return between(cubic[0].fX, cubic[1].fX, cubic[3].fX)
  17. && between(cubic[0].fX, cubic[2].fX, cubic[3].fX)
  18. && between(cubic[0].fY, cubic[1].fY, cubic[3].fY)
  19. && between(cubic[0].fY, cubic[2].fY, cubic[3].fY);
  20. }
  21. static bool tiny(const SkDCubic& cubic) {
  22. int index, minX, maxX, minY, maxY;
  23. minX = maxX = minY = maxY = 0;
  24. for (index = 1; index < 4; ++index) {
  25. if (cubic[minX].fX > cubic[index].fX) {
  26. minX = index;
  27. }
  28. if (cubic[minY].fY > cubic[index].fY) {
  29. minY = index;
  30. }
  31. if (cubic[maxX].fX < cubic[index].fX) {
  32. maxX = index;
  33. }
  34. if (cubic[maxY].fY < cubic[index].fY) {
  35. maxY = index;
  36. }
  37. }
  38. return approximately_equal(cubic[maxX].fX, cubic[minX].fX)
  39. && approximately_equal(cubic[maxY].fY, cubic[minY].fY);
  40. }
  41. static void find_tight_bounds(const SkDCubic& cubic, SkDRect& bounds) {
  42. SkDCubicPair cubicPair = cubic.chopAt(0.5);
  43. if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
  44. find_tight_bounds(cubicPair.first(), bounds);
  45. } else {
  46. bounds.add(cubicPair.first()[0]);
  47. bounds.add(cubicPair.first()[3]);
  48. }
  49. if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
  50. find_tight_bounds(cubicPair.second(), bounds);
  51. } else {
  52. bounds.add(cubicPair.second()[0]);
  53. bounds.add(cubicPair.second()[3]);
  54. }
  55. }
  56. #endif
  57. DEF_TEST(PathOpsReduceOrderCubic, reporter) {
  58. size_t index;
  59. SkReduceOrder reducer;
  60. int order;
  61. enum {
  62. RunAll,
  63. RunPointDegenerates,
  64. RunNotPointDegenerates,
  65. RunLines,
  66. RunNotLines,
  67. RunModEpsilonLines,
  68. RunLessEpsilonLines,
  69. RunNegEpsilonLines,
  70. RunQuadraticLines,
  71. RunQuadraticPoints,
  72. RunQuadraticModLines,
  73. RunComputedLines,
  74. RunNone
  75. } run = RunAll;
  76. int firstTestIndex = 0;
  77. #if 0
  78. run = RunComputedLines;
  79. firstTestIndex = 18;
  80. #endif
  81. int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates
  82. ? firstTestIndex : SK_MaxS32;
  83. int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates
  84. ? firstTestIndex : SK_MaxS32;
  85. int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
  86. int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
  87. int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines
  88. ? firstTestIndex : SK_MaxS32;
  89. int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines
  90. ? firstTestIndex : SK_MaxS32;
  91. int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines
  92. ? firstTestIndex : SK_MaxS32;
  93. int firstQuadraticPointTest = run == RunAll ? 0 : run == RunQuadraticPoints
  94. ? firstTestIndex : SK_MaxS32;
  95. int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines
  96. ? firstTestIndex : SK_MaxS32;
  97. int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines
  98. ? firstTestIndex : SK_MaxS32;
  99. #if 0
  100. int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
  101. ? firstTestIndex : SK_MaxS32;
  102. #endif
  103. for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
  104. const CubicPts& c = pointDegenerates[index];
  105. SkDCubic cubic;
  106. cubic.debugSet(c.fPts);
  107. SkASSERT(ValidCubic(cubic));
  108. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  109. if (order != 1) {
  110. SkDebugf("[%d] pointDegenerates order=%d\n", static_cast<int>(index), order);
  111. REPORTER_ASSERT(reporter, 0);
  112. }
  113. }
  114. for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
  115. const CubicPts& c = notPointDegenerates[index];
  116. SkDCubic cubic;
  117. cubic.debugSet(c.fPts);
  118. SkASSERT(ValidCubic(cubic));
  119. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  120. if (order == 1) {
  121. SkDebugf("[%d] notPointDegenerates order=%d\n", static_cast<int>(index), order);
  122. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  123. REPORTER_ASSERT(reporter, 0);
  124. }
  125. }
  126. for (index = firstLinesTest; index < lines_count; ++index) {
  127. const CubicPts& c = lines[index];
  128. SkDCubic cubic;
  129. cubic.debugSet(c.fPts);
  130. SkASSERT(ValidCubic(cubic));
  131. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  132. if (order != 2) {
  133. SkDebugf("[%d] lines order=%d\n", static_cast<int>(index), order);
  134. REPORTER_ASSERT(reporter, 0);
  135. }
  136. }
  137. for (index = firstNotLinesTest; index < notLines_count; ++index) {
  138. const CubicPts& c = notLines[index];
  139. SkDCubic cubic;
  140. cubic.debugSet(c.fPts);
  141. SkASSERT(ValidCubic(cubic));
  142. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  143. if (order == 2) {
  144. SkDebugf("[%d] notLines order=%d\n", static_cast<int>(index), order);
  145. REPORTER_ASSERT(reporter, 0);
  146. }
  147. }
  148. for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
  149. const CubicPts& c = modEpsilonLines[index];
  150. SkDCubic cubic;
  151. cubic.debugSet(c.fPts);
  152. SkASSERT(ValidCubic(cubic));
  153. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  154. if (order == 2) {
  155. SkDebugf("[%d] line mod by epsilon order=%d\n", static_cast<int>(index), order);
  156. REPORTER_ASSERT(reporter, 0);
  157. }
  158. }
  159. for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
  160. const CubicPts& c = lessEpsilonLines[index];
  161. SkDCubic cubic;
  162. cubic.debugSet(c.fPts);
  163. SkASSERT(ValidCubic(cubic));
  164. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  165. if (order != 2) {
  166. SkDebugf("[%d] line less by epsilon/2 order=%d\n", static_cast<int>(index), order);
  167. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  168. REPORTER_ASSERT(reporter, 0);
  169. }
  170. }
  171. for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
  172. const CubicPts& c = negEpsilonLines[index];
  173. SkDCubic cubic;
  174. cubic.debugSet(c.fPts);
  175. SkASSERT(ValidCubic(cubic));
  176. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  177. if (order != 2) {
  178. SkDebugf("[%d] line neg by epsilon/2 order=%d\n", static_cast<int>(index), order);
  179. REPORTER_ASSERT(reporter, 0);
  180. }
  181. }
  182. for (index = firstQuadraticPointTest; index < quadraticPoints_count; ++index) {
  183. const QuadPts& q = quadraticPoints[index];
  184. SkDQuad quad;
  185. quad.debugSet(q.fPts);
  186. SkASSERT(ValidQuad(quad));
  187. SkDCubic cubic = quad.debugToCubic();
  188. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  189. if (order != 1) {
  190. SkDebugf("[%d] point quad order=%d\n", static_cast<int>(index), order);
  191. REPORTER_ASSERT(reporter, 0);
  192. }
  193. }
  194. for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
  195. const QuadPts& q = quadraticLines[index];
  196. SkDQuad quad;
  197. quad.debugSet(q.fPts);
  198. SkASSERT(ValidQuad(quad));
  199. SkDCubic cubic = quad.debugToCubic();
  200. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  201. if (order != 2) {
  202. SkDebugf("[%d] line quad order=%d\n", static_cast<int>(index), order);
  203. REPORTER_ASSERT(reporter, 0);
  204. }
  205. }
  206. for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
  207. const QuadPts& q = quadraticModEpsilonLines[index];
  208. SkDQuad quad;
  209. quad.debugSet(q.fPts);
  210. SkASSERT(ValidQuad(quad));
  211. SkDCubic cubic = quad.debugToCubic();
  212. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics);
  213. if (order != 3) {
  214. SkDebugf("[%d] line mod quad order=%d\n", static_cast<int>(index), order);
  215. REPORTER_ASSERT(reporter, 0);
  216. }
  217. }
  218. #if 0 // disable test until stroke reduction is supported
  219. // test if computed line end points are valid
  220. for (index = firstComputedLinesTest; index < lines_count; ++index) {
  221. const SkDCubic& cubic = lines[index];
  222. SkASSERT(ValidCubic(cubic));
  223. bool controlsInside = controls_inside(cubic);
  224. order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics,
  225. SkReduceOrder::kStroke_Style);
  226. if (order == 2 && reducer.fLine[0] == reducer.fLine[1]) {
  227. SkDebugf("[%d] line computed ends match order=%d\n", static_cast<int>(index), order);
  228. REPORTER_ASSERT(reporter, 0);
  229. }
  230. if (controlsInside) {
  231. if ( (reducer.fLine[0].fX != cubic[0].fX && reducer.fLine[0].fX != cubic[3].fX)
  232. || (reducer.fLine[0].fY != cubic[0].fY && reducer.fLine[0].fY != cubic[3].fY)
  233. || (reducer.fLine[1].fX != cubic[0].fX && reducer.fLine[1].fX != cubic[3].fX)
  234. || (reducer.fLine[1].fY != cubic[0].fY && reducer.fLine[1].fY != cubic[3].fY)) {
  235. SkDebugf("[%d] line computed ends order=%d\n", static_cast<int>(index), order);
  236. REPORTER_ASSERT(reporter, 0);
  237. }
  238. } else {
  239. // binary search for extrema, compare against actual results
  240. // while a control point is outside of bounding box formed by end points, split
  241. SkDRect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
  242. find_tight_bounds(cubic, bounds);
  243. if ( (!AlmostEqualUlps(reducer.fLine[0].fX, bounds.fLeft)
  244. && !AlmostEqualUlps(reducer.fLine[0].fX, bounds.fRight))
  245. || (!AlmostEqualUlps(reducer.fLine[0].fY, bounds.fTop)
  246. && !AlmostEqualUlps(reducer.fLine[0].fY, bounds.fBottom))
  247. || (!AlmostEqualUlps(reducer.fLine[1].fX, bounds.fLeft)
  248. && !AlmostEqualUlps(reducer.fLine[1].fX, bounds.fRight))
  249. || (!AlmostEqualUlps(reducer.fLine[1].fY, bounds.fTop)
  250. && !AlmostEqualUlps(reducer.fLine[1].fY, bounds.fBottom))) {
  251. SkDebugf("[%d] line computed tight bounds order=%d\n", static_cast<int>(index), order);
  252. REPORTER_ASSERT(reporter, 0);
  253. }
  254. }
  255. }
  256. #endif
  257. }