SkPathOpsLine.cpp 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149
  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/SkPathOpsLine.h"
  8. SkDPoint SkDLine::ptAtT(double t) const {
  9. if (0 == t) {
  10. return fPts[0];
  11. }
  12. if (1 == t) {
  13. return fPts[1];
  14. }
  15. double one_t = 1 - t;
  16. SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
  17. return result;
  18. }
  19. double SkDLine::exactPoint(const SkDPoint& xy) const {
  20. if (xy == fPts[0]) { // do cheapest test first
  21. return 0;
  22. }
  23. if (xy == fPts[1]) {
  24. return 1;
  25. }
  26. return -1;
  27. }
  28. double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const {
  29. if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
  30. || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
  31. return -1;
  32. }
  33. // project a perpendicular ray from the point to the line; find the T on the line
  34. SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
  35. double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
  36. SkDVector ab0 = xy - fPts[0];
  37. double numer = len.fX * ab0.fX + ab0.fY * len.fY;
  38. if (!between(0, numer, denom)) {
  39. return -1;
  40. }
  41. if (!denom) {
  42. return 0;
  43. }
  44. double t = numer / denom;
  45. SkDPoint realPt = ptAtT(t);
  46. double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
  47. // find the ordinal in the original line with the largest unsigned exponent
  48. double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
  49. double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
  50. largest = SkTMax(largest, -tiniest);
  51. if (!AlmostEqualUlps_Pin(largest, largest + dist)) { // is the dist within ULPS tolerance?
  52. return -1;
  53. }
  54. if (unequal) {
  55. *unequal = (float) largest != (float) (largest + dist);
  56. }
  57. t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3
  58. SkASSERT(between(0, t, 1));
  59. return t;
  60. }
  61. bool SkDLine::nearRay(const SkDPoint& xy) const {
  62. // project a perpendicular ray from the point to the line; find the T on the line
  63. SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
  64. double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
  65. SkDVector ab0 = xy - fPts[0];
  66. double numer = len.fX * ab0.fX + ab0.fY * len.fY;
  67. double t = numer / denom;
  68. SkDPoint realPt = ptAtT(t);
  69. double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
  70. // find the ordinal in the original line with the largest unsigned exponent
  71. double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
  72. double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
  73. largest = SkTMax(largest, -tiniest);
  74. return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
  75. }
  76. double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
  77. if (xy.fY == y) {
  78. if (xy.fX == left) {
  79. return 0;
  80. }
  81. if (xy.fX == right) {
  82. return 1;
  83. }
  84. }
  85. return -1;
  86. }
  87. double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
  88. if (!AlmostBequalUlps(xy.fY, y)) {
  89. return -1;
  90. }
  91. if (!AlmostBetweenUlps(left, xy.fX, right)) {
  92. return -1;
  93. }
  94. double t = (xy.fX - left) / (right - left);
  95. t = SkPinT(t);
  96. SkASSERT(between(0, t, 1));
  97. double realPtX = (1 - t) * left + t * right;
  98. SkDVector distU = {xy.fY - y, xy.fX - realPtX};
  99. double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
  100. double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
  101. double tiniest = SkTMin(SkTMin(y, left), right);
  102. double largest = SkTMax(SkTMax(y, left), right);
  103. largest = SkTMax(largest, -tiniest);
  104. if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
  105. return -1;
  106. }
  107. return t;
  108. }
  109. double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
  110. if (xy.fX == x) {
  111. if (xy.fY == top) {
  112. return 0;
  113. }
  114. if (xy.fY == bottom) {
  115. return 1;
  116. }
  117. }
  118. return -1;
  119. }
  120. double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
  121. if (!AlmostBequalUlps(xy.fX, x)) {
  122. return -1;
  123. }
  124. if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
  125. return -1;
  126. }
  127. double t = (xy.fY - top) / (bottom - top);
  128. t = SkPinT(t);
  129. SkASSERT(between(0, t, 1));
  130. double realPtY = (1 - t) * top + t * bottom;
  131. SkDVector distU = {xy.fX - x, xy.fY - realPtY};
  132. double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
  133. double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
  134. double tiniest = SkTMin(SkTMin(x, top), bottom);
  135. double largest = SkTMax(SkTMax(x, top), bottom);
  136. largest = SkTMax(largest, -tiniest);
  137. if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
  138. return -1;
  139. }
  140. return t;
  141. }