SkPathOpsCurve.cpp 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145
  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/SkPathOpsBounds.h"
  8. #include "src/pathops/SkPathOpsCurve.h"
  9. #include "src/pathops/SkPathOpsRect.h"
  10. // this cheats and assumes that the perpendicular to the point is the closest ray to the curve
  11. // this case (where the line and the curve are nearly coincident) may be the only case that counts
  12. double SkDCurve::nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const {
  13. int count = SkPathOpsVerbToPoints(verb);
  14. double minX = fCubic.fPts[0].fX;
  15. double maxX = minX;
  16. for (int index = 1; index <= count; ++index) {
  17. minX = SkTMin(minX, fCubic.fPts[index].fX);
  18. maxX = SkTMax(maxX, fCubic.fPts[index].fX);
  19. }
  20. if (!AlmostBetweenUlps(minX, xy.fX, maxX)) {
  21. return -1;
  22. }
  23. double minY = fCubic.fPts[0].fY;
  24. double maxY = minY;
  25. for (int index = 1; index <= count; ++index) {
  26. minY = SkTMin(minY, fCubic.fPts[index].fY);
  27. maxY = SkTMax(maxY, fCubic.fPts[index].fY);
  28. }
  29. if (!AlmostBetweenUlps(minY, xy.fY, maxY)) {
  30. return -1;
  31. }
  32. SkIntersections i;
  33. SkDLine perp = {{ xy, { xy.fX + opp.fY - xy.fY, xy.fY + xy.fX - opp.fX }}};
  34. (*CurveDIntersectRay[verb])(*this, perp, &i);
  35. int minIndex = -1;
  36. double minDist = FLT_MAX;
  37. for (int index = 0; index < i.used(); ++index) {
  38. double dist = xy.distance(i.pt(index));
  39. if (minDist > dist) {
  40. minDist = dist;
  41. minIndex = index;
  42. }
  43. }
  44. if (minIndex < 0) {
  45. return -1;
  46. }
  47. double largest = SkTMax(SkTMax(maxX, maxY), -SkTMin(minX, minY));
  48. if (!AlmostEqualUlps_Pin(largest, largest + minDist)) { // is distance within ULPS tolerance?
  49. return -1;
  50. }
  51. return SkPinT(i[0][minIndex]);
  52. }
  53. void SkDCurve::offset(SkPath::Verb verb, const SkDVector& off) {
  54. int count = SkPathOpsVerbToPoints(verb);
  55. for (int index = 0; index <= count; ++index) {
  56. fCubic.fPts[index] += off;
  57. }
  58. }
  59. void SkDCurve::setConicBounds(const SkPoint curve[3], SkScalar curveWeight,
  60. double tStart, double tEnd, SkPathOpsBounds* bounds) {
  61. SkDConic dCurve;
  62. dCurve.set(curve, curveWeight);
  63. SkDRect dRect;
  64. dRect.setBounds(dCurve, fConic, tStart, tEnd);
  65. bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
  66. SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
  67. }
  68. void SkDCurve::setCubicBounds(const SkPoint curve[4], SkScalar ,
  69. double tStart, double tEnd, SkPathOpsBounds* bounds) {
  70. SkDCubic dCurve;
  71. dCurve.set(curve);
  72. SkDRect dRect;
  73. dRect.setBounds(dCurve, fCubic, tStart, tEnd);
  74. bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
  75. SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
  76. }
  77. void SkDCurve::setQuadBounds(const SkPoint curve[3], SkScalar ,
  78. double tStart, double tEnd, SkPathOpsBounds* bounds) {
  79. SkDQuad dCurve;
  80. dCurve.set(curve);
  81. SkDRect dRect;
  82. dRect.setBounds(dCurve, fQuad, tStart, tEnd);
  83. bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
  84. SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
  85. }
  86. void SkDCurveSweep::setCurveHullSweep(SkPath::Verb verb) {
  87. fOrdered = true;
  88. fSweep[0] = fCurve[1] - fCurve[0];
  89. if (SkPath::kLine_Verb == verb) {
  90. fSweep[1] = fSweep[0];
  91. fIsCurve = false;
  92. return;
  93. }
  94. fSweep[1] = fCurve[2] - fCurve[0];
  95. // OPTIMIZE: I do the following float check a lot -- probably need a
  96. // central place for this val-is-small-compared-to-curve check
  97. double maxVal = 0;
  98. for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
  99. maxVal = SkTMax(maxVal, SkTMax(SkTAbs(fCurve[index].fX),
  100. SkTAbs(fCurve[index].fY)));
  101. }
  102. {
  103. if (SkPath::kCubic_Verb != verb) {
  104. if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
  105. && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
  106. fSweep[0] = fSweep[1];
  107. }
  108. goto setIsCurve;
  109. }
  110. SkDVector thirdSweep = fCurve[3] - fCurve[0];
  111. if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
  112. fSweep[0] = fSweep[1];
  113. fSweep[1] = thirdSweep;
  114. if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
  115. && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
  116. fSweep[0] = fSweep[1];
  117. fCurve[1] = fCurve[3];
  118. }
  119. goto setIsCurve;
  120. }
  121. double s1x3 = fSweep[0].crossCheck(thirdSweep);
  122. double s3x2 = thirdSweep.crossCheck(fSweep[1]);
  123. if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors
  124. goto setIsCurve;
  125. }
  126. double s2x1 = fSweep[1].crossCheck(fSweep[0]);
  127. // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
  128. // probably such wide sweeps should be artificially subdivided earlier so that never happens
  129. SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
  130. if (s3x2 * s2x1 < 0) {
  131. SkASSERT(s2x1 * s1x3 > 0);
  132. fSweep[0] = fSweep[1];
  133. fOrdered = false;
  134. }
  135. fSweep[1] = thirdSweep;
  136. }
  137. setIsCurve:
  138. fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0;
  139. }