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        this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
152        return;
153    }
154
155    SkScalar t;
156    SkPoint tmp[5]; // for SkChopQuadAt
157
158    // are we partially to the left
159    if (pts[0].fX < clip.fLeft) {
160        if (chopMonoQuadAtX(pts, clip.fLeft, &t)) {
161            SkChopQuadAt(pts, tmp, t);
162            this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse);
163            // clamp to clean up imprecise numerics in the chop
164            tmp[2].fX = clip.fLeft;
165            clamp_ge(tmp[3].fX, clip.fLeft);
166
167            pts[0] = tmp[2];
168            pts[1] = tmp[3];
169        } else {
170            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
171            // so we just clamp against the left
172            this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
173            return;
174        }
175    }
176
177    // are we partially to the right
178    if (pts[2].fX > clip.fRight) {
179        if (chopMonoQuadAtX(pts, clip.fRight, &t)) {
180            SkChopQuadAt(pts, tmp, t);
181            // clamp to clean up imprecise numerics in the chop
182            clamp_le(tmp[1].fX, clip.fRight);
183            tmp[2].fX = clip.fRight;
184
185            this->appendQuad(tmp, reverse);
186            this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse);
187        } else {
188            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
189            // so we just clamp against the right
190            this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
191        }
192    } else {    // wholly inside the clip
193        this->appendQuad(pts, reverse);
194    }
195}
196
197bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
198    fCurrPoint = fPoints;
199    fCurrVerb = fVerbs;
200
201    SkRect  bounds;
202    bounds.set(srcPts, 3);
203
204    if (!quick_reject(bounds, clip)) {
205        SkPoint monoY[5];
206        int countY = SkChopQuadAtYExtrema(srcPts, monoY);
207        for (int y = 0; y <= countY; y++) {
208            SkPoint monoX[5];
209            int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
210            for (int x = 0; x <= countX; x++) {
211                this->clipMonoQuad(&monoX[x * 2], clip);
212                SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
213                SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
214            }
215        }
216    }
217
218    *fCurrVerb = SkPath::kDone_Verb;
219    fCurrPoint = fPoints;
220    fCurrVerb = fVerbs;
221    return SkPath::kDone_Verb != fVerbs[0];
222}
223
224///////////////////////////////////////////////////////////////////////////////
225
226static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
227                                 SkScalar D, SkScalar t) {
228    return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
229}
230
231/*  Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
232    t value such that cubic(t) = target
233 */
234static bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
235                           SkScalar target, SkScalar* t) {
236 //   SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
237    SkASSERT(c0 < target && target < c3);
238
239    SkScalar D = c0 - target;
240    SkScalar A = c3 + 3*(c1 - c2) - c0;
241    SkScalar B = 3*(c2 - c1 - c1 + c0);
242    SkScalar C = 3*(c1 - c0);
243
244    const SkScalar TOLERANCE = SK_Scalar1 / 4096;
245    SkScalar minT = 0;
246    SkScalar maxT = SK_Scalar1;
247    SkScalar mid;
248
249    // This is a lot of iterations. Is there a faster way?
250    for (int i = 0; i < 24; i++) {
251        mid = SkScalarAve(minT, maxT);
252        SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
253        if (delta < 0) {
254            minT = mid;
255            delta = -delta;
256        } else {
257            maxT = mid;
258        }
259        if (delta < TOLERANCE) {
260            break;
261        }
262    }
263    *t = mid;
264//    SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t));
265    return true;
266}
267
268static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) {
269    return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t);
270}
271
272static bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) {
273    return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t);
274}
275
276// Modify pts[] in place so that it is clipped in Y to the clip rect
277static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
278
279    // are we partially above
280    if (pts[0].fY < clip.fTop) {
281        SkScalar t;
282        if (chopMonoCubicAtY(pts, clip.fTop, &t)) {
283            SkPoint tmp[7];
284            SkChopCubicAt(pts, tmp, t);
285
286            // tmp[3, 4, 5].fY should all be to the below clip.fTop.
287            // Since we can't trust the numerics of
288            // the chopper, we force those conditions now
289            tmp[3].fY = clip.fTop;
290            clamp_ge(tmp[4].fY, clip.fTop);
291            clamp_ge(tmp[5].fY, clip.fTop);
292
293            pts[0] = tmp[3];
294            pts[1] = tmp[4];
295            pts[2] = tmp[5];
296        } else {
297            // if chopMonoCubicAtY failed, then we may have hit inexact numerics
298            // so we just clamp against the top
299            for (int i = 0; i < 4; i++) {
300                clamp_ge(pts[i].fY, clip.fTop);
301            }
302        }
303    }
304
305    // are we partially below
306    if (pts[3].fY > clip.fBottom) {
307        SkScalar t;
308        if (chopMonoCubicAtY(pts, clip.fBottom, &t)) {
309            SkPoint tmp[7];
310            SkChopCubicAt(pts, tmp, t);
311            tmp[3].fY = clip.fBottom;
312            clamp_le(tmp[2].fY, clip.fBottom);
313
314            pts[1] = tmp[1];
315            pts[2] = tmp[2];
316            pts[3] = tmp[3];
317        } else {
318            // if chopMonoCubicAtY failed, then we may have hit inexact numerics
319            // so we just clamp against the bottom
320            for (int i = 0; i < 4; i++) {
321                clamp_le(pts[i].fY, clip.fBottom);
322            }
323        }
324    }
325}
326
327// srcPts[] must be monotonic in X and Y
328void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
329    SkPoint pts[4];
330    bool reverse = sort_increasing_Y(pts, src, 4);
331
332    // are we completely above or below
333    if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
334        return;
335    }
336
337    // Now chop so that pts is contained within clip in Y
338    chop_cubic_in_Y(pts, clip);
339
340    if (pts[0].fX > pts[3].fX) {
341        SkTSwap<SkPoint>(pts[0], pts[3]);
342        SkTSwap<SkPoint>(pts[1], pts[2]);
343        reverse = !reverse;
344    }
345
346    // Now chop in X has needed, and record the segments
347
348    if (pts[3].fX <= clip.fLeft) {  // wholly to the left
349        this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
350        return;
351    }
352    if (pts[0].fX >= clip.fRight) {  // wholly to the right
353        this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
354        return;
355    }
356
357    // are we partially to the left
358    if (pts[0].fX < clip.fLeft) {
359        SkScalar t;
360        if (chopMonoCubicAtX(pts, clip.fLeft, &t)) {
361            SkPoint tmp[7];
362            SkChopCubicAt(pts, tmp, t);
363            this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
364
365            // tmp[3, 4, 5].fX should all be to the right of clip.fLeft.
366            // Since we can't trust the numerics of
367            // the chopper, we force those conditions now
368            tmp[3].fX = clip.fLeft;
369            clamp_ge(tmp[4].fX, clip.fLeft);
370            clamp_ge(tmp[5].fX, clip.fLeft);
371
372            pts[0] = tmp[3];
373            pts[1] = tmp[4];
374            pts[2] = tmp[5];
375        } else {
376            // if chopMonocubicAtY failed, then we may have hit inexact numerics
377            // so we just clamp against the left
378            this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
379            return;
380        }
381    }
382
383    // are we partially to the right
384    if (pts[3].fX > clip.fRight) {
385        SkScalar t;
386        if (chopMonoCubicAtX(pts, clip.fRight, &t)) {
387            SkPoint tmp[7];
388            SkChopCubicAt(pts, tmp, t);
389            tmp[3].fX = clip.fRight;
390            clamp_le(tmp[2].fX, clip.fRight);
391            clamp_le(tmp[1].fX, clip.fRight);
392
393            this->appendCubic(tmp, reverse);
394            this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
395        } else {
396            // if chopMonoCubicAtX failed, then we may have hit inexact numerics
397            // so we just clamp against the right
398            this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
399        }
400    } else {    // wholly inside the clip
401        this->appendCubic(pts, reverse);
402    }
403}
404
405bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
406    fCurrPoint = fPoints;
407    fCurrVerb = fVerbs;
408
409    SkRect  bounds;
410    bounds.set(srcPts, 4);
411
412    if (!quick_reject(bounds, clip)) {
413        SkPoint monoY[10];
414        int countY = SkChopCubicAtYExtrema(srcPts, monoY);
415        for (int y = 0; y <= countY; y++) {
416            SkPoint monoX[10];
417            int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
418            for (int x = 0; x <= countX; x++) {
419                this->clipMonoCubic(&monoX[x * 3], clip);
420                SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
421                SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
422            }
423        }
424    }
425
426    *fCurrVerb = SkPath::kDone_Verb;
427    fCurrPoint = fPoints;
428    fCurrVerb = fVerbs;
429    return SkPath::kDone_Verb != fVerbs[0];
430}
431
432///////////////////////////////////////////////////////////////////////////////
433
434void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
435                                bool reverse) {
436    *fCurrVerb++ = SkPath::kLine_Verb;
437
438    if (reverse) {
439        SkTSwap<SkScalar>(y0, y1);
440    }
441    fCurrPoint[0].set(x, y0);
442    fCurrPoint[1].set(x, y1);
443    fCurrPoint += 2;
444}
445
446void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
447    *fCurrVerb++ = SkPath::kQuad_Verb;
448
449    if (reverse) {
450        fCurrPoint[0] = pts[2];
451        fCurrPoint[2] = pts[0];
452    } else {
453        fCurrPoint[0] = pts[0];
454        fCurrPoint[2] = pts[2];
455    }
456    fCurrPoint[1] = pts[1];
457    fCurrPoint += 3;
458}
459
460void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
461    *fCurrVerb++ = SkPath::kCubic_Verb;
462
463    if (reverse) {
464        for (int i = 0; i < 4; i++) {
465            fCurrPoint[i] = pts[3 - i];
466        }
467    } else {
468        memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
469    }
470    fCurrPoint += 4;
471}
472
473SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
474    SkPath::Verb verb = *fCurrVerb;
475
476    switch (verb) {
477        case SkPath::kLine_Verb:
478            memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
479            fCurrPoint += 2;
480            fCurrVerb += 1;
481            break;
482        case SkPath::kQuad_Verb:
483            memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
484            fCurrPoint += 3;
485            fCurrVerb += 1;
486            break;
487        case SkPath::kCubic_Verb:
488            memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
489            fCurrPoint += 4;
490            fCurrVerb += 1;
491            break;
492        case SkPath::kDone_Verb:
493            break;
494        default:
495            SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
496            break;
497    }
498    return verb;
499}
500
501///////////////////////////////////////////////////////////////////////////////
502
503#ifdef SK_DEBUG
504static void assert_monotonic(const SkScalar coord[], int count) {
505    if (coord[0] > coord[(count - 1) * 2]) {
506        for (int i = 1; i < count; i++) {
507            SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
508        }
509    } else if (coord[0] < coord[(count - 1) * 2]) {
510        for (int i = 1; i < count; i++) {
511            SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
512        }
513    } else {
514        for (int i = 1; i < count; i++) {
515            SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
516        }
517    }
518}
519
520void sk_assert_monotonic_y(const SkPoint pts[], int count) {
521    if (count > 1) {
522        assert_monotonic(&pts[0].fY, count);
523    }
524}
525
526void sk_assert_monotonic_x(const SkPoint pts[], int count) {
527    if (count > 1) {
528        assert_monotonic(&pts[0].fX, count);
529    }
530}
531#endif
532