1 /* 2 * Copyright 2022 Google LLC 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 #ifndef skgpu_tessellate_LinearTolerances_DEFINED 9 #define skgpu_tessellate_LinearTolerances_DEFINED 10 11 #include "include/core/SkScalar.h" 12 #include "include/private/base/SkAssert.h" 13 #include "src/gpu/tessellate/Tessellation.h" 14 #include "src/gpu/tessellate/WangsFormula.h" 15 16 #include <algorithm> 17 18 namespace skgpu::tess { 19 20 /** 21 * LinearTolerances stores state to approximate the final device-space transform applied 22 * to curves, and uses that to calculate segmentation levels for both the parametric curves and 23 * radial components (when stroking, where you have to represent the offset of a curve). 24 * These tolerances determine the worst-case number of parametric and radial segments required to 25 * accurately linearize curves. 26 * - segments = a linear subsection on the curve, either defined as parametric (linear in t) or 27 * radial (linear in curve's internal rotation). 28 * - edges = orthogonal geometry to segments, used in stroking to offset from the central curve by 29 * half the stroke width, or to construct the join geometry. 30 * 31 * The tolerance values and decisions are estimated in the local path space, although PatchWriter 32 * uses a 2x2 vector transform that approximates the scale/skew (as-best-as-possible) of the full 33 * local-to-device transform applied in the vertex shader. 34 * 35 * The properties tracked in LinearTolerances can be used to compute the final segmentation factor 36 * for filled paths (the resolve level) or stroked paths (the number of edges). 37 */ 38 class LinearTolerances { 39 public: numParametricSegments_p4()40 float numParametricSegments_p4() const { return fNumParametricSegments_p4; } numRadialSegmentsPerRadian()41 float numRadialSegmentsPerRadian() const { return fNumRadialSegmentsPerRadian; } numEdgesInJoins()42 int numEdgesInJoins() const { return fEdgesInJoins; } 43 44 // Fast log2 of minimum required # of segments per tracked Wang's formula calculations. requiredResolveLevel()45 int requiredResolveLevel() const { 46 // log16(n^4) == log2(n) 47 return wangs_formula::nextlog16(fNumParametricSegments_p4); 48 } 49 requiredStrokeEdges()50 int requiredStrokeEdges() const { 51 // The maximum rotation we can have in a stroke is 180 degrees (SK_ScalarPI radians). 52 int maxRadialSegmentsInStroke = 53 std::max(SkScalarCeilToInt(fNumRadialSegmentsPerRadian * SK_ScalarPI), 1); 54 55 int maxParametricSegmentsInStroke = 56 SkScalarCeilToInt(wangs_formula::root4(fNumParametricSegments_p4)); 57 SkASSERT(maxParametricSegmentsInStroke >= 1); 58 59 // Now calculate the maximum number of edges we will need in the stroke portion of the 60 // instance. The first and last edges in a stroke are shared by both the parametric and 61 // radial sets of edges, so the total number of edges is: 62 // 63 // numCombinedEdges = numParametricEdges + numRadialEdges - 2 64 // 65 // It's important to differentiate between the number of edges and segments in a strip: 66 // 67 // numSegments = numEdges - 1 68 // 69 // So the total number of combined edges in the stroke is: 70 // 71 // numEdgesInStroke = numParametricSegments + 1 + numRadialSegments + 1 - 2 72 // = numParametricSegments + numRadialSegments 73 // 74 int maxEdgesInStroke = maxRadialSegmentsInStroke + maxParametricSegmentsInStroke; 75 76 // Each triangle strip has two sections: It starts with a join then transitions to a 77 // stroke. The number of edges in an instance is the sum of edges from the join and 78 // stroke sections both. 79 // NOTE: The final join edge and the first stroke edge are co-located, however we still 80 // need to emit both because the join's edge is half-width and the stroke is full-width. 81 return fEdgesInJoins + maxEdgesInStroke; 82 } 83 setParametricSegments(float n4)84 void setParametricSegments(float n4) { 85 SkASSERT(n4 >= 0.f); 86 fNumParametricSegments_p4 = n4; 87 } 88 setStroke(const StrokeParams & strokeParams,float maxScale)89 void setStroke(const StrokeParams& strokeParams, float maxScale) { 90 float approxDeviceStrokeRadius; 91 if (strokeParams.fRadius == 0.f) { 92 // Hairlines are always 1 px wide 93 approxDeviceStrokeRadius = 0.5f; 94 } else { 95 // Approximate max scale * local stroke width / 2 96 approxDeviceStrokeRadius = strokeParams.fRadius * maxScale; 97 } 98 99 fNumRadialSegmentsPerRadian = CalcNumRadialSegmentsPerRadian(approxDeviceStrokeRadius); 100 101 fEdgesInJoins = NumFixedEdgesInJoin(strokeParams); 102 if (strokeParams.fJoinType < 0.f && fNumRadialSegmentsPerRadian > 0.f) { 103 // For round joins we need to count the radial edges on our own. Account for a 104 // worst-case join of 180 degrees (SK_ScalarPI radians). 105 fEdgesInJoins += SkScalarCeilToInt(fNumRadialSegmentsPerRadian * SK_ScalarPI) - 1; 106 } 107 } 108 accumulate(const LinearTolerances & tolerances)109 void accumulate(const LinearTolerances& tolerances) { 110 if (tolerances.fNumParametricSegments_p4 > fNumParametricSegments_p4) { 111 fNumParametricSegments_p4 = tolerances.fNumParametricSegments_p4; 112 } 113 if (tolerances.fNumRadialSegmentsPerRadian > fNumRadialSegmentsPerRadian) { 114 fNumRadialSegmentsPerRadian = tolerances.fNumRadialSegmentsPerRadian; 115 } 116 if (tolerances.fEdgesInJoins > fEdgesInJoins) { 117 fEdgesInJoins = tolerances.fEdgesInJoins; 118 } 119 } 120 121 private: 122 // Used for both fills and strokes, always at least one parametric segment 123 float fNumParametricSegments_p4 = 1.f; 124 // Used for strokes, adding additional segments along the curve to account for its rotation 125 // TODO: Currently we assume the worst case 180 degree rotation for any curve, but tracking 126 // max(radialSegments * patch curvature) would be tighter. This would require computing 127 // rotation per patch, which could be approximated by tracking min of the tangent dot 128 // products, but then we'd be left with the slightly less accurate 129 // "max(radialSegments) * acos(min(tan dot product))". It is also unknown if requesting 130 // tighter bounds pays off with less GPU work for more CPU work 131 float fNumRadialSegmentsPerRadian = 0.f; 132 // Used for strokes, tracking the number of additional vertices required to handle joins 133 // based on the join type and stroke width. 134 // TODO: For round joins, we could also track the rotation angle of the join, instead of 135 // assuming 180 degrees. PatchWriter has all necessary control points to do so, but runs 136 // into similar trade offs between CPU vs GPU work, and accuracy vs. reducing calls to acos. 137 int fEdgesInJoins = 0; 138 }; 139 140 } // namespace skgpu::tess 141 142 #endif // skgpu_tessellate_LinearTolerances_DEFINED 143