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
8 #include "src/core/SkEdgeBuilder.h"
9
10 #include "include/core/SkPath.h"
11 #include "include/core/SkPoint.h"
12 #include "include/core/SkScalar.h"
13 #include "include/core/SkTypes.h"
14 #include "include/private/base/SkFixed.h"
15 #include "include/private/base/SkDebug.h"
16 #include "include/private/base/SkSafe32.h"
17 #include "include/private/base/SkTo.h"
18 #include "src/base/SkSafeMath.h"
19 #include "src/core/SkAnalyticEdge.h"
20 #include "src/core/SkEdge.h"
21 #include "src/core/SkEdgeClipper.h"
22 #include "src/core/SkGeometry.h"
23 #include "src/core/SkLineClipper.h"
24 #include "src/core/SkPathPriv.h"
25
combineVertical(const SkEdge * edge,SkEdge * last)26 SkEdgeBuilder::Combine SkBasicEdgeBuilder::combineVertical(const SkEdge* edge, SkEdge* last) {
27 // We only consider edges that were originally lines to be vertical to avoid numerical issues
28 // (crbug.com/1154864).
29 if (last->fEdgeType != SkEdge::kLine_Type || last->fDX || edge->fX != last->fX) {
30 return kNo_Combine;
31 }
32 if (edge->fWinding == last->fWinding) {
33 if (edge->fLastY + 1 == last->fFirstY) {
34 last->fFirstY = edge->fFirstY;
35 return kPartial_Combine;
36 }
37 if (edge->fFirstY == last->fLastY + 1) {
38 last->fLastY = edge->fLastY;
39 return kPartial_Combine;
40 }
41 return kNo_Combine;
42 }
43 if (edge->fFirstY == last->fFirstY) {
44 if (edge->fLastY == last->fLastY) {
45 return kTotal_Combine;
46 }
47 if (edge->fLastY < last->fLastY) {
48 last->fFirstY = edge->fLastY + 1;
49 return kPartial_Combine;
50 }
51 last->fFirstY = last->fLastY + 1;
52 last->fLastY = edge->fLastY;
53 last->fWinding = edge->fWinding;
54 return kPartial_Combine;
55 }
56 if (edge->fLastY == last->fLastY) {
57 if (edge->fFirstY > last->fFirstY) {
58 last->fLastY = edge->fFirstY - 1;
59 return kPartial_Combine;
60 }
61 last->fLastY = last->fFirstY - 1;
62 last->fFirstY = edge->fFirstY;
63 last->fWinding = edge->fWinding;
64 return kPartial_Combine;
65 }
66 return kNo_Combine;
67 }
68
combineVertical(const SkAnalyticEdge * edge,SkAnalyticEdge * last)69 SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::combineVertical(const SkAnalyticEdge* edge,
70 SkAnalyticEdge* last) {
71 auto approximately_equal = [](SkFixed a, SkFixed b) {
72 return SkAbs32(a - b) < 0x100;
73 };
74
75 // We only consider edges that were originally lines to be vertical to avoid numerical issues
76 // (crbug.com/1154864).
77 if (last->fEdgeType != SkAnalyticEdge::kLine_Type || last->fDX || edge->fX != last->fX) {
78 return kNo_Combine;
79 }
80 if (edge->fWinding == last->fWinding) {
81 if (edge->fLowerY == last->fUpperY) {
82 last->fUpperY = edge->fUpperY;
83 last->fY = last->fUpperY;
84 return kPartial_Combine;
85 }
86 if (approximately_equal(edge->fUpperY, last->fLowerY)) {
87 last->fLowerY = edge->fLowerY;
88 return kPartial_Combine;
89 }
90 return kNo_Combine;
91 }
92 if (approximately_equal(edge->fUpperY, last->fUpperY)) {
93 if (approximately_equal(edge->fLowerY, last->fLowerY)) {
94 return kTotal_Combine;
95 }
96 if (edge->fLowerY < last->fLowerY) {
97 last->fUpperY = edge->fLowerY;
98 last->fY = last->fUpperY;
99 return kPartial_Combine;
100 }
101 last->fUpperY = last->fLowerY;
102 last->fY = last->fUpperY;
103 last->fLowerY = edge->fLowerY;
104 last->fWinding = edge->fWinding;
105 return kPartial_Combine;
106 }
107 if (approximately_equal(edge->fLowerY, last->fLowerY)) {
108 if (edge->fUpperY > last->fUpperY) {
109 last->fLowerY = edge->fUpperY;
110 return kPartial_Combine;
111 }
112 last->fLowerY = last->fUpperY;
113 last->fUpperY = edge->fUpperY;
114 last->fY = last->fUpperY;
115 last->fWinding = edge->fWinding;
116 return kPartial_Combine;
117 }
118 return kNo_Combine;
119 }
120
121 template <typename Edge>
is_vertical(const Edge * edge)122 static bool is_vertical(const Edge* edge) {
123 // We only consider edges that were originally lines to be vertical to avoid numerical issues
124 // (crbug.com/1154864).
125 return edge->fDX == 0
126 && edge->fEdgeType == Edge::kLine_Type;
127 }
128
129 // TODO: we can deallocate the edge if edge->setFoo() fails
130 // or when we don't use it (kPartial_Combine or kTotal_Combine).
131
addLine(const SkPoint pts[])132 void SkBasicEdgeBuilder::addLine(const SkPoint pts[]) {
133 SkEdge* edge = fAlloc.make<SkEdge>();
134 if (edge->setLine(pts[0], pts[1], fClipShift)) {
135 Combine combine = is_vertical(edge) && !fList.empty()
136 ? this->combineVertical(edge, (SkEdge*)fList.back())
137 : kNo_Combine;
138
139 switch (combine) {
140 case kTotal_Combine: fList.pop_back(); break;
141 case kPartial_Combine: break;
142 case kNo_Combine: fList.push_back(edge); break;
143 }
144 }
145 }
addLine(const SkPoint pts[])146 void SkAnalyticEdgeBuilder::addLine(const SkPoint pts[]) {
147 SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>();
148 if (edge->setLine(pts[0], pts[1])) {
149
150 Combine combine = is_vertical(edge) && !fList.empty()
151 ? this->combineVertical(edge, (SkAnalyticEdge*)fList.back())
152 : kNo_Combine;
153
154 switch (combine) {
155 case kTotal_Combine: fList.pop_back(); break;
156 case kPartial_Combine: break;
157 case kNo_Combine: fList.push_back(edge); break;
158 }
159 }
160 }
addQuad(const SkPoint pts[])161 void SkBasicEdgeBuilder::addQuad(const SkPoint pts[]) {
162 SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>();
163 if (edge->setQuadratic(pts, fClipShift)) {
164 fList.push_back(edge);
165 }
166 }
addQuad(const SkPoint pts[])167 void SkAnalyticEdgeBuilder::addQuad(const SkPoint pts[]) {
168 SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>();
169 if (edge->setQuadratic(pts)) {
170 fList.push_back(edge);
171 }
172 }
173
addCubic(const SkPoint pts[])174 void SkBasicEdgeBuilder::addCubic(const SkPoint pts[]) {
175 SkCubicEdge* edge = fAlloc.make<SkCubicEdge>();
176 if (edge->setCubic(pts, fClipShift)) {
177 fList.push_back(edge);
178 }
179 }
addCubic(const SkPoint pts[])180 void SkAnalyticEdgeBuilder::addCubic(const SkPoint pts[]) {
181 SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>();
182 if (edge->setCubic(pts)) {
183 fList.push_back(edge);
184 }
185 }
186
187 // TODO: merge addLine() and addPolyLine()?
188
addPolyLine(const SkPoint pts[],char * arg_edge,char ** arg_edgePtr)189 SkEdgeBuilder::Combine SkBasicEdgeBuilder::addPolyLine(const SkPoint pts[],
190 char* arg_edge, char** arg_edgePtr) {
191 auto edge = (SkEdge*) arg_edge;
192 auto edgePtr = (SkEdge**)arg_edgePtr;
193
194 if (edge->setLine(pts[0], pts[1], fClipShift)) {
195 return is_vertical(edge) && edgePtr > (SkEdge**)fEdgeList
196 ? this->combineVertical(edge, edgePtr[-1])
197 : kNo_Combine;
198 }
199 return SkEdgeBuilder::kPartial_Combine; // A convenient lie. Same do-nothing behavior.
200 }
addPolyLine(const SkPoint pts[],char * arg_edge,char ** arg_edgePtr)201 SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::addPolyLine(const SkPoint pts[],
202 char* arg_edge, char** arg_edgePtr) {
203 auto edge = (SkAnalyticEdge*) arg_edge;
204 auto edgePtr = (SkAnalyticEdge**)arg_edgePtr;
205
206 if (edge->setLine(pts[0], pts[1])) {
207 return is_vertical(edge) && edgePtr > (SkAnalyticEdge**)fEdgeList
208 ? this->combineVertical(edge, edgePtr[-1])
209 : kNo_Combine;
210 }
211 return SkEdgeBuilder::kPartial_Combine; // As above.
212 }
213
recoverClip(const SkIRect & src) const214 SkRect SkBasicEdgeBuilder::recoverClip(const SkIRect& src) const {
215 return { SkIntToScalar(src.fLeft >> fClipShift),
216 SkIntToScalar(src.fTop >> fClipShift),
217 SkIntToScalar(src.fRight >> fClipShift),
218 SkIntToScalar(src.fBottom >> fClipShift), };
219 }
recoverClip(const SkIRect & src) const220 SkRect SkAnalyticEdgeBuilder::recoverClip(const SkIRect& src) const {
221 return SkRect::Make(src);
222 }
223
allocEdges(size_t n,size_t * size)224 char* SkBasicEdgeBuilder::allocEdges(size_t n, size_t* size) {
225 *size = sizeof(SkEdge);
226 return (char*)fAlloc.makeArrayDefault<SkEdge>(n);
227 }
allocEdges(size_t n,size_t * size)228 char* SkAnalyticEdgeBuilder::allocEdges(size_t n, size_t* size) {
229 *size = sizeof(SkAnalyticEdge);
230 return (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(n);
231 }
232
233 // TODO: maybe get rid of buildPoly() entirely?
buildPoly(const SkPath & path,const SkIRect * iclip,bool canCullToTheRight)234 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) {
235 size_t maxEdgeCount = path.countPoints();
236 if (iclip) {
237 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
238 // we turn portions that are clipped out on the left/right into vertical
239 // segments.
240 SkSafeMath safe;
241 maxEdgeCount = safe.mul(maxEdgeCount, SkLineClipper::kMaxClippedLineSegments);
242 if (!safe) {
243 return 0;
244 }
245 }
246
247 size_t edgeSize;
248 char* edge = this->allocEdges(maxEdgeCount, &edgeSize);
249
250 SkDEBUGCODE(char* edgeStart = edge);
251 char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount);
252 fEdgeList = (void**)edgePtr;
253
254 SkPathEdgeIter iter(path);
255 if (iclip) {
256 SkRect clip = this->recoverClip(*iclip);
257
258 while (auto e = iter.next()) {
259 switch (e.fEdge) {
260 case SkPathEdgeIter::Edge::kLine: {
261 SkPoint lines[SkLineClipper::kMaxPoints];
262 int lineCount = SkLineClipper::ClipLine(e.fPts, clip, lines, canCullToTheRight);
263 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
264 for (int i = 0; i < lineCount; i++) {
265 switch( this->addPolyLine(lines + i, edge, edgePtr) ) {
266 case kTotal_Combine: edgePtr--; break;
267 case kPartial_Combine: break;
268 case kNo_Combine: *edgePtr++ = edge;
269 edge += edgeSize;
270 }
271 }
272 break;
273 }
274 default:
275 SkDEBUGFAIL("unexpected verb");
276 break;
277 }
278 }
279 } else {
280 while (auto e = iter.next()) {
281 switch (e.fEdge) {
282 case SkPathEdgeIter::Edge::kLine: {
283 switch( this->addPolyLine(e.fPts, edge, edgePtr) ) {
284 case kTotal_Combine: edgePtr--; break;
285 case kPartial_Combine: break;
286 case kNo_Combine: *edgePtr++ = edge;
287 edge += edgeSize;
288 }
289 break;
290 }
291 default:
292 SkDEBUGFAIL("unexpected verb");
293 break;
294 }
295 }
296 }
297 SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize);
298 SkASSERT((size_t)(edgePtr - (char**)fEdgeList) <= maxEdgeCount);
299 return SkToInt(edgePtr - (char**)fEdgeList);
300 }
301
build(const SkPath & path,const SkIRect * iclip,bool canCullToTheRight)302 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) {
303 SkAutoConicToQuads quadder;
304 const SkScalar conicTol = SK_Scalar1 / 4;
305 bool is_finite = true;
306
307 SkPathEdgeIter iter(path);
308 if (iclip) {
309 SkRect clip = this->recoverClip(*iclip);
310 struct Rec {
311 SkEdgeBuilder* fBuilder;
312 bool fIsFinite;
313 } rec = { this, true };
314
315 SkEdgeClipper::ClipPath(path, clip, canCullToTheRight,
316 [](SkEdgeClipper* clipper, bool, void* ctx) {
317 Rec* rec = (Rec*)ctx;
318 SkPoint pts[4];
319 SkPath::Verb verb;
320
321 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
322 const int count = SkPathPriv::PtsInIter(verb);
323 if (!SkScalarsAreFinite(&pts[0].fX, count*2)) {
324 rec->fIsFinite = false;
325 return;
326 }
327 switch (verb) {
328 case SkPath::kLine_Verb: rec->fBuilder->addLine (pts); break;
329 case SkPath::kQuad_Verb: rec->fBuilder->addQuad (pts); break;
330 case SkPath::kCubic_Verb: rec->fBuilder->addCubic(pts); break;
331 default: break;
332 }
333 }
334 }, &rec);
335 is_finite = rec.fIsFinite;
336 } else {
337 auto handle_quad = [this](const SkPoint pts[3]) {
338 SkPoint monoX[5];
339 int n = SkChopQuadAtYExtrema(pts, monoX);
340 for (int i = 0; i <= n; i++) {
341 this->addQuad(&monoX[i * 2]);
342 }
343 };
344 while (auto e = iter.next()) {
345 switch (e.fEdge) {
346 case SkPathEdgeIter::Edge::kLine:
347 this->addLine(e.fPts);
348 break;
349 case SkPathEdgeIter::Edge::kQuad: {
350 handle_quad(e.fPts);
351 break;
352 }
353 case SkPathEdgeIter::Edge::kConic: {
354 const SkPoint* quadPts = quadder.computeQuads(
355 e.fPts, iter.conicWeight(), conicTol);
356 for (int i = 0; i < quadder.countQuads(); ++i) {
357 handle_quad(quadPts);
358 quadPts += 2;
359 }
360 } break;
361 case SkPathEdgeIter::Edge::kCubic: {
362 SkPoint monoY[10];
363 int n = SkChopCubicAtYExtrema(e.fPts, monoY);
364 for (int i = 0; i <= n; i++) {
365 this->addCubic(&monoY[i * 3]);
366 }
367 break;
368 }
369 }
370 }
371 }
372 fEdgeList = fList.begin();
373 return is_finite ? fList.size() : 0;
374 }
375
buildEdges(const SkPath & path,const SkIRect * shiftedClip)376 int SkEdgeBuilder::buildEdges(const SkPath& path,
377 const SkIRect* shiftedClip) {
378 // If we're convex, then we need both edges, even if the right edge is past the clip.
379 const bool canCullToTheRight = !path.isConvex();
380
381 // We can use our buildPoly() optimization if all the segments are lines.
382 // (Edges are homogeneous and stored contiguously in memory, no need for indirection.)
383 const int count = SkPath::kLine_SegmentMask == path.getSegmentMasks()
384 ? this->buildPoly(path, shiftedClip, canCullToTheRight)
385 : this->build (path, shiftedClip, canCullToTheRight);
386
387 SkASSERT(count >= 0);
388
389 // If we can't cull to the right, we should have count > 1 (or 0).
390 if (!canCullToTheRight) {
391 SkASSERT(count != 1);
392 }
393 return count;
394 }
395