1/*
2 * Copyright 2017 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "GrCCGeometry.h"
9
10#include "GrTypes.h"
11#include "GrPathUtils.h"
12#include <algorithm>
13#include <cmath>
14#include <cstdlib>
15
16// We convert between SkPoint and Sk2f freely throughout this file.
17GR_STATIC_ASSERT(SK_SCALAR_IS_FLOAT);
18GR_STATIC_ASSERT(2 * sizeof(float) == sizeof(SkPoint));
19GR_STATIC_ASSERT(0 == offsetof(SkPoint, fX));
20
21void GrCCGeometry::beginPath() {
22    SkASSERT(!fBuildingContour);
23    fVerbs.push_back(Verb::kBeginPath);
24}
25
26void GrCCGeometry::beginContour(const SkPoint& devPt) {
27    SkASSERT(!fBuildingContour);
28
29    fCurrFanPoint = fCurrAnchorPoint = devPt;
30
31    // Store the current verb count in the fTriangles field for now. When we close the contour we
32    // will use this value to calculate the actual number of triangles in its fan.
33    fCurrContourTallies = {fVerbs.count(), 0, 0, 0};
34
35    fPoints.push_back(devPt);
36    fVerbs.push_back(Verb::kBeginContour);
37
38    SkDEBUGCODE(fBuildingContour = true);
39}
40
41void GrCCGeometry::lineTo(const SkPoint& devPt) {
42    SkASSERT(fBuildingContour);
43    SkASSERT(fCurrFanPoint == fPoints.back());
44    fCurrFanPoint = devPt;
45    fPoints.push_back(devPt);
46    fVerbs.push_back(Verb::kLineTo);
47}
48
49static inline Sk2f normalize(const Sk2f& n) {
50    Sk2f nn = n*n;
51    return n * (nn + SkNx_shuffle<1,0>(nn)).rsqrt();
52}
53
54static inline float dot(const Sk2f& a, const Sk2f& b) {
55    float product[2];
56    (a * b).store(product);
57    return product[0] + product[1];
58}
59
60static inline bool are_collinear(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2) {
61    static constexpr float kFlatnessTolerance = 4; // 1/4 of a pixel.
62
63    // Area (times 2) of the triangle.
64    Sk2f a = (p0 - p1) * SkNx_shuffle<1,0>(p1 - p2);
65    a = (a - SkNx_shuffle<1,0>(a)).abs();
66
67    // Bounding box of the triangle.
68    Sk2f bbox0 = Sk2f::Min(Sk2f::Min(p0, p1), p2);
69    Sk2f bbox1 = Sk2f::Max(Sk2f::Max(p0, p1), p2);
70
71    // The triangle is linear if its area is within a fraction of the largest bounding box
72    // dimension, or else if its area is within a fraction of a pixel.
73    return (a * (kFlatnessTolerance/2) < Sk2f::Max(bbox1 - bbox0, 1)).anyTrue();
74}
75
76// Returns whether the (convex) curve segment is monotonic with respect to [endPt - startPt].
77static inline bool is_convex_curve_monotonic(const Sk2f& startPt, const Sk2f& startTan,
78                                             const Sk2f& endPt, const Sk2f& endTan) {
79    Sk2f v = endPt - startPt;
80    float dot0 = dot(startTan, v);
81    float dot1 = dot(endTan, v);
82
83    // A small, negative tolerance handles floating-point error in the case when one tangent
84    // approaches 0 length, meaning the (convex) curve segment is effectively a flat line.
85    float tolerance = -std::max(std::abs(dot0), std::abs(dot1)) * SK_ScalarNearlyZero;
86    return dot0 >= tolerance && dot1 >= tolerance;
87}
88
89static inline Sk2f lerp(const Sk2f& a, const Sk2f& b, const Sk2f& t) {
90    return SkNx_fma(t, b - a, a);
91}
92
93void GrCCGeometry::quadraticTo(const SkPoint& devP0, const SkPoint& devP1) {
94    SkASSERT(fBuildingContour);
95    SkASSERT(fCurrFanPoint == fPoints.back());
96
97    Sk2f p0 = Sk2f::Load(&fCurrFanPoint);
98    Sk2f p1 = Sk2f::Load(&devP0);
99    Sk2f p2 = Sk2f::Load(&devP1);
100    fCurrFanPoint = devP1;
101
102    this->appendMonotonicQuadratics(p0, p1, p2);
103}
104
105inline void GrCCGeometry::appendMonotonicQuadratics(const Sk2f& p0, const Sk2f& p1,
106                                                    const Sk2f& p2) {
107    Sk2f tan0 = p1 - p0;
108    Sk2f tan1 = p2 - p1;
109
110    // This should almost always be this case for well-behaved curves in the real world.
111    if (is_convex_curve_monotonic(p0, tan0, p2, tan1)) {
112        this->appendSingleMonotonicQuadratic(p0, p1, p2);
113        return;
114    }
115
116    // Chop the curve into two segments with equal curvature. To do this we find the T value whose
117    // tangent is perpendicular to the vector that bisects tan0 and -tan1.
118    Sk2f n = normalize(tan0) - normalize(tan1);
119
120    // This tangent can be found where (dQ(t) dot n) = 0:
121    //
122    //   0 = (dQ(t) dot n) = | 2*t  1 | * | p0 - 2*p1 + p2 | * | n |
123    //                                    | -2*p0 + 2*p1   |   | . |
124    //
125    //                     = | 2*t  1 | * | tan1 - tan0 | * | n |
126    //                                    | 2*tan0      |   | . |
127    //
128    //                     = 2*t * ((tan1 - tan0) dot n) + (2*tan0 dot n)
129    //
130    //   t = (tan0 dot n) / ((tan0 - tan1) dot n)
131    Sk2f dQ1n = (tan0 - tan1) * n;
132    Sk2f dQ0n = tan0 * n;
133    Sk2f t = (dQ0n + SkNx_shuffle<1,0>(dQ0n)) / (dQ1n + SkNx_shuffle<1,0>(dQ1n));
134    t = Sk2f::Min(Sk2f::Max(t, 0), 1); // Clamp for FP error.
135
136    Sk2f p01 = SkNx_fma(t, tan0, p0);
137    Sk2f p12 = SkNx_fma(t, tan1, p1);
138    Sk2f p012 = lerp(p01, p12, t);
139
140    this->appendSingleMonotonicQuadratic(p0, p01, p012);
141    this->appendSingleMonotonicQuadratic(p012, p12, p2);
142}
143
144inline void GrCCGeometry::appendSingleMonotonicQuadratic(const Sk2f& p0, const Sk2f& p1,
145                                                         const Sk2f& p2) {
146    SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
147
148    // Don't send curves to the GPU if we know they are nearly flat (or just very small).
149    if (are_collinear(p0, p1, p2)) {
150        p2.store(&fPoints.push_back());
151        fVerbs.push_back(Verb::kLineTo);
152        return;
153    }
154
155    p1.store(&fPoints.push_back());
156    p2.store(&fPoints.push_back());
157    fVerbs.push_back(Verb::kMonotonicQuadraticTo);
158    ++fCurrContourTallies.fQuadratics;
159}
160
161using ExcludedTerm = GrPathUtils::ExcludedTerm;
162
163// Calculates the padding to apply around inflection points, in homogeneous parametric coordinates.
164//
165// More specifically, if the inflection point lies at C(t/s), then C((t +/- returnValue) / s) will
166// be the two points on the curve at which a square box with radius "padRadius" will have a corner
167// that touches the inflection point's tangent line.
168//
169// A serpentine cubic has two inflection points, so this method takes Sk2f and computes the padding
170// for both in SIMD.
171static inline Sk2f calc_inflect_homogeneous_padding(float padRadius, const Sk2f& t, const Sk2f& s,
172                                                    const SkMatrix& CIT, ExcludedTerm skipTerm) {
173    SkASSERT(padRadius >= 0);
174
175    Sk2f Clx = s*s*s;
176    Sk2f Cly = (ExcludedTerm::kLinearTerm == skipTerm) ? s*s*t*-3 : s*t*t*3;
177
178    Sk2f Lx = CIT[0] * Clx + CIT[3] * Cly;
179    Sk2f Ly = CIT[1] * Clx + CIT[4] * Cly;
180
181    float ret[2];
182    Sk2f bloat = padRadius * (Lx.abs() + Ly.abs());
183    (bloat * s >= 0).thenElse(bloat, -bloat).store(ret);
184
185    ret[0] = cbrtf(ret[0]);
186    ret[1] = cbrtf(ret[1]);
187    return Sk2f::Load(ret);
188}
189
190static inline void swap_if_greater(float& a, float& b) {
191    if (a > b) {
192        std::swap(a, b);
193    }
194}
195
196// Calculates all parameter values for a loop at which points a square box with radius "padRadius"
197// will have a corner that touches a tangent line from the intersection.
198//
199// T2 must contain the lesser parameter value of the loop intersection in its first component, and
200// the greater in its second.
201//
202// roots[0] will be filled with 1 or 3 sorted parameter values, representing the padding points
203// around the first tangent. roots[1] will be filled with the padding points for the second tangent.
204static inline void calc_loop_intersect_padding_pts(float padRadius, const Sk2f& T2,
205                                                  const SkMatrix& CIT, ExcludedTerm skipTerm,
206                                                  SkSTArray<3, float, true> roots[2]) {
207    SkASSERT(padRadius >= 0);
208    SkASSERT(T2[0] <= T2[1]);
209    SkASSERT(roots[0].empty());
210    SkASSERT(roots[1].empty());
211
212    Sk2f T1 = SkNx_shuffle<1,0>(T2);
213    Sk2f Cl = (ExcludedTerm::kLinearTerm == skipTerm) ? T2*-2 - T1 : T2*T2 + T2*T1*2;
214    Sk2f Lx = Cl * CIT[3] + CIT[0];
215    Sk2f Ly = Cl * CIT[4] + CIT[1];
216
217    Sk2f bloat = Sk2f(+.5f * padRadius, -.5f * padRadius) * (Lx.abs() + Ly.abs());
218    Sk2f q = (1.f/3) * (T2 - T1);
219
220    Sk2f qqq = q*q*q;
221    Sk2f discr = qqq*bloat*2 + bloat*bloat;
222
223    float numRoots[2], D[2];
224    (discr < 0).thenElse(3, 1).store(numRoots);
225    (T2 - q).store(D);
226
227    // Values for calculating one root.
228    float R[2], QQ[2];
229    if ((discr >= 0).anyTrue()) {
230        Sk2f r = qqq + bloat;
231        Sk2f s = r.abs() + discr.sqrt();
232        (r > 0).thenElse(-s, s).store(R);
233        (q*q).store(QQ);
234    }
235
236    // Values for calculating three roots.
237    float P[2], cosTheta3[2];
238    if ((discr < 0).anyTrue()) {
239        (q.abs() * -2).store(P);
240        ((q >= 0).thenElse(1, -1) + bloat / qqq.abs()).store(cosTheta3);
241    }
242
243    for (int i = 0; i < 2; ++i) {
244        if (1 == numRoots[i]) {
245            float A = cbrtf(R[i]);
246            float B = A != 0 ? QQ[i]/A : 0;
247            roots[i].push_back(A + B + D[i]);
248            continue;
249        }
250
251        static constexpr float k2PiOver3 = 2 * SK_ScalarPI / 3;
252        float theta = std::acos(cosTheta3[i]) * (1.f/3);
253        roots[i].push_back(P[i] * std::cos(theta) + D[i]);
254        roots[i].push_back(P[i] * std::cos(theta + k2PiOver3) + D[i]);
255        roots[i].push_back(P[i] * std::cos(theta - k2PiOver3) + D[i]);
256
257        // Sort the three roots.
258        swap_if_greater(roots[i][0], roots[i][1]);
259        swap_if_greater(roots[i][1], roots[i][2]);
260        swap_if_greater(roots[i][0], roots[i][1]);
261    }
262}
263
264static inline Sk2f first_unless_nearly_zero(const Sk2f& a, const Sk2f& b) {
265    Sk2f aa = a*a;
266    aa += SkNx_shuffle<1,0>(aa);
267    SkASSERT(aa[0] == aa[1]);
268
269    Sk2f bb = b*b;
270    bb += SkNx_shuffle<1,0>(bb);
271    SkASSERT(bb[0] == bb[1]);
272
273    return (aa > bb * SK_ScalarNearlyZero).thenElse(a, b);
274}
275
276static inline bool is_cubic_nearly_quadratic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
277                                             const Sk2f& p3, Sk2f& tan0, Sk2f& tan3, Sk2f& c) {
278    tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0);
279    tan3 = first_unless_nearly_zero(p3 - p2, p3 - p1);
280
281    Sk2f c1 = SkNx_fma(Sk2f(1.5f), tan0, p0);
282    Sk2f c2 = SkNx_fma(Sk2f(-1.5f), tan3, p3);
283    c = (c1 + c2) * .5f; // Hopefully optimized out if not used?
284
285    return ((c1 - c2).abs() <= 1).allTrue();
286}
287
288void GrCCGeometry::cubicTo(const SkPoint& devP1, const SkPoint& devP2, const SkPoint& devP3,
289                           float inflectPad, float loopIntersectPad) {
290    SkASSERT(fBuildingContour);
291    SkASSERT(fCurrFanPoint == fPoints.back());
292
293    SkPoint devPts[4] = {fCurrFanPoint, devP1, devP2, devP3};
294    Sk2f p0 = Sk2f::Load(&fCurrFanPoint);
295    Sk2f p1 = Sk2f::Load(&devP1);
296    Sk2f p2 = Sk2f::Load(&devP2);
297    Sk2f p3 = Sk2f::Load(&devP3);
298    fCurrFanPoint = devP3;
299
300    // Don't crunch on the curve and inflate geometry if it is nearly flat (or just very small).
301    if (are_collinear(p0, p1, p2) &&
302        are_collinear(p1, p2, p3) &&
303        are_collinear(p0, (p1 + p2) * .5f, p3)) {
304        p3.store(&fPoints.push_back());
305        fVerbs.push_back(Verb::kLineTo);
306        return;
307    }
308
309    // Also detect near-quadratics ahead of time.
310    Sk2f tan0, tan3, c;
311    if (is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan3, c)) {
312        this->appendMonotonicQuadratics(p0, c, p3);
313        return;
314    }
315
316    double tt[2], ss[2];
317    fCurrCubicType = SkClassifyCubic(devPts, tt, ss);
318    SkASSERT(!SkCubicIsDegenerate(fCurrCubicType)); // Should have been caught above.
319
320    SkMatrix CIT;
321    ExcludedTerm skipTerm = GrPathUtils::calcCubicInverseTransposePowerBasisMatrix(devPts, &CIT);
322    SkASSERT(ExcludedTerm::kNonInvertible != skipTerm); // Should have been caught above.
323    SkASSERT(0 == CIT[6]);
324    SkASSERT(0 == CIT[7]);
325    SkASSERT(1 == CIT[8]);
326
327    // Each cubic has five different sections (not always inside t=[0..1]):
328    //
329    //   1. The section before the first inflection or loop intersection point, with padding.
330    //   2. The section that passes through the first inflection/intersection (aka the K,L
331    //      intersection point or T=tt[0]/ss[0]).
332    //   3. The section between the two inflections/intersections, with padding.
333    //   4. The section that passes through the second inflection/intersection (aka the K,M
334    //      intersection point or T=tt[1]/ss[1]).
335    //   5. The section after the second inflection/intersection, with padding.
336    //
337    // Sections 1,3,5 can be rendered directly using the CCPR cubic shader.
338    //
339    // Sections 2 & 4 must be approximated. For loop intersections we render them with
340    // quadratic(s), and when passing through an inflection point we use a plain old flat line.
341    //
342    // We find T0..T3 below to be the dividing points between these five sections.
343    float T0, T1, T2, T3;
344    if (SkCubicType::kLoop != fCurrCubicType) {
345        Sk2f t = Sk2f(static_cast<float>(tt[0]), static_cast<float>(tt[1]));
346        Sk2f s = Sk2f(static_cast<float>(ss[0]), static_cast<float>(ss[1]));
347        Sk2f pad = calc_inflect_homogeneous_padding(inflectPad, t, s, CIT, skipTerm);
348
349        float T[2];
350        ((t - pad) / s).store(T);
351        T0 = T[0];
352        T2 = T[1];
353
354        ((t + pad) / s).store(T);
355        T1 = T[0];
356        T3 = T[1];
357    } else {
358        const float T[2] = {static_cast<float>(tt[0]/ss[0]), static_cast<float>(tt[1]/ss[1])};
359        SkSTArray<3, float, true> roots[2];
360        calc_loop_intersect_padding_pts(loopIntersectPad, Sk2f::Load(T), CIT, skipTerm, roots);
361        T0 = roots[0].front();
362        if (1 == roots[0].count() || 1 == roots[1].count()) {
363            // The loop is tighter than our desired padding. Collapse the middle section to a point
364            // somewhere in the middle-ish of the loop and Sections 2 & 4 will approximate the the
365            // whole thing with quadratics.
366            T1 = T2 = (T[0] + T[1]) * .5f;
367        } else {
368            T1 = roots[0][1];
369            T2 = roots[1][1];
370        }
371        T3 = roots[1].back();
372    }
373
374    // Guarantee that T0..T3 are monotonic.
375    if (T0 > T3) {
376        // This is not a mathematically valid scenario. The only reason it would happen is if
377        // padding is very small and we have encountered FP rounding error.
378        T0 = T1 = T2 = T3 = (T0 + T3) / 2;
379    } else if (T1 > T2) {
380        // This just means padding before the middle section overlaps the padding after it. We
381        // collapse the middle section to a single point that splits the difference between the
382        // overlap in padding.
383        T1 = T2 = (T1 + T2) / 2;
384    }
385    // Clamp T1 & T2 inside T0..T3. The only reason this would be necessary is if we have
386    // encountered FP rounding error.
387    T1 = std::max(T0, std::min(T1, T3));
388    T2 = std::max(T0, std::min(T2, T3));
389
390    // Next we chop the cubic up at all T0..T3 inside 0..1 and store the resulting segments.
391    if (T1 >= 1) {
392        // Only sections 1 & 2 can be in 0..1.
393        this->chopCubic<&GrCCGeometry::appendMonotonicCubics,
394                        &GrCCGeometry::appendCubicApproximation>(p0, p1, p2, p3, T0);
395        return;
396    }
397
398    if (T2 <= 0) {
399        // Only sections 4 & 5 can be in 0..1.
400        this->chopCubic<&GrCCGeometry::appendCubicApproximation,
401                        &GrCCGeometry::appendMonotonicCubics>(p0, p1, p2, p3, T3);
402        return;
403    }
404
405    Sk2f midp0, midp1; // These hold the first two bezier points of the middle section, if needed.
406
407    if (T1 > 0) {
408        Sk2f T1T1 = Sk2f(T1);
409        Sk2f ab1 = lerp(p0, p1, T1T1);
410        Sk2f bc1 = lerp(p1, p2, T1T1);
411        Sk2f cd1 = lerp(p2, p3, T1T1);
412        Sk2f abc1 = lerp(ab1, bc1, T1T1);
413        Sk2f bcd1 = lerp(bc1, cd1, T1T1);
414        Sk2f abcd1 = lerp(abc1, bcd1, T1T1);
415
416        // Sections 1 & 2.
417        this->chopCubic<&GrCCGeometry::appendMonotonicCubics,
418                        &GrCCGeometry::appendCubicApproximation>(p0, ab1, abc1, abcd1, T0/T1);
419
420        if (T2 >= 1) {
421            // The rest of the curve is Section 3 (middle section).
422            this->appendMonotonicCubics(abcd1, bcd1, cd1, p3);
423            return;
424        }
425
426        // Now calculate the first two bezier points of the middle section. The final two will come
427        // from when we chop the other side, as that is numerically more stable.
428        midp0 = abcd1;
429        midp1 = lerp(abcd1, bcd1, Sk2f((T2 - T1) / (1 - T1)));
430    } else if (T2 >= 1) {
431        // The entire cubic is Section 3 (middle section).
432        this->appendMonotonicCubics(p0, p1, p2, p3);
433        return;
434    }
435
436    SkASSERT(T2 > 0 && T2 < 1);
437
438    Sk2f T2T2 = Sk2f(T2);
439    Sk2f ab2 = lerp(p0, p1, T2T2);
440    Sk2f bc2 = lerp(p1, p2, T2T2);
441    Sk2f cd2 = lerp(p2, p3, T2T2);
442    Sk2f abc2 = lerp(ab2, bc2, T2T2);
443    Sk2f bcd2 = lerp(bc2, cd2, T2T2);
444    Sk2f abcd2 = lerp(abc2, bcd2, T2T2);
445
446    if (T1 <= 0) {
447        // The curve begins at Section 3 (middle section).
448        this->appendMonotonicCubics(p0, ab2, abc2, abcd2);
449    } else if (T2 > T1) {
450        // Section 3 (middle section).
451        Sk2f midp2 = lerp(abc2, abcd2, T1/T2);
452        this->appendMonotonicCubics(midp0, midp1, midp2, abcd2);
453    }
454
455    // Sections 4 & 5.
456    this->chopCubic<&GrCCGeometry::appendCubicApproximation,
457                    &GrCCGeometry::appendMonotonicCubics>(abcd2, bcd2, cd2, p3, (T3-T2) / (1-T2));
458}
459
460template<GrCCGeometry::AppendCubicFn AppendLeftRight>
461inline void GrCCGeometry::chopCubicAtMidTangent(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
462                                                const Sk2f& p3, const Sk2f& tan0,
463                                                const Sk2f& tan3, int maxFutureSubdivisions) {
464    // Find the T value whose tangent is perpendicular to the vector that bisects tan0 and -tan3.
465    Sk2f n = normalize(tan0) - normalize(tan3);
466
467    float a = 3 * dot(p3 + (p1 - p2)*3 - p0, n);
468    float b = 6 * dot(p0 - p1*2 + p2, n);
469    float c = 3 * dot(p1 - p0, n);
470
471    float discr = b*b - 4*a*c;
472    if (discr < 0) {
473        // If this is the case then the cubic must be nearly flat.
474        (this->*AppendLeftRight)(p0, p1, p2, p3, maxFutureSubdivisions);
475        return;
476    }
477
478    float q = -.5f * (b + copysignf(std::sqrt(discr), b));
479    float m = .5f*q*a;
480    float T = std::abs(q*q - m) < std::abs(a*c - m) ? q/a : c/q;
481
482    this->chopCubic<AppendLeftRight, AppendLeftRight>(p0, p1, p2, p3, T, maxFutureSubdivisions);
483}
484
485template<GrCCGeometry::AppendCubicFn AppendLeft, GrCCGeometry::AppendCubicFn AppendRight>
486inline void GrCCGeometry::chopCubic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
487                                    const Sk2f& p3, float T, int maxFutureSubdivisions) {
488    if (T >= 1) {
489        (this->*AppendLeft)(p0, p1, p2, p3, maxFutureSubdivisions);
490        return;
491    }
492
493    if (T <= 0) {
494        (this->*AppendRight)(p0, p1, p2, p3, maxFutureSubdivisions);
495        return;
496    }
497
498    Sk2f TT = T;
499    Sk2f ab = lerp(p0, p1, TT);
500    Sk2f bc = lerp(p1, p2, TT);
501    Sk2f cd = lerp(p2, p3, TT);
502    Sk2f abc = lerp(ab, bc, TT);
503    Sk2f bcd = lerp(bc, cd, TT);
504    Sk2f abcd = lerp(abc, bcd, TT);
505    (this->*AppendLeft)(p0, ab, abc, abcd, maxFutureSubdivisions);
506    (this->*AppendRight)(abcd, bcd, cd, p3, maxFutureSubdivisions);
507}
508
509void GrCCGeometry::appendMonotonicCubics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
510                                         const Sk2f& p3, int maxSubdivisions) {
511    SkASSERT(maxSubdivisions >= 0);
512    if ((p0 == p3).allTrue()) {
513        return;
514    }
515
516    if (maxSubdivisions) {
517        Sk2f tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0);
518        Sk2f tan3 = first_unless_nearly_zero(p3 - p2, p3 - p1);
519
520        if (!is_convex_curve_monotonic(p0, tan0, p3, tan3)) {
521            this->chopCubicAtMidTangent<&GrCCGeometry::appendMonotonicCubics>(p0, p1, p2, p3,
522                                                                              tan0, tan3,
523                                                                              maxSubdivisions - 1);
524            return;
525        }
526    }
527
528    SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
529
530    // Don't send curves to the GPU if we know they are nearly flat (or just very small).
531    // Since the cubic segment is known to be convex at this point, our flatness check is simple.
532    if (are_collinear(p0, (p1 + p2) * .5f, p3)) {
533        p3.store(&fPoints.push_back());
534        fVerbs.push_back(Verb::kLineTo);
535        return;
536    }
537
538    p1.store(&fPoints.push_back());
539    p2.store(&fPoints.push_back());
540    p3.store(&fPoints.push_back());
541    fVerbs.push_back(Verb::kMonotonicCubicTo);
542    ++fCurrContourTallies.fCubics;
543}
544
545void GrCCGeometry::appendCubicApproximation(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
546                                            const Sk2f& p3, int maxSubdivisions) {
547    SkASSERT(maxSubdivisions >= 0);
548    if ((p0 == p3).allTrue()) {
549        return;
550    }
551
552    if (SkCubicType::kLoop != fCurrCubicType && SkCubicType::kQuadratic != fCurrCubicType) {
553        // This section passes through an inflection point, so we can get away with a flat line.
554        // This can cause some curves to feel slightly more flat when inspected rigorously back and
555        // forth against another renderer, but for now this seems acceptable given the simplicity.
556        SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
557        p3.store(&fPoints.push_back());
558        fVerbs.push_back(Verb::kLineTo);
559        return;
560    }
561
562    Sk2f tan0, tan3, c;
563    if (!is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan3, c) && maxSubdivisions) {
564        this->chopCubicAtMidTangent<&GrCCGeometry::appendCubicApproximation>(p0, p1, p2, p3,
565                                                                             tan0, tan3,
566                                                                             maxSubdivisions - 1);
567        return;
568    }
569
570    if (maxSubdivisions) {
571        this->appendMonotonicQuadratics(p0, c, p3);
572    } else {
573        this->appendSingleMonotonicQuadratic(p0, c, p3);
574    }
575}
576
577GrCCGeometry::PrimitiveTallies GrCCGeometry::endContour() {
578    SkASSERT(fBuildingContour);
579    SkASSERT(fVerbs.count() >= fCurrContourTallies.fTriangles);
580
581    // The fTriangles field currently contains this contour's starting verb index. We can now
582    // use it to calculate the size of the contour's fan.
583    int fanSize = fVerbs.count() - fCurrContourTallies.fTriangles;
584    if (fCurrFanPoint == fCurrAnchorPoint) {
585        --fanSize;
586        fVerbs.push_back(Verb::kEndClosedContour);
587    } else {
588        fVerbs.push_back(Verb::kEndOpenContour);
589    }
590
591    fCurrContourTallies.fTriangles = SkTMax(fanSize - 2, 0);
592
593    SkDEBUGCODE(fBuildingContour = false);
594    return fCurrContourTallies;
595}
596