1 #include "SkLineClipper.h"
2
3 // return X coordinate of intersection with horizontal line at Y
sect_with_horizontal(const SkPoint src[2],SkScalar 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
sect_with_vertical(const SkPoint src[2],SkScalar 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
nestedLT(SkScalar a,SkScalar b,SkScalar dim)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.
containsNoEmptyCheck(const SkRect & outer,const SkRect & inner)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
IntersectLine(const SkPoint src[2],const SkRect & clip,SkPoint dst[2])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.
is_between_unsorted(SkScalar value,SkScalar limit0,SkScalar limit1)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
ClipLine(const SkPoint pts[],const SkRect & clip,SkPoint lines[])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