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
ClipLine(const SkPoint pts[],const SkRect & clip,SkPoint lines[],bool canCullToTheRight)160 int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip, SkPoint lines[],
161 bool canCullToTheRight) {
162 int index0, index1;
163
164 if (pts[0].fY < pts[1].fY) {
165 index0 = 0;
166 index1 = 1;
167 } else {
168 index0 = 1;
169 index1 = 0;
170 }
171
172 // Check if we're completely clipped out in Y (above or below
173
174 if (pts[index1].fY <= clip.fTop) { // we're above the clip
175 return 0;
176 }
177 if (pts[index0].fY >= clip.fBottom) { // we're below the clip
178 return 0;
179 }
180
181 // Chop in Y to produce a single segment, stored in tmp[0..1]
182
183 SkPoint tmp[2];
184 memcpy(tmp, pts, sizeof(tmp));
185
186 // now compute intersections
187 if (pts[index0].fY < clip.fTop) {
188 tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
189 SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
190 }
191 if (tmp[index1].fY > clip.fBottom) {
192 tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
193 SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
194 }
195
196 // Chop it into 1..3 segments that are wholly within the clip in X.
197
198 // temp storage for up to 3 segments
199 SkPoint resultStorage[kMaxPoints];
200 SkPoint* result; // points to our results, either tmp or resultStorage
201 int lineCount = 1;
202 bool reverse;
203
204 if (pts[0].fX < pts[1].fX) {
205 index0 = 0;
206 index1 = 1;
207 reverse = false;
208 } else {
209 index0 = 1;
210 index1 = 0;
211 reverse = true;
212 }
213
214 if (tmp[index1].fX <= clip.fLeft) { // wholly to the left
215 tmp[0].fX = tmp[1].fX = clip.fLeft;
216 result = tmp;
217 reverse = false;
218 } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right
219 if (canCullToTheRight) {
220 return 0;
221 }
222 tmp[0].fX = tmp[1].fX = clip.fRight;
223 result = tmp;
224 reverse = false;
225 } else {
226 result = resultStorage;
227 SkPoint* r = result;
228
229 if (tmp[index0].fX < clip.fLeft) {
230 r->set(clip.fLeft, tmp[index0].fY);
231 r += 1;
232 r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft));
233 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
234 } else {
235 *r = tmp[index0];
236 }
237 r += 1;
238
239 if (tmp[index1].fX > clip.fRight) {
240 r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight));
241 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
242 r += 1;
243 r->set(clip.fRight, tmp[index1].fY);
244 } else {
245 *r = tmp[index1];
246 }
247
248 lineCount = SkToInt(r - result);
249 }
250
251 // Now copy the results into the caller's lines[] parameter
252 if (reverse) {
253 // copy the pts in reverse order to maintain winding order
254 for (int i = 0; i <= lineCount; i++) {
255 lines[lineCount - i] = result[i];
256 }
257 } else {
258 memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
259 }
260 return lineCount;
261 }
262