SkPathOpsConic.cpp 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190
  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/pathops/SkIntersections.h"
  8. #include "src/pathops/SkLineParameters.h"
  9. #include "src/pathops/SkPathOpsConic.h"
  10. #include "src/pathops/SkPathOpsCubic.h"
  11. #include "src/pathops/SkPathOpsQuad.h"
  12. #include "src/pathops/SkPathOpsRect.h"
  13. // cribbed from the float version in SkGeometry.cpp
  14. static void conic_deriv_coeff(const double src[],
  15. SkScalar w,
  16. double coeff[3]) {
  17. const double P20 = src[4] - src[0];
  18. const double P10 = src[2] - src[0];
  19. const double wP10 = w * P10;
  20. coeff[0] = w * P20 - P20;
  21. coeff[1] = P20 - 2 * wP10;
  22. coeff[2] = wP10;
  23. }
  24. static double conic_eval_tan(const double coord[], SkScalar w, double t) {
  25. double coeff[3];
  26. conic_deriv_coeff(coord, w, coeff);
  27. return t * (t * coeff[0] + coeff[1]) + coeff[2];
  28. }
  29. int SkDConic::FindExtrema(const double src[], SkScalar w, double t[1]) {
  30. double coeff[3];
  31. conic_deriv_coeff(src, w, coeff);
  32. double tValues[2];
  33. int roots = SkDQuad::RootsValidT(coeff[0], coeff[1], coeff[2], tValues);
  34. // In extreme cases, the number of roots returned can be 2. Pathops
  35. // will fail later on, so there's no advantage to plumbing in an error
  36. // return here.
  37. // SkASSERT(0 == roots || 1 == roots);
  38. if (1 == roots) {
  39. t[0] = tValues[0];
  40. return 1;
  41. }
  42. return 0;
  43. }
  44. SkDVector SkDConic::dxdyAtT(double t) const {
  45. SkDVector result = {
  46. conic_eval_tan(&fPts[0].fX, fWeight, t),
  47. conic_eval_tan(&fPts[0].fY, fWeight, t)
  48. };
  49. if (result.fX == 0 && result.fY == 0) {
  50. if (zero_or_one(t)) {
  51. result = fPts[2] - fPts[0];
  52. } else {
  53. // incomplete
  54. SkDebugf("!k");
  55. }
  56. }
  57. return result;
  58. }
  59. static double conic_eval_numerator(const double src[], SkScalar w, double t) {
  60. SkASSERT(src);
  61. SkASSERT(t >= 0 && t <= 1);
  62. double src2w = src[2] * w;
  63. double C = src[0];
  64. double A = src[4] - 2 * src2w + C;
  65. double B = 2 * (src2w - C);
  66. return (A * t + B) * t + C;
  67. }
  68. static double conic_eval_denominator(SkScalar w, double t) {
  69. double B = 2 * (w - 1);
  70. double C = 1;
  71. double A = -B;
  72. return (A * t + B) * t + C;
  73. }
  74. bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
  75. return cubic.hullIntersects(*this, isLinear);
  76. }
  77. SkDPoint SkDConic::ptAtT(double t) const {
  78. if (t == 0) {
  79. return fPts[0];
  80. }
  81. if (t == 1) {
  82. return fPts[2];
  83. }
  84. double denominator = conic_eval_denominator(fWeight, t);
  85. SkDPoint result = {
  86. sk_ieee_double_divide(conic_eval_numerator(&fPts[0].fX, fWeight, t), denominator),
  87. sk_ieee_double_divide(conic_eval_numerator(&fPts[0].fY, fWeight, t), denominator)
  88. };
  89. return result;
  90. }
  91. /* see quad subdivide for point rationale */
  92. /* w rationale : the mid point between t1 and t2 could be determined from the computed a/b/c
  93. values if the computed w was known. Since we know the mid point at (t1+t2)/2, we'll assume
  94. that it is the same as the point on the new curve t==(0+1)/2.
  95. d / dz == conic_poly(dst, unknownW, .5) / conic_weight(unknownW, .5);
  96. conic_poly(dst, unknownW, .5)
  97. = a / 4 + (b * unknownW) / 2 + c / 4
  98. = (a + c) / 4 + (bx * unknownW) / 2
  99. conic_weight(unknownW, .5)
  100. = unknownW / 2 + 1 / 2
  101. d / dz == ((a + c) / 2 + b * unknownW) / (unknownW + 1)
  102. d / dz * (unknownW + 1) == (a + c) / 2 + b * unknownW
  103. unknownW = ((a + c) / 2 - d / dz) / (d / dz - b)
  104. Thus, w is the ratio of the distance from the mid of end points to the on-curve point, and the
  105. distance of the on-curve point to the control point.
  106. */
  107. SkDConic SkDConic::subDivide(double t1, double t2) const {
  108. double ax, ay, az;
  109. if (t1 == 0) {
  110. ax = fPts[0].fX;
  111. ay = fPts[0].fY;
  112. az = 1;
  113. } else if (t1 != 1) {
  114. ax = conic_eval_numerator(&fPts[0].fX, fWeight, t1);
  115. ay = conic_eval_numerator(&fPts[0].fY, fWeight, t1);
  116. az = conic_eval_denominator(fWeight, t1);
  117. } else {
  118. ax = fPts[2].fX;
  119. ay = fPts[2].fY;
  120. az = 1;
  121. }
  122. double midT = (t1 + t2) / 2;
  123. double dx = conic_eval_numerator(&fPts[0].fX, fWeight, midT);
  124. double dy = conic_eval_numerator(&fPts[0].fY, fWeight, midT);
  125. double dz = conic_eval_denominator(fWeight, midT);
  126. double cx, cy, cz;
  127. if (t2 == 1) {
  128. cx = fPts[2].fX;
  129. cy = fPts[2].fY;
  130. cz = 1;
  131. } else if (t2 != 0) {
  132. cx = conic_eval_numerator(&fPts[0].fX, fWeight, t2);
  133. cy = conic_eval_numerator(&fPts[0].fY, fWeight, t2);
  134. cz = conic_eval_denominator(fWeight, t2);
  135. } else {
  136. cx = fPts[0].fX;
  137. cy = fPts[0].fY;
  138. cz = 1;
  139. }
  140. double bx = 2 * dx - (ax + cx) / 2;
  141. double by = 2 * dy - (ay + cy) / 2;
  142. double bz = 2 * dz - (az + cz) / 2;
  143. if (!bz) {
  144. bz = 1; // if bz is 0, weight is 0, control point has no effect: any value will do
  145. }
  146. SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}}
  147. SkDEBUGPARAMS(fPts.fDebugGlobalState) },
  148. SkDoubleToScalar(bz / sqrt(az * cz)) };
  149. return dst;
  150. }
  151. SkDPoint SkDConic::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2,
  152. SkScalar* weight) const {
  153. SkDConic chopped = this->subDivide(t1, t2);
  154. *weight = chopped.fWeight;
  155. return chopped[1];
  156. }
  157. int SkTConic::intersectRay(SkIntersections* i, const SkDLine& line) const {
  158. return i->intersectRay(fConic, line);
  159. }
  160. bool SkTConic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
  161. return quad.hullIntersects(fConic, isLinear);
  162. }
  163. bool SkTConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
  164. return cubic.hullIntersects(fConic, isLinear);
  165. }
  166. void SkTConic::setBounds(SkDRect* rect) const {
  167. rect->setBounds(fConic);
  168. }