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