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