1/*
2 * Copyright 2012 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#ifndef SkPathOpsTypes_DEFINED
8#define SkPathOpsTypes_DEFINED
9
10#include <float.h> // for FLT_EPSILON
11
12#include "include/core/SkPath.h"
13#include "include/core/SkScalar.h"
14#include "include/pathops/SkPathOps.h"
15#include "include/private/SkFloatingPoint.h"
16#include "include/private/SkSafe_math.h"
17#include "src/pathops/SkPathOpsDebug.h"
18
19enum SkPathOpsMask {
20 kWinding_PathOpsMask = -1,
21 kNo_PathOpsMask = 0,
22 kEvenOdd_PathOpsMask = 1
23};
24
25class SkArenaAlloc;
26class SkOpCoincidence;
27class SkOpContour;
28class SkOpContourHead;
29class SkIntersections;
30class SkIntersectionHelper;
31
32enum class SkOpPhase : char {
33 kNoChange,
34 kIntersecting,
35 kWalking,
36 kFixWinding,
37};
38
39class SkOpGlobalState {
40public:
41 SkOpGlobalState(SkOpContourHead* head,
42 SkArenaAlloc* allocator SkDEBUGPARAMS(bool debugSkipAssert)
43 SkDEBUGPARAMS(const char* testName));
44
45 enum {
46 kMaxWindingTries = 10
47 };
48
49 bool allocatedOpSpan() const {
50 return fAllocatedOpSpan;
51 }
52
53 SkArenaAlloc* allocator() {
54 return fAllocator;
55 }
56
57 void bumpNested() {
58 ++fNested;
59 }
60
61 void clearNested() {
62 fNested = 0;
63 }
64
65 SkOpCoincidence* coincidence() {
66 return fCoincidence;
67 }
68
69 SkOpContourHead* contourHead() {
70 return fContourHead;
71 }
72
73#ifdef SK_DEBUG
74 const class SkOpAngle* debugAngle(int id) const;
75 const SkOpCoincidence* debugCoincidence() const;
76 SkOpContour* debugContour(int id) const;
77 const class SkOpPtT* debugPtT(int id) const;
78#endif
79
80 static bool DebugRunFail();
81
82#ifdef SK_DEBUG
83 const class SkOpSegment* debugSegment(int id) const;
84 bool debugSkipAssert() const { return fDebugSkipAssert; }
85 const class SkOpSpanBase* debugSpan(int id) const;
86 const char* debugTestName() const { return fDebugTestName; }
87#endif
88
89#if DEBUG_T_SECT_LOOP_COUNT
90 void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& ,
91 const SkIntersectionHelper& );
92 void debugDoYourWorst(SkOpGlobalState* );
93 void debugLoopReport();
94 void debugResetLoopCounts();
95#endif
96
97#if DEBUG_COINCIDENCE
98 void debugSetCheckHealth(bool check) { fDebugCheckHealth = check; }
99 bool debugCheckHealth() const { return fDebugCheckHealth; }
100#endif
101
102#if DEBUG_VALIDATE || DEBUG_COIN
103 void debugSetPhase(const char* funcName DEBUG_COIN_DECLARE_PARAMS()) const;
104#endif
105
106#if DEBUG_COIN
107 void debugAddToCoinChangedDict();
108 void debugAddToGlobalCoinDicts();
109 SkPathOpsDebug::CoinDict* debugCoinChangedDict() { return &fCoinChangedDict; }
110 const SkPathOpsDebug::CoinDictEntry& debugCoinDictEntry() const { return fCoinDictEntry; }
111
112 static void DumpCoinDict();
113#endif
114
115
116 int nested() const {
117 return fNested;
118 }
119
120#ifdef SK_DEBUG
121 int nextAngleID() {
122 return ++fAngleID;
123 }
124
125 int nextCoinID() {
126 return ++fCoinID;
127 }
128
129 int nextContourID() {
130 return ++fContourID;
131 }
132
133 int nextPtTID() {
134 return ++fPtTID;
135 }
136
137 int nextSegmentID() {
138 return ++fSegmentID;
139 }
140
141 int nextSpanID() {
142 return ++fSpanID;
143 }
144#endif
145
146 SkOpPhase phase() const {
147 return fPhase;
148 }
149
150 void resetAllocatedOpSpan() {
151 fAllocatedOpSpan = false;
152 }
153
154 void setAllocatedOpSpan() {
155 fAllocatedOpSpan = true;
156 }
157
158 void setCoincidence(SkOpCoincidence* coincidence) {
159 fCoincidence = coincidence;
160 }
161
162 void setContourHead(SkOpContourHead* contourHead) {
163 fContourHead = contourHead;
164 }
165
166 void setPhase(SkOpPhase phase) {
167 if (SkOpPhase::kNoChange == phase) {
168 return;
169 }
170 SkASSERT(fPhase != phase);
171 fPhase = phase;
172 }
173
174 // called in very rare cases where angles are sorted incorrectly -- signfies op will fail
175 void setWindingFailed() {
176 fWindingFailed = true;
177 }
178
179 bool windingFailed() const {
180 return fWindingFailed;
181 }
182
183private:
184 SkArenaAlloc* fAllocator;
185 SkOpCoincidence* fCoincidence;
186 SkOpContourHead* fContourHead;
187 int fNested;
188 bool fAllocatedOpSpan;
189 bool fWindingFailed;
190 SkOpPhase fPhase;
191#ifdef SK_DEBUG
192 const char* fDebugTestName;
193 void* fDebugReporter;
194 int fAngleID;
195 int fCoinID;
196 int fContourID;
197 int fPtTID;
198 int fSegmentID;
199 int fSpanID;
200 bool fDebugSkipAssert;
201#endif
202#if DEBUG_T_SECT_LOOP_COUNT
203 int fDebugLoopCount[3];
204 SkPath::Verb fDebugWorstVerb[6];
205 SkPoint fDebugWorstPts[24];
206 float fDebugWorstWeight[6];
207#endif
208#if DEBUG_COIN
209 SkPathOpsDebug::CoinDict fCoinChangedDict;
210 SkPathOpsDebug::CoinDict fCoinVisitedDict;
211 SkPathOpsDebug::CoinDictEntry fCoinDictEntry;
212 const char* fPreviousFuncName;
213#endif
214#if DEBUG_COINCIDENCE
215 bool fDebugCheckHealth;
216#endif
217};
218
219#ifdef SK_DEBUG
220#if DEBUG_COINCIDENCE
221#define SkOPASSERT(cond) SkASSERT((this->globalState() && \
222 (this->globalState()->debugCheckHealth() || \
223 this->globalState()->debugSkipAssert())) || (cond))
224#else
225#define SkOPASSERT(cond) SkASSERT((this->globalState() && \
226 this->globalState()->debugSkipAssert()) || (cond))
227#endif
228#define SkOPOBJASSERT(obj, cond) SkASSERT((obj->globalState() && \
229 obj->globalState()->debugSkipAssert()) || (cond))
230#else
231#define SkOPASSERT(cond)
232#define SkOPOBJASSERT(obj, cond)
233#endif
234
235// Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
236bool AlmostEqualUlps(float a, float b);
237inline bool AlmostEqualUlps(double a, double b) {
238 return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
239}
240
241bool AlmostEqualUlpsNoNormalCheck(float a, float b);
242inline bool AlmostEqualUlpsNoNormalCheck(double a, double b) {
243 return AlmostEqualUlpsNoNormalCheck(SkDoubleToScalar(a), SkDoubleToScalar(b));
244}
245
246bool AlmostEqualUlps_Pin(float a, float b);
247inline bool AlmostEqualUlps_Pin(double a, double b) {
248 return AlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b));
249}
250
251// Use Almost Dequal when comparing should not special case denormalized values.
252bool AlmostDequalUlps(float a, float b);
253bool AlmostDequalUlps(double a, double b);
254
255bool NotAlmostEqualUlps(float a, float b);
256inline bool NotAlmostEqualUlps(double a, double b) {
257 return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
258}
259
260bool NotAlmostEqualUlps_Pin(float a, float b);
261inline bool NotAlmostEqualUlps_Pin(double a, double b) {
262 return NotAlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b));
263}
264
265bool NotAlmostDequalUlps(float a, float b);
266inline bool NotAlmostDequalUlps(double a, double b) {
267 return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
268}
269
270// Use Almost Bequal when comparing coordinates in conjunction with between.
271bool AlmostBequalUlps(float a, float b);
272inline bool AlmostBequalUlps(double a, double b) {
273 return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
274}
275
276bool AlmostPequalUlps(float a, float b);
277inline bool AlmostPequalUlps(double a, double b) {
278 return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
279}
280
281bool RoughlyEqualUlps(float a, float b);
282inline bool RoughlyEqualUlps(double a, double b) {
283 return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
284}
285
286bool AlmostLessUlps(float a, float b);
287inline bool AlmostLessUlps(double a, double b) {
288 return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
289}
290
291bool AlmostLessOrEqualUlps(float a, float b);
292inline bool AlmostLessOrEqualUlps(double a, double b) {
293 return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
294}
295
296bool AlmostBetweenUlps(float a, float b, float c);
297inline bool AlmostBetweenUlps(double a, double b, double c) {
298 return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
299}
300
301int UlpsDistance(float a, float b);
302inline int UlpsDistance(double a, double b) {
303 return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b));
304}
305
306// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
307// DBL_EPSILON == 2.22045e-16
308const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
309const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
310const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
311const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16;
312const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
313// Use a compile-time constant for FLT_EPSILON_SQRT to avoid initializers.
314// A 17 digit constant guarantees exact results.
315const double FLT_EPSILON_SQRT = 0.00034526697709225118; // sqrt(FLT_EPSILON);
316const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
317const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error
318const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
319const double ROUGH_EPSILON = FLT_EPSILON * 64;
320const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
321const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048;
322const double BUMP_EPSILON = FLT_EPSILON * 4096;
323
324const SkScalar INVERSE_NUMBER_RANGE = FLT_EPSILON_ORDERABLE_ERR;
325
326inline bool zero_or_one(double x) {
327 return x == 0 || x == 1;
328}
329
330inline bool approximately_zero(double x) {
331 return fabs(x) < FLT_EPSILON;
332}
333
334inline bool precisely_zero(double x) {
335 return fabs(x) < DBL_EPSILON_ERR;
336}
337
338inline bool precisely_subdivide_zero(double x) {
339 return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
340}
341
342inline bool approximately_zero(float x) {
343 return fabs(x) < FLT_EPSILON;
344}
345
346inline bool approximately_zero_cubed(double x) {
347 return fabs(x) < FLT_EPSILON_CUBED;
348}
349
350inline bool approximately_zero_half(double x) {
351 return fabs(x) < FLT_EPSILON_HALF;
352}
353
354inline bool approximately_zero_double(double x) {
355 return fabs(x) < FLT_EPSILON_DOUBLE;
356}
357
358inline bool approximately_zero_orderable(double x) {
359 return fabs(x) < FLT_EPSILON_ORDERABLE_ERR;
360}
361
362inline bool approximately_zero_squared(double x) {
363 return fabs(x) < FLT_EPSILON_SQUARED;
364}
365
366inline bool approximately_zero_sqrt(double x) {
367 return fabs(x) < FLT_EPSILON_SQRT;
368}
369
370inline bool roughly_zero(double x) {
371 return fabs(x) < ROUGH_EPSILON;
372}
373
374inline bool approximately_zero_inverse(double x) {
375 return fabs(x) > FLT_EPSILON_INVERSE;
376}
377
378inline bool approximately_zero_when_compared_to(double x, double y) {
379 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
380}
381
382inline bool precisely_zero_when_compared_to(double x, double y) {
383 return x == 0 || fabs(x) < fabs(y * DBL_EPSILON);
384}
385
386inline bool roughly_zero_when_compared_to(double x, double y) {
387 return x == 0 || fabs(x) < fabs(y * ROUGH_EPSILON);
388}
389
390// Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
391// AlmostEqualUlps instead.
392inline bool approximately_equal(double x, double y) {
393 return approximately_zero(x - y);
394}
395
396inline bool precisely_equal(double x, double y) {
397 return precisely_zero(x - y);
398}
399
400inline bool precisely_subdivide_equal(double x, double y) {
401 return precisely_subdivide_zero(x - y);
402}
403
404inline bool approximately_equal_half(double x, double y) {
405 return approximately_zero_half(x - y);
406}
407
408inline bool approximately_equal_double(double x, double y) {
409 return approximately_zero_double(x - y);
410}
411
412inline bool approximately_equal_orderable(double x, double y) {
413 return approximately_zero_orderable(x - y);
414}
415
416inline bool approximately_equal_squared(double x, double y) {
417 return approximately_equal(x, y);
418}
419
420inline bool approximately_greater(double x, double y) {
421 return x - FLT_EPSILON >= y;
422}
423
424inline bool approximately_greater_double(double x, double y) {
425 return x - FLT_EPSILON_DOUBLE >= y;
426}
427
428inline bool approximately_greater_orderable(double x, double y) {
429 return x - FLT_EPSILON_ORDERABLE_ERR >= y;
430}
431
432inline bool approximately_greater_or_equal(double x, double y) {
433 return x + FLT_EPSILON > y;
434}
435
436inline bool approximately_greater_or_equal_double(double x, double y) {
437 return x + FLT_EPSILON_DOUBLE > y;
438}
439
440inline bool approximately_greater_or_equal_orderable(double x, double y) {
441 return x + FLT_EPSILON_ORDERABLE_ERR > y;
442}
443
444inline bool approximately_lesser(double x, double y) {
445 return x + FLT_EPSILON <= y;
446}
447
448inline bool approximately_lesser_double(double x, double y) {
449 return x + FLT_EPSILON_DOUBLE <= y;
450}
451
452inline bool approximately_lesser_orderable(double x, double y) {
453 return x + FLT_EPSILON_ORDERABLE_ERR <= y;
454}
455
456inline bool approximately_lesser_or_equal(double x, double y) {
457 return x - FLT_EPSILON < y;
458}
459
460inline bool approximately_lesser_or_equal_double(double x, double y) {
461 return x - FLT_EPSILON_DOUBLE < y;
462}
463
464inline bool approximately_lesser_or_equal_orderable(double x, double y) {
465 return x - FLT_EPSILON_ORDERABLE_ERR < y;
466}
467
468inline bool approximately_greater_than_one(double x) {
469 return x > 1 - FLT_EPSILON;
470}
471
472inline bool precisely_greater_than_one(double x) {
473 return x > 1 - DBL_EPSILON_ERR;
474}
475
476inline bool approximately_less_than_zero(double x) {
477 return x < FLT_EPSILON;
478}
479
480inline bool precisely_less_than_zero(double x) {
481 return x < DBL_EPSILON_ERR;
482}
483
484inline bool approximately_negative(double x) {
485 return x < FLT_EPSILON;
486}
487
488inline bool approximately_negative_orderable(double x) {
489 return x < FLT_EPSILON_ORDERABLE_ERR;
490}
491
492inline bool precisely_negative(double x) {
493 return x < DBL_EPSILON_ERR;
494}
495
496inline bool approximately_one_or_less(double x) {
497 return x < 1 + FLT_EPSILON;
498}
499
500inline bool approximately_one_or_less_double(double x) {
501 return x < 1 + FLT_EPSILON_DOUBLE;
502}
503
504inline bool approximately_positive(double x) {
505 return x > -FLT_EPSILON;
506}
507
508inline bool approximately_positive_squared(double x) {
509 return x > -(FLT_EPSILON_SQUARED);
510}
511
512inline bool approximately_zero_or_more(double x) {
513 return x > -FLT_EPSILON;
514}
515
516inline bool approximately_zero_or_more_double(double x) {
517 return x > -FLT_EPSILON_DOUBLE;
518}
519
520inline bool approximately_between_orderable(double a, double b, double c) {
521 return a <= c
522 ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c)
523 : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b);
524}
525
526inline bool approximately_between(double a, double b, double c) {
527 return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
528 : approximately_negative(b - a) && approximately_negative(c - b);
529}
530
531inline bool precisely_between(double a, double b, double c) {
532 return a <= c ? precisely_negative(a - b) && precisely_negative(b - c)
533 : precisely_negative(b - a) && precisely_negative(c - b);
534}
535
536// returns true if (a <= b <= c) || (a >= b >= c)
537inline bool between(double a, double b, double c) {
538 SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
539 || (precisely_zero(a) && precisely_zero(b) && precisely_zero(c)));
540 return (a - b) * (c - b) <= 0;
541}
542
543inline bool roughly_equal(double x, double y) {
544 return fabs(x - y) < ROUGH_EPSILON;
545}
546
547inline bool roughly_negative(double x) {
548 return x < ROUGH_EPSILON;
549}
550
551inline bool roughly_between(double a, double b, double c) {
552 return a <= c ? roughly_negative(a - b) && roughly_negative(b - c)
553 : roughly_negative(b - a) && roughly_negative(c - b);
554}
555
556inline bool more_roughly_equal(double x, double y) {
557 return fabs(x - y) < MORE_ROUGH_EPSILON;
558}
559
560struct SkDPoint;
561struct SkDVector;
562struct SkDLine;
563struct SkDQuad;
564struct SkDConic;
565struct SkDCubic;
566struct SkDRect;
567
568inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
569 int verb = (1 << points) >> 1;
570#ifdef SK_DEBUG
571 switch (points) {
572 case 0: SkASSERT(SkPath::kMove_Verb == verb); break;
573 case 1: SkASSERT(SkPath::kLine_Verb == verb); break;
574 case 2: SkASSERT(SkPath::kQuad_Verb == verb); break;
575 case 3: SkASSERT(SkPath::kCubic_Verb == verb); break;
576 default: SkDEBUGFAIL("should not be here");
577 }
578#endif
579 return (SkPath::Verb)verb;
580}
581
582inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
583 int points = (int) verb - (((int) verb + 1) >> 2);
584#ifdef SK_DEBUG
585 switch (verb) {
586 case SkPath::kLine_Verb: SkASSERT(1 == points); break;
587 case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
588 case SkPath::kConic_Verb: SkASSERT(2 == points); break;
589 case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
590 default: SkDEBUGFAIL("should not get here");
591 }
592#endif
593 return points;
594}
595
596inline double SkDInterp(double A, double B, double t) {
597 return A + (B - A) * t;
598}
599
600double SkDCubeRoot(double x);
601
602/* Returns -1 if negative, 0 if zero, 1 if positive
603*/
604inline int SkDSign(double x) {
605 return (x > 0) - (x < 0);
606}
607
608/* Returns 0 if negative, 1 if zero, 2 if positive
609*/
610inline int SKDSide(double x) {
611 return (x > 0) + (x >= 0);
612}
613
614/* Returns 1 if negative, 2 if zero, 4 if positive
615*/
616inline int SkDSideBit(double x) {
617 return 1 << SKDSide(x);
618}
619
620inline double SkPinT(double t) {
621 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
622}
623
624#endif
625