SkLineClipper.cpp 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276
  1. /*
  2. * Copyright 2011 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 "include/private/SkTo.h"
  8. #include "src/core/SkLineClipper.h"
  9. #include <utility>
  10. template <typename T> T pin_unsorted(T value, T limit0, T limit1) {
  11. if (limit1 < limit0) {
  12. using std::swap;
  13. swap(limit0, limit1);
  14. }
  15. // now the limits are sorted
  16. SkASSERT(limit0 <= limit1);
  17. if (value < limit0) {
  18. value = limit0;
  19. } else if (value > limit1) {
  20. value = limit1;
  21. }
  22. return value;
  23. }
  24. // return X coordinate of intersection with horizontal line at Y
  25. static SkScalar sect_with_horizontal(const SkPoint src[2], SkScalar Y) {
  26. SkScalar dy = src[1].fY - src[0].fY;
  27. if (SkScalarNearlyZero(dy)) {
  28. return SkScalarAve(src[0].fX, src[1].fX);
  29. } else {
  30. // need the extra precision so we don't compute a value that exceeds
  31. // our original limits
  32. double X0 = src[0].fX;
  33. double Y0 = src[0].fY;
  34. double X1 = src[1].fX;
  35. double Y1 = src[1].fY;
  36. double result = X0 + ((double)Y - Y0) * (X1 - X0) / (Y1 - Y0);
  37. // The computed X value might still exceed [X0..X1] due to quantum flux
  38. // when the doubles were added and subtracted, so we have to pin the
  39. // answer :(
  40. return (float)pin_unsorted(result, X0, X1);
  41. }
  42. }
  43. // return Y coordinate of intersection with vertical line at X
  44. static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
  45. SkScalar dx = src[1].fX - src[0].fX;
  46. if (SkScalarNearlyZero(dx)) {
  47. return SkScalarAve(src[0].fY, src[1].fY);
  48. } else {
  49. // need the extra precision so we don't compute a value that exceeds
  50. // our original limits
  51. double X0 = src[0].fX;
  52. double Y0 = src[0].fY;
  53. double X1 = src[1].fX;
  54. double Y1 = src[1].fY;
  55. double result = Y0 + ((double)X - X0) * (Y1 - Y0) / (X1 - X0);
  56. return (float)result;
  57. }
  58. }
  59. static SkScalar sect_clamp_with_vertical(const SkPoint src[2], SkScalar x) {
  60. SkScalar y = sect_with_vertical(src, x);
  61. // Our caller expects y to be between src[0].fY and src[1].fY (unsorted), but due to the
  62. // numerics of floats/doubles, we might have computed a value slightly outside of that,
  63. // so we have to manually clamp afterwards.
  64. // See skbug.com/7491
  65. return pin_unsorted(y, src[0].fY, src[1].fY);
  66. }
  67. ///////////////////////////////////////////////////////////////////////////////
  68. static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
  69. return a <= b && (a < b || dim > 0);
  70. }
  71. // returns true if outer contains inner, even if inner is empty.
  72. // note: outer.contains(inner) always returns false if inner is empty.
  73. static inline bool containsNoEmptyCheck(const SkRect& outer,
  74. const SkRect& inner) {
  75. return outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
  76. outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
  77. }
  78. bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
  79. SkPoint dst[2]) {
  80. SkRect bounds;
  81. bounds.set(src[0], src[1]);
  82. if (containsNoEmptyCheck(clip, bounds)) {
  83. if (src != dst) {
  84. memcpy(dst, src, 2 * sizeof(SkPoint));
  85. }
  86. return true;
  87. }
  88. // check for no overlap, and only permit coincident edges if the line
  89. // and the edge are colinear
  90. if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
  91. nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
  92. nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
  93. nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
  94. return false;
  95. }
  96. int index0, index1;
  97. if (src[0].fY < src[1].fY) {
  98. index0 = 0;
  99. index1 = 1;
  100. } else {
  101. index0 = 1;
  102. index1 = 0;
  103. }
  104. SkPoint tmp[2];
  105. memcpy(tmp, src, sizeof(tmp));
  106. // now compute Y intersections
  107. if (tmp[index0].fY < clip.fTop) {
  108. tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
  109. }
  110. if (tmp[index1].fY > clip.fBottom) {
  111. tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
  112. }
  113. if (tmp[0].fX < tmp[1].fX) {
  114. index0 = 0;
  115. index1 = 1;
  116. } else {
  117. index0 = 1;
  118. index1 = 0;
  119. }
  120. // check for quick-reject in X again, now that we may have been chopped
  121. if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight)) {
  122. // usually we will return false, but we don't if the line is vertical and coincident
  123. // with the clip.
  124. if (tmp[0].fX != tmp[1].fX || tmp[0].fX < clip.fLeft || tmp[0].fX > clip.fRight) {
  125. return false;
  126. }
  127. }
  128. if (tmp[index0].fX < clip.fLeft) {
  129. tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
  130. }
  131. if (tmp[index1].fX > clip.fRight) {
  132. tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
  133. }
  134. #ifdef SK_DEBUG
  135. bounds.set(tmp[0], tmp[1]);
  136. SkASSERT(containsNoEmptyCheck(clip, bounds));
  137. #endif
  138. memcpy(dst, tmp, sizeof(tmp));
  139. return true;
  140. }
  141. #ifdef SK_DEBUG
  142. // return value between the two limits, where the limits are either ascending
  143. // or descending.
  144. static bool is_between_unsorted(SkScalar value,
  145. SkScalar limit0, SkScalar limit1) {
  146. if (limit0 < limit1) {
  147. return limit0 <= value && value <= limit1;
  148. } else {
  149. return limit1 <= value && value <= limit0;
  150. }
  151. }
  152. #endif
  153. int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip, SkPoint lines[],
  154. bool canCullToTheRight) {
  155. int index0, index1;
  156. if (pts[0].fY < pts[1].fY) {
  157. index0 = 0;
  158. index1 = 1;
  159. } else {
  160. index0 = 1;
  161. index1 = 0;
  162. }
  163. // Check if we're completely clipped out in Y (above or below
  164. if (pts[index1].fY <= clip.fTop) { // we're above the clip
  165. return 0;
  166. }
  167. if (pts[index0].fY >= clip.fBottom) { // we're below the clip
  168. return 0;
  169. }
  170. // Chop in Y to produce a single segment, stored in tmp[0..1]
  171. SkPoint tmp[2];
  172. memcpy(tmp, pts, sizeof(tmp));
  173. // now compute intersections
  174. if (pts[index0].fY < clip.fTop) {
  175. tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
  176. SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
  177. }
  178. if (tmp[index1].fY > clip.fBottom) {
  179. tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
  180. SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
  181. }
  182. // Chop it into 1..3 segments that are wholly within the clip in X.
  183. // temp storage for up to 3 segments
  184. SkPoint resultStorage[kMaxPoints];
  185. SkPoint* result; // points to our results, either tmp or resultStorage
  186. int lineCount = 1;
  187. bool reverse;
  188. if (pts[0].fX < pts[1].fX) {
  189. index0 = 0;
  190. index1 = 1;
  191. reverse = false;
  192. } else {
  193. index0 = 1;
  194. index1 = 0;
  195. reverse = true;
  196. }
  197. if (tmp[index1].fX <= clip.fLeft) { // wholly to the left
  198. tmp[0].fX = tmp[1].fX = clip.fLeft;
  199. result = tmp;
  200. reverse = false;
  201. } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right
  202. if (canCullToTheRight) {
  203. return 0;
  204. }
  205. tmp[0].fX = tmp[1].fX = clip.fRight;
  206. result = tmp;
  207. reverse = false;
  208. } else {
  209. result = resultStorage;
  210. SkPoint* r = result;
  211. if (tmp[index0].fX < clip.fLeft) {
  212. r->set(clip.fLeft, tmp[index0].fY);
  213. r += 1;
  214. r->set(clip.fLeft, sect_clamp_with_vertical(tmp, clip.fLeft));
  215. SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
  216. } else {
  217. *r = tmp[index0];
  218. }
  219. r += 1;
  220. if (tmp[index1].fX > clip.fRight) {
  221. r->set(clip.fRight, sect_clamp_with_vertical(tmp, clip.fRight));
  222. SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
  223. r += 1;
  224. r->set(clip.fRight, tmp[index1].fY);
  225. } else {
  226. *r = tmp[index1];
  227. }
  228. lineCount = SkToInt(r - result);
  229. }
  230. // Now copy the results into the caller's lines[] parameter
  231. if (reverse) {
  232. // copy the pts in reverse order to maintain winding order
  233. for (int i = 0; i <= lineCount; i++) {
  234. lines[lineCount - i] = result[i];
  235. }
  236. } else {
  237. memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
  238. }
  239. return lineCount;
  240. }