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