SkLineClipper.cpp revision e28ff55d980d2992618b6b721c848aba96cf759a 
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
27bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
28                                  SkPoint dst[2]) {
29    SkRect bounds;
30
31    bounds.set(src, 2);
32    if (bounds.fLeft >= clip.fRight || clip.fLeft >= bounds.fRight ||
33        bounds.fTop >= clip.fBottom || clip.fTop >= bounds.fBottom) {
34        return false;
35    }
36    if (clip.contains(bounds)) {
37        if (src != dst) {
38            memcpy(dst, src, 2 * sizeof(SkPoint));
39        }
40        return true;
41    }
42
43    int index0, index1;
44
45    if (src[0].fY < src[1].fY) {
46        index0 = 0;
47        index1 = 1;
48    } else {
49        index0 = 1;
50        index1 = 0;
51    }
52
53    SkPoint tmp[2];
54    memcpy(tmp, src, sizeof(tmp));
55
56    // now compute Y intersections
57    if (tmp[index0].fY < clip.fTop) {
58        tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
59    }
60    if (tmp[index1].fY > clip.fBottom) {
61        tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
62    }
63
64    if (tmp[0].fX < tmp[1].fX) {
65        index0 = 0;
66        index1 = 1;
67    } else {
68        index0 = 1;
69        index1 = 0;
70    }
71
72    // check for quick-reject in X again, now that we may have been chopped
73    if (tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) {
74        return false;
75    }
76
77    if (tmp[index0].fX < clip.fLeft) {
78        tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
79    }
80    if (tmp[index1].fX > clip.fRight) {
81        tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
82    }
83    memcpy(dst, tmp, sizeof(tmp));
84    return true;
85}
86
87int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip,
88                            SkPoint lines[]) {
89    int index0, index1;
90
91    if (pts[0].fY < pts[1].fY) {
92        index0 = 0;
93        index1 = 1;
94    } else {
95        index0 = 1;
96        index1 = 0;
97    }
98
99    // Check if we're completely clipped out in Y (above or below
100
101    if (pts[index1].fY <= clip.fTop) {  // we're above the clip
102        return 0;
103    }
104    if (pts[index0].fY >= clip.fBottom) {  // we're below the clip
105        return 0;
106    }
107
108    // Chop in Y to produce a single segment, stored in tmp[0..1]
109
110    SkPoint tmp[2];
111    memcpy(tmp, pts, sizeof(tmp));
112
113    // now compute intersections
114    if (pts[index0].fY < clip.fTop) {
115        tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
116    }
117    if (tmp[index1].fY > clip.fBottom) {
118        tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
119    }
120
121    // Chop it into 1..3 segments that are wholly within the clip in X.
122
123    // temp storage for up to 3 segments
124    SkPoint resultStorage[kMaxPoints];
125    SkPoint* result;    // points to our results, either tmp or resultStorage
126    int lineCount = 1;
127
128    if (pts[0].fX < pts[1].fX) {
129        index0 = 0;
130        index1 = 1;
131    } else {
132        index0 = 1;
133        index1 = 0;
134    }
135
136    if (tmp[index1].fX <= clip.fLeft) {  // wholly to the left
137        tmp[0].fX = tmp[1].fX = clip.fLeft;
138        result = tmp;
139    } else if (tmp[index0].fX >= clip.fRight) {    // wholly to the right
140        tmp[0].fX = tmp[1].fX = clip.fRight;
141        result = tmp;
142    } else {
143        result = resultStorage;
144        SkPoint* r = result;
145
146        if (tmp[index0].fX < clip.fLeft) {
147            r->set(clip.fLeft, tmp[index0].fY);
148            r += 1;
149            r->set(clip.fLeft, sect_with_vertical(pts, clip.fLeft));
150        } else {
151            *r = tmp[index0];
152        }
153        r += 1;
154
155        if (tmp[index1].fX > clip.fRight) {
156            r->set(clip.fRight, sect_with_vertical(pts, clip.fRight));
157            r += 1;
158            r->set(clip.fRight, tmp[index1].fY);
159        } else {
160            *r = tmp[index1];
161        }
162
163        lineCount = r - result;
164    }
165
166    // Now copy the results into the caller's lines[] parameter
167    if (0 == index1) {
168        // copy the pts in reverse order to maintain winding order
169        for (int i = 0; i <= lineCount; i++) {
170            lines[lineCount - i] = result[i];
171        }
172    } else {
173        memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
174    }
175    return lineCount;
176}
177
178