1419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton/* 2419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton * Copyright 2017 Google Inc. 3419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton * 4419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton * Use of this source code is governed by a BSD-style license that can be 5419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton * found in the LICENSE file. 6419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton */ 7419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 8383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton#include "GrCCGeometry.h" 9419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 10419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton#include "GrTypes.h" 117f578bf07b016778e3105b7655a895728b12d847Chris Dalton#include "GrPathUtils.h" 12419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton#include <algorithm> 13419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton#include <cmath> 14419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton#include <cstdlib> 15419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 16419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton// We convert between SkPoint and Sk2f freely throughout this file. 17419a94da028b33425a0feeb44d0d022a5d3d3704Chris DaltonGR_STATIC_ASSERT(SK_SCALAR_IS_FLOAT); 18419a94da028b33425a0feeb44d0d022a5d3d3704Chris DaltonGR_STATIC_ASSERT(2 * sizeof(float) == sizeof(SkPoint)); 19419a94da028b33425a0feeb44d0d022a5d3d3704Chris DaltonGR_STATIC_ASSERT(0 == offsetof(SkPoint, fX)); 20419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 21383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::beginPath() { 22c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(!fBuildingContour); 23c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fVerbs.push_back(Verb::kBeginPath); 24c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 25c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 26383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::beginContour(const SkPoint& devPt) { 27c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(!fBuildingContour); 28c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 29c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fCurrFanPoint = fCurrAnchorPoint = devPt; 30c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 31c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton // Store the current verb count in the fTriangles field for now. When we close the contour we 32c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton // will use this value to calculate the actual number of triangles in its fan. 3384403d7f53d88b2449fd19415538ba1479fe300bChris Dalton fCurrContourTallies = {fVerbs.count(), 0, 0, 0}; 34c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 35c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fPoints.push_back(devPt); 36c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fVerbs.push_back(Verb::kBeginContour); 37c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 38383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton SkDEBUGCODE(fBuildingContour = true); 39c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 40c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 41383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::lineTo(const SkPoint& devPt) { 42c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(fBuildingContour); 43900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton SkASSERT(fCurrFanPoint == fPoints.back()); 44c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fCurrFanPoint = devPt; 45c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fPoints.push_back(devPt); 46c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fVerbs.push_back(Verb::kLineTo); 47c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 48c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 49419a94da028b33425a0feeb44d0d022a5d3d3704Chris Daltonstatic inline Sk2f normalize(const Sk2f& n) { 50419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f nn = n*n; 51419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton return n * (nn + SkNx_shuffle<1,0>(nn)).rsqrt(); 52419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton} 53419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 54419a94da028b33425a0feeb44d0d022a5d3d3704Chris Daltonstatic inline float dot(const Sk2f& a, const Sk2f& b) { 55419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton float product[2]; 56419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton (a * b).store(product); 57419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton return product[0] + product[1]; 58419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton} 59419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 60900cd05037739eac6fd7bb8611ac489bb5ad305eChris Daltonstatic inline bool are_collinear(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2) { 6143646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton static constexpr float kFlatnessTolerance = 4; // 1/4 of a pixel. 62900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton 63900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton // Area (times 2) of the triangle. 64900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton Sk2f a = (p0 - p1) * SkNx_shuffle<1,0>(p1 - p2); 65900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton a = (a - SkNx_shuffle<1,0>(a)).abs(); 66900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton 67900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton // Bounding box of the triangle. 68900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton Sk2f bbox0 = Sk2f::Min(Sk2f::Min(p0, p1), p2); 69900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton Sk2f bbox1 = Sk2f::Max(Sk2f::Max(p0, p1), p2); 70900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton 71900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton // The triangle is linear if its area is within a fraction of the largest bounding box 72900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton // dimension, or else if its area is within a fraction of a pixel. 73900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton return (a * (kFlatnessTolerance/2) < Sk2f::Max(bbox1 - bbox0, 1)).anyTrue(); 74900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton} 75900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton 76419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton// Returns whether the (convex) curve segment is monotonic with respect to [endPt - startPt]. 77419a94da028b33425a0feeb44d0d022a5d3d3704Chris Daltonstatic inline bool is_convex_curve_monotonic(const Sk2f& startPt, const Sk2f& startTan, 78419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton const Sk2f& endPt, const Sk2f& endTan) { 79419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f v = endPt - startPt; 80419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton float dot0 = dot(startTan, v); 81419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton float dot1 = dot(endTan, v); 82419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 83419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // A small, negative tolerance handles floating-point error in the case when one tangent 84419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // approaches 0 length, meaning the (convex) curve segment is effectively a flat line. 85419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton float tolerance = -std::max(std::abs(dot0), std::abs(dot1)) * SK_ScalarNearlyZero; 86419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton return dot0 >= tolerance && dot1 >= tolerance; 87419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton} 88419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 89419a94da028b33425a0feeb44d0d022a5d3d3704Chris Daltonstatic inline Sk2f lerp(const Sk2f& a, const Sk2f& b, const Sk2f& t) { 90419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton return SkNx_fma(t, b - a, a); 91419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton} 92419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 93383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::quadraticTo(const SkPoint& devP0, const SkPoint& devP1) { 94c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(fBuildingContour); 95900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton SkASSERT(fCurrFanPoint == fPoints.back()); 96c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 97c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton Sk2f p0 = Sk2f::Load(&fCurrFanPoint); 98c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton Sk2f p1 = Sk2f::Load(&devP0); 99c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton Sk2f p2 = Sk2f::Load(&devP1); 100c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fCurrFanPoint = devP1; 101419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 10229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton this->appendMonotonicQuadratics(p0, p1, p2); 10329011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton} 10429011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 105383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltoninline void GrCCGeometry::appendMonotonicQuadratics(const Sk2f& p0, const Sk2f& p1, 106383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& p2) { 107419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f tan0 = p1 - p0; 108419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f tan1 = p2 - p1; 10929011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 110419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // This should almost always be this case for well-behaved curves in the real world. 11143646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton if (is_convex_curve_monotonic(p0, tan0, p2, tan1)) { 11243646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton this->appendSingleMonotonicQuadratic(p0, p1, p2); 113c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton return; 114419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton } 115419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 116419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // Chop the curve into two segments with equal curvature. To do this we find the T value whose 117419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // tangent is perpendicular to the vector that bisects tan0 and -tan1. 118419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f n = normalize(tan0) - normalize(tan1); 119419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 120419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // This tangent can be found where (dQ(t) dot n) = 0: 121419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // 122419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // 0 = (dQ(t) dot n) = | 2*t 1 | * | p0 - 2*p1 + p2 | * | n | 123419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // | -2*p0 + 2*p1 | | . | 124419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // 125419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // = | 2*t 1 | * | tan1 - tan0 | * | n | 126419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // | 2*tan0 | | . | 127419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // 128419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // = 2*t * ((tan1 - tan0) dot n) + (2*tan0 dot n) 129419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // 130419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton // t = (tan0 dot n) / ((tan0 - tan1) dot n) 131419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f dQ1n = (tan0 - tan1) * n; 132419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f dQ0n = tan0 * n; 133419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f t = (dQ0n + SkNx_shuffle<1,0>(dQ0n)) / (dQ1n + SkNx_shuffle<1,0>(dQ1n)); 134419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton t = Sk2f::Min(Sk2f::Max(t, 0), 1); // Clamp for FP error. 135419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 136419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f p01 = SkNx_fma(t, tan0, p0); 137419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f p12 = SkNx_fma(t, tan1, p1); 138419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton Sk2f p012 = lerp(p01, p12, t); 139419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 14043646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton this->appendSingleMonotonicQuadratic(p0, p01, p012); 14143646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton this->appendSingleMonotonicQuadratic(p012, p12, p2); 14243646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton} 14343646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton 144383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltoninline void GrCCGeometry::appendSingleMonotonicQuadratic(const Sk2f& p0, const Sk2f& p1, 145383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& p2) { 14643646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1])); 14743646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton 14843646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton // Don't send curves to the GPU if we know they are nearly flat (or just very small). 14943646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton if (are_collinear(p0, p1, p2)) { 15043646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton p2.store(&fPoints.push_back()); 15143646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton fVerbs.push_back(Verb::kLineTo); 15243646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton return; 15343646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton } 15443646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton 15543646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton p1.store(&fPoints.push_back()); 156c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton p2.store(&fPoints.push_back()); 15743646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton fVerbs.push_back(Verb::kMonotonicQuadraticTo); 15843646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton ++fCurrContourTallies.fQuadratics; 159c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 160c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 1617f578bf07b016778e3105b7655a895728b12d847Chris Daltonusing ExcludedTerm = GrPathUtils::ExcludedTerm; 1627f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1637f578bf07b016778e3105b7655a895728b12d847Chris Dalton// Calculates the padding to apply around inflection points, in homogeneous parametric coordinates. 1647f578bf07b016778e3105b7655a895728b12d847Chris Dalton// 1657f578bf07b016778e3105b7655a895728b12d847Chris Dalton// More specifically, if the inflection point lies at C(t/s), then C((t +/- returnValue) / s) will 1667f578bf07b016778e3105b7655a895728b12d847Chris Dalton// be the two points on the curve at which a square box with radius "padRadius" will have a corner 1677f578bf07b016778e3105b7655a895728b12d847Chris Dalton// that touches the inflection point's tangent line. 1687f578bf07b016778e3105b7655a895728b12d847Chris Dalton// 1697f578bf07b016778e3105b7655a895728b12d847Chris Dalton// A serpentine cubic has two inflection points, so this method takes Sk2f and computes the padding 1707f578bf07b016778e3105b7655a895728b12d847Chris Dalton// for both in SIMD. 1717f578bf07b016778e3105b7655a895728b12d847Chris Daltonstatic inline Sk2f calc_inflect_homogeneous_padding(float padRadius, const Sk2f& t, const Sk2f& s, 1727f578bf07b016778e3105b7655a895728b12d847Chris Dalton const SkMatrix& CIT, ExcludedTerm skipTerm) { 1737f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(padRadius >= 0); 1747f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1757f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Clx = s*s*s; 1767f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Cly = (ExcludedTerm::kLinearTerm == skipTerm) ? s*s*t*-3 : s*t*t*3; 1777f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1787f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Lx = CIT[0] * Clx + CIT[3] * Cly; 1797f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Ly = CIT[1] * Clx + CIT[4] * Cly; 1807f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1817f578bf07b016778e3105b7655a895728b12d847Chris Dalton float ret[2]; 1827f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bloat = padRadius * (Lx.abs() + Ly.abs()); 1837f578bf07b016778e3105b7655a895728b12d847Chris Dalton (bloat * s >= 0).thenElse(bloat, -bloat).store(ret); 1847f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1857f578bf07b016778e3105b7655a895728b12d847Chris Dalton ret[0] = cbrtf(ret[0]); 1867f578bf07b016778e3105b7655a895728b12d847Chris Dalton ret[1] = cbrtf(ret[1]); 1877f578bf07b016778e3105b7655a895728b12d847Chris Dalton return Sk2f::Load(ret); 1887f578bf07b016778e3105b7655a895728b12d847Chris Dalton} 1897f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1907f578bf07b016778e3105b7655a895728b12d847Chris Daltonstatic inline void swap_if_greater(float& a, float& b) { 1917f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (a > b) { 1927f578bf07b016778e3105b7655a895728b12d847Chris Dalton std::swap(a, b); 1937f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 1947f578bf07b016778e3105b7655a895728b12d847Chris Dalton} 1957f578bf07b016778e3105b7655a895728b12d847Chris Dalton 1967f578bf07b016778e3105b7655a895728b12d847Chris Dalton// Calculates all parameter values for a loop at which points a square box with radius "padRadius" 1977f578bf07b016778e3105b7655a895728b12d847Chris Dalton// will have a corner that touches a tangent line from the intersection. 1987f578bf07b016778e3105b7655a895728b12d847Chris Dalton// 1997f578bf07b016778e3105b7655a895728b12d847Chris Dalton// T2 must contain the lesser parameter value of the loop intersection in its first component, and 2007f578bf07b016778e3105b7655a895728b12d847Chris Dalton// the greater in its second. 2017f578bf07b016778e3105b7655a895728b12d847Chris Dalton// 2027f578bf07b016778e3105b7655a895728b12d847Chris Dalton// roots[0] will be filled with 1 or 3 sorted parameter values, representing the padding points 2037f578bf07b016778e3105b7655a895728b12d847Chris Dalton// around the first tangent. roots[1] will be filled with the padding points for the second tangent. 2047f578bf07b016778e3105b7655a895728b12d847Chris Daltonstatic inline void calc_loop_intersect_padding_pts(float padRadius, const Sk2f& T2, 2057f578bf07b016778e3105b7655a895728b12d847Chris Dalton const SkMatrix& CIT, ExcludedTerm skipTerm, 2067f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkSTArray<3, float, true> roots[2]) { 2077f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(padRadius >= 0); 2087f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(T2[0] <= T2[1]); 2097f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(roots[0].empty()); 2107f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(roots[1].empty()); 2117f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2127f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f T1 = SkNx_shuffle<1,0>(T2); 2137f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Cl = (ExcludedTerm::kLinearTerm == skipTerm) ? T2*-2 - T1 : T2*T2 + T2*T1*2; 2147f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Lx = Cl * CIT[3] + CIT[0]; 2157f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f Ly = Cl * CIT[4] + CIT[1]; 2167f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2177f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bloat = Sk2f(+.5f * padRadius, -.5f * padRadius) * (Lx.abs() + Ly.abs()); 2187f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f q = (1.f/3) * (T2 - T1); 2197f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2207f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f qqq = q*q*q; 2217f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f discr = qqq*bloat*2 + bloat*bloat; 2227f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2237f578bf07b016778e3105b7655a895728b12d847Chris Dalton float numRoots[2], D[2]; 2247f578bf07b016778e3105b7655a895728b12d847Chris Dalton (discr < 0).thenElse(3, 1).store(numRoots); 2257f578bf07b016778e3105b7655a895728b12d847Chris Dalton (T2 - q).store(D); 2267f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2277f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Values for calculating one root. 2287f578bf07b016778e3105b7655a895728b12d847Chris Dalton float R[2], QQ[2]; 2297f578bf07b016778e3105b7655a895728b12d847Chris Dalton if ((discr >= 0).anyTrue()) { 2307f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f r = qqq + bloat; 2317f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f s = r.abs() + discr.sqrt(); 2327f578bf07b016778e3105b7655a895728b12d847Chris Dalton (r > 0).thenElse(-s, s).store(R); 2337f578bf07b016778e3105b7655a895728b12d847Chris Dalton (q*q).store(QQ); 2347f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 2357f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2367f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Values for calculating three roots. 2377f578bf07b016778e3105b7655a895728b12d847Chris Dalton float P[2], cosTheta3[2]; 2387f578bf07b016778e3105b7655a895728b12d847Chris Dalton if ((discr < 0).anyTrue()) { 2397f578bf07b016778e3105b7655a895728b12d847Chris Dalton (q.abs() * -2).store(P); 2407f578bf07b016778e3105b7655a895728b12d847Chris Dalton ((q >= 0).thenElse(1, -1) + bloat / qqq.abs()).store(cosTheta3); 2417f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 2427f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2437f578bf07b016778e3105b7655a895728b12d847Chris Dalton for (int i = 0; i < 2; ++i) { 2447f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (1 == numRoots[i]) { 2457f578bf07b016778e3105b7655a895728b12d847Chris Dalton float A = cbrtf(R[i]); 2467f578bf07b016778e3105b7655a895728b12d847Chris Dalton float B = A != 0 ? QQ[i]/A : 0; 2477f578bf07b016778e3105b7655a895728b12d847Chris Dalton roots[i].push_back(A + B + D[i]); 2487f578bf07b016778e3105b7655a895728b12d847Chris Dalton continue; 2497f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 2507f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2517f578bf07b016778e3105b7655a895728b12d847Chris Dalton static constexpr float k2PiOver3 = 2 * SK_ScalarPI / 3; 2527f578bf07b016778e3105b7655a895728b12d847Chris Dalton float theta = std::acos(cosTheta3[i]) * (1.f/3); 2537f578bf07b016778e3105b7655a895728b12d847Chris Dalton roots[i].push_back(P[i] * std::cos(theta) + D[i]); 2547f578bf07b016778e3105b7655a895728b12d847Chris Dalton roots[i].push_back(P[i] * std::cos(theta + k2PiOver3) + D[i]); 2557f578bf07b016778e3105b7655a895728b12d847Chris Dalton roots[i].push_back(P[i] * std::cos(theta - k2PiOver3) + D[i]); 2567f578bf07b016778e3105b7655a895728b12d847Chris Dalton 2577f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Sort the three roots. 2587f578bf07b016778e3105b7655a895728b12d847Chris Dalton swap_if_greater(roots[i][0], roots[i][1]); 2597f578bf07b016778e3105b7655a895728b12d847Chris Dalton swap_if_greater(roots[i][1], roots[i][2]); 2607f578bf07b016778e3105b7655a895728b12d847Chris Dalton swap_if_greater(roots[i][0], roots[i][1]); 2617f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 2627f578bf07b016778e3105b7655a895728b12d847Chris Dalton} 2637f578bf07b016778e3105b7655a895728b12d847Chris Dalton 26429011a2bda560a645e6ddbe162df0856fe259e7bChris Daltonstatic inline Sk2f first_unless_nearly_zero(const Sk2f& a, const Sk2f& b) { 26529011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton Sk2f aa = a*a; 26629011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton aa += SkNx_shuffle<1,0>(aa); 26729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton SkASSERT(aa[0] == aa[1]); 26829011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 26929011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton Sk2f bb = b*b; 27029011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton bb += SkNx_shuffle<1,0>(bb); 27129011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton SkASSERT(bb[0] == bb[1]); 27229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 27329011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton return (aa > bb * SK_ScalarNearlyZero).thenElse(a, b); 27429011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton} 27529011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 27629011a2bda560a645e6ddbe162df0856fe259e7bChris Daltonstatic inline bool is_cubic_nearly_quadratic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, 27729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton const Sk2f& p3, Sk2f& tan0, Sk2f& tan3, Sk2f& c) { 27829011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0); 27929011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton tan3 = first_unless_nearly_zero(p3 - p2, p3 - p1); 28029011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 28129011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton Sk2f c1 = SkNx_fma(Sk2f(1.5f), tan0, p0); 28229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton Sk2f c2 = SkNx_fma(Sk2f(-1.5f), tan3, p3); 28329011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton c = (c1 + c2) * .5f; // Hopefully optimized out if not used? 28429011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 28529011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton return ((c1 - c2).abs() <= 1).allTrue(); 28629011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton} 28729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 288383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::cubicTo(const SkPoint& devP1, const SkPoint& devP2, const SkPoint& devP3, 289383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton float inflectPad, float loopIntersectPad) { 290c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(fBuildingContour); 291900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton SkASSERT(fCurrFanPoint == fPoints.back()); 292c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 2937f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkPoint devPts[4] = {fCurrFanPoint, devP1, devP2, devP3}; 2947f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f p0 = Sk2f::Load(&fCurrFanPoint); 2957f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f p1 = Sk2f::Load(&devP1); 2967f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f p2 = Sk2f::Load(&devP2); 2977f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f p3 = Sk2f::Load(&devP3); 2987f578bf07b016778e3105b7655a895728b12d847Chris Dalton fCurrFanPoint = devP3; 299c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 30043646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton // Don't crunch on the curve and inflate geometry if it is nearly flat (or just very small). 301900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton if (are_collinear(p0, p1, p2) && 302900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton are_collinear(p1, p2, p3) && 303900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton are_collinear(p0, (p1 + p2) * .5f, p3)) { 304900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton p3.store(&fPoints.push_back()); 305900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton fVerbs.push_back(Verb::kLineTo); 306900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton return; 307900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton } 308900cd05037739eac6fd7bb8611ac489bb5ad305eChris Dalton 30929011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton // Also detect near-quadratics ahead of time. 31029011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton Sk2f tan0, tan3, c; 31129011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton if (is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan3, c)) { 31229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton this->appendMonotonicQuadratics(p0, c, p3); 313c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton return; 314c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton } 315c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 31629011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton double tt[2], ss[2]; 31729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton fCurrCubicType = SkClassifyCubic(devPts, tt, ss); 31829011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton SkASSERT(!SkCubicIsDegenerate(fCurrCubicType)); // Should have been caught above. 31929011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton 3207f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkMatrix CIT; 3217f578bf07b016778e3105b7655a895728b12d847Chris Dalton ExcludedTerm skipTerm = GrPathUtils::calcCubicInverseTransposePowerBasisMatrix(devPts, &CIT); 32229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton SkASSERT(ExcludedTerm::kNonInvertible != skipTerm); // Should have been caught above. 3237f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(0 == CIT[6]); 3247f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(0 == CIT[7]); 3257f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(1 == CIT[8]); 326c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 3277f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Each cubic has five different sections (not always inside t=[0..1]): 3287f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 3297f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 1. The section before the first inflection or loop intersection point, with padding. 3307f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 2. The section that passes through the first inflection/intersection (aka the K,L 3317f578bf07b016778e3105b7655a895728b12d847Chris Dalton // intersection point or T=tt[0]/ss[0]). 3327f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 3. The section between the two inflections/intersections, with padding. 3337f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 4. The section that passes through the second inflection/intersection (aka the K,M 3347f578bf07b016778e3105b7655a895728b12d847Chris Dalton // intersection point or T=tt[1]/ss[1]). 3357f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 5. The section after the second inflection/intersection, with padding. 3367f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 3377f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Sections 1,3,5 can be rendered directly using the CCPR cubic shader. 3387f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 3397f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Sections 2 & 4 must be approximated. For loop intersections we render them with 3407f578bf07b016778e3105b7655a895728b12d847Chris Dalton // quadratic(s), and when passing through an inflection point we use a plain old flat line. 3417f578bf07b016778e3105b7655a895728b12d847Chris Dalton // 3427f578bf07b016778e3105b7655a895728b12d847Chris Dalton // We find T0..T3 below to be the dividing points between these five sections. 3437f578bf07b016778e3105b7655a895728b12d847Chris Dalton float T0, T1, T2, T3; 3447f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (SkCubicType::kLoop != fCurrCubicType) { 3457f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f t = Sk2f(static_cast<float>(tt[0]), static_cast<float>(tt[1])); 3467f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f s = Sk2f(static_cast<float>(ss[0]), static_cast<float>(ss[1])); 3477f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f pad = calc_inflect_homogeneous_padding(inflectPad, t, s, CIT, skipTerm); 3487f578bf07b016778e3105b7655a895728b12d847Chris Dalton 3497f578bf07b016778e3105b7655a895728b12d847Chris Dalton float T[2]; 3507f578bf07b016778e3105b7655a895728b12d847Chris Dalton ((t - pad) / s).store(T); 3517f578bf07b016778e3105b7655a895728b12d847Chris Dalton T0 = T[0]; 3527f578bf07b016778e3105b7655a895728b12d847Chris Dalton T2 = T[1]; 3537f578bf07b016778e3105b7655a895728b12d847Chris Dalton 3547f578bf07b016778e3105b7655a895728b12d847Chris Dalton ((t + pad) / s).store(T); 3557f578bf07b016778e3105b7655a895728b12d847Chris Dalton T1 = T[0]; 3567f578bf07b016778e3105b7655a895728b12d847Chris Dalton T3 = T[1]; 3577f578bf07b016778e3105b7655a895728b12d847Chris Dalton } else { 3587f578bf07b016778e3105b7655a895728b12d847Chris Dalton const float T[2] = {static_cast<float>(tt[0]/ss[0]), static_cast<float>(tt[1]/ss[1])}; 3597f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkSTArray<3, float, true> roots[2]; 3607f578bf07b016778e3105b7655a895728b12d847Chris Dalton calc_loop_intersect_padding_pts(loopIntersectPad, Sk2f::Load(T), CIT, skipTerm, roots); 3617f578bf07b016778e3105b7655a895728b12d847Chris Dalton T0 = roots[0].front(); 3627f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (1 == roots[0].count() || 1 == roots[1].count()) { 3637f578bf07b016778e3105b7655a895728b12d847Chris Dalton // The loop is tighter than our desired padding. Collapse the middle section to a point 3647f578bf07b016778e3105b7655a895728b12d847Chris Dalton // somewhere in the middle-ish of the loop and Sections 2 & 4 will approximate the the 3657f578bf07b016778e3105b7655a895728b12d847Chris Dalton // whole thing with quadratics. 3667f578bf07b016778e3105b7655a895728b12d847Chris Dalton T1 = T2 = (T[0] + T[1]) * .5f; 3677f578bf07b016778e3105b7655a895728b12d847Chris Dalton } else { 3687f578bf07b016778e3105b7655a895728b12d847Chris Dalton T1 = roots[0][1]; 3697f578bf07b016778e3105b7655a895728b12d847Chris Dalton T2 = roots[1][1]; 3707f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 3717f578bf07b016778e3105b7655a895728b12d847Chris Dalton T3 = roots[1].back(); 3727f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 373c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 3747f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Guarantee that T0..T3 are monotonic. 3757f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T0 > T3) { 3767f578bf07b016778e3105b7655a895728b12d847Chris Dalton // This is not a mathematically valid scenario. The only reason it would happen is if 3777f578bf07b016778e3105b7655a895728b12d847Chris Dalton // padding is very small and we have encountered FP rounding error. 3787f578bf07b016778e3105b7655a895728b12d847Chris Dalton T0 = T1 = T2 = T3 = (T0 + T3) / 2; 3797f578bf07b016778e3105b7655a895728b12d847Chris Dalton } else if (T1 > T2) { 3807f578bf07b016778e3105b7655a895728b12d847Chris Dalton // This just means padding before the middle section overlaps the padding after it. We 3817f578bf07b016778e3105b7655a895728b12d847Chris Dalton // collapse the middle section to a single point that splits the difference between the 3827f578bf07b016778e3105b7655a895728b12d847Chris Dalton // overlap in padding. 3837f578bf07b016778e3105b7655a895728b12d847Chris Dalton T1 = T2 = (T1 + T2) / 2; 3847f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 3857f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Clamp T1 & T2 inside T0..T3. The only reason this would be necessary is if we have 3867f578bf07b016778e3105b7655a895728b12d847Chris Dalton // encountered FP rounding error. 3877f578bf07b016778e3105b7655a895728b12d847Chris Dalton T1 = std::max(T0, std::min(T1, T3)); 3887f578bf07b016778e3105b7655a895728b12d847Chris Dalton T2 = std::max(T0, std::min(T2, T3)); 3897f578bf07b016778e3105b7655a895728b12d847Chris Dalton 3907f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Next we chop the cubic up at all T0..T3 inside 0..1 and store the resulting segments. 3917f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T1 >= 1) { 3927f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Only sections 1 & 2 can be in 0..1. 393383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton this->chopCubic<&GrCCGeometry::appendMonotonicCubics, 394383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton &GrCCGeometry::appendCubicApproximation>(p0, p1, p2, p3, T0); 3957f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 3967f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 397c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 3987f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T2 <= 0) { 3997f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Only sections 4 & 5 can be in 0..1. 400383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton this->chopCubic<&GrCCGeometry::appendCubicApproximation, 401383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton &GrCCGeometry::appendMonotonicCubics>(p0, p1, p2, p3, T3); 4027f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 4037f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 404c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 4057f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f midp0, midp1; // These hold the first two bezier points of the middle section, if needed. 4067f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4077f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T1 > 0) { 4087f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f T1T1 = Sk2f(T1); 4097f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f ab1 = lerp(p0, p1, T1T1); 4107f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bc1 = lerp(p1, p2, T1T1); 4117f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f cd1 = lerp(p2, p3, T1T1); 4127f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f abc1 = lerp(ab1, bc1, T1T1); 4137f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bcd1 = lerp(bc1, cd1, T1T1); 4147f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f abcd1 = lerp(abc1, bcd1, T1T1); 4157f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4167f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Sections 1 & 2. 417383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton this->chopCubic<&GrCCGeometry::appendMonotonicCubics, 418383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton &GrCCGeometry::appendCubicApproximation>(p0, ab1, abc1, abcd1, T0/T1); 4197f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4207f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T2 >= 1) { 4217f578bf07b016778e3105b7655a895728b12d847Chris Dalton // The rest of the curve is Section 3 (middle section). 4227f578bf07b016778e3105b7655a895728b12d847Chris Dalton this->appendMonotonicCubics(abcd1, bcd1, cd1, p3); 4237f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 424c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton } 425c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 4267f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Now calculate the first two bezier points of the middle section. The final two will come 4277f578bf07b016778e3105b7655a895728b12d847Chris Dalton // from when we chop the other side, as that is numerically more stable. 4287f578bf07b016778e3105b7655a895728b12d847Chris Dalton midp0 = abcd1; 4297f578bf07b016778e3105b7655a895728b12d847Chris Dalton midp1 = lerp(abcd1, bcd1, Sk2f((T2 - T1) / (1 - T1))); 4307f578bf07b016778e3105b7655a895728b12d847Chris Dalton } else if (T2 >= 1) { 4317f578bf07b016778e3105b7655a895728b12d847Chris Dalton // The entire cubic is Section 3 (middle section). 4327f578bf07b016778e3105b7655a895728b12d847Chris Dalton this->appendMonotonicCubics(p0, p1, p2, p3); 4337f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 4347f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 435c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 4367f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(T2 > 0 && T2 < 1); 4377f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4387f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f T2T2 = Sk2f(T2); 4397f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f ab2 = lerp(p0, p1, T2T2); 4407f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bc2 = lerp(p1, p2, T2T2); 4417f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f cd2 = lerp(p2, p3, T2T2); 4427f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f abc2 = lerp(ab2, bc2, T2T2); 4437f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bcd2 = lerp(bc2, cd2, T2T2); 4447f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f abcd2 = lerp(abc2, bcd2, T2T2); 4457f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4467f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T1 <= 0) { 4477f578bf07b016778e3105b7655a895728b12d847Chris Dalton // The curve begins at Section 3 (middle section). 4487f578bf07b016778e3105b7655a895728b12d847Chris Dalton this->appendMonotonicCubics(p0, ab2, abc2, abcd2); 4497f578bf07b016778e3105b7655a895728b12d847Chris Dalton } else if (T2 > T1) { 4507f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Section 3 (middle section). 4517f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f midp2 = lerp(abc2, abcd2, T1/T2); 4527f578bf07b016778e3105b7655a895728b12d847Chris Dalton this->appendMonotonicCubics(midp0, midp1, midp2, abcd2); 4537f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 4547f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4557f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Sections 4 & 5. 456383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton this->chopCubic<&GrCCGeometry::appendCubicApproximation, 457383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton &GrCCGeometry::appendMonotonicCubics>(abcd2, bcd2, cd2, p3, (T3-T2) / (1-T2)); 4587f578bf07b016778e3105b7655a895728b12d847Chris Dalton} 459c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 460383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltontemplate<GrCCGeometry::AppendCubicFn AppendLeftRight> 461383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltoninline void GrCCGeometry::chopCubicAtMidTangent(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, 462383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& p3, const Sk2f& tan0, 463383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& tan3, int maxFutureSubdivisions) { 4647f578bf07b016778e3105b7655a895728b12d847Chris Dalton // Find the T value whose tangent is perpendicular to the vector that bisects tan0 and -tan3. 4657f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f n = normalize(tan0) - normalize(tan3); 4667f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4677f578bf07b016778e3105b7655a895728b12d847Chris Dalton float a = 3 * dot(p3 + (p1 - p2)*3 - p0, n); 4687f578bf07b016778e3105b7655a895728b12d847Chris Dalton float b = 6 * dot(p0 - p1*2 + p2, n); 4697f578bf07b016778e3105b7655a895728b12d847Chris Dalton float c = 3 * dot(p1 - p0, n); 4707f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4717f578bf07b016778e3105b7655a895728b12d847Chris Dalton float discr = b*b - 4*a*c; 4727f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (discr < 0) { 4737f578bf07b016778e3105b7655a895728b12d847Chris Dalton // If this is the case then the cubic must be nearly flat. 4747f578bf07b016778e3105b7655a895728b12d847Chris Dalton (this->*AppendLeftRight)(p0, p1, p2, p3, maxFutureSubdivisions); 4757f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 476c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton } 477c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 4787f578bf07b016778e3105b7655a895728b12d847Chris Dalton float q = -.5f * (b + copysignf(std::sqrt(discr), b)); 4797f578bf07b016778e3105b7655a895728b12d847Chris Dalton float m = .5f*q*a; 4807f578bf07b016778e3105b7655a895728b12d847Chris Dalton float T = std::abs(q*q - m) < std::abs(a*c - m) ? q/a : c/q; 4817f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4827f578bf07b016778e3105b7655a895728b12d847Chris Dalton this->chopCubic<AppendLeftRight, AppendLeftRight>(p0, p1, p2, p3, T, maxFutureSubdivisions); 483c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 484c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 485383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltontemplate<GrCCGeometry::AppendCubicFn AppendLeft, GrCCGeometry::AppendCubicFn AppendRight> 486383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltoninline void GrCCGeometry::chopCubic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, 487383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& p3, float T, int maxFutureSubdivisions) { 4887f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T >= 1) { 4897f578bf07b016778e3105b7655a895728b12d847Chris Dalton (this->*AppendLeft)(p0, p1, p2, p3, maxFutureSubdivisions); 4907f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 4917f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 4927f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4937f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (T <= 0) { 4947f578bf07b016778e3105b7655a895728b12d847Chris Dalton (this->*AppendRight)(p0, p1, p2, p3, maxFutureSubdivisions); 4957f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 4967f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 4977f578bf07b016778e3105b7655a895728b12d847Chris Dalton 4987f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f TT = T; 4997f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f ab = lerp(p0, p1, TT); 5007f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bc = lerp(p1, p2, TT); 5017f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f cd = lerp(p2, p3, TT); 5027f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f abc = lerp(ab, bc, TT); 5037f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f bcd = lerp(bc, cd, TT); 5047f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f abcd = lerp(abc, bcd, TT); 5057f578bf07b016778e3105b7655a895728b12d847Chris Dalton (this->*AppendLeft)(p0, ab, abc, abcd, maxFutureSubdivisions); 5067f578bf07b016778e3105b7655a895728b12d847Chris Dalton (this->*AppendRight)(abcd, bcd, cd, p3, maxFutureSubdivisions); 507c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 508c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 509383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::appendMonotonicCubics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, 510383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& p3, int maxSubdivisions) { 51129011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton SkASSERT(maxSubdivisions >= 0); 5127f578bf07b016778e3105b7655a895728b12d847Chris Dalton if ((p0 == p3).allTrue()) { 5137f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 5147f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 5157f578bf07b016778e3105b7655a895728b12d847Chris Dalton 5167f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (maxSubdivisions) { 5177f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0); 5187f578bf07b016778e3105b7655a895728b12d847Chris Dalton Sk2f tan3 = first_unless_nearly_zero(p3 - p2, p3 - p1); 5197f578bf07b016778e3105b7655a895728b12d847Chris Dalton 5207f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (!is_convex_curve_monotonic(p0, tan0, p3, tan3)) { 521383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton this->chopCubicAtMidTangent<&GrCCGeometry::appendMonotonicCubics>(p0, p1, p2, p3, 522383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton tan0, tan3, 523383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton maxSubdivisions - 1); 5247f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 5257f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 5267f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 5277f578bf07b016778e3105b7655a895728b12d847Chris Dalton 5287f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1])); 52943646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton 53043646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton // Don't send curves to the GPU if we know they are nearly flat (or just very small). 53143646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton // Since the cubic segment is known to be convex at this point, our flatness check is simple. 53243646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton if (are_collinear(p0, (p1 + p2) * .5f, p3)) { 53343646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton p3.store(&fPoints.push_back()); 53443646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton fVerbs.push_back(Verb::kLineTo); 53543646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton return; 53643646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton } 53743646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton 5387f578bf07b016778e3105b7655a895728b12d847Chris Dalton p1.store(&fPoints.push_back()); 5397f578bf07b016778e3105b7655a895728b12d847Chris Dalton p2.store(&fPoints.push_back()); 5407f578bf07b016778e3105b7655a895728b12d847Chris Dalton p3.store(&fPoints.push_back()); 541be4ffab4e208ec47b4298621b9c9e8456f31717eChris Dalton fVerbs.push_back(Verb::kMonotonicCubicTo); 542be4ffab4e208ec47b4298621b9c9e8456f31717eChris Dalton ++fCurrContourTallies.fCubics; 543c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton} 544c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 545383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Daltonvoid GrCCGeometry::appendCubicApproximation(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, 546383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton const Sk2f& p3, int maxSubdivisions) { 54729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton SkASSERT(maxSubdivisions >= 0); 5487f578bf07b016778e3105b7655a895728b12d847Chris Dalton if ((p0 == p3).allTrue()) { 5497f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 5507f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 5517f578bf07b016778e3105b7655a895728b12d847Chris Dalton 5527f578bf07b016778e3105b7655a895728b12d847Chris Dalton if (SkCubicType::kLoop != fCurrCubicType && SkCubicType::kQuadratic != fCurrCubicType) { 5537f578bf07b016778e3105b7655a895728b12d847Chris Dalton // This section passes through an inflection point, so we can get away with a flat line. 5547f578bf07b016778e3105b7655a895728b12d847Chris Dalton // This can cause some curves to feel slightly more flat when inspected rigorously back and 5557f578bf07b016778e3105b7655a895728b12d847Chris Dalton // forth against another renderer, but for now this seems acceptable given the simplicity. 5567f578bf07b016778e3105b7655a895728b12d847Chris Dalton SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1])); 5577f578bf07b016778e3105b7655a895728b12d847Chris Dalton p3.store(&fPoints.push_back()); 5587f578bf07b016778e3105b7655a895728b12d847Chris Dalton fVerbs.push_back(Verb::kLineTo); 5597f578bf07b016778e3105b7655a895728b12d847Chris Dalton return; 5607f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 5617f578bf07b016778e3105b7655a895728b12d847Chris Dalton 56229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton Sk2f tan0, tan3, c; 56329011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton if (!is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan3, c) && maxSubdivisions) { 564383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton this->chopCubicAtMidTangent<&GrCCGeometry::appendCubicApproximation>(p0, p1, p2, p3, 565383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton tan0, tan3, 566383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton maxSubdivisions - 1); 56729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton return; 5687f578bf07b016778e3105b7655a895728b12d847Chris Dalton } 5697f578bf07b016778e3105b7655a895728b12d847Chris Dalton 57043646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton if (maxSubdivisions) { 57143646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton this->appendMonotonicQuadratics(p0, c, p3); 57243646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton } else { 57343646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton this->appendSingleMonotonicQuadratic(p0, c, p3); 57443646533fa6fb7cd6724cf00f6b8af15ac1649eaChris Dalton } 5757f578bf07b016778e3105b7655a895728b12d847Chris Dalton} 5767f578bf07b016778e3105b7655a895728b12d847Chris Dalton 577383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris DaltonGrCCGeometry::PrimitiveTallies GrCCGeometry::endContour() { 578c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(fBuildingContour); 579c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton SkASSERT(fVerbs.count() >= fCurrContourTallies.fTriangles); 580c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 581c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton // The fTriangles field currently contains this contour's starting verb index. We can now 582c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton // use it to calculate the size of the contour's fan. 583c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton int fanSize = fVerbs.count() - fCurrContourTallies.fTriangles; 584c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton if (fCurrFanPoint == fCurrAnchorPoint) { 585c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton --fanSize; 586c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fVerbs.push_back(Verb::kEndClosedContour); 587c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton } else { 588c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fVerbs.push_back(Verb::kEndOpenContour); 589c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton } 590c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton 591c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton fCurrContourTallies.fTriangles = SkTMax(fanSize - 2, 0); 592419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton 593383a2ef6edb84dbebc7a9c22ea7423037bbf6a2fChris Dalton SkDEBUGCODE(fBuildingContour = false); 594c1e59638b4a08f5210f72f671292b1b3759f54c6Chris Dalton return fCurrContourTallies; 595419a94da028b33425a0feeb44d0d022a5d3d3704Chris Dalton} 596