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 pts[1].fX = std::min(pts[1].fX, clip.fRight);
213 pts[2].fX = std::min(pts[2].fX, clip.fRight);
214 this->appendQuad(pts, reverse);
215 }
216 } else { // wholly inside the clip
217 this->appendQuad(pts, reverse);
218 }
219}
220
221bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
222 fCurrPoint = fPoints;
223 fCurrVerb = fVerbs;
224
225 SkRect bounds;
226 bounds.setBounds(srcPts, 3);
227
228 if (!quick_reject(bounds, clip)) {
229 SkPoint monoY[5];
230 int countY = SkChopQuadAtYExtrema(srcPts, monoY);
231 for (int y = 0; y <= countY; y++) {
232 SkPoint monoX[5];
233 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
234 for (int x = 0; x <= countX; x++) {
235 this->clipMonoQuad(&monoX[x * 2], clip);
236 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
237 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
238 }
239 }
240 }
241
242 *fCurrVerb = SkPath::kDone_Verb;
243 fCurrPoint = fPoints;
244 fCurrVerb = fVerbs;
245 return SkPath::kDone_Verb != fVerbs[0];
246}
247
248///////////////////////////////////////////////////////////////////////////////
249
250static SkScalar mono_cubic_closestT(const SkScalar src[], SkScalar x) {
251 SkScalar t = 0.5f;
252 SkScalar lastT;
253 SkScalar bestT SK_INIT_TO_AVOID_WARNING;
254 SkScalar step = 0.25f;
255 SkScalar D = src[0];
256 SkScalar A = src[6] + 3*(src[2] - src[4]) - D;
257 SkScalar B = 3*(src[4] - src[2] - src[2] + D);
258 SkScalar C = 3*(src[2] - D);
259 x -= D;
260 SkScalar closest = SK_ScalarMax;
261 do {
262 SkScalar loc = ((A * t + B) * t + C) * t;
263 SkScalar dist = SkScalarAbs(loc - x);
264 if (closest > dist) {
265 closest = dist;
266 bestT = t;
267 }
268 lastT = t;
269 t += loc < x ? step : -step;
270 step *= 0.5f;
271 } while (closest > 0.25f && lastT != t);
272 return bestT;
273}
274
275static void chop_mono_cubic_at_y(SkPoint src[4], SkScalar y, SkPoint dst[7]) {
276 if (SkChopMonoCubicAtY(src, y, dst)) {
277 return;
278 }
279 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fY, y));
280}
281
282// Modify pts[] in place so that it is clipped in Y to the clip rect
283static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
284
285 // are we partially above
286 if (pts[0].fY < clip.fTop) {
287 SkPoint tmp[7];
288 chop_mono_cubic_at_y(pts, clip.fTop, tmp);
289
290 /*
291 * For a large range in the points, we can do a poor job of chopping, such that the t
292 * we computed resulted in the lower cubic still being partly above the clip.
293 *
294 * If just the first or first 2 Y values are above the fTop, we can just smash them
295 * down. If the first 3 Ys are above fTop, we can't smash all 3, as that can really
296 * distort the cubic. In this case, we take the first output (tmp[3..6] and treat it as
297 * a guess, and re-chop against fTop. Then we fall through to checking if we need to
298 * smash the first 1 or 2 Y values.
299 */
300 if (tmp[3].fY < clip.fTop && tmp[4].fY < clip.fTop && tmp[5].fY < clip.fTop) {
301 SkPoint tmp2[4];
302 memcpy(tmp2, &tmp[3].fX, 4 * sizeof(SkPoint));
303 chop_mono_cubic_at_y(tmp2, clip.fTop, tmp);
304 }
305
306 // tmp[3, 4].fY should all be to the below clip.fTop.
307 // Since we can't trust the numerics of the chopper, we force those conditions now
308 tmp[3].fY = clip.fTop;
309 clamp_ge(tmp[4].fY, clip.fTop);
310
311 pts[0] = tmp[3];
312 pts[1] = tmp[4];
313 pts[2] = tmp[5];
314 }
315
316 // are we partially below
317 if (pts[3].fY > clip.fBottom) {
318 SkPoint tmp[7];
319 chop_mono_cubic_at_y(pts, clip.fBottom, tmp);
320 tmp[3].fY = clip.fBottom;
321 clamp_le(tmp[2].fY, clip.fBottom);
322
323 pts[1] = tmp[1];
324 pts[2] = tmp[2];
325 pts[3] = tmp[3];
326 }
327}
328
329static void chop_mono_cubic_at_x(SkPoint src[4], SkScalar x, SkPoint dst[7]) {
330 if (SkChopMonoCubicAtX(src, x, dst)) {
331 return;
332 }
333 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fX, x));
334}
335
336// srcPts[] must be monotonic in X and Y
337void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
338 SkPoint pts[4];
339 bool reverse = sort_increasing_Y(pts, src, 4);
340
341 // are we completely above or below
342 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
343 return;
344 }
345
346 // Now chop so that pts is contained within clip in Y
347 chop_cubic_in_Y(pts, clip);
348
349 if (pts[0].fX > pts[3].fX) {
350 using std::swap;
351 swap(pts[0], pts[3]);
352 swap(pts[1], pts[2]);
353 reverse = !reverse;
354 }
355
356 // Now chop in X has needed, and record the segments
357
358 if (pts[3].fX <= clip.fLeft) { // wholly to the left
359 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
360 return;
361 }
362 if (pts[0].fX >= clip.fRight) { // wholly to the right
363 if (!this->canCullToTheRight()) {
364 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
365 }
366 return;
367 }
368
369 // are we partially to the left
370 if (pts[0].fX < clip.fLeft) {
371 SkPoint tmp[7];
372 chop_mono_cubic_at_x(pts, clip.fLeft, tmp);
373 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
374
375 // tmp[3, 4].fX should all be to the right of clip.fLeft.
376 // Since we can't trust the numerics of
377 // the chopper, we force those conditions now
378 tmp[3].fX = clip.fLeft;
379 clamp_ge(tmp[4].fX, clip.fLeft);
380
381 pts[0] = tmp[3];
382 pts[1] = tmp[4];
383 pts[2] = tmp[5];
384 }
385
386 // are we partially to the right
387 if (pts[3].fX > clip.fRight) {
388 SkPoint tmp[7];
389 chop_mono_cubic_at_x(pts, clip.fRight, tmp);
390 tmp[3].fX = clip.fRight;
391 clamp_le(tmp[2].fX, clip.fRight);
392
393 this->appendCubic(tmp, reverse);
394 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
395 } else { // wholly inside the clip
396 this->appendCubic(pts, reverse);
397 }
398}
399
400static SkRect compute_cubic_bounds(const SkPoint pts[4]) {
401 SkRect r;
402 r.setBounds(pts, 4);
403 return r;
404}
405
406static bool too_big_for_reliable_float_math(const SkRect& r) {
407 // limit set as the largest float value for which we can still reliably compute things like
408 // - chopping at XY extrema
409 // - chopping at Y or X values for clipping
410 //
411 // Current value chosen just by experiment. Larger (and still succeeds) is always better.
412 //
413 const SkScalar limit = 1 << 22;
414 return r.fLeft < -limit || r.fTop < -limit || r.fRight > limit || r.fBottom > limit;
415}
416
417bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
418 fCurrPoint = fPoints;
419 fCurrVerb = fVerbs;
420
421 const SkRect bounds = compute_cubic_bounds(srcPts);
422 // check if we're clipped out vertically
423 if (bounds.fBottom > clip.fTop && bounds.fTop < clip.fBottom) {
424 if (too_big_for_reliable_float_math(bounds)) {
425 // can't safely clip the cubic, so we give up and draw a line (which we can safely clip)
426 //
427 // If we rewrote chopcubicat*extrema and chopmonocubic using doubles, we could very
428 // likely always handle the cubic safely, but (it seems) at a big loss in speed, so
429 // we'd only want to take that alternate impl if needed. Perhaps a TODO to try it.
430 //
431 return this->clipLine(srcPts[0], srcPts[3], clip);
432 } else {
433 SkPoint monoY[10];
434 int countY = SkChopCubicAtYExtrema(srcPts, monoY);
435 for (int y = 0; y <= countY; y++) {
436 SkPoint monoX[10];
437 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
438 for (int x = 0; x <= countX; x++) {
439 this->clipMonoCubic(&monoX[x * 3], clip);
440 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
441 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
442 }
443 }
444 }
445 }
446
447 *fCurrVerb = SkPath::kDone_Verb;
448 fCurrPoint = fPoints;
449 fCurrVerb = fVerbs;
450 return SkPath::kDone_Verb != fVerbs[0];
451}
452
453///////////////////////////////////////////////////////////////////////////////
454
455void SkEdgeClipper::appendLine(SkPoint p0, SkPoint p1) {
456 *fCurrVerb++ = SkPath::kLine_Verb;
457 fCurrPoint[0] = p0;
458 fCurrPoint[1] = p1;
459 fCurrPoint += 2;
460}
461
462void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, bool reverse) {
463 *fCurrVerb++ = SkPath::kLine_Verb;
464
465 if (reverse) {
466 using std::swap;
467 swap(y0, y1);
468 }
469 fCurrPoint[0].set(x, y0);
470 fCurrPoint[1].set(x, y1);
471 fCurrPoint += 2;
472}
473
474void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
475 *fCurrVerb++ = SkPath::kQuad_Verb;
476
477 if (reverse) {
478 fCurrPoint[0] = pts[2];
479 fCurrPoint[2] = pts[0];
480 } else {
481 fCurrPoint[0] = pts[0];
482 fCurrPoint[2] = pts[2];
483 }
484 fCurrPoint[1] = pts[1];
485 fCurrPoint += 3;
486}
487
488void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
489 *fCurrVerb++ = SkPath::kCubic_Verb;
490
491 if (reverse) {
492 for (int i = 0; i < 4; i++) {
493 fCurrPoint[i] = pts[3 - i];
494 }
495 } else {
496 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
497 }
498 fCurrPoint += 4;
499}
500
501SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
502 SkPath::Verb verb = *fCurrVerb;
503
504 switch (verb) {
505 case SkPath::kLine_Verb:
506 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
507 fCurrPoint += 2;
508 fCurrVerb += 1;
509 break;
510 case SkPath::kQuad_Verb:
511 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
512 fCurrPoint += 3;
513 fCurrVerb += 1;
514 break;
515 case SkPath::kCubic_Verb:
516 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
517 fCurrPoint += 4;
518 fCurrVerb += 1;
519 break;
520 case SkPath::kDone_Verb:
521 break;
522 default:
523 SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
524 break;
525 }
526 return verb;
527}
528
529///////////////////////////////////////////////////////////////////////////////
530
531#ifdef SK_DEBUG
532static void assert_monotonic(const SkScalar coord[], int count) {
533 if (coord[0] > coord[(count - 1) * 2]) {
534 for (int i = 1; i < count; i++) {
535 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
536 }
537 } else if (coord[0] < coord[(count - 1) * 2]) {
538 for (int i = 1; i < count; i++) {
539 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
540 }
541 } else {
542 for (int i = 1; i < count; i++) {
543 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
544 }
545 }
546}
547
548void sk_assert_monotonic_y(const SkPoint pts[], int count) {
549 if (count > 1) {
550 assert_monotonic(&pts[0].fY, count);
551 }
552}
553
554void sk_assert_monotonic_x(const SkPoint pts[], int count) {
555 if (count > 1) {
556 assert_monotonic(&pts[0].fX, count);
557 }
558}
559#endif
560
561#include "src/core/SkPathPriv.h"
562
563void SkEdgeClipper::ClipPath(const SkPathView& view, const SkRect& clip, bool canCullToTheRight,
564 void (*consume)(SkEdgeClipper*, bool newCtr, void* ctx), void* ctx) {
565 SkASSERT(view.isFinite());
566 SkAutoConicToQuads quadder;
567 const SkScalar conicTol = SK_Scalar1 / 4;
568
569 SkPathEdgeIter iter(view);
570 SkEdgeClipper clipper(canCullToTheRight);
571
572 while (auto e = iter.next()) {
573 switch (e.fEdge) {
574 case SkPathEdgeIter::Edge::kLine:
575 if (clipper.clipLine(e.fPts[0], e.fPts[1], clip)) {
576 consume(&clipper, e.fIsNewContour, ctx);
577 }
578 break;
579 case SkPathEdgeIter::Edge::kQuad:
580 if (clipper.clipQuad(e.fPts, clip)) {
581 consume(&clipper, e.fIsNewContour, ctx);
582 }
583 break;
584 case SkPathEdgeIter::Edge::kConic: {
585 const SkPoint* quadPts = quadder.computeQuads(e.fPts, iter.conicWeight(), conicTol);
586 for (int i = 0; i < quadder.countQuads(); ++i) {
587 if (clipper.clipQuad(quadPts, clip)) {
588 consume(&clipper, e.fIsNewContour, ctx);
589 }
590 quadPts += 2;
591 }
592 } break;
593 case SkPathEdgeIter::Edge::kCubic:
594 if (clipper.clipCubic(e.fPts, clip)) {
595 consume(&clipper, e.fIsNewContour, ctx);
596 }
597 break;
598 }
599 }
600}
601