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 "SkFloatingPoint.h"
13#include "SkPath.h"
14#include "SkPathOps.h"
15#include "SkPathOpsDebug.h"
16#include "SkSafe_math.h"  // for fabs, sqrt
17#include "SkScalar.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