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