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