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