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
25// Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
26bool AlmostEqualUlps(float a, float b);
27inline bool AlmostEqualUlps(double a, double b) {
28    return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
29}
30
31// Use Almost Dequal when comparing should not special case denormalized values.
32bool AlmostDequalUlps(float a, float b);
33inline bool AlmostDequalUlps(double a, double b) {
34    return AlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
35}
36
37bool NotAlmostEqualUlps(float a, float b);
38inline bool NotAlmostEqualUlps(double a, double b) {
39    return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
40}
41
42bool NotAlmostDequalUlps(float a, float b);
43inline bool NotAlmostDequalUlps(double a, double b) {
44    return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
45}
46
47// Use Almost Bequal when comparing coordinates in conjunction with between.
48bool AlmostBequalUlps(float a, float b);
49inline bool AlmostBequalUlps(double a, double b) {
50    return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
51}
52
53bool AlmostPequalUlps(float a, float b);
54inline bool AlmostPequalUlps(double a, double b) {
55    return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
56}
57
58bool RoughlyEqualUlps(float a, float b);
59inline bool RoughlyEqualUlps(double a, double b) {
60    return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
61}
62
63bool AlmostLessUlps(float a, float b);
64inline bool AlmostLessUlps(double a, double b) {
65    return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
66}
67
68bool AlmostLessOrEqualUlps(float a, float b);
69inline bool AlmostLessOrEqualUlps(double a, double b) {
70    return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
71}
72
73bool AlmostBetweenUlps(float a, float b, float c);
74inline bool AlmostBetweenUlps(double a, double b, double c) {
75    return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
76}
77
78int UlpsDistance(float a, float b);
79inline int UlpsDistance(double a, double b) {
80    return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b));
81}
82
83// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
84// DBL_EPSILON == 2.22045e-16
85const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
86const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
87const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
88const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
89const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
90const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
91const double DBL_EPSILON_ERR = DBL_EPSILON * 4;  // FIXME: tune -- allow a few bits of error
92const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
93const double ROUGH_EPSILON = FLT_EPSILON * 64;
94const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
95
96inline bool approximately_zero(double x) {
97    return fabs(x) < FLT_EPSILON;
98}
99
100inline bool precisely_zero(double x) {
101    return fabs(x) < DBL_EPSILON_ERR;
102}
103
104inline bool precisely_subdivide_zero(double x) {
105    return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
106}
107
108inline bool approximately_zero(float x) {
109    return fabs(x) < FLT_EPSILON;
110}
111
112inline bool approximately_zero_cubed(double x) {
113    return fabs(x) < FLT_EPSILON_CUBED;
114}
115
116inline bool approximately_zero_half(double x) {
117    return fabs(x) < FLT_EPSILON_HALF;
118}
119
120inline bool approximately_zero_double(double x) {
121    return fabs(x) < FLT_EPSILON_DOUBLE;
122}
123
124inline bool approximately_zero_squared(double x) {
125    return fabs(x) < FLT_EPSILON_SQUARED;
126}
127
128inline bool approximately_zero_sqrt(double x) {
129    return fabs(x) < FLT_EPSILON_SQRT;
130}
131
132inline bool roughly_zero(double x) {
133    return fabs(x) < ROUGH_EPSILON;
134}
135
136inline bool approximately_zero_inverse(double x) {
137    return fabs(x) > FLT_EPSILON_INVERSE;
138}
139
140// OPTIMIZATION: if called multiple times with the same denom, we want to pass 1/y instead
141inline bool approximately_zero_when_compared_to(double x, double y) {
142    return x == 0 || fabs(x / y) < FLT_EPSILON;
143}
144
145// Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
146// AlmostEqualUlps instead.
147inline bool approximately_equal(double x, double y) {
148    return approximately_zero(x - y);
149}
150
151inline bool precisely_equal(double x, double y) {
152    return precisely_zero(x - y);
153}
154
155inline bool precisely_subdivide_equal(double x, double y) {
156    return precisely_subdivide_zero(x - y);
157}
158
159inline bool approximately_equal_half(double x, double y) {
160    return approximately_zero_half(x - y);
161}
162
163inline bool approximately_equal_double(double x, double y) {
164    return approximately_zero_double(x - y);
165}
166
167inline bool approximately_equal_squared(double x, double y) {
168    return approximately_equal(x, y);
169}
170
171inline bool approximately_greater(double x, double y) {
172    return x - FLT_EPSILON >= y;
173}
174
175inline bool approximately_greater_or_equal(double x, double y) {
176    return x + FLT_EPSILON > y;
177}
178
179inline bool approximately_lesser(double x, double y) {
180    return x + FLT_EPSILON <= y;
181}
182
183inline bool approximately_lesser_or_equal(double x, double y) {
184    return x - FLT_EPSILON < y;
185}
186
187inline bool approximately_greater_than_one(double x) {
188    return x > 1 - FLT_EPSILON;
189}
190
191inline bool precisely_greater_than_one(double x) {
192    return x > 1 - DBL_EPSILON_ERR;
193}
194
195inline bool approximately_less_than_zero(double x) {
196    return x < FLT_EPSILON;
197}
198
199inline bool precisely_less_than_zero(double x) {
200    return x < DBL_EPSILON_ERR;
201}
202
203inline bool approximately_negative(double x) {
204    return x < FLT_EPSILON;
205}
206
207inline bool precisely_negative(double x) {
208    return x < DBL_EPSILON_ERR;
209}
210
211inline bool approximately_one_or_less(double x) {
212    return x < 1 + FLT_EPSILON;
213}
214
215inline bool approximately_positive(double x) {
216    return x > -FLT_EPSILON;
217}
218
219inline bool approximately_positive_squared(double x) {
220    return x > -(FLT_EPSILON_SQUARED);
221}
222
223inline bool approximately_zero_or_more(double x) {
224    return x > -FLT_EPSILON;
225}
226
227inline bool approximately_between(double a, double b, double c) {
228    return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
229            : approximately_negative(b - a) && approximately_negative(c - b);
230}
231
232inline bool precisely_between(double a, double b, double c) {
233    return a <= c ? precisely_negative(a - b) && precisely_negative(b - c)
234            : precisely_negative(b - a) && precisely_negative(c - b);
235}
236
237// returns true if (a <= b <= c) || (a >= b >= c)
238inline bool between(double a, double b, double c) {
239    SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0));
240    return (a - b) * (c - b) <= 0;
241}
242
243inline bool more_roughly_equal(double x, double y) {
244    return fabs(x - y) < MORE_ROUGH_EPSILON;
245}
246
247inline bool roughly_equal(double x, double y) {
248    return fabs(x - y) < ROUGH_EPSILON;
249}
250
251struct SkDPoint;
252struct SkDVector;
253struct SkDLine;
254struct SkDQuad;
255struct SkDTriangle;
256struct SkDCubic;
257struct SkDRect;
258
259inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
260    int verb = (1 << points) >> 1;
261#ifdef SK_DEBUG
262    switch (points) {
263        case 0: SkASSERT(SkPath::kMove_Verb == verb); break;
264        case 1: SkASSERT(SkPath::kLine_Verb == verb); break;
265        case 2: SkASSERT(SkPath::kQuad_Verb == verb); break;
266        case 3: SkASSERT(SkPath::kCubic_Verb == verb); break;
267        default: SkDEBUGFAIL("should not be here");
268    }
269#endif
270    return (SkPath::Verb)verb;
271}
272
273inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
274    int points = (int) verb - ((int) verb >> 2);
275#ifdef SK_DEBUG
276    switch (verb) {
277        case SkPath::kLine_Verb: SkASSERT(1 == points); break;
278        case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
279        case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
280        default: SkDEBUGFAIL("should not get here");
281    }
282#endif
283    return points;
284}
285
286inline double SkDInterp(double A, double B, double t) {
287    return A + (B - A) * t;
288}
289
290double SkDCubeRoot(double x);
291
292/* Returns -1 if negative, 0 if zero, 1 if positive
293*/
294inline int SkDSign(double x) {
295    return (x > 0) - (x < 0);
296}
297
298/* Returns 0 if negative, 1 if zero, 2 if positive
299*/
300inline int SKDSide(double x) {
301    return (x > 0) + (x >= 0);
302}
303
304/* Returns 1 if negative, 2 if zero, 4 if positive
305*/
306inline int SkDSideBit(double x) {
307    return 1 << SKDSide(x);
308}
309
310inline double SkPinT(double t) {
311    return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
312}
313
314#ifdef SK_DEBUG
315inline void DebugDumpDouble(double x) {
316    if (x == floor(x)) {
317        SkDebugf("%.0f", x);
318    } else {
319        SkDebugf("%1.17g", x);
320    }
321}
322
323inline void DebugDumpFloat(float x) {
324    if (x == floorf(x)) {
325        SkDebugf("%.0f", x);
326    } else {
327        SkDebugf("%1.9gf", x);
328    }
329}
330#endif
331
332#endif
333