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