1/*
2 * Copyright 2021 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#ifndef skgpu_tessellate_Tessellation_DEFINED
9#define skgpu_tessellate_Tessellation_DEFINED
10
11#include "include/core/SkPaint.h"
12#include "include/core/SkPoint.h"
13#include "include/core/SkStrokeRec.h"
14#include "include/gpu/GrTypes.h"
15#include "src/base/SkVx.h"
16
17class SkMatrix;
18class SkPath;
19struct SkRect;
20
21namespace skgpu::tess {
22
23// Don't allow linearized segments to be off by more than 1/4th of a pixel from the true curve.
24constexpr static float kPrecision = 4;
25
26// This is the maximum number of subdivisions of a Bezier curve that can be represented in the fixed
27// count vertex and index buffers. If rendering a curve that requires more subdivisions, it must be
28// chopped.
29constexpr static int kMaxResolveLevel = 5;
30
31// This is the maximum number of parametric segments (linear sections) that a curve can be split
32// into. This is the same for path filling and stroking, although fixed-count stroking also uses
33// additional vertices to handle radial segments, joins, and caps. Additionally the fixed-count
34// path filling algorithms snap their dynamic vertex counts to powers-of-two, whereas the stroking
35// algorithm does not.
36constexpr static int kMaxParametricSegments = 1 << kMaxResolveLevel;
37constexpr static int kMaxParametricSegments_p2 = kMaxParametricSegments * kMaxParametricSegments;
38constexpr static int kMaxParametricSegments_p4 = kMaxParametricSegments_p2 *
39 kMaxParametricSegments_p2;
40
41// Don't tessellate paths that might have an individual curve that requires more than 1024 segments.
42// (See wangs_formula::worst_case_cubic). If this is the case, call "PreChopPathCurves" first.
43// Standard chopping, when Wang's formula is between kMaxParametricSegments and
44// kMaxTessellationSegmentsPerCurve is handled automatically by PatchWriter. It differs from
45// PreChopPathCurves in that it does no culling of offscreen chopped paths.
46constexpr static float kMaxSegmentsPerCurve = 1024;
47constexpr static float kMaxSegmentsPerCurve_p2 = kMaxSegmentsPerCurve * kMaxSegmentsPerCurve;
48constexpr static float kMaxSegmentsPerCurve_p4 = kMaxSegmentsPerCurve_p2 * kMaxSegmentsPerCurve_p2;
49
50// Returns a new path, equivalent to 'path' within the given viewport, whose verbs can all be drawn
51// with 'maxSegments' tessellation segments or fewer, while staying within '1/tessellationPrecision'
52// pixels of the true curve. Curves and chops that fall completely outside the viewport are
53// flattened into lines.
54SkPath PreChopPathCurves(float tessellationPrecision,
55 const SkPath&,
56 const SkMatrix&,
57 const SkRect& viewport);
58
59// How many triangles are in a curve with 2^resolveLevel line segments?
60// Resolve level defines the tessellation factor for filled paths drawn using curves or wedges.
61constexpr static int NumCurveTrianglesAtResolveLevel(int resolveLevel) {
62 // resolveLevel=0 -> 0 line segments -> 0 triangles
63 // resolveLevel=1 -> 2 line segments -> 1 triangle
64 // resolveLevel=2 -> 4 line segments -> 3 triangles
65 // resolveLevel=3 -> 8 line segments -> 7 triangles
66 // ...
67 return (1 << resolveLevel) - 1;
68}
69
70// Optional attribs that are included in tessellation patches, following the control points and in
71// the same order as they appear here.
72enum class PatchAttribs {
73 // Attribs.
74 kNone = 0,
75 kJoinControlPoint = 1 << 0, // [float2] Used by strokes. This defines tangent direction.
76 kFanPoint = 1 << 1, // [float2] Used by wedges. This is the center point the wedges fan around.
77 kStrokeParams = 1 << 2, // [float2] Used when strokes have different widths or join types.
78 kColor = 1 << 3, // [ubyte4 or float4] Used when patches have different colors.
79 kPaintDepth = 1 << 4, // [float] Used in Graphite to specify depth attachment value for draw.
80 kExplicitCurveType = 1 << 5, // [float] Used when GPU can't infer curve type based on infinity.
81 kSsboIndex = 1 << 7, // [int] Used to index into a shared storage buffer for this patch's
82 // uniform values.
83
84 // Extra flags.
85 kWideColorIfEnabled = 1 << 6, // If kColor is set, specifies it to be float4 wide color.
86};
87
88GR_MAKE_BITFIELD_CLASS_OPS(PatchAttribs)
89
90// When PatchAttribs::kExplicitCurveType is set, these are the values that tell the GPU what type of
91// curve is being drawn.
92constexpr static float kCubicCurveType [[maybe_unused]] = 0;
93constexpr static float kConicCurveType [[maybe_unused]] = 1;
94constexpr static float kTriangularConicCurveType [[maybe_unused]] = 2; // Conic curve with w=Inf.
95
96// Returns the packed size in bytes of the attribs portion of tessellation patches (or instances) in
97// GPU buffers.
98constexpr size_t PatchAttribsStride(PatchAttribs attribs) {
99 return (attribs & PatchAttribs::kJoinControlPoint ? sizeof(float) * 2 : 0) +
100 (attribs & PatchAttribs::kFanPoint ? sizeof(float) * 2 : 0) +
101 (attribs & PatchAttribs::kStrokeParams ? sizeof(float) * 2 : 0) +
102 (attribs & PatchAttribs::kColor
103 ? (attribs & PatchAttribs::kWideColorIfEnabled ? sizeof(float)
104 : sizeof(uint8_t)) * 4 : 0) +
105 (attribs & PatchAttribs::kPaintDepth ? sizeof(float) : 0) +
106 (attribs & PatchAttribs::kExplicitCurveType ? sizeof(float) : 0) +
107 (attribs & PatchAttribs::kSsboIndex ? (sizeof(int)) : 0);
108}
109constexpr size_t PatchStride(PatchAttribs attribs) {
110 return 4*sizeof(SkPoint) + PatchAttribsStride(attribs);
111}
112
113// Finds 0, 1, or 2 T values at which to chop the given curve in order to guarantee the resulting
114// cubics are convex and rotate no more than 180 degrees.
115//
116// - If the cubic is "serpentine", then the T values are any inflection points in [0 < T < 1].
117// - If the cubic is linear, then the T values are any 180-degree cusp points in [0 < T < 1].
118// - Otherwise the T value is the point at which rotation reaches 180 degrees, iff in [0 < T < 1].
119//
120// 'areCusps' is set to true if the chop point occurred at a cusp (within tolerance), or if the chop
121// point(s) occurred at 180-degree turnaround points on a degenerate flat line.
122int FindCubicConvex180Chops(const SkPoint[], float T[2], bool* areCusps);
123
124// Returns true if the given conic (or quadratic) has a cusp point. The w value is not necessary in
125// determining this. If there is a cusp, it can be found at the midtangent.
126inline bool ConicHasCusp(const SkPoint p[3]) {
127 SkVector a = p[1] - p[0];
128 SkVector b = p[2] - p[1];
129 // A conic of any class can only have a cusp if it is a degenerate flat line with a 180 degree
130 // turnarund. To detect this, the beginning and ending tangents must be parallel
131 // (a.cross(b) == 0) and pointing in opposite directions (a.dot(b) < 0).
132 return a.cross(vec: b) == 0 && a.dot(vec: b) < 0;
133}
134
135// We encode all of a join's information in a single float value:
136//
137// Negative => Round Join
138// Zero => Bevel Join
139// Positive => Miter join, and the value is also the miter limit
140//
141inline float GetJoinType(const SkStrokeRec& stroke) {
142 switch (stroke.getJoin()) {
143 case SkPaint::kRound_Join: return -1;
144 case SkPaint::kBevel_Join: return 0;
145 case SkPaint::kMiter_Join: SkASSERT(stroke.getMiter() >= 0); return stroke.getMiter();
146 }
147 SkUNREACHABLE;
148}
149
150// This float2 gets written out with each patch/instance if PatchAttribs::kStrokeParams is enabled.
151struct StrokeParams {
152 StrokeParams() = default;
153 StrokeParams(float radius, float joinType) : fRadius(radius), fJoinType(joinType) {}
154 StrokeParams(const SkStrokeRec& stroke) {
155 this->set(stroke);
156 }
157 void set(const SkStrokeRec& stroke) {
158 fRadius = stroke.getWidth() * .5f;
159 fJoinType = GetJoinType(stroke);
160 }
161
162 float fRadius;
163 float fJoinType; // See GetJoinType().
164};
165
166inline bool StrokesHaveEqualParams(const SkStrokeRec& a, const SkStrokeRec& b) {
167 return a.getWidth() == b.getWidth() && a.getJoin() == b.getJoin() &&
168 (a.getJoin() != SkPaint::kMiter_Join || a.getMiter() == b.getMiter());
169}
170
171// Returns the fixed number of edges that are always emitted with the given join type. If the
172// join is round, the caller needs to account for the additional radial edges on their own.
173// Specifically, each join always emits:
174//
175// * Two colocated edges at the beginning (a full-width edge to seam with the preceding stroke
176// and a half-width edge to begin the join).
177//
178// * An extra edge in the middle for miter joins, or else a variable number of radial edges
179// for round joins (the caller is responsible for counting radial edges from round joins).
180//
181// * A half-width edge at the end of the join that will be colocated with the first
182// (full-width) edge of the stroke.
183//
184constexpr int NumFixedEdgesInJoin(SkPaint::Join joinType) {
185 switch (joinType) {
186 case SkPaint::kMiter_Join:
187 return 4;
188 case SkPaint::kRound_Join:
189 // The caller is responsible for counting the variable number of middle, radial
190 // segments on round joins.
191 [[fallthrough]];
192 case SkPaint::kBevel_Join:
193 return 3;
194 }
195 SkUNREACHABLE;
196}
197constexpr int NumFixedEdgesInJoin(const StrokeParams& strokeParams) {
198 // The caller is responsible for counting the variable number of segments for round joins.
199 return strokeParams.fJoinType > 0.f ? /* miter */ 4 : /* round or bevel */ 3;
200}
201
202// Decides the number of radial segments the tessellator adds for each curve. (Uniform steps
203// in tangent angle.) The tessellator will add this number of radial segments for each
204// radian of rotation in local path space.
205inline float CalcNumRadialSegmentsPerRadian(float approxDevStrokeRadius) {
206 float cosTheta = 1.f - (1.f / kPrecision) / approxDevStrokeRadius;
207 return .5f / acosf(x: std::max(a: cosTheta, b: -1.f));
208}
209
210} // namespace skgpu::tess
211
212#endif // skgpu_tessellate_Tessellation_DEFINED
213

source code of flutter_engine/third_party/skia/src/gpu/tessellate/Tessellation.h