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
pin_unsorted(T value,T limit0,T limit1)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
sect_with_horizontal(const SkPoint src[2],SkScalar 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 #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 = X0 + ((double)Y - Y0) * (X1 - X0) / (Y1 - Y0);
39
40 // The computed X value might still exceed [X0..X1] due to quantum flux
41 // when the doubles were added and subtracted, so we have to pin the
42 // answer :(
43 return (float)pin_unsorted(result, X0, X1);
44 #else
45 return src[0].fX + SkScalarMulDiv(Y - src[0].fY, src[1].fX - src[0].fX,
46 dy);
47 #endif
48 }
49 }
50
51 // return Y coordinate of intersection with vertical line at X
sect_with_vertical(const SkPoint src[2],SkScalar X)52 static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
53 SkScalar dx = src[1].fX - src[0].fX;
54 if (SkScalarNearlyZero(dx)) {
55 return SkScalarAve(src[0].fY, src[1].fY);
56 } else {
57 #ifdef SK_SCALAR_IS_FLOAT
58 // need the extra precision so we don't compute a value that exceeds
59 // our original limits
60 double X0 = src[0].fX;
61 double Y0 = src[0].fY;
62 double X1 = src[1].fX;
63 double Y1 = src[1].fY;
64 double result = Y0 + ((double)X - X0) * (Y1 - Y0) / (X1 - X0);
65 return (float)result;
66 #else
67 return src[0].fY + SkScalarMulDiv(X - src[0].fX, src[1].fY - src[0].fY,
68 dx);
69 #endif
70 }
71 }
72
73 ///////////////////////////////////////////////////////////////////////////////
74
nestedLT(SkScalar a,SkScalar b,SkScalar dim)75 static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
76 return a <= b && (a < b || dim > 0);
77 }
78
79 // returns true if outer contains inner, even if inner is empty.
80 // note: outer.contains(inner) always returns false if inner is empty.
containsNoEmptyCheck(const SkRect & outer,const SkRect & inner)81 static inline bool containsNoEmptyCheck(const SkRect& outer,
82 const SkRect& inner) {
83 return outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
84 outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
85 }
86
IntersectLine(const SkPoint src[2],const SkRect & clip,SkPoint dst[2])87 bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
88 SkPoint dst[2]) {
89 SkRect bounds;
90
91 bounds.set(src, 2);
92 if (containsNoEmptyCheck(clip, bounds)) {
93 if (src != dst) {
94 memcpy(dst, src, 2 * sizeof(SkPoint));
95 }
96 return true;
97 }
98 // check for no overlap, and only permit coincident edges if the line
99 // and the edge are colinear
100 if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
101 nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
102 nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
103 nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
104 return false;
105 }
106
107 int index0, index1;
108
109 if (src[0].fY < src[1].fY) {
110 index0 = 0;
111 index1 = 1;
112 } else {
113 index0 = 1;
114 index1 = 0;
115 }
116
117 SkPoint tmp[2];
118 memcpy(tmp, src, sizeof(tmp));
119
120 // now compute Y intersections
121 if (tmp[index0].fY < clip.fTop) {
122 tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
123 }
124 if (tmp[index1].fY > clip.fBottom) {
125 tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
126 }
127
128 if (tmp[0].fX < tmp[1].fX) {
129 index0 = 0;
130 index1 = 1;
131 } else {
132 index0 = 1;
133 index1 = 0;
134 }
135
136 // check for quick-reject in X again, now that we may have been chopped
137 if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) &&
138 tmp[index0].fX < tmp[index1].fX) {
139 // only reject if we have a non-zero width
140 return false;
141 }
142
143 if (tmp[index0].fX < clip.fLeft) {
144 tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
145 }
146 if (tmp[index1].fX > clip.fRight) {
147 tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
148 }
149 #ifdef SK_DEBUG
150 bounds.set(tmp, 2);
151 SkASSERT(containsNoEmptyCheck(clip, bounds));
152 #endif
153 memcpy(dst, tmp, sizeof(tmp));
154 return true;
155 }
156
157 #ifdef SK_DEBUG
158 // return value between the two limits, where the limits are either ascending
159 // or descending.
is_between_unsorted(SkScalar value,SkScalar limit0,SkScalar limit1)160 static bool is_between_unsorted(SkScalar value,
161 SkScalar limit0, SkScalar limit1) {
162 if (limit0 < limit1) {
163 return limit0 <= value && value <= limit1;
164 } else {
165 return limit1 <= value && value <= limit0;
166 }
167 }
168 #endif
169
170 #ifdef SK_SCALAR_IS_FLOAT
171 #ifdef SK_DEBUG
172 // This is an example of why we need to pin the result computed in
173 // sect_with_horizontal. If we didn't explicitly pin, is_between_unsorted would
174 // fail.
175 //
sect_with_horizontal_test_for_pin_results()176 static void sect_with_horizontal_test_for_pin_results() {
177 const SkPoint pts[] = {
178 { -540000, -720000 },
179 { -9.10000017e-05f, 9.99999996e-13f }
180 };
181 float x = sect_with_horizontal(pts, 0);
182 SkASSERT(is_between_unsorted(x, pts[0].fX, pts[1].fX));
183 }
184 #endif
185 #endif
186
ClipLine(const SkPoint pts[],const SkRect & clip,SkPoint lines[])187 int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip,
188 SkPoint lines[]) {
189 #ifdef SK_SCALAR_IS_FLOAT
190 #ifdef SK_DEBUG
191 {
192 static bool gOnce;
193 if (!gOnce) {
194 sect_with_horizontal_test_for_pin_results();
195 gOnce = true;
196 }
197 }
198 #endif
199 #endif
200
201 int index0, index1;
202
203 if (pts[0].fY < pts[1].fY) {
204 index0 = 0;
205 index1 = 1;
206 } else {
207 index0 = 1;
208 index1 = 0;
209 }
210
211 // Check if we're completely clipped out in Y (above or below
212
213 if (pts[index1].fY <= clip.fTop) { // we're above the clip
214 return 0;
215 }
216 if (pts[index0].fY >= clip.fBottom) { // we're below the clip
217 return 0;
218 }
219
220 // Chop in Y to produce a single segment, stored in tmp[0..1]
221
222 SkPoint tmp[2];
223 memcpy(tmp, pts, sizeof(tmp));
224
225 // now compute intersections
226 if (pts[index0].fY < clip.fTop) {
227 tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
228 SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
229 }
230 if (tmp[index1].fY > clip.fBottom) {
231 tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
232 SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
233 }
234
235 // Chop it into 1..3 segments that are wholly within the clip in X.
236
237 // temp storage for up to 3 segments
238 SkPoint resultStorage[kMaxPoints];
239 SkPoint* result; // points to our results, either tmp or resultStorage
240 int lineCount = 1;
241 bool reverse;
242
243 if (pts[0].fX < pts[1].fX) {
244 index0 = 0;
245 index1 = 1;
246 reverse = false;
247 } else {
248 index0 = 1;
249 index1 = 0;
250 reverse = true;
251 }
252
253 if (tmp[index1].fX <= clip.fLeft) { // wholly to the left
254 tmp[0].fX = tmp[1].fX = clip.fLeft;
255 result = tmp;
256 reverse = false;
257 } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right
258 tmp[0].fX = tmp[1].fX = clip.fRight;
259 result = tmp;
260 reverse = false;
261 } else {
262 result = resultStorage;
263 SkPoint* r = result;
264
265 if (tmp[index0].fX < clip.fLeft) {
266 r->set(clip.fLeft, tmp[index0].fY);
267 r += 1;
268 r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft));
269 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
270 } else {
271 *r = tmp[index0];
272 }
273 r += 1;
274
275 if (tmp[index1].fX > clip.fRight) {
276 r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight));
277 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
278 r += 1;
279 r->set(clip.fRight, tmp[index1].fY);
280 } else {
281 *r = tmp[index1];
282 }
283
284 lineCount = r - result;
285 }
286
287 // Now copy the results into the caller's lines[] parameter
288 if (reverse) {
289 // copy the pts in reverse order to maintain winding order
290 for (int i = 0; i <= lineCount; i++) {
291 lines[lineCount - i] = result[i];
292 }
293 } else {
294 memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
295 }
296 return lineCount;
297 }
298