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