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
10template <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
26static 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
47static 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
65static 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.
71static 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
77bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
78                                  SkPoint dst[2]) {
79    SkRect bounds;
80
81    bounds.set(src, 2);
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, 2);
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.
150static 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
160#ifdef SK_DEBUG
161// This is an example of why we need to pin the result computed in
162// sect_with_horizontal. If we didn't explicitly pin, is_between_unsorted would
163// fail.
164//
165static void sect_with_horizontal_test_for_pin_results() {
166    const SkPoint pts[] = {
167        { -540000,    -720000 },
168        { -9.10000017e-05f, 9.99999996e-13f }
169    };
170    float x = sect_with_horizontal(pts, 0);
171    SkASSERT(is_between_unsorted(x, pts[0].fX, pts[1].fX));
172}
173#endif
174
175int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip,
176                            SkPoint lines[]) {
177#ifdef SK_DEBUG
178    {
179        static bool gOnce;
180        if (!gOnce) {
181            sect_with_horizontal_test_for_pin_results();
182            gOnce = true;
183        }
184    }
185#endif
186
187    int index0, index1;
188
189    if (pts[0].fY < pts[1].fY) {
190        index0 = 0;
191        index1 = 1;
192    } else {
193        index0 = 1;
194        index1 = 0;
195    }
196
197    // Check if we're completely clipped out in Y (above or below
198
199    if (pts[index1].fY <= clip.fTop) {  // we're above the clip
200        return 0;
201    }
202    if (pts[index0].fY >= clip.fBottom) {  // we're below the clip
203        return 0;
204    }
205
206    // Chop in Y to produce a single segment, stored in tmp[0..1]
207
208    SkPoint tmp[2];
209    memcpy(tmp, pts, sizeof(tmp));
210
211    // now compute intersections
212    if (pts[index0].fY < clip.fTop) {
213        tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
214        SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
215    }
216    if (tmp[index1].fY > clip.fBottom) {
217        tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
218        SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
219    }
220
221    // Chop it into 1..3 segments that are wholly within the clip in X.
222
223    // temp storage for up to 3 segments
224    SkPoint resultStorage[kMaxPoints];
225    SkPoint* result;    // points to our results, either tmp or resultStorage
226    int lineCount = 1;
227    bool reverse;
228
229    if (pts[0].fX < pts[1].fX) {
230        index0 = 0;
231        index1 = 1;
232        reverse = false;
233    } else {
234        index0 = 1;
235        index1 = 0;
236        reverse = true;
237    }
238
239    if (tmp[index1].fX <= clip.fLeft) {  // wholly to the left
240        tmp[0].fX = tmp[1].fX = clip.fLeft;
241        result = tmp;
242        reverse = false;
243    } else if (tmp[index0].fX >= clip.fRight) {    // wholly to the right
244        tmp[0].fX = tmp[1].fX = clip.fRight;
245        result = tmp;
246        reverse = false;
247    } else {
248        result = resultStorage;
249        SkPoint* r = result;
250
251        if (tmp[index0].fX < clip.fLeft) {
252            r->set(clip.fLeft, tmp[index0].fY);
253            r += 1;
254            r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft));
255            SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
256        } else {
257            *r = tmp[index0];
258        }
259        r += 1;
260
261        if (tmp[index1].fX > clip.fRight) {
262            r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight));
263            SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
264            r += 1;
265            r->set(clip.fRight, tmp[index1].fY);
266        } else {
267            *r = tmp[index1];
268        }
269
270        lineCount = SkToInt(r - result);
271    }
272
273    // Now copy the results into the caller's lines[] parameter
274    if (reverse) {
275        // copy the pts in reverse order to maintain winding order
276        for (int i = 0; i <= lineCount; i++) {
277            lines[lineCount - i] = result[i];
278        }
279    } else {
280        memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
281    }
282    return lineCount;
283}
284