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