SkLineClipper.cpp revision ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976e 
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
11static 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
33static 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
56static 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.
62static 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
68bool 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.
141static 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
151int 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