1/*
2 * Copyright 2009 The Android Open Source Project
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/private/SkMacros.h"
9#include "src/core/SkEdgeClipper.h"
10#include "src/core/SkGeometry.h"
11#include "src/core/SkLineClipper.h"
12
13#include <utility>
14
15static bool quick_reject(const SkRect& bounds, const SkRect& clip) {
16 return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
17}
18
19static inline void clamp_le(SkScalar& value, SkScalar max) {
20 if (value > max) {
21 value = max;
22 }
23}
24
25static inline void clamp_ge(SkScalar& value, SkScalar min) {
26 if (value < min) {
27 value = min;
28 }
29}
30
31/* src[] must be monotonic in Y. This routine copies src into dst, and sorts
32 it to be increasing in Y. If it had to reverse the order of the points,
33 it returns true, otherwise it returns false
34 */
35static bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) {
36 // we need the data to be monotonically increasing in Y
37 if (src[0].fY > src[count - 1].fY) {
38 for (int i = 0; i < count; i++) {
39 dst[i] = src[count - i - 1];
40 }
41 return true;
42 } else {
43 memcpy(dst, src, count * sizeof(SkPoint));
44 return false;
45 }
46}
47
48bool SkEdgeClipper::clipLine(SkPoint p0, SkPoint p1, const SkRect& clip) {
49 fCurrPoint = fPoints;
50 fCurrVerb = fVerbs;
51
52 SkPoint lines[SkLineClipper::kMaxPoints];
53 const SkPoint pts[] = { p0, p1 };
54 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, fCanCullToTheRight);
55 for (int i = 0; i < lineCount; i++) {
56 this->appendLine(lines[i], lines[i + 1]);
57 }
58
59 *fCurrVerb = SkPath::kDone_Verb;
60 fCurrPoint = fPoints;
61 fCurrVerb = fVerbs;
62 return SkPath::kDone_Verb != fVerbs[0];
63}
64
65///////////////////////////////////////////////////////////////////////////////
66
67static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2,
68 SkScalar target, SkScalar* t) {
69 /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
70 * We solve for t, using quadratic equation, hence we have to rearrange
71 * our cooefficents to look like At^2 + Bt + C
72 */
73 SkScalar A = c0 - c1 - c1 + c2;
74 SkScalar B = 2*(c1 - c0);
75 SkScalar C = c0 - target;
76
77 SkScalar roots[2]; // we only expect one, but make room for 2 for safety
78 int count = SkFindUnitQuadRoots(A, B, C, roots);
79 if (count) {
80 *t = roots[0];
81 return true;
82 }
83 return false;
84}
85
86static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) {
87 return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t);
88}
89
90static bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) {
91 return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t);
92}
93
94// Modify pts[] in place so that it is clipped in Y to the clip rect
95static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) {
96 SkScalar t;
97 SkPoint tmp[5]; // for SkChopQuadAt
98
99 // are we partially above
100 if (pts[0].fY < clip.fTop) {
101 if (chopMonoQuadAtY(pts, clip.fTop, &t)) {
102 // take the 2nd chopped quad
103 SkChopQuadAt(pts, tmp, t);
104 // clamp to clean up imprecise numerics in the chop
105 tmp[2].fY = clip.fTop;
106 clamp_ge(tmp[3].fY, clip.fTop);
107
108 pts[0] = tmp[2];
109 pts[1] = tmp[3];
110 } else {
111 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
112 // so we just clamp against the top
113 for (int i = 0; i < 3; i++) {
114 if (pts[i].fY < clip.fTop) {
115 pts[i].fY = clip.fTop;
116 }
117 }
118 }
119 }
120
121 // are we partially below
122 if (pts[2].fY > clip.fBottom) {
123 if (chopMonoQuadAtY(pts, clip.fBottom, &t)) {
124 SkChopQuadAt(pts, tmp, t);
125 // clamp to clean up imprecise numerics in the chop
126 clamp_le(tmp[1].fY, clip.fBottom);
127 tmp[2].fY = clip.fBottom;
128
129 pts[1] = tmp[1];
130 pts[2] = tmp[2];
131 } else {
132 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
133 // so we just clamp against the bottom
134 for (int i = 0; i < 3; i++) {
135 if (pts[i].fY > clip.fBottom) {
136 pts[i].fY = clip.fBottom;
137 }
138 }
139 }
140 }
141}
142
143// srcPts[] must be monotonic in X and Y
144void SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) {
145 SkPoint pts[3];
146 bool reverse = sort_increasing_Y(pts, srcPts, 3);
147
148 // are we completely above or below
149 if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
150 return;
151 }
152
153 // Now chop so that pts is contained within clip in Y
154 chop_quad_in_Y(pts, clip);
155
156 if (pts[0].fX > pts[2].fX) {
157 using std::swap;
158 swap(pts[0], pts[2]);
159 reverse = !reverse;
160 }
161 SkASSERT(pts[0].fX <= pts[1].fX);
162 SkASSERT(pts[1].fX <= pts[2].fX);
163
164 // Now chop in X has needed, and record the segments
165
166 if (pts[2].fX <= clip.fLeft) { // wholly to the left
167 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
168 return;
169 }
170 if (pts[0].fX >= clip.fRight) { // wholly to the right
171 if (!this->canCullToTheRight()) {
172 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
173 }
174 return;
175 }
176
177 SkScalar t;
178 SkPoint tmp[5]; // for SkChopQuadAt
179
180 // are we partially to the left
181 if (pts[0].fX < clip.fLeft) {
182 if (chopMonoQuadAtX(pts, clip.fLeft, &t)) {
183 SkChopQuadAt(pts, tmp, t);
184 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse);
185 // clamp to clean up imprecise numerics in the chop
186 tmp[2].fX = clip.fLeft;
187 clamp_ge(tmp[3].fX, clip.fLeft);
188
189 pts[0] = tmp[2];
190 pts[1] = tmp[3];
191 } else {
192 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
193 // so we just clamp against the left
194 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
195 return;
196 }
197 }
198
199 // are we partially to the right
200 if (pts[2].fX > clip.fRight) {
201 if (chopMonoQuadAtX(pts, clip.fRight, &t)) {
202 SkChopQuadAt(pts, tmp, t);
203 // clamp to clean up imprecise numerics in the chop
204 clamp_le(tmp[1].fX, clip.fRight);
205 tmp[2].fX = clip.fRight;
206
207 this->appendQuad(tmp, reverse);
208 this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse);
209 } else {
210 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
211 // so we just clamp against the right
212 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
213 }
214 } else { // wholly inside the clip
215 this->appendQuad(pts, reverse);
216 }
217}
218
219bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
220 fCurrPoint = fPoints;
221 fCurrVerb = fVerbs;
222
223 SkRect bounds;
224 bounds.setBounds(srcPts, 3);
225
226 if (!quick_reject(bounds, clip)) {
227 SkPoint monoY[5];
228 int countY = SkChopQuadAtYExtrema(srcPts, monoY);
229 for (int y = 0; y <= countY; y++) {
230 SkPoint monoX[5];
231 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
232 for (int x = 0; x <= countX; x++) {
233 this->clipMonoQuad(&monoX[x * 2], clip);
234 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
235 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
236 }
237 }
238 }
239
240 *fCurrVerb = SkPath::kDone_Verb;
241 fCurrPoint = fPoints;
242 fCurrVerb = fVerbs;
243 return SkPath::kDone_Verb != fVerbs[0];
244}
245
246///////////////////////////////////////////////////////////////////////////////
247
248static SkScalar mono_cubic_closestT(const SkScalar src[], SkScalar x) {
249 SkScalar t = 0.5f;
250 SkScalar lastT;
251 SkScalar bestT SK_INIT_TO_AVOID_WARNING;
252 SkScalar step = 0.25f;
253 SkScalar D = src[0];
254 SkScalar A = src[6] + 3*(src[2] - src[4]) - D;
255 SkScalar B = 3*(src[4] - src[2] - src[2] + D);
256 SkScalar C = 3*(src[2] - D);
257 x -= D;
258 SkScalar closest = SK_ScalarMax;
259 do {
260 SkScalar loc = ((A * t + B) * t + C) * t;
261 SkScalar dist = SkScalarAbs(loc - x);
262 if (closest > dist) {
263 closest = dist;
264 bestT = t;
265 }
266 lastT = t;
267 t += loc < x ? step : -step;
268 step *= 0.5f;
269 } while (closest > 0.25f && lastT != t);
270 return bestT;
271}
272
273static void chop_mono_cubic_at_y(SkPoint src[4], SkScalar y, SkPoint dst[7]) {
274 if (SkChopMonoCubicAtY(src, y, dst)) {
275 return;
276 }
277 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fY, y));
278}
279
280// Modify pts[] in place so that it is clipped in Y to the clip rect
281static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
282
283 // are we partially above
284 if (pts[0].fY < clip.fTop) {
285 SkPoint tmp[7];
286 chop_mono_cubic_at_y(pts, clip.fTop, tmp);
287
288 /*
289 * For a large range in the points, we can do a poor job of chopping, such that the t
290 * we computed resulted in the lower cubic still being partly above the clip.
291 *
292 * If just the first or first 2 Y values are above the fTop, we can just smash them
293 * down. If the first 3 Ys are above fTop, we can't smash all 3, as that can really
294 * distort the cubic. In this case, we take the first output (tmp[3..6] and treat it as
295 * a guess, and re-chop against fTop. Then we fall through to checking if we need to
296 * smash the first 1 or 2 Y values.
297 */
298 if (tmp[3].fY < clip.fTop && tmp[4].fY < clip.fTop && tmp[5].fY < clip.fTop) {
299 SkPoint tmp2[4];
300 memcpy(tmp2, &tmp[3].fX, 4 * sizeof(SkPoint));
301 chop_mono_cubic_at_y(tmp2, clip.fTop, tmp);
302 }
303
304 // tmp[3, 4].fY should all be to the below clip.fTop.
305 // Since we can't trust the numerics of the chopper, we force those conditions now
306 tmp[3].fY = clip.fTop;
307 clamp_ge(tmp[4].fY, clip.fTop);
308
309 pts[0] = tmp[3];
310 pts[1] = tmp[4];
311 pts[2] = tmp[5];
312 }
313
314 // are we partially below
315 if (pts[3].fY > clip.fBottom) {
316 SkPoint tmp[7];
317 chop_mono_cubic_at_y(pts, clip.fBottom, tmp);
318 tmp[3].fY = clip.fBottom;
319 clamp_le(tmp[2].fY, clip.fBottom);
320
321 pts[1] = tmp[1];
322 pts[2] = tmp[2];
323 pts[3] = tmp[3];
324 }
325}
326
327static void chop_mono_cubic_at_x(SkPoint src[4], SkScalar x, SkPoint dst[7]) {
328 if (SkChopMonoCubicAtX(src, x, dst)) {
329 return;
330 }
331 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fX, x));
332}
333
334// srcPts[] must be monotonic in X and Y
335void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
336 SkPoint pts[4];
337 bool reverse = sort_increasing_Y(pts, src, 4);
338
339 // are we completely above or below
340 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
341 return;
342 }
343
344 // Now chop so that pts is contained within clip in Y
345 chop_cubic_in_Y(pts, clip);
346
347 if (pts[0].fX > pts[3].fX) {
348 using std::swap;
349 swap(pts[0], pts[3]);
350 swap(pts[1], pts[2]);
351 reverse = !reverse;
352 }
353
354 // Now chop in X has needed, and record the segments
355
356 if (pts[3].fX <= clip.fLeft) { // wholly to the left
357 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
358 return;
359 }
360 if (pts[0].fX >= clip.fRight) { // wholly to the right
361 if (!this->canCullToTheRight()) {
362 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
363 }
364 return;
365 }
366
367 // are we partially to the left
368 if (pts[0].fX < clip.fLeft) {
369 SkPoint tmp[7];
370 chop_mono_cubic_at_x(pts, clip.fLeft, tmp);
371 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
372
373 // tmp[3, 4].fX should all be to the right of clip.fLeft.
374 // Since we can't trust the numerics of
375 // the chopper, we force those conditions now
376 tmp[3].fX = clip.fLeft;
377 clamp_ge(tmp[4].fX, clip.fLeft);
378
379 pts[0] = tmp[3];
380 pts[1] = tmp[4];
381 pts[2] = tmp[5];
382 }
383
384 // are we partially to the right
385 if (pts[3].fX > clip.fRight) {
386 SkPoint tmp[7];
387 chop_mono_cubic_at_x(pts, clip.fRight, tmp);
388 tmp[3].fX = clip.fRight;
389 clamp_le(tmp[2].fX, clip.fRight);
390
391 this->appendCubic(tmp, reverse);
392 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
393 } else { // wholly inside the clip
394 this->appendCubic(pts, reverse);
395 }
396}
397
398static SkRect compute_cubic_bounds(const SkPoint pts[4]) {
399 SkRect r;
400 r.setBounds(pts, 4);
401 return r;
402}
403
404static bool too_big_for_reliable_float_math(const SkRect& r) {
405 // limit set as the largest float value for which we can still reliably compute things like
406 // - chopping at XY extrema
407 // - chopping at Y or X values for clipping
408 //
409 // Current value chosen just by experiment. Larger (and still succeeds) is always better.
410 //
411 const SkScalar limit = 1 << 22;
412 return r.fLeft < -limit || r.fTop < -limit || r.fRight > limit || r.fBottom > limit;
413}
414
415bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
416 fCurrPoint = fPoints;
417 fCurrVerb = fVerbs;
418
419 const SkRect bounds = compute_cubic_bounds(srcPts);
420 // check if we're clipped out vertically
421 if (bounds.fBottom > clip.fTop && bounds.fTop < clip.fBottom) {
422 if (too_big_for_reliable_float_math(bounds)) {
423 // can't safely clip the cubic, so we give up and draw a line (which we can safely clip)
424 //
425 // If we rewrote chopcubicat*extrema and chopmonocubic using doubles, we could very
426 // likely always handle the cubic safely, but (it seems) at a big loss in speed, so
427 // we'd only want to take that alternate impl if needed. Perhaps a TODO to try it.
428 //
429 return this->clipLine(srcPts[0], srcPts[3], clip);
430 } else {
431 SkPoint monoY[10];
432 int countY = SkChopCubicAtYExtrema(srcPts, monoY);
433 for (int y = 0; y <= countY; y++) {
434 SkPoint monoX[10];
435 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
436 for (int x = 0; x <= countX; x++) {
437 this->clipMonoCubic(&monoX[x * 3], clip);
438 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
439 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
440 }
441 }
442 }
443 }
444
445 *fCurrVerb = SkPath::kDone_Verb;
446 fCurrPoint = fPoints;
447 fCurrVerb = fVerbs;
448 return SkPath::kDone_Verb != fVerbs[0];
449}
450
451///////////////////////////////////////////////////////////////////////////////
452
453void SkEdgeClipper::appendLine(SkPoint p0, SkPoint p1) {
454 *fCurrVerb++ = SkPath::kLine_Verb;
455 fCurrPoint[0] = p0;
456 fCurrPoint[1] = p1;
457 fCurrPoint += 2;
458}
459
460void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, bool reverse) {
461 *fCurrVerb++ = SkPath::kLine_Verb;
462
463 if (reverse) {
464 using std::swap;
465 swap(y0, y1);
466 }
467 fCurrPoint[0].set(x, y0);
468 fCurrPoint[1].set(x, y1);
469 fCurrPoint += 2;
470}
471
472void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
473 *fCurrVerb++ = SkPath::kQuad_Verb;
474
475 if (reverse) {
476 fCurrPoint[0] = pts[2];
477 fCurrPoint[2] = pts[0];
478 } else {
479 fCurrPoint[0] = pts[0];
480 fCurrPoint[2] = pts[2];
481 }
482 fCurrPoint[1] = pts[1];
483 fCurrPoint += 3;
484}
485
486void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
487 *fCurrVerb++ = SkPath::kCubic_Verb;
488
489 if (reverse) {
490 for (int i = 0; i < 4; i++) {
491 fCurrPoint[i] = pts[3 - i];
492 }
493 } else {
494 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
495 }
496 fCurrPoint += 4;
497}
498
499SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
500 SkPath::Verb verb = *fCurrVerb;
501
502 switch (verb) {
503 case SkPath::kLine_Verb:
504 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
505 fCurrPoint += 2;
506 fCurrVerb += 1;
507 break;
508 case SkPath::kQuad_Verb:
509 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
510 fCurrPoint += 3;
511 fCurrVerb += 1;
512 break;
513 case SkPath::kCubic_Verb:
514 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
515 fCurrPoint += 4;
516 fCurrVerb += 1;
517 break;
518 case SkPath::kDone_Verb:
519 break;
520 default:
521 SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
522 break;
523 }
524 return verb;
525}
526
527///////////////////////////////////////////////////////////////////////////////
528
529#ifdef SK_DEBUG
530static void assert_monotonic(const SkScalar coord[], int count) {
531 if (coord[0] > coord[(count - 1) * 2]) {
532 for (int i = 1; i < count; i++) {
533 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
534 }
535 } else if (coord[0] < coord[(count - 1) * 2]) {
536 for (int i = 1; i < count; i++) {
537 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
538 }
539 } else {
540 for (int i = 1; i < count; i++) {
541 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
542 }
543 }
544}
545
546void sk_assert_monotonic_y(const SkPoint pts[], int count) {
547 if (count > 1) {
548 assert_monotonic(&pts[0].fY, count);
549 }
550}
551
552void sk_assert_monotonic_x(const SkPoint pts[], int count) {
553 if (count > 1) {
554 assert_monotonic(&pts[0].fX, count);
555 }
556}
557#endif
558
559#include "src/core/SkPathPriv.h"
560
561void SkEdgeClipper::ClipPath(const SkPath& path, const SkRect& clip, bool canCullToTheRight,
562 void (*consume)(SkEdgeClipper*, bool newCtr, void* ctx), void* ctx) {
563 SkASSERT(path.isFinite());
564
565 SkAutoConicToQuads quadder;
566 const SkScalar conicTol = SK_Scalar1 / 4;
567
568 SkPathEdgeIter iter(path);
569 SkEdgeClipper clipper(canCullToTheRight);
570
571 while (auto e = iter.next()) {
572 switch (e.fEdge) {
573 case SkPathEdgeIter::Edge::kLine:
574 if (clipper.clipLine(e.fPts[0], e.fPts[1], clip)) {
575 consume(&clipper, e.fIsNewContour, ctx);
576 }
577 break;
578 case SkPathEdgeIter::Edge::kQuad:
579 if (clipper.clipQuad(e.fPts, clip)) {
580 consume(&clipper, e.fIsNewContour, ctx);
581 }
582 break;
583 case SkPathEdgeIter::Edge::kConic: {
584 const SkPoint* quadPts = quadder.computeQuads(e.fPts, iter.conicWeight(), conicTol);
585 for (int i = 0; i < quadder.countQuads(); ++i) {
586 if (clipper.clipQuad(quadPts, clip)) {
587 consume(&clipper, e.fIsNewContour, ctx);
588 }
589 quadPts += 2;
590 }
591 } break;
592 case SkPathEdgeIter::Edge::kCubic:
593 if (clipper.clipCubic(e.fPts, clip)) {
594 consume(&clipper, e.fIsNewContour, ctx);
595 }
596 break;
597 }
598 }
599}
600