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 "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[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 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[0], tmp[1]); 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 int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip, SkPoint lines[], 161 bool canCullToTheRight) { 162 int index0, index1; 163 164 if (pts[0].fY < pts[1].fY) { 165 index0 = 0; 166 index1 = 1; 167 } else { 168 index0 = 1; 169 index1 = 0; 170 } 171 172 // Check if we're completely clipped out in Y (above or below 173 174 if (pts[index1].fY <= clip.fTop) { // we're above the clip 175 return 0; 176 } 177 if (pts[index0].fY >= clip.fBottom) { // we're below the clip 178 return 0; 179 } 180 181 // Chop in Y to produce a single segment, stored in tmp[0..1] 182 183 SkPoint tmp[2]; 184 memcpy(tmp, pts, sizeof(tmp)); 185 186 // now compute intersections 187 if (pts[index0].fY < clip.fTop) { 188 tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop); 189 SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX)); 190 } 191 if (tmp[index1].fY > clip.fBottom) { 192 tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom); 193 SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX)); 194 } 195 196 // Chop it into 1..3 segments that are wholly within the clip in X. 197 198 // temp storage for up to 3 segments 199 SkPoint resultStorage[kMaxPoints]; 200 SkPoint* result; // points to our results, either tmp or resultStorage 201 int lineCount = 1; 202 bool reverse; 203 204 if (pts[0].fX < pts[1].fX) { 205 index0 = 0; 206 index1 = 1; 207 reverse = false; 208 } else { 209 index0 = 1; 210 index1 = 0; 211 reverse = true; 212 } 213 214 if (tmp[index1].fX <= clip.fLeft) { // wholly to the left 215 tmp[0].fX = tmp[1].fX = clip.fLeft; 216 result = tmp; 217 reverse = false; 218 } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right 219 if (canCullToTheRight) { 220 return 0; 221 } 222 tmp[0].fX = tmp[1].fX = clip.fRight; 223 result = tmp; 224 reverse = false; 225 } else { 226 result = resultStorage; 227 SkPoint* r = result; 228 229 if (tmp[index0].fX < clip.fLeft) { 230 r->set(clip.fLeft, tmp[index0].fY); 231 r += 1; 232 r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft)); 233 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY)); 234 } else { 235 *r = tmp[index0]; 236 } 237 r += 1; 238 239 if (tmp[index1].fX > clip.fRight) { 240 r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight)); 241 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY)); 242 r += 1; 243 r->set(clip.fRight, tmp[index1].fY); 244 } else { 245 *r = tmp[index1]; 246 } 247 248 lineCount = SkToInt(r - result); 249 } 250 251 // Now copy the results into the caller's lines[] parameter 252 if (reverse) { 253 // copy the pts in reverse order to maintain winding order 254 for (int i = 0; i <= lineCount; i++) { 255 lines[lineCount - i] = result[i]; 256 } 257 } else { 258 memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint)); 259 } 260 return lineCount; 261 } 262