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