1 /*
2  * Copyright 2017 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 GrGrCCGeometry_DEFINED
9 #define GrGrCCGeometry_DEFINED
10 
11 #include "SkGeometry.h"
12 #include "SkNx.h"
13 #include "SkPoint.h"
14 #include "SkTArray.h"
15 
16 /**
17  * This class chops device-space contours up into a series of segments that CCPR knows how to
18  * render. (See GrCCGeometry::Verb.)
19  *
20  * NOTE: This must be done in device space, since an affine transformation can change whether a
21  * curve is monotonic.
22  */
23 class GrCCGeometry {
24 public:
25     // These are the verbs that CCPR knows how to draw. If a path has any segments that don't map to
26     // this list, then they are chopped into smaller ones that do. A list of these comprise a
27     // compact representation of what can later be expanded into GPU instance data.
28     enum class Verb : uint8_t {
29         kBeginPath, // Included only for caller convenience.
30         kBeginContour,
31         kLineTo,
32         kMonotonicQuadraticTo, // Monotonic relative to the vector between its endpoints [P2 - P0].
33         kMonotonicCubicTo,
34         kEndClosedContour, // endPt == startPt.
35         kEndOpenContour // endPt != startPt.
36     };
37 
38     // These tallies track numbers of CCPR primitives that are required to draw a contour.
39     struct PrimitiveTallies {
40         int fTriangles; // Number of triangles in the contour's fan.
41         int fWoundTriangles; // Triangles (from the tessellator) whose winding magnitude > 1.
42         int fQuadratics;
43         int fCubics;
44 
45         void operator+=(const PrimitiveTallies&);
46         PrimitiveTallies operator-(const PrimitiveTallies&) const;
47         bool operator==(const PrimitiveTallies&);
48     };
49 
50     GrCCGeometry(int numSkPoints = 0, int numSkVerbs = 0)
51             : fPoints(numSkPoints * 3) // Reserve for a 3x expansion in points and verbs.
52             , fVerbs(numSkVerbs * 3) {}
53 
points()54     const SkTArray<SkPoint, true>& points() const { SkASSERT(!fBuildingContour); return fPoints; }
verbs()55     const SkTArray<Verb, true>& verbs() const { SkASSERT(!fBuildingContour); return fVerbs; }
56 
reset()57     void reset() {
58         SkASSERT(!fBuildingContour);
59         fPoints.reset();
60         fVerbs.reset();
61     }
62 
63     // This is included in case the caller needs to discard previously added contours. It is up to
64     // the caller to track counts and ensure we don't pop back into the middle of a different
65     // contour.
resize_back(int numPoints,int numVerbs)66     void resize_back(int numPoints, int numVerbs) {
67         SkASSERT(!fBuildingContour);
68         fPoints.resize_back(numPoints);
69         fVerbs.resize_back(numVerbs);
70         SkASSERT(fVerbs.empty() || fVerbs.back() == Verb::kEndOpenContour ||
71                  fVerbs.back() == Verb::kEndClosedContour);
72     }
73 
74     void beginPath();
75     void beginContour(const SkPoint& devPt);
76     void lineTo(const SkPoint& devPt);
77     void quadraticTo(const SkPoint& devP1, const SkPoint& devP2);
78 
79     // We pass through inflection points and loop intersections using a line and quadratic(s)
80     // respectively. 'inflectPad' and 'loopIntersectPad' specify how close (in pixels) cubic
81     // segments are allowed to get to these points. For normal rendering you will want to use the
82     // default values, but these can be overridden for testing purposes.
83     //
84     // NOTE: loops do appear to require two full pixels of padding around the intersection point.
85     //       With just one pixel-width of pad, we start to see bad pixels. Ultimately this has a
86     //       minimal effect on the total amount of segments produced. Most sections that pass
87     //       through the loop intersection can be approximated with a single quadratic anyway,
88     //       regardless of whether we are use one pixel of pad or two (1.622 avg. quads per loop
89     //       intersection vs. 1.489 on the tiger).
90     void cubicTo(const SkPoint& devP1, const SkPoint& devP2, const SkPoint& devP3,
91                  float inflectPad = 0.55f, float loopIntersectPad = 2);
92 
93     PrimitiveTallies endContour(); // Returns the numbers of primitives needed to draw the contour.
94 
95 private:
96     inline void appendMonotonicQuadratics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2);
97     inline void appendSingleMonotonicQuadratic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2);
98 
99     using AppendCubicFn = void(GrCCGeometry::*)(const Sk2f& p0, const Sk2f& p1,
100                                                 const Sk2f& p2, const Sk2f& p3,
101                                                 int maxSubdivisions);
102     static constexpr int kMaxSubdivionsPerCubicSection = 2;
103 
104     template<AppendCubicFn AppendLeftRight>
105     inline void chopCubicAtMidTangent(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
106                                       const Sk2f& p3, const Sk2f& tan0, const Sk2f& tan3,
107                                       int maxFutureSubdivisions = kMaxSubdivionsPerCubicSection);
108 
109     template<AppendCubicFn AppendLeft, AppendCubicFn AppendRight>
110     inline void chopCubic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, const Sk2f& p3,
111                           float T, int maxFutureSubdivisions = kMaxSubdivionsPerCubicSection);
112 
113     void appendMonotonicCubics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, const Sk2f& p3,
114                                int maxSubdivisions = kMaxSubdivionsPerCubicSection);
115     void appendCubicApproximation(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, const Sk2f& p3,
116                                   int maxSubdivisions = kMaxSubdivionsPerCubicSection);
117 
118     // Transient state used while building a contour.
119     SkPoint fCurrAnchorPoint;
120     SkPoint fCurrFanPoint;
121     PrimitiveTallies fCurrContourTallies;
122     SkCubicType fCurrCubicType;
123     SkDEBUGCODE(bool fBuildingContour = false);
124 
125     // TODO: These points could eventually be written directly to block-allocated GPU buffers.
126     SkSTArray<128, SkPoint, true>   fPoints;
127     SkSTArray<128, Verb, true>      fVerbs;
128 };
129 
130 inline void GrCCGeometry::PrimitiveTallies::operator+=(const PrimitiveTallies& b) {
131     fTriangles += b.fTriangles;
132     fWoundTriangles += b.fWoundTriangles;
133     fQuadratics += b.fQuadratics;
134     fCubics += b.fCubics;
135 }
136 
137 GrCCGeometry::PrimitiveTallies
138 inline GrCCGeometry::PrimitiveTallies::operator-(const PrimitiveTallies& b) const {
139     return {fTriangles - b.fTriangles,
140             fWoundTriangles - b.fWoundTriangles,
141             fQuadratics - b.fQuadratics,
142             fCubics - b.fCubics};
143 }
144 
145 inline bool GrCCGeometry::PrimitiveTallies::operator==(const PrimitiveTallies& b) {
146     return fTriangles == b.fTriangles && fWoundTriangles == b.fWoundTriangles &&
147            fQuadratics == b.fQuadratics && fCubics == b.fCubics;
148 }
149 
150 #endif
151