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