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/ops/PathInnerTriangulateOp.h"
9
10#include "src/gpu/GrEagerVertexAllocator.h"
11#include "src/gpu/GrGpu.h"
12#include "src/gpu/GrOpFlushState.h"
13#include "src/gpu/GrRecordingContextPriv.h"
14#include "src/gpu/GrResourceProvider.h"
15#include "src/gpu/glsl/GrGLSLVertexGeoBuilder.h"
16#include "src/gpu/tessellate/PathCurveTessellator.h"
17#include "src/gpu/tessellate/shaders/GrPathTessellationShader.h"
18
19namespace {
20
21// Fills an array of convex hulls surrounding 4-point cubic or conic instances. This shader is used
22// for the "cover" pass after the curves have been fully stencilled.
23class HullShader : public GrPathTessellationShader {
24public:
25    HullShader(const SkMatrix& viewMatrix, SkPMColor4f color, const GrShaderCaps& shaderCaps)
26            : GrPathTessellationShader(kTessellate_HullShader_ClassID,
27                                       GrPrimitiveType::kTriangleStrip, 0, viewMatrix, color,
28                                       skgpu::PatchAttribs::kNone) {
29        fInstanceAttribs.emplace_back("p01", kFloat4_GrVertexAttribType, kFloat4_GrSLType);
30        fInstanceAttribs.emplace_back("p23", kFloat4_GrVertexAttribType, kFloat4_GrSLType);
31        if (!shaderCaps.infinitySupport()) {
32            // A conic curve is written out with p3=[w,Infinity], but GPUs that don't support
33            // infinity can't detect this. On these platforms we also write out an extra float with
34            // each patch that explicitly tells the shader what type of curve it is.
35            fInstanceAttribs.emplace_back("curveType", kFloat_GrVertexAttribType, kFloat_GrSLType);
36        }
37        this->setInstanceAttributes(fInstanceAttribs.data(), fInstanceAttribs.count());
38        SkASSERT(fInstanceAttribs.count() <= kMaxInstanceAttribCount);
39
40        if (!shaderCaps.vertexIDSupport()) {
41            constexpr static Attribute kVertexIdxAttrib("vertexidx", kFloat_GrVertexAttribType,
42                                                        kFloat_GrSLType);
43            this->setVertexAttributes(&kVertexIdxAttrib, 1);
44        }
45    }
46
47    int maxTessellationSegments(const GrShaderCaps&) const override { SkUNREACHABLE; }
48
49private:
50    const char* name() const final { return "tessellate_HullShader"; }
51    SkString getShaderDfxInfo() const override { return SkString("ShaderDfx_HullShader"); }
52    void addToKey(const GrShaderCaps&, GrProcessorKeyBuilder*) const final {}
53    std::unique_ptr<ProgramImpl> makeProgramImpl(const GrShaderCaps&) const final;
54
55    constexpr static int kMaxInstanceAttribCount = 3;
56    SkSTArray<kMaxInstanceAttribCount, Attribute> fInstanceAttribs;
57};
58
59std::unique_ptr<GrGeometryProcessor::ProgramImpl> HullShader::makeProgramImpl(
60        const GrShaderCaps&) const {
61    class Impl : public GrPathTessellationShader::Impl {
62        void emitVertexCode(const GrShaderCaps& shaderCaps,
63                            const GrPathTessellationShader&,
64                            GrGLSLVertexBuilder* v,
65                            GrGLSLVaryingHandler*,
66                            GrGPArgs* gpArgs) override {
67            if (shaderCaps.infinitySupport()) {
68                v->insertFunction(R"(
69                bool is_conic_curve() { return isinf(p23.w); }
70                bool is_non_triangular_conic_curve() {
71                    // We consider a conic non-triangular as long as its weight isn't infinity.
72                    // NOTE: "isinf == false" works on Mac Radeon GLSL; "!isinf" can get the wrong
73                    // answer.
74                    return isinf(p23.z) == false;
75                })");
76            } else {
77                v->insertFunction(SkStringPrintf(R"(
78                bool is_conic_curve() { return curveType != %g; })", kCubicCurveType).c_str());
79                v->insertFunction(SkStringPrintf(R"(
80                bool is_non_triangular_conic_curve() {
81                    return curveType == %g;
82                })", kConicCurveType).c_str());
83            }
84            v->codeAppend(R"(
85            float2 p0=p01.xy, p1=p01.zw, p2=p23.xy, p3=p23.zw;
86            if (is_conic_curve()) {
87                // Conics are 3 points, with the weight in p3.
88                float w = p3.x;
89                p3 = p2;  // Duplicate the endpoint for shared code that also runs on cubics.
90                if (is_non_triangular_conic_curve()) {
91                    // Convert the points to a trapeziodal hull that circumcscribes the conic.
92                    float2 p1w = p1 * w;
93                    float T = .51;  // Bias outward a bit to ensure we cover the outermost samples.
94                    float2 c1 = mix(p0, p1w, T);
95                    float2 c2 = mix(p2, p1w, T);
96                    float iw = 1 / mix(1, w, T);
97                    p2 = c2 * iw;
98                    p1 = c1 * iw;
99                }
100            }
101
102            // Translate the points to v0..3 where v0=0.
103            float2 v1 = p1 - p0;
104            float2 v2 = p2 - p0;
105            float2 v3 = p3 - p0;
106
107            // Reorder the points so v2 bisects v1 and v3.
108            if (sign(cross(v2, v1)) == sign(cross(v2, v3))) {
109                float2 tmp = p2;
110                if (sign(cross(v1, v2)) != sign(cross(v1, v3))) {
111                    p2 = p1;  // swap(p2, p1)
112                    p1 = tmp;
113                } else {
114                    p2 = p3;  // swap(p2, p3)
115                    p3 = tmp;
116                }
117            })");
118
119            if (shaderCaps.vertexIDSupport()) {
120                // If we don't have sk_VertexID support then "vertexidx" already came in as a
121                // vertex attrib.
122                v->codeAppend(R"(
123                // sk_VertexID comes in fan order. Convert to strip order.
124                int vertexidx = sk_VertexID;
125                vertexidx ^= vertexidx >> 1;)");
126            }
127
128            v->codeAppend(R"(
129            // Find the "turn direction" of each corner and net turn direction.
130            float vertexdir = 0;
131            float netdir = 0;
132            float2 prev, next;
133            float dir;
134            float2 localcoord;
135            float2 nextcoord;)");
136
137            for (int i = 0; i < 4; ++i) {
138                v->codeAppendf(R"(
139                prev = p%i - p%i;)", i, (i + 3) % 4);
140                v->codeAppendf(R"(
141                next = p%i - p%i;)", (i + 1) % 4, i);
142                v->codeAppendf(R"(
143                dir = sign(cross(prev, next));
144                if (vertexidx == %i) {
145                    vertexdir = dir;
146                    localcoord = p%i;
147                    nextcoord = p%i;
148                }
149                netdir += dir;)", i, i, (i + 1) % 4);
150            }
151
152            v->codeAppend(R"(
153            // Remove the non-convex vertex, if any.
154            if (vertexdir != sign(netdir)) {
155                localcoord = nextcoord;
156            }
157
158            float2 vertexpos = AFFINE_MATRIX * localcoord + TRANSLATE;)");
159            gpArgs->fLocalCoordVar.set(kFloat2_GrSLType, "localcoord");
160            gpArgs->fPositionVar.set(kFloat2_GrSLType, "vertexpos");
161        }
162    };
163    return std::make_unique<Impl>();
164}
165
166}  // anonymous namespace
167
168namespace skgpu::v1 {
169
170void PathInnerTriangulateOp::visitProxies(const GrVisitProxyFunc& func) const {
171    if (fPipelineForFills) {
172        fPipelineForFills->visitProxies(func);
173    } else {
174        fProcessors.visitProxies(func);
175    }
176}
177
178GrDrawOp::FixedFunctionFlags PathInnerTriangulateOp::fixedFunctionFlags() const {
179    auto flags = FixedFunctionFlags::kUsesStencil;
180    if (GrAAType::kNone != fAAType) {
181        flags |= FixedFunctionFlags::kUsesHWAA;
182    }
183    return flags;
184}
185
186GrProcessorSet::Analysis PathInnerTriangulateOp::finalize(const GrCaps& caps,
187                                                          const GrAppliedClip* clip,
188                                                          GrClampType clampType) {
189    return fProcessors.finalize(fColor, GrProcessorAnalysisCoverage::kNone, clip, nullptr, caps,
190                                clampType, &fColor);
191}
192
193void PathInnerTriangulateOp::pushFanStencilProgram(const GrTessellationShader::ProgramArgs& args,
194                                                   const GrPipeline* pipelineForStencils,
195                                                   const GrUserStencilSettings* stencil) {
196    SkASSERT(pipelineForStencils);
197    auto shader = GrPathTessellationShader::MakeSimpleTriangleShader(args.fArena, fViewMatrix,
198                                                                     SK_PMColor4fTRANSPARENT);
199    fFanPrograms.push_back(GrTessellationShader::MakeProgram(args, shader, pipelineForStencils,
200                                                             stencil)); }
201
202void PathInnerTriangulateOp::pushFanFillProgram(const GrTessellationShader::ProgramArgs& args,
203                                                const GrUserStencilSettings* stencil) {
204    SkASSERT(fPipelineForFills);
205    auto shader = GrPathTessellationShader::MakeSimpleTriangleShader(args.fArena, fViewMatrix,
206                                                                     fColor);
207    fFanPrograms.push_back(GrTessellationShader::MakeProgram(args, shader, fPipelineForFills,
208                                                             stencil));
209}
210
211void PathInnerTriangulateOp::prePreparePrograms(const GrTessellationShader::ProgramArgs& args,
212                                                GrAppliedClip&& appliedClip) {
213    SkASSERT(!fFanTriangulator);
214    SkASSERT(!fFanPolys);
215    SkASSERT(!fPipelineForFills);
216    SkASSERT(!fTessellator);
217    SkASSERT(!fStencilCurvesProgram);
218    SkASSERT(fFanPrograms.empty());
219    SkASSERT(!fCoverHullsProgram);
220
221    if (fPath.countVerbs() <= 0) {
222        return;
223    }
224
225    // If using wireframe, we have to fall back on a standard Redbook "stencil then cover" algorithm
226    // instead of bypassing the stencil buffer to fill the fan directly.
227    bool forceRedbookStencilPass =
228            (fPathFlags & (FillPathFlags::kStencilOnly | FillPathFlags::kWireframe));
229    bool doFill = !(fPathFlags & FillPathFlags::kStencilOnly);
230
231    bool isLinear;
232    fFanTriangulator = args.fArena->make<GrInnerFanTriangulator>(fPath, args.fArena);
233    fFanPolys = fFanTriangulator->pathToPolys(&fFanBreadcrumbs, &isLinear);
234
235    // Create a pipeline for stencil passes if needed.
236    const GrPipeline* pipelineForStencils = nullptr;
237    if (forceRedbookStencilPass || !isLinear) {  // Curves always get stencilled.
238        auto pipelineFlags = (fPathFlags & FillPathFlags::kWireframe)
239                ? GrPipeline::InputFlags::kWireframe
240                : GrPipeline::InputFlags::kNone;
241        pipelineForStencils = GrPathTessellationShader::MakeStencilOnlyPipeline(
242                args, fAAType, appliedClip.hardClip(), pipelineFlags);
243    }
244
245    // Create a pipeline for fill passes if needed.
246    if (doFill) {
247        fPipelineForFills = GrTessellationShader::MakePipeline(args, fAAType,
248                                                               std::move(appliedClip),
249                                                               std::move(fProcessors));
250    }
251
252    // Pass 1: Tessellate the outer curves into the stencil buffer.
253    if (!isLinear) {
254        fTessellator = PathCurveTessellator::Make(args.fArena,
255                                                  args.fCaps->shaderCaps()->infinitySupport());
256        auto* tessShader = GrPathTessellationShader::Make(args.fArena,
257                                                          fViewMatrix,
258                                                          SK_PMColor4fTRANSPARENT,
259                                                          fPath.countVerbs(),
260                                                          *pipelineForStencils,
261                                                          fTessellator->patchAttribs(),
262                                                          *args.fCaps);
263        const GrUserStencilSettings* stencilPathSettings =
264                GrPathTessellationShader::StencilPathSettings(GrFillRuleForSkPath(fPath));
265        fStencilCurvesProgram = GrTessellationShader::MakeProgram(args,
266                                                                  tessShader,
267                                                                  pipelineForStencils,
268                                                                  stencilPathSettings);
269    }
270
271    // Pass 2: Fill the path's inner fan with a stencil test against the curves.
272    if (fFanPolys) {
273        if (forceRedbookStencilPass) {
274            // Use a standard Redbook "stencil then cover" algorithm instead of bypassing the
275            // stencil buffer to fill the fan directly.
276            const GrUserStencilSettings* stencilPathSettings =
277                    GrPathTessellationShader::StencilPathSettings(GrFillRuleForSkPath(fPath));
278            this->pushFanStencilProgram(args, pipelineForStencils, stencilPathSettings);
279            if (doFill) {
280                this->pushFanFillProgram(args,
281                                         GrPathTessellationShader::TestAndResetStencilSettings());
282            }
283        } else if (isLinear) {
284            // There are no outer curves! Ignore stencil and fill the path directly.
285            SkASSERT(!pipelineForStencils);
286            this->pushFanFillProgram(args, &GrUserStencilSettings::kUnused);
287        } else if (!fPipelineForFills->hasStencilClip()) {
288            // These are a twist on the standard Redbook stencil settings that allow us to fill the
289            // inner polygon directly to the final render target. By the time these programs
290            // execute, the outer curves will already be stencilled in. So if the stencil value is
291            // zero, then it means the sample in question is not affected by any curves and we can
292            // fill it in directly. If the stencil value is nonzero, then we don't fill and instead
293            // continue the standard Redbook counting process.
294            constexpr static GrUserStencilSettings kFillOrIncrDecrStencil(
295                GrUserStencilSettings::StaticInitSeparate<
296                    0x0000,                       0x0000,
297                    GrUserStencilTest::kEqual,    GrUserStencilTest::kEqual,
298                    0xffff,                       0xffff,
299                    GrUserStencilOp::kKeep,       GrUserStencilOp::kKeep,
300                    GrUserStencilOp::kIncWrap,    GrUserStencilOp::kDecWrap,
301                    0xffff,                       0xffff>());
302
303            constexpr static GrUserStencilSettings kFillOrInvertStencil(
304                GrUserStencilSettings::StaticInit<
305                    0x0000,
306                    GrUserStencilTest::kEqual,
307                    0xffff,
308                    GrUserStencilOp::kKeep,
309                    // "Zero" instead of "Invert" because the fan only touches any given pixel once.
310                    GrUserStencilOp::kZero,
311                    0xffff>());
312
313            auto* stencil = (fPath.getFillType() == SkPathFillType::kWinding)
314                    ? &kFillOrIncrDecrStencil
315                    : &kFillOrInvertStencil;
316            this->pushFanFillProgram(args, stencil);
317        } else {
318            // This is the same idea as above, but we use two passes instead of one because there is
319            // a stencil clip. The stencil test isn't expressive enough to do the above tests and
320            // also check the clip bit in a single pass.
321            constexpr static GrUserStencilSettings kFillIfZeroAndInClip(
322                GrUserStencilSettings::StaticInit<
323                    0x0000,
324                    GrUserStencilTest::kEqualIfInClip,
325                    0xffff,
326                    GrUserStencilOp::kKeep,
327                    GrUserStencilOp::kKeep,
328                    0xffff>());
329
330            constexpr static GrUserStencilSettings kIncrDecrStencilIfNonzero(
331                GrUserStencilSettings::StaticInitSeparate<
332                    0x0000,                         0x0000,
333                    // No need to check the clip because the previous stencil pass will have only
334                    // written to samples already inside the clip.
335                    GrUserStencilTest::kNotEqual,   GrUserStencilTest::kNotEqual,
336                    0xffff,                         0xffff,
337                    GrUserStencilOp::kIncWrap,      GrUserStencilOp::kDecWrap,
338                    GrUserStencilOp::kKeep,         GrUserStencilOp::kKeep,
339                    0xffff,                         0xffff>());
340
341            constexpr static GrUserStencilSettings kInvertStencilIfNonZero(
342                GrUserStencilSettings::StaticInit<
343                    0x0000,
344                    // No need to check the clip because the previous stencil pass will have only
345                    // written to samples already inside the clip.
346                    GrUserStencilTest::kNotEqual,
347                    0xffff,
348                    // "Zero" instead of "Invert" because the fan only touches any given pixel once.
349                    GrUserStencilOp::kZero,
350                    GrUserStencilOp::kKeep,
351                    0xffff>());
352
353            // Pass 2a: Directly fill fan samples whose stencil values (from curves) are zero.
354            this->pushFanFillProgram(args, &kFillIfZeroAndInClip);
355
356            // Pass 2b: Redbook counting on fan samples whose stencil values (from curves) != 0.
357            auto* stencil = (fPath.getFillType() == SkPathFillType::kWinding)
358                    ? &kIncrDecrStencilIfNonzero
359                    : &kInvertStencilIfNonZero;
360            this->pushFanStencilProgram(args, pipelineForStencils, stencil);
361        }
362    }
363
364    // Pass 3: Draw convex hulls around each curve.
365    if (doFill && !isLinear) {
366        // By the time this program executes, every pixel will be filled in except the ones touched
367        // by curves. We issue a final cover pass over the curves by drawing their convex hulls.
368        // This will fill in any remaining samples and reset the stencil values back to zero.
369        SkASSERT(fTessellator);
370        auto* hullShader = args.fArena->make<HullShader>(fViewMatrix, fColor,
371                                                         *args.fCaps->shaderCaps());
372        fCoverHullsProgram = GrTessellationShader::MakeProgram(
373                args, hullShader, fPipelineForFills,
374                GrPathTessellationShader::TestAndResetStencilSettings());
375    }
376}
377
378void PathInnerTriangulateOp::onPrePrepare(GrRecordingContext* context,
379                                          const GrSurfaceProxyView& writeView,
380                                          GrAppliedClip* clip,
381                                          const GrDstProxyView& dstProxyView,
382                                          GrXferBarrierFlags renderPassXferBarriers,
383                                          GrLoadOp colorLoadOp) {
384    // DMSAA is not supported on DDL.
385    bool usesMSAASurface = writeView.asRenderTargetProxy()->numSamples() > 1;
386    this->prePreparePrograms({context->priv().recordTimeAllocator(), writeView, usesMSAASurface,
387                             &dstProxyView, renderPassXferBarriers, colorLoadOp,
388                             context->priv().caps()},
389                             (clip) ? std::move(*clip) : GrAppliedClip::Disabled());
390    if (fStencilCurvesProgram) {
391        context->priv().recordProgramInfo(fStencilCurvesProgram);
392    }
393    for (const GrProgramInfo* fanProgram : fFanPrograms) {
394        context->priv().recordProgramInfo(fanProgram);
395    }
396    if (fCoverHullsProgram) {
397        context->priv().recordProgramInfo(fCoverHullsProgram);
398    }
399}
400
401GR_DECLARE_STATIC_UNIQUE_KEY(gHullVertexBufferKey);
402
403void PathInnerTriangulateOp::onPrepare(GrOpFlushState* flushState) {
404    const GrCaps& caps = flushState->caps();
405
406    if (!fFanTriangulator) {
407        this->prePreparePrograms({flushState->allocator(), flushState->writeView(),
408                                 flushState->usesMSAASurface(), &flushState->dstProxyView(),
409                                 flushState->renderPassBarriers(), flushState->colorLoadOp(),
410                                 &caps}, flushState->detachAppliedClip());
411        if (!fFanTriangulator) {
412            return;
413        }
414    }
415
416    if (fFanPolys) {
417        GrEagerDynamicVertexAllocator alloc(flushState, &fFanBuffer, &fBaseFanVertex);
418        fFanVertexCount = fFanTriangulator->polysToTriangles(fFanPolys, &alloc, &fFanBreadcrumbs);
419    }
420
421    if (fTessellator) {
422        int patchPreallocCount = fFanBreadcrumbs.count() +
423                                 fTessellator->patchPreallocCount(fPath.countVerbs());
424        SkASSERT(patchPreallocCount);  // Otherwise fTessellator should be null.
425
426        PatchWriter patchWriter(flushState, fTessellator, patchPreallocCount);
427
428        // Write out breadcrumb triangles. This must be called after polysToTriangles() in order for
429        // fFanBreadcrumbs to be complete.
430        SkDEBUGCODE(int breadcrumbCount = 0;)
431        for (const auto* tri = fFanBreadcrumbs.head(); tri; tri = tri->fNext) {
432            SkDEBUGCODE(++breadcrumbCount;)
433            auto p0 = float2::Load(tri->fPts);
434            auto p1 = float2::Load(tri->fPts + 1);
435            auto p2 = float2::Load(tri->fPts + 2);
436            if (skvx::any((p0 == p1) & (p1 == p2))) {
437                // Cull completely horizontal or vertical triangles. GrTriangulator can't always
438                // get these breadcrumb edges right when they run parallel to the sweep
439                // direction because their winding is undefined by its current definition.
440                // FIXME(skia:12060): This seemed safe, but if there is a view matrix it will
441                // introduce T-junctions.
442                continue;
443            }
444            PatchWriter::TrianglePatch(patchWriter) << p0 << p1 << p2;
445        }
446        SkASSERT(breadcrumbCount == fFanBreadcrumbs.count());
447
448        // Write out the curves.
449        auto tessShader = &fStencilCurvesProgram->geomProc().cast<GrPathTessellationShader>();
450        fTessellator->writePatches(patchWriter,
451                                   tessShader->maxTessellationSegments(*caps.shaderCaps()),
452                                   tessShader->viewMatrix(),
453                                   {SkMatrix::I(), fPath, SK_PMColor4fTRANSPARENT});
454
455        if (!tessShader->willUseTessellationShaders()) {
456            fTessellator->prepareFixedCountBuffers(flushState);
457        }
458    }
459
460    if (!caps.shaderCaps()->vertexIDSupport()) {
461        constexpr static float kStripOrderIDs[4] = {0, 1, 3, 2};
462
463        GR_DEFINE_STATIC_UNIQUE_KEY(gHullVertexBufferKey);
464
465        fHullVertexBufferIfNoIDSupport = flushState->resourceProvider()->findOrMakeStaticBuffer(
466                GrGpuBufferType::kVertex, sizeof(kStripOrderIDs), kStripOrderIDs,
467                gHullVertexBufferKey);
468    }
469}
470
471void PathInnerTriangulateOp::onExecute(GrOpFlushState* flushState, const SkRect& chainBounds) {
472    if (fCoverHullsProgram &&
473        fCoverHullsProgram->geomProc().hasVertexAttributes() &&
474        !fHullVertexBufferIfNoIDSupport) {
475        return;
476    }
477
478    if (fStencilCurvesProgram) {
479        SkASSERT(fTessellator);
480        flushState->bindPipelineAndScissorClip(*fStencilCurvesProgram, this->bounds());
481        fTessellator->draw(flushState,
482                           fStencilCurvesProgram->geomProc().willUseTessellationShaders());
483        if (flushState->caps().requiresManualFBBarrierAfterTessellatedStencilDraw()) {
484            flushState->gpu()->insertManualFramebufferBarrier();  // http://skbug.com/9739
485        }
486    }
487
488    // Allocation of the fan vertex buffer may have failed but we already pushed back fan programs.
489    if (fFanBuffer) {
490        for (const GrProgramInfo* fanProgram : fFanPrograms) {
491            flushState->bindPipelineAndScissorClip(*fanProgram, this->bounds());
492            flushState->bindTextures(fanProgram->geomProc(), nullptr, fanProgram->pipeline());
493            flushState->bindBuffers(nullptr, nullptr, fFanBuffer);
494            flushState->draw(fFanVertexCount, fBaseFanVertex);
495        }
496    }
497
498    if (fCoverHullsProgram) {
499        SkASSERT(fTessellator);
500        flushState->bindPipelineAndScissorClip(*fCoverHullsProgram, this->bounds());
501        flushState->bindTextures(fCoverHullsProgram->geomProc(), nullptr, *fPipelineForFills);
502        fTessellator->drawHullInstances(flushState, fHullVertexBufferIfNoIDSupport);
503    }
504}
505
506} // namespace skgpu::v1
507