1 /*
2 * Copyright 2021 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/graphite/geom/Shape.h"
9
10 #include "include/core/SkPathBuilder.h"
11 #include "include/core/SkRect.h"
12 #include "include/core/SkScalar.h"
13 #include "include/private/base/SkAlign.h"
14 #include "include/private/base/SkDebug.h"
15 #include "include/private/base/SkMalloc.h"
16 #include "src/core/SkPathPriv.h"
17 #include "src/core/SkRRectPriv.h"
18
19 #include <cstring>
20
21 namespace {
22 // Keys for paths may be extracted from the path data for small paths, to maximize matches
23 // even when the genIDs may differ. The value is based on emperical experience, to trade off
24 // matches vs. key size.
25 constexpr int kMaxKeyFromDataVerbCnt = 10;
26 }
27
28 namespace skgpu::graphite {
29
operator =(const Shape & shape)30 Shape& Shape::operator=(const Shape& shape) {
31 switch (shape.type()) {
32 case Type::kEmpty: this->reset(); break;
33 case Type::kLine: this->setLine(shape.p0(), shape.p1()); break;
34 case Type::kRect: this->setRect(shape.rect()); break;
35 case Type::kRRect: this->setRRect(shape.rrect()); break;
36 case Type::kArc: this->setArc(shape.arc()); break;
37 case Type::kPath: this->setPath(shape.path()); break;
38 }
39
40 fInverted = shape.fInverted;
41 return *this;
42 }
43
conservativeContains(const Rect & rect) const44 bool Shape::conservativeContains(const Rect& rect) const {
45 switch (fType) {
46 case Type::kEmpty: return false;
47 case Type::kLine: return false;
48 case Type::kRect: return fRect.contains(rect);
49 case Type::kRRect: return fRRect.contains(rect.asSkRect());
50 case Type::kPath: // We need to ensure the path is non-inverted.
51 if (this->inverted()) {
52 SkPath nonInverted(fPath);
53 nonInverted.toggleInverseFillType();
54 return nonInverted.conservativelyContainsRect(rect.asSkRect());
55 } else {
56 return fPath.conservativelyContainsRect(rect.asSkRect());
57 }
58 case Type::kArc: if (fArc.fType == SkArc::Type::kWedge) {
59 SkPath arc = this->asPath();
60 if (this->inverted()) {
61 arc.toggleInverseFillType();
62 }
63 return arc.conservativelyContainsRect(rect.asSkRect());
64 } else {
65 return false;
66 }
67 }
68 SkUNREACHABLE;
69 }
70
conservativeContains(skvx::float2 point) const71 bool Shape::conservativeContains(skvx::float2 point) const {
72 switch (fType) {
73 case Type::kEmpty: return false;
74 case Type::kLine: return false;
75 case Type::kRect: return fRect.contains(Rect::Point(point));
76 case Type::kRRect: return SkRRectPriv::ContainsPoint(fRRect, {point.x(), point.y()});
77 case Type::kPath: // We need to ensure the path is non-inverted.
78 if (this->inverted()) {
79 SkPath nonInverted(fPath);
80 nonInverted.toggleInverseFillType();
81 return nonInverted.contains(point.x(), point.y());
82 } else {
83 return fPath.contains(point.x(), point.y());
84 }
85 case Type::kArc: return false;
86 }
87 SkUNREACHABLE;
88 }
89
convex(bool simpleFill) const90 bool Shape::convex(bool simpleFill) const {
91 if (this->isPath()) {
92 // SkPath.isConvex() really means "is this path convex were it to be closed".
93 return (simpleFill || fPath.isLastContourClosed()) && fPath.isConvex();
94 } else if (this->isArc()) {
95 return SkPathPriv::DrawArcIsConvex(fArc.sweepAngle(), fArc.fType, simpleFill);
96 } else {
97 // Every other shape type is convex by construction.
98 return true;
99 }
100 }
101
bounds() const102 Rect Shape::bounds() const {
103 switch (fType) {
104 case Type::kEmpty: return Rect(0, 0, 0, 0);
105 case Type::kLine: return fRect.makeSorted(); // sorting corners computes bbox of segment
106 case Type::kRect: return fRect; // assuming it's sorted
107 case Type::kRRect: return fRRect.getBounds();
108 case Type::kArc: return fArc.oval();
109 case Type::kPath: return fPath.getBounds();
110 }
111 SkUNREACHABLE;
112 }
113
asPath() const114 SkPath Shape::asPath() const {
115 if (fType == Type::kPath) {
116 return fPath;
117 }
118
119 if (fType == Type::kArc) {
120 SkPath out;
121 // Filled ovals are already culled out so we assume no simple fills
122 SkPathPriv::CreateDrawArcPath(&out, fArc, /*isFillNoPathEffect=*/false);
123 // CreateDrawArcPath resets the output path and configures its fill
124 // type, so we just have to ensure invertedness is correct.
125 if (fInverted) {
126 out.toggleInverseFillType();
127 }
128 return out;
129 }
130
131 SkPathBuilder builder(this->fillType());
132 switch (fType) {
133 case Type::kEmpty: /* do nothing */ break;
134 case Type::kLine: builder.moveTo(fRect.left(), fRect.top())
135 .lineTo(fRect.right(), fRect.bot()); break;
136 case Type::kRect: builder.addRect(fRect.asSkRect()); break;
137 case Type::kRRect: builder.addRRect(fRRect); break;
138 case Type::kPath:
139 case Type::kArc: SkUNREACHABLE;
140 }
141 return builder.detach();
142 }
143
144 namespace {
path_key_from_data_size(const SkPath & path)145 int path_key_from_data_size(const SkPath& path) {
146 const int verbCnt = path.countVerbs();
147 if (verbCnt > kMaxKeyFromDataVerbCnt) {
148 return -1;
149 }
150 const int pointCnt = path.countPoints();
151 const int conicWeightCnt = SkPathPriv::ConicWeightCnt(path);
152
153 static_assert(sizeof(SkPoint) == 2 * sizeof(uint32_t));
154 static_assert(sizeof(SkScalar) == sizeof(uint32_t));
155 // 1 is for the verb count. Each verb is a byte but we'll pad the verb data out to
156 // a uint32_t length.
157 return 1 + (SkAlign4(verbCnt) >> 2) + 2 * pointCnt + conicWeightCnt;
158 }
159
160 // Writes the path data key into the passed pointer.
write_path_key_from_data(const SkPath & path,uint32_t * origKey)161 void write_path_key_from_data(const SkPath& path, uint32_t* origKey) {
162 uint32_t* key = origKey;
163 // The check below should take care of negative values casted positive.
164 const int verbCnt = path.countVerbs();
165 const int pointCnt = path.countPoints();
166 const int conicWeightCnt = SkPathPriv::ConicWeightCnt(path);
167 SkASSERT(verbCnt <= kMaxKeyFromDataVerbCnt);
168 SkASSERT(pointCnt && verbCnt);
169 *key++ = verbCnt;
170 memcpy(key, SkPathPriv::VerbData(path), verbCnt * sizeof(uint8_t));
171 int verbKeySize = SkAlign4(verbCnt);
172 // pad out to uint32_t alignment using value that will stand out when debugging.
173 uint8_t* pad = reinterpret_cast<uint8_t*>(key)+ verbCnt;
174 memset(pad, 0xDE, verbKeySize - verbCnt);
175 key += verbKeySize >> 2;
176
177 memcpy(key, SkPathPriv::PointData(path), sizeof(SkPoint) * pointCnt);
178 static_assert(sizeof(SkPoint) == 2 * sizeof(uint32_t));
179 key += 2 * pointCnt;
180 sk_careful_memcpy(key, SkPathPriv::ConicWeightData(path), sizeof(SkScalar) * conicWeightCnt);
181 static_assert(sizeof(SkScalar) == sizeof(uint32_t));
182 SkDEBUGCODE(key += conicWeightCnt);
183 SkASSERT(key - origKey == path_key_from_data_size(path));
184 }
185 } // anonymous namespace
186
keySize() const187 int Shape::keySize() const {
188 int count = 1; // Every key has the state flags from the Shape
189 switch(this->type()) {
190 case Type::kLine:
191 static_assert(0 == sizeof(skvx::float4) % sizeof(uint32_t));
192 count += sizeof(skvx::float4) / sizeof(uint32_t);
193 break;
194 case Type::kRect:
195 static_assert(0 == sizeof(Rect) % sizeof(uint32_t));
196 count += sizeof(Rect) / sizeof(uint32_t);
197 break;
198 case Type::kRRect:
199 static_assert(0 == SkRRect::kSizeInMemory % sizeof(uint32_t));
200 count += SkRRect::kSizeInMemory / sizeof(uint32_t);
201 break;
202 case Type::kArc:
203 static_assert(0 == sizeof(SkArc) % sizeof(uint32_t));
204 count += sizeof(SkArc) / sizeof(uint32_t);
205 break;
206 case Type::kPath: {
207 if (this->path().isVolatile()) {
208 return -1; // volatile, so won't be keyed
209 }
210 if (this->path().isEmpty()) {
211 return -1; // empty, so won't be keyed
212 }
213 int dataKeySize = path_key_from_data_size(this->path());
214 if (dataKeySize >= 0) {
215 count += dataKeySize;
216 } else {
217 count++; // Just adds the gen ID.
218 }
219 break;
220 }
221 default:
222 // else it's empty, which just needs the state flags for its key
223 SkASSERT(this->isEmpty());
224 }
225 return count;
226 }
227
writeKey(uint32_t * key,bool includeInverted) const228 void Shape::writeKey(uint32_t* key, bool includeInverted) const {
229 SkASSERT(this->keySize());
230 SkDEBUGCODE(uint32_t* origKey = key;)
231
232 // Every key starts with the state from the Shape (this includes path fill type,
233 // and any tracked inversion, as well as the class of geometry).
234 *key++ = this->stateKey(includeInverted);
235
236 switch(this->type()) {
237 case Type::kPath: {
238 SkASSERT(!this->path().isVolatile());
239 SkASSERT(!this->path().isEmpty());
240 // Ensure that the path's inversion matches our state so that the path's key suffices.
241 SkASSERT(this->inverted() == this->path().isInverseFillType());
242
243 int dataKeySize = path_key_from_data_size(this->path());
244 if (dataKeySize >= 0) {
245 write_path_key_from_data(this->path(), key);
246 return;
247 } else {
248 *key++ = this->path().getGenerationID();
249 }
250 break;
251 }
252 case Type::kRect:
253 memcpy(key, &this->rect(), sizeof(Rect));
254 key += sizeof(Rect) / sizeof(uint32_t);
255 break;
256 case Type::kRRect:
257 this->rrect().writeToMemory(key);
258 key += SkRRect::kSizeInMemory / sizeof(uint32_t);
259 break;
260 case Type::kArc: {
261 // Write dense floats first
262 memcpy(key, &fArc, sizeof(SkRect) + 2 * sizeof(float));
263 key += (sizeof(SkArc) / sizeof(uint32_t) - 1);
264 // Then write the final bool as an int, to make sure upper bits are set
265 *key++ = fArc.isWedge() ? 1 : 0;
266 break;
267 }
268 case Type::kLine: {
269 skvx::float4 line = this->line();
270 memcpy(key, &line, sizeof(skvx::float4));
271 key += sizeof(skvx::float4) / sizeof(uint32_t);
272 break;
273 }
274 default:
275 // Nothing other than the flag state is needed in the key for an empty shape
276 SkASSERT(this->isEmpty());
277 }
278 SkASSERT(key - origKey == this->keySize());
279 }
280
281 namespace {
noninverted_fill_type(SkPathFillType fillType)282 SkPathFillType noninverted_fill_type(SkPathFillType fillType) {
283 switch (fillType) {
284 case SkPathFillType::kWinding:
285 case SkPathFillType::kInverseWinding:
286 return SkPathFillType::kWinding;
287 case SkPathFillType::kEvenOdd:
288 case SkPathFillType::kInverseEvenOdd:
289 return SkPathFillType::kEvenOdd;
290 }
291 SkUNREACHABLE;
292 }
293 } // anonymous namespace
294
stateKey(bool includeInverted) const295 uint32_t Shape::stateKey(bool includeInverted) const {
296 uint32_t key;
297 if (includeInverted) {
298 // Use the path's full fill type instead of just whether or not it's inverted.
299 key = this->isPath() ? static_cast<uint32_t>(fPath.getFillType())
300 : (fInverted ? 1 : 0);
301 } else {
302 // Use the path's noninverted fill type.
303 key = this->isPath() ? static_cast<uint32_t>(noninverted_fill_type(fPath.getFillType()))
304 : 0;
305 }
306 key |= ((uint32_t) fType) << 2; // fill type was 2 bits
307 return key;
308 }
309
310 } // namespace skgpu::graphite
311