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