Flutter Engine
The Flutter Engine
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
SkEdgeBuilder.cpp
Go to the documentation of this file.
1/*
2 * Copyright 2011 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
9
10#include "include/core/SkPath.h"
19#include "src/base/SkSafeMath.h"
21#include "src/core/SkEdge.h"
23#include "src/core/SkGeometry.h"
25#include "src/core/SkPathPriv.h"
26
27SkEdgeBuilder::Combine SkBasicEdgeBuilder::combineVertical(const SkEdge* edge, SkEdge* last) {
28 // We only consider edges that were originally lines to be vertical to avoid numerical issues
29 // (crbug.com/1154864).
30 if (last->fEdgeType != SkEdge::kLine_Type || last->fDX || edge->fX != last->fX) {
31 return kNo_Combine;
32 }
33 if (edge->fWinding == last->fWinding) {
34 if (edge->fLastY + 1 == last->fFirstY) {
35 last->fFirstY = edge->fFirstY;
36 return kPartial_Combine;
37 }
38 if (edge->fFirstY == last->fLastY + 1) {
39 last->fLastY = edge->fLastY;
40 return kPartial_Combine;
41 }
42 return kNo_Combine;
43 }
44 if (edge->fFirstY == last->fFirstY) {
45 if (edge->fLastY == last->fLastY) {
46 return kTotal_Combine;
47 }
48 if (edge->fLastY < last->fLastY) {
49 last->fFirstY = edge->fLastY + 1;
50 return kPartial_Combine;
51 }
52 last->fFirstY = last->fLastY + 1;
53 last->fLastY = edge->fLastY;
54 last->fWinding = edge->fWinding;
55 return kPartial_Combine;
56 }
57 if (edge->fLastY == last->fLastY) {
58 if (edge->fFirstY > last->fFirstY) {
59 last->fLastY = edge->fFirstY - 1;
60 return kPartial_Combine;
61 }
62 last->fLastY = last->fFirstY - 1;
63 last->fFirstY = edge->fFirstY;
64 last->fWinding = edge->fWinding;
65 return kPartial_Combine;
66 }
67 return kNo_Combine;
68}
69
70SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::combineVertical(const SkAnalyticEdge* edge,
71 SkAnalyticEdge* last) {
73 return SkAbs32(a - b) < 0x100;
74 };
75
76 // We only consider edges that were originally lines to be vertical to avoid numerical issues
77 // (crbug.com/1154864).
78 if (last->fEdgeType != SkAnalyticEdge::kLine_Type || last->fDX || edge->fX != last->fX) {
79 return kNo_Combine;
80 }
81 if (edge->fWinding == last->fWinding) {
82 if (edge->fLowerY == last->fUpperY) {
83 last->fUpperY = edge->fUpperY;
84 last->fY = last->fUpperY;
85 return kPartial_Combine;
86 }
87 if (approximately_equal(edge->fUpperY, last->fLowerY)) {
88 last->fLowerY = edge->fLowerY;
89 return kPartial_Combine;
90 }
91 return kNo_Combine;
92 }
93 if (approximately_equal(edge->fUpperY, last->fUpperY)) {
94 if (approximately_equal(edge->fLowerY, last->fLowerY)) {
95 return kTotal_Combine;
96 }
97 if (edge->fLowerY < last->fLowerY) {
98 last->fUpperY = edge->fLowerY;
99 last->fY = last->fUpperY;
100 return kPartial_Combine;
101 }
102 last->fUpperY = last->fLowerY;
103 last->fY = last->fUpperY;
104 last->fLowerY = edge->fLowerY;
105 last->fWinding = edge->fWinding;
106 return kPartial_Combine;
107 }
108 if (approximately_equal(edge->fLowerY, last->fLowerY)) {
109 if (edge->fUpperY > last->fUpperY) {
110 last->fLowerY = edge->fUpperY;
111 return kPartial_Combine;
112 }
113 last->fLowerY = last->fUpperY;
114 last->fUpperY = edge->fUpperY;
115 last->fY = last->fUpperY;
116 last->fWinding = edge->fWinding;
117 return kPartial_Combine;
118 }
119 return kNo_Combine;
120}
121
122template <typename Edge>
123static bool is_vertical(const Edge* edge) {
124 // We only consider edges that were originally lines to be vertical to avoid numerical issues
125 // (crbug.com/1154864).
126 return edge->fDX == 0
127 && edge->fEdgeType == Edge::kLine_Type;
128}
129
130// TODO: we can deallocate the edge if edge->setFoo() fails
131// or when we don't use it (kPartial_Combine or kTotal_Combine).
132
133void SkBasicEdgeBuilder::addLine(const SkPoint pts[]) {
134 SkEdge* edge = fAlloc.make<SkEdge>();
135 if (edge->setLine(pts[0], pts[1], fClipShift)) {
136 Combine combine = is_vertical(edge) && !fList.empty()
137 ? this->combineVertical(edge, (SkEdge*)fList.back())
138 : kNo_Combine;
139
140 switch (combine) {
141 case kTotal_Combine: fList.pop_back(); break;
142 case kPartial_Combine: break;
143 case kNo_Combine: fList.push_back(edge); break;
144 }
145 }
146}
147void SkAnalyticEdgeBuilder::addLine(const SkPoint pts[]) {
149 if (edge->setLine(pts[0], pts[1])) {
150
151 Combine combine = is_vertical(edge) && !fList.empty()
152 ? this->combineVertical(edge, (SkAnalyticEdge*)fList.back())
153 : kNo_Combine;
154
155 switch (combine) {
156 case kTotal_Combine: fList.pop_back(); break;
157 case kPartial_Combine: break;
158 case kNo_Combine: fList.push_back(edge); break;
159 }
160 }
161}
162void SkBasicEdgeBuilder::addQuad(const SkPoint pts[]) {
164 if (edge->setQuadratic(pts, fClipShift)) {
165 fList.push_back(edge);
166 }
167}
168void SkAnalyticEdgeBuilder::addQuad(const SkPoint pts[]) {
170 if (edge->setQuadratic(pts)) {
171 fList.push_back(edge);
172 }
173}
174
175void SkBasicEdgeBuilder::addCubic(const SkPoint pts[]) {
177 if (edge->setCubic(pts, fClipShift)) {
178 fList.push_back(edge);
179 }
180}
181void SkAnalyticEdgeBuilder::addCubic(const SkPoint pts[]) {
183 if (edge->setCubic(pts)) {
184 fList.push_back(edge);
185 }
186}
187
188// TODO: merge addLine() and addPolyLine()?
189
190SkEdgeBuilder::Combine SkBasicEdgeBuilder::addPolyLine(const SkPoint pts[],
191 char* arg_edge, char** arg_edgePtr) {
192 auto edge = (SkEdge*) arg_edge;
193 auto edgePtr = (SkEdge**)arg_edgePtr;
194
195 if (edge->setLine(pts[0], pts[1], fClipShift)) {
196 return is_vertical(edge) && edgePtr > (SkEdge**)fEdgeList
197 ? this->combineVertical(edge, edgePtr[-1])
198 : kNo_Combine;
199 }
200 return SkEdgeBuilder::kPartial_Combine; // A convenient lie. Same do-nothing behavior.
201}
202SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::addPolyLine(const SkPoint pts[],
203 char* arg_edge, char** arg_edgePtr) {
204 auto edge = (SkAnalyticEdge*) arg_edge;
205 auto edgePtr = (SkAnalyticEdge**)arg_edgePtr;
206
207 if (edge->setLine(pts[0], pts[1])) {
208 return is_vertical(edge) && edgePtr > (SkAnalyticEdge**)fEdgeList
209 ? this->combineVertical(edge, edgePtr[-1])
210 : kNo_Combine;
211 }
212 return SkEdgeBuilder::kPartial_Combine; // As above.
213}
214
215SkRect SkBasicEdgeBuilder::recoverClip(const SkIRect& src) const {
216 return { SkIntToScalar(src.fLeft >> fClipShift),
217 SkIntToScalar(src.fTop >> fClipShift),
218 SkIntToScalar(src.fRight >> fClipShift),
219 SkIntToScalar(src.fBottom >> fClipShift), };
220}
221SkRect SkAnalyticEdgeBuilder::recoverClip(const SkIRect& src) const {
222 return SkRect::Make(src);
223}
224
225char* SkBasicEdgeBuilder::allocEdges(size_t n, size_t* size) {
226 *size = sizeof(SkEdge);
227 return (char*)fAlloc.makeArrayDefault<SkEdge>(n);
228}
229char* SkAnalyticEdgeBuilder::allocEdges(size_t n, size_t* size) {
230 *size = sizeof(SkAnalyticEdge);
231 return (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(n);
232}
233
234// TODO: maybe get rid of buildPoly() entirely?
235int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) {
236 size_t maxEdgeCount = path.countPoints();
237 if (iclip) {
238 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
239 // we turn portions that are clipped out on the left/right into vertical
240 // segments.
241 SkSafeMath safe;
242 maxEdgeCount = safe.mul(maxEdgeCount, SkLineClipper::kMaxClippedLineSegments);
243 if (!safe) {
244 return 0;
245 }
246 }
247
248 size_t edgeSize;
249 char* edge = this->allocEdges(maxEdgeCount, &edgeSize);
250
251 SkDEBUGCODE(char* edgeStart = edge);
252 char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount);
253 fEdgeList = (void**)edgePtr;
254
255 SkPathEdgeIter iter(path);
256 if (iclip) {
257 SkRect clip = this->recoverClip(*iclip);
258
259 while (auto e = iter.next()) {
260 switch (e.fEdge) {
263 int lineCount = SkLineClipper::ClipLine(e.fPts, clip, lines, canCullToTheRight);
265 for (int i = 0; i < lineCount; i++) {
266 switch( this->addPolyLine(lines + i, edge, edgePtr) ) {
267 case kTotal_Combine: edgePtr--; break;
268 case kPartial_Combine: break;
269 case kNo_Combine: *edgePtr++ = edge;
270 edge += edgeSize;
271 }
272 }
273 break;
274 }
275 default:
276 SkDEBUGFAIL("unexpected verb");
277 break;
278 }
279 }
280 } else {
281 while (auto e = iter.next()) {
282 switch (e.fEdge) {
284 switch( this->addPolyLine(e.fPts, edge, edgePtr) ) {
285 case kTotal_Combine: edgePtr--; break;
286 case kPartial_Combine: break;
287 case kNo_Combine: *edgePtr++ = edge;
288 edge += edgeSize;
289 }
290 break;
291 }
292 default:
293 SkDEBUGFAIL("unexpected verb");
294 break;
295 }
296 }
297 }
298 SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize);
299 SkASSERT((size_t)(edgePtr - (char**)fEdgeList) <= maxEdgeCount);
300 return SkToInt(edgePtr - (char**)fEdgeList);
301}
302
303int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) {
304 SkAutoConicToQuads quadder;
305 const SkScalar conicTol = SK_Scalar1 / 4;
306 bool is_finite = true;
307
308 SkPathEdgeIter iter(path);
309 if (iclip) {
310 SkRect clip = this->recoverClip(*iclip);
311 struct Rec {
312 SkEdgeBuilder* fBuilder;
313 bool fIsFinite;
314 } rec = { this, true };
315
316 SkEdgeClipper::ClipPath(path, clip, canCullToTheRight,
317 [](SkEdgeClipper* clipper, bool, void* ctx) {
318 Rec* rec = (Rec*)ctx;
319 SkPoint pts[4];
320 SkPath::Verb verb;
321
322 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
323 const int count = SkPathPriv::PtsInIter(verb);
324 if (!SkIsFinite(&pts[0].fX, count*2)) {
325 rec->fIsFinite = false;
326 return;
327 }
328 switch (verb) {
329 case SkPath::kLine_Verb: rec->fBuilder->addLine (pts); break;
330 case SkPath::kQuad_Verb: rec->fBuilder->addQuad (pts); break;
331 case SkPath::kCubic_Verb: rec->fBuilder->addCubic(pts); break;
332 default: break;
333 }
334 }
335 }, &rec);
336 is_finite = rec.fIsFinite;
337 } else {
338 auto handle_quad = [this](const SkPoint pts[3]) {
339 SkPoint monoX[5];
340 int n = SkChopQuadAtYExtrema(pts, monoX);
341 for (int i = 0; i <= n; i++) {
342 this->addQuad(&monoX[i * 2]);
343 }
344 };
345 while (auto e = iter.next()) {
346 switch (e.fEdge) {
348 this->addLine(e.fPts);
349 break;
351 handle_quad(e.fPts);
352 break;
353 }
355 const SkPoint* quadPts = quadder.computeQuads(
356 e.fPts, iter.conicWeight(), conicTol);
357 for (int i = 0; i < quadder.countQuads(); ++i) {
358 handle_quad(quadPts);
359 quadPts += 2;
360 }
361 } break;
363 SkPoint monoY[10];
364 int n = SkChopCubicAtYExtrema(e.fPts, monoY);
365 for (int i = 0; i <= n; i++) {
366 this->addCubic(&monoY[i * 3]);
367 }
368 break;
369 }
370 }
371 }
372 }
374 return is_finite ? fList.size() : 0;
375}
376
378 const SkIRect* shiftedClip) {
379 // If we're convex, then we need both edges, even if the right edge is past the clip.
380 const bool canCullToTheRight = !path.isConvex();
381
382 // We can use our buildPoly() optimization if all the segments are lines.
383 // (Edges are homogeneous and stored contiguously in memory, no need for indirection.)
384 const int count = SkPath::kLine_SegmentMask == path.getSegmentMasks()
385 ? this->buildPoly(path, shiftedClip, canCullToTheRight)
386 : this->build (path, shiftedClip, canCullToTheRight);
387
388 SkASSERT(count >= 0);
389
390 // If we can't cull to the right, we should have count > 1 (or 0).
391 if (!canCullToTheRight) {
392 SkASSERT(count != 1);
393 }
394 return count;
395}
int count
Definition: FontMgrTest.cpp:50
#define SkDEBUGFAIL(message)
Definition: SkAssert.h:118
#define SkASSERT(cond)
Definition: SkAssert.h:116
static bool is_vertical(const Edge *edge)
int32_t SkFixed
Definition: SkFixed.h:25
static bool SkIsFinite(T x, Pack... values)
int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10])
Definition: SkGeometry.cpp:698
int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5])
Definition: SkGeometry.cpp:279
bool approximately_equal(double x, double y)
static SkPath clip(const SkPath &path, const SkHalfPlane &plane)
Definition: SkPath.cpp:3892
static int32_t SkAbs32(int32_t value)
Definition: SkSafe32.h:41
#define SK_Scalar1
Definition: SkScalar.h:18
#define SkIntToScalar(x)
Definition: SkScalar.h:57
SkDEBUGCODE(SK_SPI) SkThreadID SkGetThreadID()
constexpr int SkToInt(S x)
Definition: SkTo.h:29
T * makeArrayDefault(size_t count)
Definition: SkArenaAlloc.h:171
auto make(Ctor &&ctor) -> decltype(ctor(nullptr))
Definition: SkArenaAlloc.h:120
const SkPoint * computeQuads(const SkConic &conic, SkScalar tol)
Definition: SkGeometry.h:524
int countQuads() const
Definition: SkGeometry.h:539
virtual void addLine(const SkPoint pts[])=0
virtual SkRect recoverClip(const SkIRect &) const =0
SkTDArray< void * > fList
Definition: SkEdgeBuilder.h:33
virtual void addCubic(const SkPoint pts[])=0
virtual void addQuad(const SkPoint pts[])=0
void ** fEdgeList
Definition: SkEdgeBuilder.h:32
SkSTArenaAlloc< 512 > fAlloc
Definition: SkEdgeBuilder.h:34
int buildEdges(const SkPath &path, const SkIRect *shiftedClip)
virtual char * allocEdges(size_t n, size_t *sizeof_edge)=0
virtual Combine addPolyLine(const SkPoint pts[], char *edge, char **edgePtr)=0
static void ClipPath(const SkPath &path, const SkRect &clip, bool canCullToTheRight, void(*consume)(SkEdgeClipper *, bool newCtr, void *ctx), void *ctx)
SkPath::Verb next(SkPoint pts[])
static int ClipLine(const SkPoint pts[2], const SkRect &clip, SkPoint lines[kMaxPoints], bool canCullToTheRight)
static int PtsInIter(unsigned verb)
Definition: SkPathPriv.h:305
Definition: SkPath.h:59
@ kLine_SegmentMask
Definition: SkPath.h:1445
@ kDone_Verb
Definition: SkPath.h:1472
@ kCubic_Verb
Definition: SkPath.h:1470
@ kQuad_Verb
Definition: SkPath.h:1468
@ kLine_Verb
Definition: SkPath.h:1467
size_t mul(size_t x, size_t y)
Definition: SkSafeMath.h:29
const T & back() const
Definition: SkTDArray.h:162
int size() const
Definition: SkTDArray.h:138
bool empty() const
Definition: SkTDArray.h:135
void push_back(const T &v)
Definition: SkTDArray.h:219
T * begin()
Definition: SkTDArray.h:150
void pop_back()
Definition: SkTDArray.h:223
float SkScalar
Definition: extension.cpp:12
static bool b
struct MyStruct a[10]
Definition: build.py:1
DEF_SWITCHES_START aot vmservice shared library Name of the *so containing AOT compiled Dart assets for launching the service isolate vm snapshot The VM snapshot data that will be memory mapped as read only SnapshotAssetPath must be present isolate snapshot The isolate snapshot data that will be memory mapped as read only SnapshotAssetPath must be present cache dir path
Definition: switches.h:57
it will be possible to load the file into Perfetto s trace viewer disable asset Prevents usage of any non test fonts unless they were explicitly Loaded via prefetched default font Indicates whether the embedding started a prefetch of the default font manager before creating the engine run In non interactive keep the shell running after the Dart script has completed enable serial On low power devices with low core running concurrent GC tasks on threads can cause them to contend with the UI thread which could potentially lead to jank This option turns off all concurrent GC activities domain network JSON encoded network policy per domain This overrides the DisallowInsecureConnections switch Embedder can specify whether to allow or disallow insecure connections at a domain level old gen heap size
Definition: switches.h:259
bool setCubic(const SkPoint pts[4], bool sortY=true)
bool setLine(const SkPoint &p0, const SkPoint &p1)
bool setQuadratic(const SkPoint pts[3])
int setCubic(const SkPoint pts[4], int shiftUp)
Definition: SkEdge.cpp:474
Definition: SkEdge.h:27
int8_t fWinding
Definition: SkEdge.h:45
int32_t fLastY
Definition: SkEdge.h:40
@ kLine_Type
Definition: SkEdge.h:29
SkFixed fX
Definition: SkEdge.h:37
int setLine(const SkPoint &p0, const SkPoint &p1, const SkIRect *clip, int shiftUp)
Definition: SkEdge.cpp:57
SkFixed fDX
Definition: SkEdge.h:38
Type fEdgeType
Definition: SkEdge.h:41
int32_t fFirstY
Definition: SkEdge.h:39
Definition: SkRect.h:32
int setQuadratic(const SkPoint pts[3], int shiftUp)
Definition: SkEdge.cpp:303
static SkRect Make(const SkISize &size)
Definition: SkRect.h:669