SkReduceOrder.cpp 8.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283
  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/SkGeometry.h"
  8. #include "src/pathops/SkReduceOrder.h"
  9. int SkReduceOrder::reduce(const SkDLine& line) {
  10. fLine[0] = line[0];
  11. int different = line[0] != line[1];
  12. fLine[1] = line[different];
  13. return 1 + different;
  14. }
  15. static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
  16. reduction[0] = reduction[1] = quad[0];
  17. return 1;
  18. }
  19. static int reductionLineCount(const SkDQuad& reduction) {
  20. return 1 + !reduction[0].approximatelyEqual(reduction[1]);
  21. }
  22. static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
  23. reduction[0] = quad[0];
  24. reduction[1] = quad[2];
  25. return reductionLineCount(reduction);
  26. }
  27. static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
  28. reduction[0] = quad[0];
  29. reduction[1] = quad[2];
  30. return reductionLineCount(reduction);
  31. }
  32. static int check_linear(const SkDQuad& quad,
  33. int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
  34. if (!quad.isLinear(0, 2)) {
  35. return 0;
  36. }
  37. // four are colinear: return line formed by outside
  38. reduction[0] = quad[0];
  39. reduction[1] = quad[2];
  40. return reductionLineCount(reduction);
  41. }
  42. // reduce to a quadratic or smaller
  43. // look for identical points
  44. // look for all four points in a line
  45. // note that three points in a line doesn't simplify a cubic
  46. // look for approximation with single quadratic
  47. // save approximation with multiple quadratics for later
  48. int SkReduceOrder::reduce(const SkDQuad& quad) {
  49. int index, minX, maxX, minY, maxY;
  50. int minXSet, minYSet;
  51. minX = maxX = minY = maxY = 0;
  52. minXSet = minYSet = 0;
  53. for (index = 1; index < 3; ++index) {
  54. if (quad[minX].fX > quad[index].fX) {
  55. minX = index;
  56. }
  57. if (quad[minY].fY > quad[index].fY) {
  58. minY = index;
  59. }
  60. if (quad[maxX].fX < quad[index].fX) {
  61. maxX = index;
  62. }
  63. if (quad[maxY].fY < quad[index].fY) {
  64. maxY = index;
  65. }
  66. }
  67. for (index = 0; index < 3; ++index) {
  68. if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
  69. minXSet |= 1 << index;
  70. }
  71. if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
  72. minYSet |= 1 << index;
  73. }
  74. }
  75. if ((minXSet & 0x05) == 0x5 && (minYSet & 0x05) == 0x5) { // test for degenerate
  76. // this quad starts and ends at the same place, so never contributes
  77. // to the fill
  78. return coincident_line(quad, fQuad);
  79. }
  80. if (minXSet == 0x7) { // test for vertical line
  81. return vertical_line(quad, fQuad);
  82. }
  83. if (minYSet == 0x7) { // test for horizontal line
  84. return horizontal_line(quad, fQuad);
  85. }
  86. int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
  87. if (result) {
  88. return result;
  89. }
  90. fQuad = quad;
  91. return 3;
  92. }
  93. ////////////////////////////////////////////////////////////////////////////////////
  94. static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
  95. reduction[0] = reduction[1] = cubic[0];
  96. return 1;
  97. }
  98. static int reductionLineCount(const SkDCubic& reduction) {
  99. return 1 + !reduction[0].approximatelyEqual(reduction[1]);
  100. }
  101. static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
  102. reduction[0] = cubic[0];
  103. reduction[1] = cubic[3];
  104. return reductionLineCount(reduction);
  105. }
  106. static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
  107. reduction[0] = cubic[0];
  108. reduction[1] = cubic[3];
  109. return reductionLineCount(reduction);
  110. }
  111. // check to see if it is a quadratic or a line
  112. static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
  113. double dx10 = cubic[1].fX - cubic[0].fX;
  114. double dx23 = cubic[2].fX - cubic[3].fX;
  115. double midX = cubic[0].fX + dx10 * 3 / 2;
  116. double sideAx = midX - cubic[3].fX;
  117. double sideBx = dx23 * 3 / 2;
  118. if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
  119. : !AlmostEqualUlps_Pin(sideAx, sideBx)) {
  120. return 0;
  121. }
  122. double dy10 = cubic[1].fY - cubic[0].fY;
  123. double dy23 = cubic[2].fY - cubic[3].fY;
  124. double midY = cubic[0].fY + dy10 * 3 / 2;
  125. double sideAy = midY - cubic[3].fY;
  126. double sideBy = dy23 * 3 / 2;
  127. if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
  128. : !AlmostEqualUlps_Pin(sideAy, sideBy)) {
  129. return 0;
  130. }
  131. reduction[0] = cubic[0];
  132. reduction[1].fX = midX;
  133. reduction[1].fY = midY;
  134. reduction[2] = cubic[3];
  135. return 3;
  136. }
  137. static int check_linear(const SkDCubic& cubic,
  138. int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
  139. if (!cubic.isLinear(0, 3)) {
  140. return 0;
  141. }
  142. // four are colinear: return line formed by outside
  143. reduction[0] = cubic[0];
  144. reduction[1] = cubic[3];
  145. return reductionLineCount(reduction);
  146. }
  147. /* food for thought:
  148. http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
  149. Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
  150. corresponding quadratic Bezier are (given in convex combinations of
  151. points):
  152. q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
  153. q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
  154. q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
  155. Of course, this curve does not interpolate the end-points, but it would
  156. be interesting to see the behaviour of such a curve in an applet.
  157. --
  158. Kalle Rutanen
  159. http://kaba.hilvi.org
  160. */
  161. // reduce to a quadratic or smaller
  162. // look for identical points
  163. // look for all four points in a line
  164. // note that three points in a line doesn't simplify a cubic
  165. // look for approximation with single quadratic
  166. // save approximation with multiple quadratics for later
  167. int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
  168. int index, minX, maxX, minY, maxY;
  169. int minXSet, minYSet;
  170. minX = maxX = minY = maxY = 0;
  171. minXSet = minYSet = 0;
  172. for (index = 1; index < 4; ++index) {
  173. if (cubic[minX].fX > cubic[index].fX) {
  174. minX = index;
  175. }
  176. if (cubic[minY].fY > cubic[index].fY) {
  177. minY = index;
  178. }
  179. if (cubic[maxX].fX < cubic[index].fX) {
  180. maxX = index;
  181. }
  182. if (cubic[maxY].fY < cubic[index].fY) {
  183. maxY = index;
  184. }
  185. }
  186. for (index = 0; index < 4; ++index) {
  187. double cx = cubic[index].fX;
  188. double cy = cubic[index].fY;
  189. double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
  190. SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
  191. if (denom == 0) {
  192. minXSet |= 1 << index;
  193. minYSet |= 1 << index;
  194. continue;
  195. }
  196. double inv = 1 / denom;
  197. if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
  198. minXSet |= 1 << index;
  199. }
  200. if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
  201. minYSet |= 1 << index;
  202. }
  203. }
  204. if (minXSet == 0xF) { // test for vertical line
  205. if (minYSet == 0xF) { // return 1 if all four are coincident
  206. return coincident_line(cubic, fCubic);
  207. }
  208. return vertical_line(cubic, fCubic);
  209. }
  210. if (minYSet == 0xF) { // test for horizontal line
  211. return horizontal_line(cubic, fCubic);
  212. }
  213. int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
  214. if (result) {
  215. return result;
  216. }
  217. if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
  218. && (result = check_quadratic(cubic, fCubic))) {
  219. return result;
  220. }
  221. fCubic = cubic;
  222. return 4;
  223. }
  224. SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
  225. SkDQuad quad;
  226. quad.set(a);
  227. SkReduceOrder reducer;
  228. int order = reducer.reduce(quad);
  229. if (order == 2) { // quad became line
  230. for (int index = 0; index < order; ++index) {
  231. *reducePts++ = reducer.fLine[index].asSkPoint();
  232. }
  233. }
  234. return SkPathOpsPointsToVerb(order - 1);
  235. }
  236. SkPath::Verb SkReduceOrder::Conic(const SkConic& c, SkPoint* reducePts) {
  237. SkPath::Verb verb = SkReduceOrder::Quad(c.fPts, reducePts);
  238. if (verb > SkPath::kLine_Verb && c.fW == 1) {
  239. return SkPath::kQuad_Verb;
  240. }
  241. return verb == SkPath::kQuad_Verb ? SkPath::kConic_Verb : verb;
  242. }
  243. SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
  244. if (SkDPoint::ApproximatelyEqual(a[0], a[1]) && SkDPoint::ApproximatelyEqual(a[0], a[2])
  245. && SkDPoint::ApproximatelyEqual(a[0], a[3])) {
  246. reducePts[0] = a[0];
  247. return SkPath::kMove_Verb;
  248. }
  249. SkDCubic cubic;
  250. cubic.set(a);
  251. SkReduceOrder reducer;
  252. int order = reducer.reduce(cubic, kAllow_Quadratics);
  253. if (order == 2 || order == 3) { // cubic became line or quad
  254. for (int index = 0; index < order; ++index) {
  255. *reducePts++ = reducer.fQuad[index].asSkPoint();
  256. }
  257. }
  258. return SkPathOpsPointsToVerb(order - 1);
  259. }