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