1/*
2 * Copyright 2020 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 GrAATriangulator_DEFINED
9#define GrAATriangulator_DEFINED
10
11#include "src/gpu/geometry/GrTriangulator.h"
12
13// Triangulates the given path in device space with a mesh of alpha ramps for antialiasing.
14class SK_API GrAATriangulator : private GrTriangulator {
15public:
16    static int PathToAATriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
17                                 GrEagerVertexAllocator* vertexAllocator) {
18        SkArenaAlloc alloc(kArenaDefaultChunkSize);
19        GrAATriangulator aaTriangulator(path, &alloc);
20        aaTriangulator.fRoundVerticesToQuarterPixel = true;
21        aaTriangulator.fEmitCoverage = true;
22        bool isLinear;
23        Poly* polys = aaTriangulator.pathToPolys(tolerance, clipBounds, &isLinear);
24        return aaTriangulator.polysToAATriangles(polys, vertexAllocator);
25    }
26
27    // Structs used by GrAATriangulator internals.
28    struct SSEdge;
29    struct EventList;
30    struct Event {
31        Event(SSEdge* edge, const SkPoint& point, uint8_t alpha)
32                : fEdge(edge), fPoint(point), fAlpha(alpha) {}
33        SSEdge* fEdge;
34        SkPoint fPoint;
35        uint8_t fAlpha;
36        void apply(VertexList* mesh, const Comparator&, EventList* events, const GrAATriangulator*);
37    };
38    struct EventComparator {
39        enum class Op { kLessThan, kGreaterThan };
40        EventComparator(Op op) : fOp(op) {}
41        bool operator() (Event* const &e1, Event* const &e2) {
42            return fOp == Op::kLessThan ? e1->fAlpha < e2->fAlpha
43                                        : e1->fAlpha > e2->fAlpha;
44        }
45        Op fOp;
46    };
47
48private:
49    GrAATriangulator(const SkPath& path, SkArenaAlloc* alloc) : GrTriangulator(path, alloc) {}
50
51    // For screenspace antialiasing, the algorithm is modified as follows:
52    //
53    // Run steps 1-5 above to produce polygons.
54    // 5b) Apply fill rules to extract boundary contours from the polygons:
55    void extractBoundary(EdgeList* boundary, Edge* e) const;
56    void extractBoundaries(const VertexList& inMesh, VertexList* innerVertices,
57                           const Comparator&) const;
58
59    // 5c) Simplify boundaries to remove "pointy" vertices that cause inversions:
60    void simplifyBoundary(EdgeList* boundary, const Comparator&) const;
61
62    // 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find
63    //     new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
64    //     new antialiased mesh from those vertices:
65    void strokeBoundary(EdgeList* boundary, VertexList* innerMesh, const Comparator&) const;
66
67    // Run steps 3-6 above on the new mesh, and produce antialiased triangles.
68    Poly* tessellate(const VertexList& mesh, const Comparator&) const override;
69    int polysToAATriangles(Poly*, GrEagerVertexAllocator*) const;
70
71    // Additional helpers and driver functions.
72    void makeEvent(SSEdge*, EventList* events) const;
73    void makeEvent(SSEdge*, Vertex* v, SSEdge* other, Vertex* dest, EventList* events,
74                   const Comparator&) const;
75    void connectPartners(VertexList* mesh, const Comparator&) const;
76    void removeNonBoundaryEdges(const VertexList& mesh) const;
77    void connectSSEdge(Vertex* v, Vertex* dest, const Comparator&) const;
78    bool collapseOverlapRegions(VertexList* mesh, const Comparator&, EventComparator comp) const;
79
80    // FIXME: fOuterMesh should be plumbed through function parameters instead.
81    mutable VertexList fOuterMesh;
82};
83
84#endif
85