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