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