1/*
2 * Copyright 2018 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 "src/gpu/tessellate/GrStrokePatchBuilder.h"
9
10#include "include/core/SkStrokeRec.h"
11#include "include/private/SkNx.h"
12#include "src/core/SkGeometry.h"
13#include "src/core/SkMathPriv.h"
14#include "src/core/SkPathPriv.h"
15#include "src/gpu/tessellate/GrStrokeTessellateShader.h"
16#include "src/gpu/tessellate/GrVectorXform.h"
17#include "src/gpu/tessellate/GrWangsFormula.h"
18
19// This is the maximum distance in pixels that we can stray from the edge of a stroke when
20// converting it to flat line segments.
21static constexpr float kLinearizationIntolerance = 8; // 1/8 pixel.
22
23constexpr static float kInternalRoundJoinType = GrStrokeTessellateShader::kInternalRoundJoinType;
24
25static Sk2f lerp(const Sk2f& a, const Sk2f& b, float T) {
26 SkASSERT(1 != T); // The below does not guarantee lerp(a, b, 1) === b.
27 return (b - a) * T + a;
28}
29
30static inline void transpose(const Sk2f& a, const Sk2f& b, Sk2f* X, Sk2f* Y) {
31 float transpose[4];
32 a.store(transpose);
33 b.store(transpose+2);
34 Sk2f::Load2(transpose, X, Y);
35}
36
37static inline float calc_curvature_costheta(const Sk2f& leftTan, const Sk2f& rightTan) {
38 Sk2f X, Y;
39 transpose(leftTan, rightTan, &X, &Y);
40 Sk2f invlength = (X*X + Y*Y).rsqrt();
41 Sk2f dotprod = leftTan * rightTan;
42 return (dotprod[0] + dotprod[1]) * invlength[0] * invlength[1];
43}
44
45void GrStrokePatchBuilder::allocVertexChunk(int minVertexAllocCount) {
46 VertexChunk* chunk = &fVertexChunkArray->push_back();
47 fCurrChunkVertexData = (SkPoint*)fTarget->makeVertexSpaceAtLeast(
48 sizeof(SkPoint), minVertexAllocCount, minVertexAllocCount, &chunk->fVertexBuffer,
49 &chunk->fBaseVertex, &fCurrChunkVertexCapacity);
50 fCurrChunkMinVertexAllocCount = minVertexAllocCount;
51}
52
53SkPoint* GrStrokePatchBuilder::reservePatch() {
54 constexpr static int kNumVerticesPerPatch = GrStrokeTessellateShader::kNumVerticesPerPatch;
55 if (fVertexChunkArray->back().fVertexCount + kNumVerticesPerPatch > fCurrChunkVertexCapacity) {
56 // The current chunk is full. Time to allocate a new one. (And no need to put back vertices;
57 // the buffer is full.)
58 this->allocVertexChunk(fCurrChunkMinVertexAllocCount * 2);
59 }
60 if (!fCurrChunkVertexData) {
61 SkDebugf("WARNING: Failed to allocate vertex buffer for tessellated stroke.");
62 return nullptr;
63 }
64 SkASSERT(fVertexChunkArray->back().fVertexCount + kNumVerticesPerPatch <=
65 fCurrChunkVertexCapacity);
66 SkPoint* patch = fCurrChunkVertexData + fVertexChunkArray->back().fVertexCount;
67 fVertexChunkArray->back().fVertexCount += kNumVerticesPerPatch;
68 return patch;
69}
70
71void GrStrokePatchBuilder::writeCubicSegment(float leftJoinType, const SkPoint pts[4],
72 float overrideNumSegments) {
73 SkPoint c1 = (pts[1] == pts[0]) ? pts[2] : pts[1];
74 SkPoint c2 = (pts[2] == pts[3]) ? pts[1] : pts[2];
75
76 if (fHasPreviousSegment) {
77 this->writeJoin(leftJoinType, pts[0], fLastControlPoint, c1);
78 } else {
79 fCurrContourFirstControlPoint = c1;
80 fHasPreviousSegment = true;
81 }
82
83 if (SkPoint* patch = this->reservePatch()) {
84 memcpy(patch, pts, sizeof(SkPoint) * 4);
85 patch[4].set(overrideNumSegments, fCurrStrokeRadius);
86 }
87
88 fLastControlPoint = c2;
89 fCurrentPoint = pts[3];
90}
91
92void GrStrokePatchBuilder::writeJoin(float joinType, const SkPoint& anchorPoint,
93 const SkPoint& prevControlPoint,
94 const SkPoint& nextControlPoint) {
95 if (SkPoint* joinPatch = this->reservePatch()) {
96 joinPatch[0] = anchorPoint;
97 joinPatch[1] = prevControlPoint;
98 joinPatch[2] = nextControlPoint;
99 joinPatch[3] = anchorPoint;
100 joinPatch[4].set(joinType, fCurrStrokeRadius);
101 }
102}
103
104void GrStrokePatchBuilder::writeSquareCap(const SkPoint& endPoint, const SkPoint& controlPoint) {
105 SkVector v = (endPoint - controlPoint);
106 v.normalize();
107 SkPoint capPoint = endPoint + v*fCurrStrokeRadius;
108 // Construct a line that incorporates controlPoint so we get a water tight edge with the rest of
109 // the stroke. The cubic will technically step outside the cap, but we will force it to only
110 // have one segment, giving edges only at the endpoints.
111 if (SkPoint* capPatch = this->reservePatch()) {
112 capPatch[0] = endPoint;
113 capPatch[1] = controlPoint;
114 // Straddle the midpoint of the cap because the tessellated geometry emits a center point at
115 // T=.5, and we need to ensure that point stays inside the cap.
116 capPatch[2] = endPoint + capPoint - controlPoint;
117 capPatch[3] = capPoint;
118 capPatch[4].set(1, fCurrStrokeRadius);
119 }
120}
121
122void GrStrokePatchBuilder::writeCaps() {
123 if (!fHasPreviousSegment) {
124 // We don't have any control points to orient the caps. In this case, square and round caps
125 // are specified to be drawn as an axis-aligned square or circle respectively. Assign
126 // default control points that achieve this.
127 fCurrContourFirstControlPoint = fCurrContourStartPoint - SkPoint{1,0};
128 fLastControlPoint = fCurrContourStartPoint + SkPoint{1,0};
129 fCurrentPoint = fCurrContourStartPoint;
130 }
131
132 switch (fCurrStrokeCapType) {
133 case SkPaint::kButt_Cap:
134 break;
135 case SkPaint::kRound_Cap:
136 // A round cap is the same thing as a 180-degree round join.
137 this->writeJoin(GrStrokeTessellateShader::kRoundJoinType, fCurrContourStartPoint,
138 fCurrContourFirstControlPoint, fCurrContourFirstControlPoint);
139 this->writeJoin(GrStrokeTessellateShader::kRoundJoinType, fCurrentPoint,
140 fLastControlPoint, fLastControlPoint);
141 break;
142 case SkPaint::kSquare_Cap:
143 this->writeSquareCap(fCurrContourStartPoint, fCurrContourFirstControlPoint);
144 this->writeSquareCap(fCurrentPoint, fLastControlPoint);
145 break;
146 }
147}
148
149void GrStrokePatchBuilder::addPath(const SkPath& path, const SkStrokeRec& stroke) {
150 this->beginPath(stroke);
151 SkPathVerb previousVerb = SkPathVerb::kClose;
152 for (auto [verb, rawPts, w] : SkPathPriv::Iterate(path)) {
153 SkPoint pts[4];
154 int numPtsInVerb = SkPathPriv::PtsInIter((unsigned)verb);
155 for (int i = 0; i < numPtsInVerb; ++i) {
156 // TEMPORORY: Scale all the points up front. SkFind*MaxCurvature and GrWangsFormula::*
157 // both expect arrays of points. As we refine this class and its math, this scale will
158 // hopefully be integrated more efficiently.
159 pts[i] = rawPts[i] * fMatrixScale;
160 }
161 switch (verb) {
162 case SkPathVerb::kMove:
163 // "A subpath ... consisting of a single moveto shall not be stroked."
164 // https://www.w3.org/TR/SVG11/painting.html#StrokeProperties
165 if (previousVerb != SkPathVerb::kMove && previousVerb != SkPathVerb::kClose) {
166 this->writeCaps();
167 }
168 this->moveTo(pts[0]);
169 break;
170 case SkPathVerb::kClose:
171 this->close();
172 break;
173 case SkPathVerb::kLine:
174 SkASSERT(previousVerb != SkPathVerb::kClose);
175 this->lineTo(pts[0], pts[1]);
176 break;
177 case SkPathVerb::kQuad:
178 SkASSERT(previousVerb != SkPathVerb::kClose);
179 this->quadraticTo(pts);
180 break;
181 case SkPathVerb::kCubic:
182 SkASSERT(previousVerb != SkPathVerb::kClose);
183 this->cubicTo(pts);
184 break;
185 case SkPathVerb::kConic:
186 SkASSERT(previousVerb != SkPathVerb::kClose);
187 SkUNREACHABLE;
188 }
189 previousVerb = verb;
190 }
191 if (previousVerb != SkPathVerb::kMove && previousVerb != SkPathVerb::kClose) {
192 this->writeCaps();
193 }
194}
195
196static float join_type_from_join(SkPaint::Join join) {
197 switch (join) {
198 case SkPaint::kBevel_Join:
199 return GrStrokeTessellateShader::kBevelJoinType;
200 case SkPaint::kMiter_Join:
201 return GrStrokeTessellateShader::kMiterJoinType;
202 case SkPaint::kRound_Join:
203 return GrStrokeTessellateShader::kRoundJoinType;
204 }
205 SkUNREACHABLE;
206}
207
208void GrStrokePatchBuilder::beginPath(const SkStrokeRec& stroke) {
209 // We don't support hairline strokes. For now, the client can transform the path into device
210 // space and then use a stroke width of 1.
211 SkASSERT(stroke.getWidth() > 0);
212
213 fCurrStrokeRadius = stroke.getWidth()/2 * fMatrixScale;
214 fCurrStrokeJoinType = join_type_from_join(stroke.getJoin());
215 fCurrStrokeCapType = stroke.getCap();
216
217 // Find the angle of curvature where the arc height above a simple line from point A to point B
218 // is equal to 1/kLinearizationIntolerance. (The arc height is always the same no matter how
219 // long the line is. What we are interested in is the difference in height between the part of
220 // the stroke whose normal is orthogonal to the line, vs the heights at the endpoints.)
221 float r = std::max(1 - 1/(fCurrStrokeRadius * kLinearizationIntolerance), 0.f);
222 fMaxCurvatureCosTheta = 2*r*r - 1;
223
224 fHasPreviousSegment = false;
225}
226
227void GrStrokePatchBuilder::moveTo(const SkPoint& pt) {
228 fHasPreviousSegment = false;
229 fCurrContourStartPoint = pt;
230}
231
232void GrStrokePatchBuilder::lineTo(const SkPoint& p0, const SkPoint& p1) {
233 this->lineTo(fCurrStrokeJoinType, p0, p1);
234}
235
236void GrStrokePatchBuilder::lineTo(float leftJoinType, const SkPoint& pt0, const SkPoint& pt1) {
237 Sk2f p0 = Sk2f::Load(&pt0);
238 Sk2f p1 = Sk2f::Load(&pt1);
239 if ((p0 == p1).allTrue()) {
240 return;
241 }
242 this->writeCubicSegment(leftJoinType, p0, lerp(p0, p1, 1/3.f), lerp(p0, p1, 2/3.f), p1, 1);
243}
244
245void GrStrokePatchBuilder::quadraticTo(const SkPoint P[3]) {
246 this->quadraticTo(fCurrStrokeJoinType, P, SkFindQuadMaxCurvature(P));
247}
248
249void GrStrokePatchBuilder::quadraticTo(float leftJoinType, const SkPoint P[3],
250 float maxCurvatureT) {
251 if (P[1] == P[0] || P[1] == P[2]) {
252 this->lineTo(leftJoinType, P[0], P[2]);
253 return;
254 }
255
256 // Decide a lower bound on the length (in parametric sense) of linear segments the curve will be
257 // chopped into.
258 int numSegments = 1 << GrWangsFormula::quadratic_log2(kLinearizationIntolerance, P);
259 float segmentLength = SkScalarInvert(numSegments);
260
261 Sk2f p0 = Sk2f::Load(P);
262 Sk2f p1 = Sk2f::Load(P+1);
263 Sk2f p2 = Sk2f::Load(P+2);
264
265 Sk2f tan0 = p1 - p0;
266 Sk2f tan1 = p2 - p1;
267
268 // At + B gives a vector tangent to the quadratic.
269 Sk2f A = p0 - p1*2 + p2;
270 Sk2f B = p1 - p0;
271
272 // Find a line segment that crosses max curvature.
273 float leftT = maxCurvatureT - segmentLength/2;
274 float rightT = maxCurvatureT + segmentLength/2;
275 Sk2f leftTan, rightTan;
276 if (leftT <= 0) {
277 leftT = 0;
278 leftTan = tan0;
279 rightT = segmentLength;
280 rightTan = A*rightT + B;
281 } else if (rightT >= 1) {
282 leftT = 1 - segmentLength;
283 leftTan = A*leftT + B;
284 rightT = 1;
285 rightTan = tan1;
286 } else {
287 leftTan = A*leftT + B;
288 rightTan = A*rightT + B;
289 }
290
291 // Check if curvature is too strong for a triangle strip on the line segment that crosses max
292 // curvature. If it is, we will chop and convert the segment to a "lineTo" with round joins.
293 //
294 // FIXME: This is quite costly and the vast majority of curves only have moderate curvature. We
295 // would benefit significantly from a quick reject that detects curves that don't need special
296 // treatment for strong curvature.
297 if (numSegments > 1 && calc_curvature_costheta(leftTan, rightTan) < fMaxCurvatureCosTheta) {
298 SkPoint ptsBuffer[5];
299 const SkPoint* currQuadratic = P;
300
301 if (leftT > 0) {
302 SkChopQuadAt(currQuadratic, ptsBuffer, leftT);
303 this->quadraticTo(leftJoinType, ptsBuffer, /*maxCurvatureT=*/1);
304 if (rightT < 1) {
305 rightT = (rightT - leftT) / (1 - leftT);
306 }
307 currQuadratic = ptsBuffer + 2;
308 } else {
309 this->rotateTo(leftJoinType, currQuadratic[0], currQuadratic[1]);
310 }
311
312 if (rightT < 1) {
313 SkChopQuadAt(currQuadratic, ptsBuffer, rightT);
314 this->lineTo(kInternalRoundJoinType, ptsBuffer[0], ptsBuffer[2]);
315 this->quadraticTo(kInternalRoundJoinType, ptsBuffer + 2, /*maxCurvatureT=*/0);
316 } else {
317 this->lineTo(kInternalRoundJoinType, currQuadratic[0], currQuadratic[2]);
318 this->rotateTo(kInternalRoundJoinType, currQuadratic[2],
319 currQuadratic[2]*2 - currQuadratic[1]);
320 }
321 return;
322 }
323 if (numSegments > fMaxTessellationSegments) {
324 SkPoint ptsBuffer[5];
325 SkChopQuadAt(P, ptsBuffer, 0.5f);
326 this->quadraticTo(leftJoinType, ptsBuffer, 0);
327 this->quadraticTo(kInternalRoundJoinType, ptsBuffer + 3, 0);
328 return;
329 }
330
331 this->writeCubicSegment(leftJoinType, p0, lerp(p0, p1, 2/3.f), lerp(p1, p2, 1/3.f), p2);
332}
333
334void GrStrokePatchBuilder::cubicTo(const SkPoint P[4]) {
335 float roots[3];
336 int numRoots = SkFindCubicMaxCurvature(P, roots);
337 this->cubicTo(fCurrStrokeJoinType, P,
338 numRoots > 0 ? roots[numRoots/2] : 0,
339 numRoots > 1 ? roots[0] : kLeftMaxCurvatureNone,
340 numRoots > 2 ? roots[2] : kRightMaxCurvatureNone);
341}
342
343void GrStrokePatchBuilder::cubicTo(float leftJoinType, const SkPoint P[4], float maxCurvatureT,
344 float leftMaxCurvatureT, float rightMaxCurvatureT) {
345 if (P[1] == P[2] && (P[1] == P[0] || P[1] == P[3])) {
346 this->lineTo(leftJoinType, P[0], P[3]);
347 return;
348 }
349
350 // Decide a lower bound on the length (in parametric sense) of linear segments the curve will be
351 // chopped into.
352 int numSegments = 1 << GrWangsFormula::cubic_log2(kLinearizationIntolerance, P);
353 float segmentLength = SkScalarInvert(numSegments);
354
355 Sk2f p0 = Sk2f::Load(P);
356 Sk2f p1 = Sk2f::Load(P+1);
357 Sk2f p2 = Sk2f::Load(P+2);
358 Sk2f p3 = Sk2f::Load(P+3);
359
360 Sk2f tan0 = p1 - p0;
361 Sk2f tan1 = p3 - p2;
362
363 // At^2 + Bt + C gives a vector tangent to the cubic. (More specifically, it's the derivative
364 // minus an irrelevant scale by 3, since all we care about is the direction.)
365 Sk2f A = p3 + (p1 - p2)*3 - p0;
366 Sk2f B = (p0 - p1*2 + p2)*2;
367 Sk2f C = p1 - p0;
368
369 // Find a line segment that crosses max curvature.
370 float leftT = maxCurvatureT - segmentLength/2;
371 float rightT = maxCurvatureT + segmentLength/2;
372 Sk2f leftTan, rightTan;
373 if (leftT <= 0) {
374 leftT = 0;
375 leftTan = tan0;
376 rightT = segmentLength;
377 rightTan = A*rightT*rightT + B*rightT + C;
378 } else if (rightT >= 1) {
379 leftT = 1 - segmentLength;
380 leftTan = A*leftT*leftT + B*leftT + C;
381 rightT = 1;
382 rightTan = tan1;
383 } else {
384 leftTan = A*leftT*leftT + B*leftT + C;
385 rightTan = A*rightT*rightT + B*rightT + C;
386 }
387
388 // Check if curvature is too strong for a triangle strip on the line segment that crosses max
389 // curvature. If it is, we will chop and convert the segment to a "lineTo" with round joins.
390 //
391 // FIXME: This is quite costly and the vast majority of curves only have moderate curvature. We
392 // would benefit significantly from a quick reject that detects curves that don't need special
393 // treatment for strong curvature.
394 if (numSegments > 1 && calc_curvature_costheta(leftTan, rightTan) < fMaxCurvatureCosTheta) {
395 SkPoint ptsBuffer[7];
396 p0.store(ptsBuffer);
397 p1.store(ptsBuffer + 1);
398 p2.store(ptsBuffer + 2);
399 p3.store(ptsBuffer + 3);
400 const SkPoint* currCubic = ptsBuffer;
401
402 if (leftT > 0) {
403 SkChopCubicAt(currCubic, ptsBuffer, leftT);
404 this->cubicTo(leftJoinType, ptsBuffer, /*maxCurvatureT=*/1,
405 (kLeftMaxCurvatureNone != leftMaxCurvatureT)
406 ? leftMaxCurvatureT/leftT : kLeftMaxCurvatureNone,
407 kRightMaxCurvatureNone);
408 if (rightT < 1) {
409 rightT = (rightT - leftT) / (1 - leftT);
410 }
411 if (rightMaxCurvatureT < 1 && kRightMaxCurvatureNone != rightMaxCurvatureT) {
412 rightMaxCurvatureT = (rightMaxCurvatureT - leftT) / (1 - leftT);
413 }
414 currCubic = ptsBuffer + 3;
415 } else {
416 SkPoint c1 = (ptsBuffer[1] == ptsBuffer[0]) ? ptsBuffer[2] : ptsBuffer[1];
417 this->rotateTo(leftJoinType, ptsBuffer[0], c1);
418 }
419
420 if (rightT < 1) {
421 SkChopCubicAt(currCubic, ptsBuffer, rightT);
422 this->lineTo(kInternalRoundJoinType, ptsBuffer[0], ptsBuffer[3]);
423 currCubic = ptsBuffer + 3;
424 this->cubicTo(kInternalRoundJoinType, currCubic, /*maxCurvatureT=*/0,
425 kLeftMaxCurvatureNone, kRightMaxCurvatureNone);
426 } else {
427 this->lineTo(kInternalRoundJoinType, currCubic[0], currCubic[3]);
428 SkPoint c2 = (currCubic[2] == currCubic[3]) ? currCubic[1] : currCubic[2];
429 this->rotateTo(kInternalRoundJoinType, currCubic[3], currCubic[3]*2 - c2);
430 }
431 return;
432 }
433
434 // Recurse and check the other two points of max curvature, if any.
435 if (kRightMaxCurvatureNone != rightMaxCurvatureT) {
436 this->cubicTo(leftJoinType, P, rightMaxCurvatureT, leftMaxCurvatureT,
437 kRightMaxCurvatureNone);
438 return;
439 }
440 if (kLeftMaxCurvatureNone != leftMaxCurvatureT) {
441 SkASSERT(kRightMaxCurvatureNone == rightMaxCurvatureT);
442 this->cubicTo(leftJoinType, P, leftMaxCurvatureT, kLeftMaxCurvatureNone,
443 kRightMaxCurvatureNone);
444 return;
445 }
446 if (numSegments > fMaxTessellationSegments) {
447 SkPoint ptsBuffer[7];
448 SkChopCubicAt(P, ptsBuffer, 0.5f);
449 this->cubicTo(leftJoinType, ptsBuffer, 0, kLeftMaxCurvatureNone, kRightMaxCurvatureNone);
450 this->cubicTo(kInternalRoundJoinType, ptsBuffer + 3, 0, kLeftMaxCurvatureNone,
451 kRightMaxCurvatureNone);
452 return;
453 }
454
455 this->writeCubicSegment(leftJoinType, p0, p1, p2, p3);
456}
457
458void GrStrokePatchBuilder::rotateTo(float leftJoinType, const SkPoint& anchorPoint,
459 const SkPoint& controlPoint) {
460 // Effectively rotate the current normal by drawing a zero length, 1-segment cubic.
461 // writeCubicSegment automatically adds the necessary join and the zero length cubic serves as
462 // a glue that guarantees a water tight rasterized edge between the new join and the segment
463 // that comes after the rotate.
464 SkPoint pts[4] = {anchorPoint, controlPoint, anchorPoint*2 - controlPoint, anchorPoint};
465 this->writeCubicSegment(leftJoinType, pts, 1);
466}
467
468void GrStrokePatchBuilder::close() {
469 if (!fHasPreviousSegment) {
470 // Draw caps instead of closing if the subpath is zero length:
471 //
472 // "Any zero length subpath ... shall be stroked if the 'stroke-linecap' property has a
473 // value of round or square producing respectively a circle or a square."
474 //
475 // (https://www.w3.org/TR/SVG11/painting.html#StrokeProperties)
476 //
477 this->writeCaps();
478 return;
479 }
480
481 // Draw a line back to the beginning. (This will be discarded if
482 // fCurrentPoint == fCurrContourStartPoint.)
483 this->lineTo(fCurrStrokeJoinType, fCurrentPoint, fCurrContourStartPoint);
484 this->writeJoin(fCurrStrokeJoinType, fCurrContourStartPoint, fLastControlPoint,
485 fCurrContourFirstControlPoint);
486}
487