SkLineClipper.cpp revision 83edde21f3945f988656c023384bd33e87f8b48d
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 10template <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 26static 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 52static 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 75static 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. 81static 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 87bool 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. 160static 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// This is an example of why we need to pin the result computed in 172// sect_with_horizontal. If we didn't explicitly pin, is_between_unsorted would 173// fail. 174// 175static void sect_with_horizontal_test_for_pin_results() { 176 const SkPoint pts[] = { 177 { -540000, -720000 }, 178 { -9.10000017e-05f, 9.99999996e-13f } 179 }; 180 float x = sect_with_horizontal(pts, 0); 181 SkASSERT(is_between_unsorted(x, pts[0].fX, pts[1].fX)); 182} 183#endif 184 185int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip, 186 SkPoint lines[]) { 187#ifdef SK_SCALAR_IS_FLOAT 188#ifdef SK_DEBUG 189 { 190 static bool gOnce; 191 if (!gOnce) { 192 sect_with_horizontal_test_for_pin_results(); 193 gOnce = true; 194 } 195 } 196#endif 197#endif 198 199 int index0, index1; 200 201 if (pts[0].fY < pts[1].fY) { 202 index0 = 0; 203 index1 = 1; 204 } else { 205 index0 = 1; 206 index1 = 0; 207 } 208 209 // Check if we're completely clipped out in Y (above or below 210 211 if (pts[index1].fY <= clip.fTop) { // we're above the clip 212 return 0; 213 } 214 if (pts[index0].fY >= clip.fBottom) { // we're below the clip 215 return 0; 216 } 217 218 // Chop in Y to produce a single segment, stored in tmp[0..1] 219 220 SkPoint tmp[2]; 221 memcpy(tmp, pts, sizeof(tmp)); 222 223 // now compute intersections 224 if (pts[index0].fY < clip.fTop) { 225 tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop); 226 SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX)); 227 } 228 if (tmp[index1].fY > clip.fBottom) { 229 tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom); 230 SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX)); 231 } 232 233 // Chop it into 1..3 segments that are wholly within the clip in X. 234 235 // temp storage for up to 3 segments 236 SkPoint resultStorage[kMaxPoints]; 237 SkPoint* result; // points to our results, either tmp or resultStorage 238 int lineCount = 1; 239 bool reverse; 240 241 if (pts[0].fX < pts[1].fX) { 242 index0 = 0; 243 index1 = 1; 244 reverse = false; 245 } else { 246 index0 = 1; 247 index1 = 0; 248 reverse = true; 249 } 250 251 if (tmp[index1].fX <= clip.fLeft) { // wholly to the left 252 tmp[0].fX = tmp[1].fX = clip.fLeft; 253 result = tmp; 254 reverse = false; 255 } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right 256 tmp[0].fX = tmp[1].fX = clip.fRight; 257 result = tmp; 258 reverse = false; 259 } else { 260 result = resultStorage; 261 SkPoint* r = result; 262 263 if (tmp[index0].fX < clip.fLeft) { 264 r->set(clip.fLeft, tmp[index0].fY); 265 r += 1; 266 r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft)); 267 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY)); 268 } else { 269 *r = tmp[index0]; 270 } 271 r += 1; 272 273 if (tmp[index1].fX > clip.fRight) { 274 r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight)); 275 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY)); 276 r += 1; 277 r->set(clip.fRight, tmp[index1].fY); 278 } else { 279 *r = tmp[index1]; 280 } 281 282 lineCount = r - result; 283 } 284 285 // Now copy the results into the caller's lines[] parameter 286 if (reverse) { 287 // copy the pts in reverse order to maintain winding order 288 for (int i = 0; i <= lineCount; i++) { 289 lines[lineCount - i] = result[i]; 290 } 291 } else { 292 memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint)); 293 } 294 return lineCount; 295} 296 297