SkCubicClipper.cpp 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  1. /*
  2. * Copyright 2009 The Android Open Source Project
  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/SkCubicClipper.h"
  8. #include "src/core/SkGeometry.h"
  9. #include <utility>
  10. SkCubicClipper::SkCubicClipper() {
  11. fClip.setEmpty();
  12. }
  13. void SkCubicClipper::setClip(const SkIRect& clip) {
  14. // conver to scalars, since that's where we'll see the points
  15. fClip.set(clip);
  16. }
  17. bool SkCubicClipper::ChopMonoAtY(const SkPoint pts[4], SkScalar y, SkScalar* t) {
  18. SkScalar ycrv[4];
  19. ycrv[0] = pts[0].fY - y;
  20. ycrv[1] = pts[1].fY - y;
  21. ycrv[2] = pts[2].fY - y;
  22. ycrv[3] = pts[3].fY - y;
  23. #ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations.
  24. // Initial guess.
  25. // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve
  26. // is not only monotonic but degenerate.
  27. SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]);
  28. // Newton's iterations.
  29. const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits.
  30. SkScalar t0;
  31. const int maxiters = 5;
  32. int iters = 0;
  33. bool converged;
  34. do {
  35. t0 = t1;
  36. SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0);
  37. SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0);
  38. SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0);
  39. SkScalar y012 = SkScalarInterp(y01, y12, t0);
  40. SkScalar y123 = SkScalarInterp(y12, y23, t0);
  41. SkScalar y0123 = SkScalarInterp(y012, y123, t0);
  42. SkScalar yder = (y123 - y012) * 3;
  43. // TODO(turk): check for yder==0: horizontal.
  44. t1 -= y0123 / yder;
  45. converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe
  46. ++iters;
  47. } while (!converged && (iters < maxiters));
  48. *t = t1; // Return the result.
  49. // The result might be valid, even if outside of the range [0, 1], but
  50. // we never evaluate a Bezier outside this interval, so we return false.
  51. if (t1 < 0 || t1 > SK_Scalar1)
  52. return false; // This shouldn't happen, but check anyway.
  53. return converged;
  54. #else // BISECTION // Linear convergence, typically 16 iterations.
  55. // Check that the endpoints straddle zero.
  56. SkScalar tNeg, tPos; // Negative and positive function parameters.
  57. if (ycrv[0] < 0) {
  58. if (ycrv[3] < 0)
  59. return false;
  60. tNeg = 0;
  61. tPos = SK_Scalar1;
  62. } else if (ycrv[0] > 0) {
  63. if (ycrv[3] > 0)
  64. return false;
  65. tNeg = SK_Scalar1;
  66. tPos = 0;
  67. } else {
  68. *t = 0;
  69. return true;
  70. }
  71. const SkScalar tol = SK_Scalar1 / 65536; // 1 for fixed, 1e-5 for float.
  72. int iters = 0;
  73. do {
  74. SkScalar tMid = (tPos + tNeg) / 2;
  75. SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], tMid);
  76. SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], tMid);
  77. SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], tMid);
  78. SkScalar y012 = SkScalarInterp(y01, y12, tMid);
  79. SkScalar y123 = SkScalarInterp(y12, y23, tMid);
  80. SkScalar y0123 = SkScalarInterp(y012, y123, tMid);
  81. if (y0123 == 0) {
  82. *t = tMid;
  83. return true;
  84. }
  85. if (y0123 < 0) tNeg = tMid;
  86. else tPos = tMid;
  87. ++iters;
  88. } while (!(SkScalarAbs(tPos - tNeg) <= tol)); // Nan-safe
  89. *t = (tNeg + tPos) / 2;
  90. return true;
  91. #endif // BISECTION
  92. }
  93. bool SkCubicClipper::clipCubic(const SkPoint srcPts[4], SkPoint dst[4]) {
  94. bool reverse;
  95. // we need the data to be monotonically descending in Y
  96. if (srcPts[0].fY > srcPts[3].fY) {
  97. dst[0] = srcPts[3];
  98. dst[1] = srcPts[2];
  99. dst[2] = srcPts[1];
  100. dst[3] = srcPts[0];
  101. reverse = true;
  102. } else {
  103. memcpy(dst, srcPts, 4 * sizeof(SkPoint));
  104. reverse = false;
  105. }
  106. // are we completely above or below
  107. const SkScalar ctop = fClip.fTop;
  108. const SkScalar cbot = fClip.fBottom;
  109. if (dst[3].fY <= ctop || dst[0].fY >= cbot) {
  110. return false;
  111. }
  112. SkScalar t;
  113. SkPoint tmp[7]; // for SkChopCubicAt
  114. // are we partially above
  115. if (dst[0].fY < ctop && ChopMonoAtY(dst, ctop, &t)) {
  116. SkChopCubicAt(dst, tmp, t);
  117. dst[0] = tmp[3];
  118. dst[1] = tmp[4];
  119. dst[2] = tmp[5];
  120. }
  121. // are we partially below
  122. if (dst[3].fY > cbot && ChopMonoAtY(dst, cbot, &t)) {
  123. SkChopCubicAt(dst, tmp, t);
  124. dst[1] = tmp[1];
  125. dst[2] = tmp[2];
  126. dst[3] = tmp[3];
  127. }
  128. if (reverse) {
  129. using std::swap;
  130. swap(dst[0], dst[3]);
  131. swap(dst[1], dst[2]);
  132. }
  133. return true;
  134. }