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 SkPathOpsCurve_DEFINE
8#define SkPathOpsCurve_DEFINE
9
10#include "SkIntersections.h"
11
12#ifndef SK_RELEASE
13#include "SkPath.h"
14#endif
15
16struct SkPathOpsBounds;
17
18struct SkOpCurve {
19    SkPoint fPts[4];
20    SkScalar fWeight;
21    SkDEBUGCODE(SkPath::Verb fVerb);
22
23    const SkPoint& operator[](int n) const {
24        SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
25        return fPts[n];
26    }
27
28    void dump() const;
29
30    void set(const SkDQuad& quad) {
31        for (int index = 0; index < SkDQuad::kPointCount; ++index) {
32            fPts[index] = quad[index].asSkPoint();
33        }
34        SkDEBUGCODE(fWeight = 1);
35        SkDEBUGCODE(fVerb = SkPath::kQuad_Verb);
36    }
37
38    void set(const SkDCubic& cubic) {
39        for (int index = 0; index < SkDCubic::kPointCount; ++index) {
40            fPts[index] = cubic[index].asSkPoint();
41        }
42        SkDEBUGCODE(fWeight = 1);
43        SkDEBUGCODE(fVerb = SkPath::kCubic_Verb);
44    }
45
46};
47
48struct SkDCurve {
49    union {
50        SkDLine fLine;
51        SkDQuad fQuad;
52        SkDConic fConic;
53        SkDCubic fCubic;
54    };
55    SkDEBUGCODE(SkPath::Verb fVerb);
56
57    const SkDPoint& operator[](int n) const {
58        SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
59        return fCubic[n];
60    }
61
62    SkDPoint& operator[](int n) {
63        SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
64        return fCubic[n];
65    }
66
67    SkDPoint conicTop(const SkPoint curve[3], SkScalar curveWeight,
68                      double s, double e, double* topT);
69    SkDPoint cubicTop(const SkPoint curve[4], SkScalar , double s, double e, double* topT);
70    void dump() const;
71    void dumpID(int ) const;
72    SkDPoint lineTop(const SkPoint[2], SkScalar , double , double , double* topT);
73    double nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const;
74    void offset(SkPath::Verb verb, const SkDVector& );
75    SkDPoint quadTop(const SkPoint curve[3], SkScalar , double s, double e, double* topT);
76
77    void setConicBounds(const SkPoint curve[3], SkScalar curveWeight,
78                        double s, double e, SkPathOpsBounds* );
79    void setCubicBounds(const SkPoint curve[4], SkScalar ,
80                        double s, double e, SkPathOpsBounds* );
81    void setQuadBounds(const SkPoint curve[3], SkScalar ,
82                       double s, double e, SkPathOpsBounds*);
83};
84
85class SkDCurveSweep {
86public:
87    bool isCurve() const { return fIsCurve; }
88    bool isOrdered() const { return fOrdered; }
89    void setCurveHullSweep(SkPath::Verb verb);
90
91    SkDCurve fCurve;
92    SkDVector fSweep[2];
93private:
94    bool fIsCurve;
95    bool fOrdered;  // cleared when a cubic's control point isn't between the sweep vectors
96
97};
98
99extern SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar cWeight,
100    double tStart, double tEnd, double* topT);
101
102static SkDPoint dline_xy_at_t(const SkPoint a[2], SkScalar , double t) {
103    SkDLine line;
104    line.set(a);
105    return line.ptAtT(t);
106}
107
108static SkDPoint dquad_xy_at_t(const SkPoint a[3], SkScalar , double t) {
109    SkDQuad quad;
110    quad.set(a);
111    return quad.ptAtT(t);
112}
113
114static SkDPoint dconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
115    SkDConic conic;
116    conic.set(a, weight);
117    return conic.ptAtT(t);
118}
119
120static SkDPoint dcubic_xy_at_t(const SkPoint a[4], SkScalar , double t) {
121    SkDCubic cubic;
122    cubic.set(a);
123    return cubic.ptAtT(t);
124}
125
126static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], SkScalar , double ) = {
127    nullptr,
128    dline_xy_at_t,
129    dquad_xy_at_t,
130    dconic_xy_at_t,
131    dcubic_xy_at_t
132};
133
134static SkDPoint ddline_xy_at_t(const SkDCurve& c, double t) {
135    return c.fLine.ptAtT(t);
136}
137
138static SkDPoint ddquad_xy_at_t(const SkDCurve& c, double t) {
139    return c.fQuad.ptAtT(t);
140}
141
142static SkDPoint ddconic_xy_at_t(const SkDCurve& c, double t) {
143    return c.fConic.ptAtT(t);
144}
145
146static SkDPoint ddcubic_xy_at_t(const SkDCurve& c, double t) {
147    return c.fCubic.ptAtT(t);
148}
149
150static SkDPoint (* const CurveDDPointAtT[])(const SkDCurve& , double ) = {
151    nullptr,
152    ddline_xy_at_t,
153    ddquad_xy_at_t,
154    ddconic_xy_at_t,
155    ddcubic_xy_at_t
156};
157
158static SkPoint fline_xy_at_t(const SkPoint a[2], SkScalar weight, double t) {
159    return dline_xy_at_t(a, weight, t).asSkPoint();
160}
161
162static SkPoint fquad_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
163    return dquad_xy_at_t(a, weight, t).asSkPoint();
164}
165
166static SkPoint fconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
167    return dconic_xy_at_t(a, weight, t).asSkPoint();
168}
169
170static SkPoint fcubic_xy_at_t(const SkPoint a[4], SkScalar weight, double t) {
171    return dcubic_xy_at_t(a, weight, t).asSkPoint();
172}
173
174static SkPoint (* const CurvePointAtT[])(const SkPoint[], SkScalar , double ) = {
175    nullptr,
176    fline_xy_at_t,
177    fquad_xy_at_t,
178    fconic_xy_at_t,
179    fcubic_xy_at_t
180};
181
182static SkDVector dline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
183    SkDLine line;
184    line.set(a);
185    return line[1] - line[0];
186}
187
188static SkDVector dquad_dxdy_at_t(const SkPoint a[3], SkScalar , double t) {
189    SkDQuad quad;
190    quad.set(a);
191    return quad.dxdyAtT(t);
192}
193
194static SkDVector dconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
195    SkDConic conic;
196    conic.set(a, weight);
197    return conic.dxdyAtT(t);
198}
199
200static SkDVector dcubic_dxdy_at_t(const SkPoint a[4], SkScalar , double t) {
201    SkDCubic cubic;
202    cubic.set(a);
203    return cubic.dxdyAtT(t);
204}
205
206static SkDVector (* const CurveDSlopeAtT[])(const SkPoint[], SkScalar , double ) = {
207    nullptr,
208    dline_dxdy_at_t,
209    dquad_dxdy_at_t,
210    dconic_dxdy_at_t,
211    dcubic_dxdy_at_t
212};
213
214static SkDVector ddline_dxdy_at_t(const SkDCurve& c, double ) {
215    return c.fLine.fPts[1] - c.fLine.fPts[0];
216}
217
218static SkDVector ddquad_dxdy_at_t(const SkDCurve& c, double t) {
219    return c.fQuad.dxdyAtT(t);
220}
221
222static SkDVector ddconic_dxdy_at_t(const SkDCurve& c, double t) {
223    return c.fConic.dxdyAtT(t);
224}
225
226static SkDVector ddcubic_dxdy_at_t(const SkDCurve& c, double t) {
227    return c.fCubic.dxdyAtT(t);
228}
229
230static SkDVector (* const CurveDDSlopeAtT[])(const SkDCurve& , double ) = {
231    nullptr,
232    ddline_dxdy_at_t,
233    ddquad_dxdy_at_t,
234    ddconic_dxdy_at_t,
235    ddcubic_dxdy_at_t
236};
237
238static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
239    return a[1] - a[0];
240}
241
242static SkVector fquad_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
243    return dquad_dxdy_at_t(a, weight, t).asSkVector();
244}
245
246static SkVector fconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
247    return dconic_dxdy_at_t(a, weight, t).asSkVector();
248}
249
250static SkVector fcubic_dxdy_at_t(const SkPoint a[4], SkScalar weight, double t) {
251    return dcubic_dxdy_at_t(a, weight, t).asSkVector();
252}
253
254static SkVector (* const CurveSlopeAtT[])(const SkPoint[], SkScalar , double ) = {
255    nullptr,
256    fline_dxdy_at_t,
257    fquad_dxdy_at_t,
258    fconic_dxdy_at_t,
259    fcubic_dxdy_at_t
260};
261
262static bool line_is_vertical(const SkPoint a[2], SkScalar , double startT, double endT) {
263    SkDLine line;
264    line.set(a);
265    SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) };
266    return AlmostEqualUlps(dst[0].fX, dst[1].fX);
267}
268
269static bool quad_is_vertical(const SkPoint a[3], SkScalar , double startT, double endT) {
270    SkDQuad quad;
271    quad.set(a);
272    SkDQuad dst = quad.subDivide(startT, endT);
273    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
274}
275
276static bool conic_is_vertical(const SkPoint a[3], SkScalar weight, double startT, double endT) {
277    SkDConic conic;
278    conic.set(a, weight);
279    SkDConic dst = conic.subDivide(startT, endT);
280    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
281}
282
283static bool cubic_is_vertical(const SkPoint a[4], SkScalar , double startT, double endT) {
284    SkDCubic cubic;
285    cubic.set(a);
286    SkDCubic dst = cubic.subDivide(startT, endT);
287    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX)
288            && AlmostEqualUlps(dst[2].fX, dst[3].fX);
289}
290
291static bool (* const CurveIsVertical[])(const SkPoint[], SkScalar , double , double) = {
292    nullptr,
293    line_is_vertical,
294    quad_is_vertical,
295    conic_is_vertical,
296    cubic_is_vertical
297};
298
299static void line_intersect_ray(const SkPoint a[2], SkScalar , const SkDLine& ray,
300        SkIntersections* i) {
301    SkDLine line;
302    line.set(a);
303    i->intersectRay(line, ray);
304}
305
306static void quad_intersect_ray(const SkPoint a[3], SkScalar , const SkDLine& ray,
307        SkIntersections* i) {
308    SkDQuad quad;
309    quad.set(a);
310    i->intersectRay(quad, ray);
311}
312
313static void conic_intersect_ray(const SkPoint a[3], SkScalar weight, const SkDLine& ray,
314        SkIntersections* i) {
315    SkDConic conic;
316    conic.set(a, weight);
317    i->intersectRay(conic, ray);
318}
319
320static void cubic_intersect_ray(const SkPoint a[4], SkScalar , const SkDLine& ray,
321        SkIntersections* i) {
322    SkDCubic cubic;
323    cubic.set(a);
324    i->intersectRay(cubic, ray);
325}
326
327static void (* const CurveIntersectRay[])(const SkPoint[] , SkScalar , const SkDLine& ,
328        SkIntersections* ) = {
329    nullptr,
330    line_intersect_ray,
331    quad_intersect_ray,
332    conic_intersect_ray,
333    cubic_intersect_ray
334};
335
336static void dline_intersect_ray(const SkDCurve& c, const SkDLine& ray,  SkIntersections* i) {
337    i->intersectRay(c.fLine, ray);
338}
339
340static void dquad_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
341    i->intersectRay(c.fQuad, ray);
342}
343
344static void dconic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
345    i->intersectRay(c.fConic, ray);
346}
347
348static void dcubic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
349    i->intersectRay(c.fCubic, ray);
350}
351
352static void (* const CurveDIntersectRay[])(const SkDCurve& , const SkDLine& , SkIntersections* ) = {
353    nullptr,
354    dline_intersect_ray,
355    dquad_intersect_ray,
356    dconic_intersect_ray,
357    dcubic_intersect_ray
358};
359
360static int line_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
361    SkDLine line;
362    roots[0] = SkIntersections::HorizontalIntercept(line.set(a), y);
363    return between(0, roots[0], 1);
364}
365
366static int line_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
367    SkDLine line;
368    roots[0] = SkIntersections::VerticalIntercept(line.set(a), x);
369    return between(0, roots[0], 1);
370}
371
372static int quad_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
373    SkDQuad quad;
374    return SkIntersections::HorizontalIntercept(quad.set(a), y, roots);
375}
376
377static int quad_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
378    SkDQuad quad;
379    return SkIntersections::VerticalIntercept(quad.set(a), x, roots);
380}
381
382static int conic_intercept_h(const SkPoint a[2], SkScalar w, SkScalar y, double* roots) {
383    SkDConic conic;
384    return SkIntersections::HorizontalIntercept(conic.set(a, w), y, roots);
385}
386
387static int conic_intercept_v(const SkPoint a[2], SkScalar w, SkScalar x, double* roots) {
388    SkDConic conic;
389    return SkIntersections::VerticalIntercept(conic.set(a, w), x, roots);
390}
391
392static int cubic_intercept_h(const SkPoint a[3], SkScalar , SkScalar y, double* roots) {
393    SkDCubic cubic;
394    return cubic.set(a).horizontalIntersect(y, roots);
395}
396
397static int cubic_intercept_v(const SkPoint a[3], SkScalar , SkScalar x, double* roots) {
398    SkDCubic cubic;
399    return cubic.set(a).verticalIntersect(x, roots);
400}
401
402static int (* const CurveIntercept[])(const SkPoint[] , SkScalar , SkScalar , double* ) = {
403    nullptr,
404    nullptr,
405    line_intercept_h,
406    line_intercept_v,
407    quad_intercept_h,
408    quad_intercept_v,
409    conic_intercept_h,
410    conic_intercept_v,
411    cubic_intercept_h,
412    cubic_intercept_v,
413};
414
415#endif
416