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