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 "src/pathops/SkIntersections.h"
11
12#ifndef SK_RELEASE
13#include "include/core/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 if (a[0].fY == a[1].fY) {
362 return false;
363 }
364 SkDLine line;
365 roots[0] = SkIntersections::HorizontalIntercept(line.set(a), y);
366 return between(0, roots[0], 1);
367}
368
369static int line_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
370 if (a[0].fX == a[1].fX) {
371 return false;
372 }
373 SkDLine line;
374 roots[0] = SkIntersections::VerticalIntercept(line.set(a), x);
375 return between(0, roots[0], 1);
376}
377
378static int quad_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
379 SkDQuad quad;
380 return SkIntersections::HorizontalIntercept(quad.set(a), y, roots);
381}
382
383static int quad_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
384 SkDQuad quad;
385 return SkIntersections::VerticalIntercept(quad.set(a), x, roots);
386}
387
388static int conic_intercept_h(const SkPoint a[2], SkScalar w, SkScalar y, double* roots) {
389 SkDConic conic;
390 return SkIntersections::HorizontalIntercept(conic.set(a, w), y, roots);
391}
392
393static int conic_intercept_v(const SkPoint a[2], SkScalar w, SkScalar x, double* roots) {
394 SkDConic conic;
395 return SkIntersections::VerticalIntercept(conic.set(a, w), x, roots);
396}
397
398static int cubic_intercept_h(const SkPoint a[3], SkScalar , SkScalar y, double* roots) {
399 SkDCubic cubic;
400 return cubic.set(a).horizontalIntersect(y, roots);
401}
402
403static int cubic_intercept_v(const SkPoint a[3], SkScalar , SkScalar x, double* roots) {
404 SkDCubic cubic;
405 return cubic.set(a).verticalIntersect(x, roots);
406}
407
408static int (* const CurveIntercept[])(const SkPoint[] , SkScalar , SkScalar , double* ) = {
409 nullptr,
410 nullptr,
411 line_intercept_h,
412 line_intercept_v,
413 quad_intercept_h,
414 quad_intercept_v,
415 conic_intercept_h,
416 conic_intercept_v,
417 cubic_intercept_h,
418 cubic_intercept_v,
419};
420
421#endif
422