1/*
2 * Copyright 2019 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#include "src/gpu/tessellate/GrTessellationPathRenderer.h"
9
10#include "include/pathops/SkPathOps.h"
11#include "src/core/SkIPoint16.h"
12#include "src/core/SkPathPriv.h"
13#include "src/gpu/GrClip.h"
14#include "src/gpu/GrMemoryPool.h"
15#include "src/gpu/GrRecordingContextPriv.h"
16#include "src/gpu/GrRenderTargetContext.h"
17#include "src/gpu/GrSurfaceContextPriv.h"
18#include "src/gpu/geometry/GrStyledShape.h"
19#include "src/gpu/ops/GrFillRectOp.h"
20#include "src/gpu/tessellate/GrDrawAtlasPathOp.h"
21#include "src/gpu/tessellate/GrPathTessellateOp.h"
22#include "src/gpu/tessellate/GrStrokeTessellateOp.h"
23#include "src/gpu/tessellate/GrWangsFormula.h"
24
25constexpr static SkISize kAtlasInitialSize{512, 512};
26constexpr static int kMaxAtlasSize = 2048;
27
28constexpr static auto kAtlasAlpha8Type = GrColorType::kAlpha_8;
29
30// The atlas is only used for small-area paths, which means at least one dimension of every path is
31// guaranteed to be quite small. So if we transpose tall paths, then every path will have a small
32// height, which lends very well to efficient pow2 atlas packing.
33constexpr static auto kAtlasAlgorithm = GrDynamicAtlas::RectanizerAlgorithm::kPow2;
34
35// Ensure every path in the atlas falls in or below the 128px high rectanizer band.
36constexpr static int kMaxAtlasPathHeight = 128;
37
38bool GrTessellationPathRenderer::IsSupported(const GrCaps& caps) {
39 return caps.drawInstancedSupport() && caps.shaderCaps()->vertexIDSupport();
40}
41
42GrTessellationPathRenderer::GrTessellationPathRenderer(const GrCaps& caps)
43 : fAtlas(kAtlasAlpha8Type, GrDynamicAtlas::InternalMultisample::kYes, kAtlasInitialSize,
44 std::min(kMaxAtlasSize, caps.maxPreferredRenderTargetSize()),
45 caps, kAtlasAlgorithm) {
46 this->initAtlasFlags(caps);
47}
48
49void GrTessellationPathRenderer::initAtlasFlags(const GrCaps& caps) {
50 fStencilAtlasFlags = OpFlags::kStencilOnly | OpFlags::kDisableHWTessellation;
51 fMaxAtlasPathWidth = fAtlas.maxAtlasSize() / 2;
52
53 auto atlasFormat = caps.getDefaultBackendFormat(kAtlasAlpha8Type, GrRenderable::kYes);
54 if (caps.internalMultisampleCount(atlasFormat) <= 1) {
55 // MSAA is not supported on kAlpha8. Disable the atlas.
56 fMaxAtlasPathWidth = 0;
57 return;
58 }
59
60 // The atlas usually does better with hardware tessellation. If hardware tessellation is
61 // supported, we will next choose a max atlas path width that is guaranteed to never require
62 // more tessellation segments than are supported by the hardware.
63 if (!caps.shaderCaps()->tessellationSupport()) {
64 return;
65 }
66
67 // Since we limit the area of paths in the atlas to kMaxAtlasPathHeight^2, taller paths can't
68 // get very wide anyway. Find the tallest path whose width is limited by
69 // GrWangsFormula::worst_case_cubic() rather than the max area constraint, and use that for our
70 // max atlas path width.
71 //
72 // Solve the following equation for w:
73 //
74 // GrWangsFormula::worst_case_cubic(kLinearizationIntolerance, w, kMaxAtlasPathHeight^2 / w)
75 // == maxTessellationSegments
76 //
77 float k = GrWangsFormula::cubic_k(kLinearizationIntolerance);
78 float h = kMaxAtlasPathHeight;
79 float s = caps.shaderCaps()->maxTessellationSegments();
80 // Quadratic formula from Numerical Recipes in C:
81 //
82 // q = -1/2 [b + sign(b) sqrt(b*b - 4*a*c)]
83 // x1 = q/a
84 // x2 = c/q
85 //
86 // float a = 1; // 'a' is always 1 in our specific equation.
87 float b = -s*s*s*s / (4*k*k); // Always negative.
88 float c = h*h*h*h; // Always positive.
89 float det = b*b - 4*1*c;
90 if (det <= 0) {
91 // maxTessellationSegments is too small for any path whose area == kMaxAtlasPathHeight^2.
92 // (This is unexpected because the GL spec mandates a minimum of 64 segments.)
93 SkDebugf("WARNING: maxTessellationSegments seems too low. (%i)\n",
94 caps.shaderCaps()->maxTessellationSegments());
95 return;
96 }
97 float q = -.5f * (b - std::sqrt(det)); // Always positive.
98 // The two roots represent the width^2 and height^2 of the tallest rectangle that is limited by
99 // GrWangsFormula::worst_case_cubic().
100 float r0 = q; // Always positive.
101 float r1 = c/q; // Always positive.
102 float worstCaseWidth = std::sqrt(std::max(r0, r1));
103#ifdef SK_DEBUG
104 float worstCaseHeight = std::sqrt(std::min(r0, r1));
105 // Verify the above equation worked as expected. It should have found a width and height whose
106 // area == kMaxAtlasPathHeight^2.
107 SkASSERT(SkScalarNearlyEqual(worstCaseHeight * worstCaseWidth, h*h, 1));
108 // Verify GrWangsFormula::worst_case_cubic() still works as we expect. The worst case number of
109 // segments for this bounding box should be maxTessellationSegments.
110 SkASSERT(SkScalarNearlyEqual(GrWangsFormula::worst_case_cubic(
111 kLinearizationIntolerance, worstCaseWidth, worstCaseHeight), s, 1));
112#endif
113 fStencilAtlasFlags &= ~OpFlags::kDisableHWTessellation;
114 fMaxAtlasPathWidth = std::min(fMaxAtlasPathWidth, (int)worstCaseWidth);
115}
116
117GrPathRenderer::CanDrawPath GrTessellationPathRenderer::onCanDrawPath(
118 const CanDrawPathArgs& args) const {
119 const GrStyledShape& shape = *args.fShape;
120 if (shape.inverseFilled() || shape.style().hasPathEffect() ||
121 args.fViewMatrix->hasPerspective()) {
122 return CanDrawPath::kNo;
123 }
124
125 if (GrAAType::kCoverage == args.fAAType) {
126 SkASSERT(1 == args.fProxy->numSamples());
127 if (!args.fProxy->canUseMixedSamples(*args.fCaps)) {
128 return CanDrawPath::kNo;
129 }
130 }
131
132 SkPath path;
133 shape.asPath(&path);
134 if (SkPathPriv::ConicWeightCnt(path)) {
135 return CanDrawPath::kNo;
136 }
137
138 if (!shape.style().isSimpleFill()) {
139 SkPMColor4f constantColor;
140 // These are only temporary restrictions while we bootstrap tessellated stroking. Every one
141 // of them will eventually go away.
142 if (shape.style().strokeRec().getStyle() == SkStrokeRec::kStrokeAndFill_Style ||
143 !args.fCaps->shaderCaps()->tessellationSupport() ||
144 GrAAType::kCoverage == args.fAAType ||
145 !args.fPaint->isConstantBlendedColor(&constantColor) ||
146 args.fPaint->hasCoverageFragmentProcessor()) {
147 return CanDrawPath::kNo;
148 }
149 }
150
151 return CanDrawPath::kYes;
152}
153
154bool GrTessellationPathRenderer::onDrawPath(const DrawPathArgs& args) {
155 GrRenderTargetContext* renderTargetContext = args.fRenderTargetContext;
156 GrOpMemoryPool* pool = args.fContext->priv().opMemoryPool();
157 const GrShaderCaps& shaderCaps = *args.fContext->priv().caps()->shaderCaps();
158
159 SkPath path;
160 args.fShape->asPath(&path);
161
162 SkRect devBounds;
163 args.fViewMatrix->mapRect(&devBounds, path.getBounds());
164
165 // See if the path is small and simple enough to atlas instead of drawing directly.
166 //
167 // NOTE: The atlas uses alpha8 coverage even for msaa render targets. We could theoretically
168 // render the sample mask to an integer texture, but such a scheme would probably require
169 // GL_EXT_post_depth_coverage, which appears to have low adoption.
170 SkIRect devIBounds;
171 SkIPoint16 locationInAtlas;
172 bool transposedInAtlas;
173 if (args.fShape->style().isSimpleFill() &&
174 this->tryAddPathToAtlas(*args.fContext->priv().caps(), *args.fViewMatrix, path, devBounds,
175 args.fAAType, &devIBounds, &locationInAtlas, &transposedInAtlas)) {
176#ifdef SK_DEBUG
177 // If using hardware tessellation in the atlas, make sure the max number of segments is
178 // sufficient for this path. fMaxAtlasPathWidth should have been tuned for this to always be
179 // the case.
180 if (!(fStencilAtlasFlags & OpFlags::kDisableHWTessellation)) {
181 int worstCaseNumSegments = GrWangsFormula::worst_case_cubic(kLinearizationIntolerance,
182 devIBounds.width(),
183 devIBounds.height());
184 SkASSERT(worstCaseNumSegments <= shaderCaps.maxTessellationSegments());
185 }
186#endif
187 auto op = pool->allocate<GrDrawAtlasPathOp>(
188 renderTargetContext->numSamples(), sk_ref_sp(fAtlas.textureProxy()),
189 devIBounds, locationInAtlas, transposedInAtlas, *args.fViewMatrix,
190 std::move(args.fPaint));
191 renderTargetContext->addDrawOp(args.fClip, std::move(op));
192 return true;
193 }
194
195 // Find the worst-case log2 number of line segments that a curve in this path might need to be
196 // divided into.
197 int worstCaseResolveLevel = GrWangsFormula::worst_case_cubic_log2(kLinearizationIntolerance,
198 devBounds.width(),
199 devBounds.height());
200 if (worstCaseResolveLevel > kMaxResolveLevel) {
201 // The path is too large for our internal indirect draw shaders. Crop it to the viewport.
202 auto viewport = SkRect::MakeIWH(renderTargetContext->width(),
203 renderTargetContext->height());
204 float inflationRadius = 1;
205 const SkStrokeRec& stroke = args.fShape->style().strokeRec();
206 if (stroke.getStyle() == SkStrokeRec::kHairline_Style) {
207 inflationRadius += SkStrokeRec::GetInflationRadius(stroke.getJoin(), stroke.getMiter(),
208 stroke.getCap(), 1);
209 } else if (stroke.getStyle() != SkStrokeRec::kFill_Style) {
210 inflationRadius += stroke.getInflationRadius() * args.fViewMatrix->getMaxScale();
211 }
212 viewport.outset(inflationRadius, inflationRadius);
213
214 SkPath viewportPath;
215 viewportPath.addRect(viewport);
216 // Perform the crop in device space so it's a simple rect-path intersection.
217 path.transform(*args.fViewMatrix);
218 if (!Op(viewportPath, path, kIntersect_SkPathOp, &path)) {
219 // The crop can fail if the PathOps encounter NaN or infinities. Return true
220 // because drawing nothing is acceptable behavior for FP overflow.
221 return true;
222 }
223
224 // Transform the path back to its own local space.
225 SkMatrix inverse;
226 if (!args.fViewMatrix->invert(&inverse)) {
227 return true; // Singular view matrix. Nothing would have drawn anyway. Return true.
228 }
229 path.transform(inverse);
230 path.setIsVolatile(true);
231 args.fViewMatrix->mapRect(&devBounds, path.getBounds());
232 worstCaseResolveLevel = GrWangsFormula::worst_case_cubic_log2(kLinearizationIntolerance,
233 devBounds.width(),
234 devBounds.height());
235 // kMaxResolveLevel should be large enough to tessellate paths the size of any screen we
236 // might encounter.
237 SkASSERT(worstCaseResolveLevel <= kMaxResolveLevel);
238 }
239
240 if (args.fShape->style().isSimpleHairline()) {
241 // Pre-transform the path into device space and use a stroke width of 1.
242#ifdef SK_DEBUG
243 // Since we will be transforming the path, just double check that we are still in a position
244 // where the paint will not use local coordinates.
245 SkPMColor4f constantColor;
246 SkASSERT(args.fPaint.isConstantBlendedColor(&constantColor));
247#endif
248 SkPath devPath;
249 path.transform(*args.fViewMatrix, &devPath);
250 SkStrokeRec devStroke = args.fShape->style().strokeRec();
251 devStroke.setStrokeStyle(1);
252 auto op = pool->allocate<GrStrokeTessellateOp>(args.fAAType, SkMatrix::I(), devPath,
253 devStroke, std::move(args.fPaint));
254 renderTargetContext->addDrawOp(args.fClip, std::move(op));
255 return true;
256 }
257
258 if (!args.fShape->style().isSimpleFill()) {
259 const SkStrokeRec& stroke = args.fShape->style().strokeRec();
260 SkASSERT(stroke.getStyle() == SkStrokeRec::kStroke_Style);
261 auto op = pool->allocate<GrStrokeTessellateOp>(args.fAAType, *args.fViewMatrix, path,
262 stroke, std::move(args.fPaint));
263 renderTargetContext->addDrawOp(args.fClip, std::move(op));
264 return true;
265 }
266
267 auto drawPathFlags = OpFlags::kNone;
268 if ((1 << worstCaseResolveLevel) > shaderCaps.maxTessellationSegments()) {
269 // The path is too large for hardware tessellation; a curve in this bounding box could
270 // potentially require more segments than are supported by the hardware. Fall back on
271 // indirect draws.
272 drawPathFlags |= OpFlags::kDisableHWTessellation;
273 }
274
275 auto op = pool->allocate<GrPathTessellateOp>(*args.fViewMatrix, path, std::move(args.fPaint),
276 args.fAAType, drawPathFlags);
277 renderTargetContext->addDrawOp(args.fClip, std::move(op));
278 return true;
279}
280
281bool GrTessellationPathRenderer::tryAddPathToAtlas(
282 const GrCaps& caps, const SkMatrix& viewMatrix, const SkPath& path, const SkRect& devBounds,
283 GrAAType aaType, SkIRect* devIBounds, SkIPoint16* locationInAtlas,
284 bool* transposedInAtlas) {
285 if (!fMaxAtlasPathWidth) {
286 return false;
287 }
288
289 if (!caps.multisampleDisableSupport() && GrAAType::kNone == aaType) {
290 return false;
291 }
292
293 // Atlas paths require their points to be transformed on the CPU and copied into an "uber path".
294 // Check if this path has too many points to justify this extra work.
295 if (path.countPoints() > 200) {
296 return false;
297 }
298
299 // Transpose tall paths in the atlas. Since we limit ourselves to small-area paths, this
300 // guarantees that every atlas entry has a small height, which lends very well to efficient pow2
301 // atlas packing.
302 devBounds.roundOut(devIBounds);
303 int maxDimenstion = devIBounds->width();
304 int minDimension = devIBounds->height();
305 *transposedInAtlas = minDimension > maxDimenstion;
306 if (*transposedInAtlas) {
307 std::swap(minDimension, maxDimenstion);
308 }
309
310 // Check if the path is too large for an atlas. Since we use "minDimension" for height in the
311 // atlas, limiting to kMaxAtlasPathHeight^2 pixels guarantees height <= kMaxAtlasPathHeight.
312 if (maxDimenstion * minDimension > kMaxAtlasPathHeight * kMaxAtlasPathHeight ||
313 maxDimenstion > fMaxAtlasPathWidth) {
314 return false;
315 }
316
317 if (!fAtlas.addRect(maxDimenstion, minDimension, locationInAtlas)) {
318 return false;
319 }
320
321 SkMatrix atlasMatrix = viewMatrix;
322 if (*transposedInAtlas) {
323 std::swap(atlasMatrix[0], atlasMatrix[3]);
324 std::swap(atlasMatrix[1], atlasMatrix[4]);
325 float tx=atlasMatrix.getTranslateX(), ty=atlasMatrix.getTranslateY();
326 atlasMatrix.setTranslateX(ty - devIBounds->y() + locationInAtlas->x());
327 atlasMatrix.setTranslateY(tx - devIBounds->x() + locationInAtlas->y());
328 } else {
329 atlasMatrix.postTranslate(locationInAtlas->x() - devIBounds->x(),
330 locationInAtlas->y() - devIBounds->y());
331 }
332
333 // Concatenate this path onto our uber path that matches its fill and AA types.
334 SkPath* uberPath = this->getAtlasUberPath(path.getFillType(), GrAAType::kNone != aaType);
335 uberPath->moveTo(locationInAtlas->x(), locationInAtlas->y()); // Implicit moveTo(0,0).
336 uberPath->addPath(path, atlasMatrix);
337 return true;
338}
339
340void GrTessellationPathRenderer::onStencilPath(const StencilPathArgs& args) {
341 SkPath path;
342 args.fShape->asPath(&path);
343
344 GrAAType aaType = (GrAA::kYes == args.fDoStencilMSAA) ? GrAAType::kMSAA : GrAAType::kNone;
345
346 auto op = args.fContext->priv().opMemoryPool()->allocate<GrPathTessellateOp>(
347 *args.fViewMatrix, path, GrPaint(), aaType, OpFlags::kStencilOnly);
348 args.fRenderTargetContext->addDrawOp(args.fClip, std::move(op));
349}
350
351void GrTessellationPathRenderer::preFlush(GrOnFlushResourceProvider* onFlushRP,
352 const uint32_t* opsTaskIDs, int numOpsTaskIDs) {
353 if (!fAtlas.drawBounds().isEmpty()) {
354 this->renderAtlas(onFlushRP);
355 fAtlas.reset(kAtlasInitialSize, *onFlushRP->caps());
356 }
357 for (SkPath& path : fAtlasUberPaths) {
358 path.reset();
359 }
360}
361
362constexpr static GrUserStencilSettings kTestStencil(
363 GrUserStencilSettings::StaticInit<
364 0x0000,
365 GrUserStencilTest::kNotEqual,
366 0xffff,
367 GrUserStencilOp::kKeep,
368 GrUserStencilOp::kKeep,
369 0xffff>());
370
371constexpr static GrUserStencilSettings kTestAndResetStencil(
372 GrUserStencilSettings::StaticInit<
373 0x0000,
374 GrUserStencilTest::kNotEqual,
375 0xffff,
376 GrUserStencilOp::kZero,
377 GrUserStencilOp::kKeep,
378 0xffff>());
379
380void GrTessellationPathRenderer::renderAtlas(GrOnFlushResourceProvider* onFlushRP) {
381 auto rtc = fAtlas.instantiate(onFlushRP);
382 if (!rtc) {
383 return;
384 }
385
386 // Add ops to stencil the atlas paths.
387 for (auto antialias : {false, true}) {
388 for (auto fillType : {SkPathFillType::kWinding, SkPathFillType::kEvenOdd}) {
389 SkPath* uberPath = this->getAtlasUberPath(fillType, antialias);
390 if (uberPath->isEmpty()) {
391 continue;
392 }
393 uberPath->setFillType(fillType);
394 GrAAType aaType = (antialias) ? GrAAType::kMSAA : GrAAType::kNone;
395 auto op = onFlushRP->opMemoryPool()->allocate<GrPathTessellateOp>(
396 SkMatrix::I(), *uberPath, GrPaint(), aaType, fStencilAtlasFlags);
397 rtc->addDrawOp(nullptr, std::move(op));
398 }
399 }
400
401 // Finally, draw a fullscreen rect to convert our stencilled paths into alpha coverage masks.
402 auto aaType = GrAAType::kMSAA;
403 auto fillRectFlags = GrFillRectOp::InputFlags::kNone;
404
405 // This will be the final op in the renderTargetContext. So if Ganesh is planning to discard the
406 // stencil values anyway, then we might not actually need to reset the stencil values back to 0.
407 bool mustResetStencil = !onFlushRP->caps()->discardStencilValuesAfterRenderPass();
408
409 if (rtc->numSamples() == 1) {
410 // We are mixed sampled. We need to either enable conservative raster (preferred) or disable
411 // MSAA in order to avoid double blend artifacts. (Even if we disable MSAA for the cover
412 // geometry, the stencil test is still multisampled and will still produce smooth results.)
413 if (onFlushRP->caps()->conservativeRasterSupport()) {
414 fillRectFlags |= GrFillRectOp::InputFlags::kConservativeRaster;
415 } else {
416 aaType = GrAAType::kNone;
417 }
418 mustResetStencil = true;
419 }
420
421 SkRect coverRect = SkRect::MakeIWH(fAtlas.drawBounds().width(), fAtlas.drawBounds().height());
422 const GrUserStencilSettings* stencil;
423 if (mustResetStencil) {
424 // Outset the cover rect in case there are T-junctions in the path bounds.
425 coverRect.outset(1, 1);
426 stencil = &kTestAndResetStencil;
427 } else {
428 stencil = &kTestStencil;
429 }
430
431 GrQuad coverQuad(coverRect);
432 DrawQuad drawQuad{coverQuad, coverQuad, GrQuadAAFlags::kAll};
433
434 GrPaint paint;
435 paint.setColor4f(SK_PMColor4fWHITE);
436
437 auto coverOp = GrFillRectOp::Make(rtc->surfPriv().getContext(), std::move(paint), aaType,
438 &drawQuad, stencil, fillRectFlags);
439 rtc->addDrawOp(nullptr, std::move(coverOp));
440
441 if (rtc->asSurfaceProxy()->requiresManualMSAAResolve()) {
442 onFlushRP->addTextureResolveTask(sk_ref_sp(rtc->asTextureProxy()),
443 GrSurfaceProxy::ResolveFlags::kMSAA);
444 }
445}
446