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