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/SkDebug.h"
15 #include "include/private/base/SkFixed.h"
16 #include "include/private/base/SkFloatingPoint.h"
17 #include "include/private/base/SkSafe32.h"
18 #include "include/private/base/SkTo.h"
19 #include "src/base/SkSafeMath.h"
20 #include "src/core/SkAnalyticEdge.h"
21 #include "src/core/SkEdge.h"
22 #include "src/core/SkEdgeClipper.h"
23 #include "src/core/SkGeometry.h"
24 #include "src/core/SkLineClipper.h"
25 #include "src/core/SkPathPriv.h"
26
combineVertical(const SkEdge * edge,SkEdge * last)27 SkEdgeBuilder::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
combineVertical(const SkAnalyticEdge * edge,SkAnalyticEdge * last)70 SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::combineVertical(const SkAnalyticEdge* edge,
71 SkAnalyticEdge* last) {
72 auto approximately_equal = [](SkFixed a, SkFixed b) {
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
122 template <typename Edge>
is_vertical(const Edge * edge)123 static 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
addLine(const SkPoint pts[])133 void 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 }
addLine(const SkPoint pts[])147 void SkAnalyticEdgeBuilder::addLine(const SkPoint pts[]) {
148 SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>();
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 }
addQuad(const SkPoint pts[])162 void SkBasicEdgeBuilder::addQuad(const SkPoint pts[]) {
163 SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>();
164 if (edge->setQuadratic(pts, fClipShift)) {
165 fList.push_back(edge);
166 }
167 }
addQuad(const SkPoint pts[])168 void SkAnalyticEdgeBuilder::addQuad(const SkPoint pts[]) {
169 SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>();
170 if (edge->setQuadratic(pts)) {
171 fList.push_back(edge);
172 }
173 }
174
addCubic(const SkPoint pts[])175 void SkBasicEdgeBuilder::addCubic(const SkPoint pts[]) {
176 SkCubicEdge* edge = fAlloc.make<SkCubicEdge>();
177 if (edge->setCubic(pts, fClipShift)) {
178 fList.push_back(edge);
179 }
180 }
addCubic(const SkPoint pts[])181 void SkAnalyticEdgeBuilder::addCubic(const SkPoint pts[]) {
182 SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>();
183 if (edge->setCubic(pts)) {
184 fList.push_back(edge);
185 }
186 }
187
188 // TODO: merge addLine() and addPolyLine()?
189
addPolyLine(const SkPoint pts[],char * arg_edge,char ** arg_edgePtr)190 SkEdgeBuilder::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 }
addPolyLine(const SkPoint pts[],char * arg_edge,char ** arg_edgePtr)202 SkEdgeBuilder::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
recoverClip(const SkIRect & src) const215 SkRect 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 }
recoverClip(const SkIRect & src) const221 SkRect SkAnalyticEdgeBuilder::recoverClip(const SkIRect& src) const {
222 return SkRect::Make(src);
223 }
224
allocEdges(size_t n,size_t * size)225 char* SkBasicEdgeBuilder::allocEdges(size_t n, size_t* size) {
226 *size = sizeof(SkEdge);
227 return (char*)fAlloc.makeArrayDefault<SkEdge>(n);
228 }
allocEdges(size_t n,size_t * size)229 char* 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?
buildPoly(const SkPath & path,const SkIRect * iclip,bool canCullToTheRight)235 int 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) {
261 case SkPathEdgeIter::Edge::kLine: {
262 SkPoint lines[SkLineClipper::kMaxPoints];
263 int lineCount = SkLineClipper::ClipLine(e.fPts, clip, lines, canCullToTheRight);
264 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
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) {
283 case SkPathEdgeIter::Edge::kLine: {
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
build(const SkPath & path,const SkIRect * iclip,bool canCullToTheRight)303 int 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) {
347 case SkPathEdgeIter::Edge::kLine:
348 this->addLine(e.fPts);
349 break;
350 case SkPathEdgeIter::Edge::kQuad: {
351 handle_quad(e.fPts);
352 break;
353 }
354 case SkPathEdgeIter::Edge::kConic: {
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;
362 case SkPathEdgeIter::Edge::kCubic: {
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 }
373 fEdgeList = fList.begin();
374 return is_finite ? fList.size() : 0;
375 }
376
buildEdges(const SkPath & path,const SkIRect * shiftedClip)377 int SkEdgeBuilder::buildEdges(const SkPath& path,
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 }
396