SkPathOpsTypes.h revision 65f553182ab7069378ef863d30094d0327f178d0 
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
144#if 0  // unused for now
145inline bool way_roughly_zero(double x) {
146    return fabs(x) < WAY_ROUGH_EPSILON;
147}
148#endif
149
150inline bool approximately_zero_inverse(double x) {
151    return fabs(x) > FLT_EPSILON_INVERSE;
152}
153
154// OPTIMIZATION: if called multiple times with the same denom, we want to pass 1/y instead
155inline bool approximately_zero_when_compared_to(double x, double y) {
156    return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
157}
158
159// Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
160// AlmostEqualUlps instead.
161inline bool approximately_equal(double x, double y) {
162    return approximately_zero(x - y);
163}
164
165inline bool precisely_equal(double x, double y) {
166    return precisely_zero(x - y);
167}
168
169inline bool precisely_subdivide_equal(double x, double y) {
170    return precisely_subdivide_zero(x - y);
171}
172
173inline bool approximately_equal_half(double x, double y) {
174    return approximately_zero_half(x - y);
175}
176
177inline bool approximately_equal_double(double x, double y) {
178    return approximately_zero_double(x - y);
179}
180
181inline bool approximately_equal_orderable(double x, double y) {
182    return approximately_zero_orderable(x - y);
183}
184
185inline bool approximately_equal_squared(double x, double y) {
186    return approximately_equal(x, y);
187}
188
189inline bool approximately_greater(double x, double y) {
190    return x - FLT_EPSILON >= y;
191}
192
193inline bool approximately_greater_double(double x, double y) {
194    return x - FLT_EPSILON_DOUBLE >= y;
195}
196
197inline bool approximately_greater_orderable(double x, double y) {
198    return x - FLT_EPSILON_ORDERABLE_ERR >= y;
199}
200
201inline bool approximately_greater_or_equal(double x, double y) {
202    return x + FLT_EPSILON > y;
203}
204
205inline bool approximately_greater_or_equal_double(double x, double y) {
206    return x + FLT_EPSILON_DOUBLE > y;
207}
208
209inline bool approximately_greater_or_equal_orderable(double x, double y) {
210    return x + FLT_EPSILON_ORDERABLE_ERR > y;
211}
212
213inline bool approximately_lesser(double x, double y) {
214    return x + FLT_EPSILON <= y;
215}
216
217inline bool approximately_lesser_double(double x, double y) {
218    return x + FLT_EPSILON_DOUBLE <= y;
219}
220
221inline bool approximately_lesser_orderable(double x, double y) {
222    return x + FLT_EPSILON_ORDERABLE_ERR <= y;
223}
224
225inline bool approximately_lesser_or_equal(double x, double y) {
226    return x - FLT_EPSILON < y;
227}
228
229inline bool approximately_lesser_or_equal_double(double x, double y) {
230    return x - FLT_EPSILON_DOUBLE < y;
231}
232
233inline bool approximately_lesser_or_equal_orderable(double x, double y) {
234    return x - FLT_EPSILON_ORDERABLE_ERR < y;
235}
236
237inline bool approximately_greater_than_one(double x) {
238    return x > 1 - FLT_EPSILON;
239}
240
241inline bool precisely_greater_than_one(double x) {
242    return x > 1 - DBL_EPSILON_ERR;
243}
244
245inline bool approximately_less_than_zero(double x) {
246    return x < FLT_EPSILON;
247}
248
249inline bool precisely_less_than_zero(double x) {
250    return x < DBL_EPSILON_ERR;
251}
252
253inline bool approximately_negative(double x) {
254    return x < FLT_EPSILON;
255}
256
257inline bool approximately_negative_orderable(double x) {
258    return x < FLT_EPSILON_ORDERABLE_ERR;
259}
260
261inline bool precisely_negative(double x) {
262    return x < DBL_EPSILON_ERR;
263}
264
265inline bool approximately_one_or_less(double x) {
266    return x < 1 + FLT_EPSILON;
267}
268
269inline bool approximately_one_or_less_double(double x) {
270    return x < 1 + FLT_EPSILON_DOUBLE;
271}
272
273inline bool approximately_positive(double x) {
274    return x > -FLT_EPSILON;
275}
276
277inline bool approximately_positive_squared(double x) {
278    return x > -(FLT_EPSILON_SQUARED);
279}
280
281inline bool approximately_zero_or_more(double x) {
282    return x > -FLT_EPSILON;
283}
284
285inline bool approximately_zero_or_more_double(double x) {
286    return x > -FLT_EPSILON_DOUBLE;
287}
288
289inline bool approximately_between_orderable(double a, double b, double c) {
290    return a <= c
291            ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c)
292            : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b);
293}
294
295inline bool approximately_between(double a, double b, double c) {
296    return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
297            : approximately_negative(b - a) && approximately_negative(c - b);
298}
299
300inline bool precisely_between(double a, double b, double c) {
301    return a <= c ? precisely_negative(a - b) && precisely_negative(b - c)
302            : precisely_negative(b - a) && precisely_negative(c - b);
303}
304
305// returns true if (a <= b <= c) || (a >= b >= c)
306inline bool between(double a, double b, double c) {
307    SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0));
308    return (a - b) * (c - b) <= 0;
309}
310
311inline bool roughly_equal(double x, double y) {
312    return fabs(x - y) < ROUGH_EPSILON;
313}
314
315inline bool more_roughly_equal(double x, double y) {
316    return fabs(x - y) < MORE_ROUGH_EPSILON;
317}
318
319inline bool way_roughly_equal(double x, double y) {
320    return fabs(x - y) < WAY_ROUGH_EPSILON;
321}
322
323struct SkDPoint;
324struct SkDVector;
325struct SkDLine;
326struct SkDQuad;
327struct SkDTriangle;
328struct SkDCubic;
329struct SkDRect;
330
331inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
332    int verb = (1 << points) >> 1;
333#ifdef SK_DEBUG
334    switch (points) {
335        case 0: SkASSERT(SkPath::kMove_Verb == verb); break;
336        case 1: SkASSERT(SkPath::kLine_Verb == verb); break;
337        case 2: SkASSERT(SkPath::kQuad_Verb == verb); break;
338        case 3: SkASSERT(SkPath::kCubic_Verb == verb); break;
339        default: SkDEBUGFAIL("should not be here");
340    }
341#endif
342    return (SkPath::Verb)verb;
343}
344
345inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
346    int points = (int) verb - ((int) verb >> 2);
347#ifdef SK_DEBUG
348    switch (verb) {
349        case SkPath::kLine_Verb: SkASSERT(1 == points); break;
350        case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
351        case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
352        default: SkDEBUGFAIL("should not get here");
353    }
354#endif
355    return points;
356}
357
358inline double SkDInterp(double A, double B, double t) {
359    return A + (B - A) * t;
360}
361
362double SkDCubeRoot(double x);
363
364/* Returns -1 if negative, 0 if zero, 1 if positive
365*/
366inline int SkDSign(double x) {
367    return (x > 0) - (x < 0);
368}
369
370/* Returns 0 if negative, 1 if zero, 2 if positive
371*/
372inline int SKDSide(double x) {
373    return (x > 0) + (x >= 0);
374}
375
376/* Returns 1 if negative, 2 if zero, 4 if positive
377*/
378inline int SkDSideBit(double x) {
379    return 1 << SKDSide(x);
380}
381
382inline double SkPinT(double t) {
383    return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
384}
385
386#endif
387