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