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