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