1
2/*
3 * Copyright 2009 The Android Open Source Project
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
9
10#include "SkEdgeClipper.h"
11#include "SkGeometry.h"
12
13static bool quick_reject(const SkRect& bounds, const SkRect& clip) {
14    return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
15}
16
17static inline void clamp_le(SkScalar& value, SkScalar max) {
18    if (value > max) {
19        value = max;
20    }
21}
22
23static inline void clamp_ge(SkScalar& value, SkScalar min) {
24    if (value < min) {
25        value = min;
26    }
27}
28
29/*  src[] must be monotonic in Y. This routine copies src into dst, and sorts
30 it to be increasing in Y. If it had to reverse the order of the points,
31 it returns true, otherwise it returns false
32 */
33static bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) {
34    // we need the data to be monotonically increasing in Y
35    if (src[0].fY > src[count - 1].fY) {
36        for (int i = 0; i < count; i++) {
37            dst[i] = src[count - i - 1];
38        }
39        return true;
40    } else {
41        memcpy(dst, src, count * sizeof(SkPoint));
42        return false;
43    }
44}
45
46///////////////////////////////////////////////////////////////////////////////
47
48static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2,
49                           SkScalar target, SkScalar* t) {
50    /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
51     *  We solve for t, using quadratic equation, hence we have to rearrange
52     * our cooefficents to look like At^2 + Bt + C
53     */
54    SkScalar A = c0 - c1 - c1 + c2;
55    SkScalar B = 2*(c1 - c0);
56    SkScalar C = c0 - target;
57
58    SkScalar roots[2];  // we only expect one, but make room for 2 for safety
59    int count = SkFindUnitQuadRoots(A, B, C, roots);
60    if (count) {
61        *t = roots[0];
62        return true;
63    }
64    return false;
65}
66
67static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) {
68    return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t);
69}
70
71static bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) {
72    return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t);
73}
74
75// Modify pts[] in place so that it is clipped in Y to the clip rect
76static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) {
77    SkScalar t;
78    SkPoint tmp[5]; // for SkChopQuadAt
79
80    // are we partially above
81    if (pts[0].fY < clip.fTop) {
82        if (chopMonoQuadAtY(pts, clip.fTop, &t)) {
83            // take the 2nd chopped quad
84            SkChopQuadAt(pts, tmp, t);
85            // clamp to clean up imprecise numerics in the chop
86            tmp[2].fY = clip.fTop;
87            clamp_ge(tmp[3].fY, clip.fTop);
88
89            pts[0] = tmp[2];
90            pts[1] = tmp[3];
91        } else {
92            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
93            // so we just clamp against the top
94            for (int i = 0; i < 3; i++) {
95                if (pts[i].fY < clip.fTop) {
96                    pts[i].fY = clip.fTop;
97                }
98            }
99        }
100    }
101
102    // are we partially below
103    if (pts[2].fY > clip.fBottom) {
104        if (chopMonoQuadAtY(pts, clip.fBottom, &t)) {
105            SkChopQuadAt(pts, tmp, t);
106            // clamp to clean up imprecise numerics in the chop
107            clamp_le(tmp[1].fY, clip.fBottom);
108            tmp[2].fY = clip.fBottom;
109
110            pts[1] = tmp[1];
111            pts[2] = tmp[2];
112        } else {
113            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
114            // so we just clamp against the bottom
115            for (int i = 0; i < 3; i++) {
116                if (pts[i].fY > clip.fBottom) {
117                    pts[i].fY = clip.fBottom;
118                }
119            }
120        }
121    }
122}
123
124// srcPts[] must be monotonic in X and Y
125void SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) {
126    SkPoint pts[3];
127    bool reverse = sort_increasing_Y(pts, srcPts, 3);
128
129    // are we completely above or below
130    if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
131        return;
132    }
133
134    // Now chop so that pts is contained within clip in Y
135    chop_quad_in_Y(pts, clip);
136
137    if (pts[0].fX > pts[2].fX) {
138        SkTSwap<SkPoint>(pts[0], pts[2]);
139        reverse = !reverse;
140    }
141    SkASSERT(pts[0].fX <= pts[1].fX);
142    SkASSERT(pts[1].fX <= pts[2].fX);
143
144    // Now chop in X has needed, and record the segments
145
146    if (pts[2].fX <= clip.fLeft) {  // wholly to the left
147        this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
148        return;
149    }
150    if (pts[0].fX >= clip.fRight) {  // wholly to the right
151        if (!this->canCullToTheRight()) {
152            this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
153        }
154        return;
155    }
156
157    SkScalar t;
158    SkPoint tmp[5]; // for SkChopQuadAt
159
160    // are we partially to the left
161    if (pts[0].fX < clip.fLeft) {
162        if (chopMonoQuadAtX(pts, clip.fLeft, &t)) {
163            SkChopQuadAt(pts, tmp, t);
164            this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse);
165            // clamp to clean up imprecise numerics in the chop
166            tmp[2].fX = clip.fLeft;
167            clamp_ge(tmp[3].fX, clip.fLeft);
168
169            pts[0] = tmp[2];
170            pts[1] = tmp[3];
171        } else {
172            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
173            // so we just clamp against the left
174            this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
175            return;
176        }
177    }
178
179    // are we partially to the right
180    if (pts[2].fX > clip.fRight) {
181        if (chopMonoQuadAtX(pts, clip.fRight, &t)) {
182            SkChopQuadAt(pts, tmp, t);
183            // clamp to clean up imprecise numerics in the chop
184            clamp_le(tmp[1].fX, clip.fRight);
185            tmp[2].fX = clip.fRight;
186
187            this->appendQuad(tmp, reverse);
188            this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse);
189        } else {
190            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
191            // so we just clamp against the right
192            this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
193        }
194    } else {    // wholly inside the clip
195        this->appendQuad(pts, reverse);
196    }
197}
198
199bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
200    fCurrPoint = fPoints;
201    fCurrVerb = fVerbs;
202
203    SkRect  bounds;
204    bounds.set(srcPts, 3);
205
206    if (!quick_reject(bounds, clip)) {
207        SkPoint monoY[5];
208        int countY = SkChopQuadAtYExtrema(srcPts, monoY);
209        for (int y = 0; y <= countY; y++) {
210            SkPoint monoX[5];
211            int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
212            for (int x = 0; x <= countX; x++) {
213                this->clipMonoQuad(&monoX[x * 2], clip);
214                SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
215                SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
216            }
217        }
218    }
219
220    *fCurrVerb = SkPath::kDone_Verb;
221    fCurrPoint = fPoints;
222    fCurrVerb = fVerbs;
223    return SkPath::kDone_Verb != fVerbs[0];
224}
225
226///////////////////////////////////////////////////////////////////////////////
227
228// Modify pts[] in place so that it is clipped in Y to the clip rect
229static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
230
231    // are we partially above
232    if (pts[0].fY < clip.fTop) {
233        SkPoint tmp[7];
234        if (SkChopMonoCubicAtY(pts, clip.fTop, tmp)) {
235            // tmp[3, 4].fY should all be to the below clip.fTop.
236            // Since we can't trust the numerics of
237            // the chopper, we force those conditions now
238            tmp[3].fY = clip.fTop;
239            clamp_ge(tmp[4].fY, clip.fTop);
240
241            pts[0] = tmp[3];
242            pts[1] = tmp[4];
243            pts[2] = tmp[5];
244        } else {
245            // if chopMonoCubicAtY failed, then we may have hit inexact numerics
246            // so we just clamp against the top
247            for (int i = 0; i < 4; i++) {
248                clamp_ge(pts[i].fY, clip.fTop);
249            }
250        }
251    }
252
253    // are we partially below
254    if (pts[3].fY > clip.fBottom) {
255        SkPoint tmp[7];
256        if (SkChopMonoCubicAtY(pts, clip.fBottom, tmp)) {
257            tmp[3].fY = clip.fBottom;
258            clamp_le(tmp[2].fY, clip.fBottom);
259
260            pts[1] = tmp[1];
261            pts[2] = tmp[2];
262            pts[3] = tmp[3];
263        } else {
264            // if chopMonoCubicAtY failed, then we may have hit inexact numerics
265            // so we just clamp against the bottom
266            for (int i = 0; i < 4; i++) {
267                clamp_le(pts[i].fY, clip.fBottom);
268            }
269        }
270    }
271}
272
273// srcPts[] must be monotonic in X and Y
274void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
275    SkPoint pts[4];
276    bool reverse = sort_increasing_Y(pts, src, 4);
277
278    // are we completely above or below
279    if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
280        return;
281    }
282
283    // Now chop so that pts is contained within clip in Y
284    chop_cubic_in_Y(pts, clip);
285
286    if (pts[0].fX > pts[3].fX) {
287        SkTSwap<SkPoint>(pts[0], pts[3]);
288        SkTSwap<SkPoint>(pts[1], pts[2]);
289        reverse = !reverse;
290    }
291
292    // Now chop in X has needed, and record the segments
293
294    if (pts[3].fX <= clip.fLeft) {  // wholly to the left
295        this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
296        return;
297    }
298    if (pts[0].fX >= clip.fRight) {  // wholly to the right
299        if (!this->canCullToTheRight()) {
300            this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
301        }
302        return;
303    }
304
305    // are we partially to the left
306    if (pts[0].fX < clip.fLeft) {
307        SkPoint tmp[7];
308        if (SkChopMonoCubicAtX(pts, clip.fLeft, tmp)) {
309            this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
310
311            // tmp[3, 4].fX should all be to the right of clip.fLeft.
312            // Since we can't trust the numerics of
313            // the chopper, we force those conditions now
314            tmp[3].fX = clip.fLeft;
315            clamp_ge(tmp[4].fX, clip.fLeft);
316
317            pts[0] = tmp[3];
318            pts[1] = tmp[4];
319            pts[2] = tmp[5];
320        } else {
321            // if chopMonocubicAtY failed, then we may have hit inexact numerics
322            // so we just clamp against the left
323            this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
324            return;
325        }
326    }
327
328    // are we partially to the right
329    if (pts[3].fX > clip.fRight) {
330        SkPoint tmp[7];
331        if (SkChopMonoCubicAtX(pts, clip.fRight, tmp)) {
332            tmp[3].fX = clip.fRight;
333            clamp_le(tmp[2].fX, clip.fRight);
334
335            this->appendCubic(tmp, reverse);
336            this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
337        } else {
338            // if chopMonoCubicAtX failed, then we may have hit inexact numerics
339            // so we just clamp against the right
340            this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
341        }
342    } else {    // wholly inside the clip
343        this->appendCubic(pts, reverse);
344    }
345}
346
347bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
348    fCurrPoint = fPoints;
349    fCurrVerb = fVerbs;
350
351    SkRect  bounds;
352    bounds.set(srcPts, 4);
353
354    if (!quick_reject(bounds, clip)) {
355        SkPoint monoY[10];
356        int countY = SkChopCubicAtYExtrema(srcPts, monoY);
357        for (int y = 0; y <= countY; y++) {
358            SkPoint monoX[10];
359            int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
360            for (int x = 0; x <= countX; x++) {
361                this->clipMonoCubic(&monoX[x * 3], clip);
362                SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
363                SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
364            }
365        }
366    }
367
368    *fCurrVerb = SkPath::kDone_Verb;
369    fCurrPoint = fPoints;
370    fCurrVerb = fVerbs;
371    return SkPath::kDone_Verb != fVerbs[0];
372}
373
374///////////////////////////////////////////////////////////////////////////////
375
376void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
377                                bool reverse) {
378    *fCurrVerb++ = SkPath::kLine_Verb;
379
380    if (reverse) {
381        SkTSwap<SkScalar>(y0, y1);
382    }
383    fCurrPoint[0].set(x, y0);
384    fCurrPoint[1].set(x, y1);
385    fCurrPoint += 2;
386}
387
388void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
389    *fCurrVerb++ = SkPath::kQuad_Verb;
390
391    if (reverse) {
392        fCurrPoint[0] = pts[2];
393        fCurrPoint[2] = pts[0];
394    } else {
395        fCurrPoint[0] = pts[0];
396        fCurrPoint[2] = pts[2];
397    }
398    fCurrPoint[1] = pts[1];
399    fCurrPoint += 3;
400}
401
402void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
403    *fCurrVerb++ = SkPath::kCubic_Verb;
404
405    if (reverse) {
406        for (int i = 0; i < 4; i++) {
407            fCurrPoint[i] = pts[3 - i];
408        }
409    } else {
410        memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
411    }
412    fCurrPoint += 4;
413}
414
415SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
416    SkPath::Verb verb = *fCurrVerb;
417
418    switch (verb) {
419        case SkPath::kLine_Verb:
420            memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
421            fCurrPoint += 2;
422            fCurrVerb += 1;
423            break;
424        case SkPath::kQuad_Verb:
425            memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
426            fCurrPoint += 3;
427            fCurrVerb += 1;
428            break;
429        case SkPath::kCubic_Verb:
430            memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
431            fCurrPoint += 4;
432            fCurrVerb += 1;
433            break;
434        case SkPath::kDone_Verb:
435            break;
436        default:
437            SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
438            break;
439    }
440    return verb;
441}
442
443///////////////////////////////////////////////////////////////////////////////
444
445#ifdef SK_DEBUG
446static void assert_monotonic(const SkScalar coord[], int count) {
447    if (coord[0] > coord[(count - 1) * 2]) {
448        for (int i = 1; i < count; i++) {
449            SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
450        }
451    } else if (coord[0] < coord[(count - 1) * 2]) {
452        for (int i = 1; i < count; i++) {
453            SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
454        }
455    } else {
456        for (int i = 1; i < count; i++) {
457            SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
458        }
459    }
460}
461
462void sk_assert_monotonic_y(const SkPoint pts[], int count) {
463    if (count > 1) {
464        assert_monotonic(&pts[0].fY, count);
465    }
466}
467
468void sk_assert_monotonic_x(const SkPoint pts[], int count) {
469    if (count > 1) {
470        assert_monotonic(&pts[0].fX, count);
471    }
472}
473#endif
474