• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
16 struct SkPathOpsBounds;
17 
18 struct 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 
setSkOpCurve30     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 
setSkOpCurve38     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 
48 struct 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 
85 class SkDCurveSweep {
86 public:
isCurve()87     bool isCurve() const { return fIsCurve; }
isOrdered()88     bool isOrdered() const { return fOrdered; }
89     void setCurveHullSweep(SkPath::Verb verb);
90 
91     SkDCurve fCurve;
92     SkDVector fSweep[2];
93 private:
94     bool fIsCurve;
95     bool fOrdered;  // cleared when a cubic's control point isn't between the sweep vectors
96 
97 };
98 
99 extern SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar cWeight,
100     double tStart, double tEnd, double* topT);
101 
dline_xy_at_t(const SkPoint a[2],SkScalar,double t)102 static 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 
dquad_xy_at_t(const SkPoint a[3],SkScalar,double t)108 static 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 
dconic_xy_at_t(const SkPoint a[3],SkScalar weight,double t)114 static 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 
dcubic_xy_at_t(const SkPoint a[4],SkScalar,double t)120 static 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 
126 static 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 
ddline_xy_at_t(const SkDCurve & c,double t)134 static SkDPoint ddline_xy_at_t(const SkDCurve& c, double t) {
135     return c.fLine.ptAtT(t);
136 }
137 
ddquad_xy_at_t(const SkDCurve & c,double t)138 static SkDPoint ddquad_xy_at_t(const SkDCurve& c, double t) {
139     return c.fQuad.ptAtT(t);
140 }
141 
ddconic_xy_at_t(const SkDCurve & c,double t)142 static SkDPoint ddconic_xy_at_t(const SkDCurve& c, double t) {
143     return c.fConic.ptAtT(t);
144 }
145 
ddcubic_xy_at_t(const SkDCurve & c,double t)146 static SkDPoint ddcubic_xy_at_t(const SkDCurve& c, double t) {
147     return c.fCubic.ptAtT(t);
148 }
149 
150 static 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 
fline_xy_at_t(const SkPoint a[2],SkScalar weight,double t)158 static 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 
fquad_xy_at_t(const SkPoint a[3],SkScalar weight,double t)162 static 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 
fconic_xy_at_t(const SkPoint a[3],SkScalar weight,double t)166 static 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 
fcubic_xy_at_t(const SkPoint a[4],SkScalar weight,double t)170 static 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 
174 static 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 
dline_dxdy_at_t(const SkPoint a[2],SkScalar,double)182 static 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 
dquad_dxdy_at_t(const SkPoint a[3],SkScalar,double t)188 static 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 
dconic_dxdy_at_t(const SkPoint a[3],SkScalar weight,double t)194 static 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 
dcubic_dxdy_at_t(const SkPoint a[4],SkScalar,double t)200 static 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 
206 static 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 
ddline_dxdy_at_t(const SkDCurve & c,double)214 static SkDVector ddline_dxdy_at_t(const SkDCurve& c, double ) {
215     return c.fLine.fPts[1] - c.fLine.fPts[0];
216 }
217 
ddquad_dxdy_at_t(const SkDCurve & c,double t)218 static SkDVector ddquad_dxdy_at_t(const SkDCurve& c, double t) {
219     return c.fQuad.dxdyAtT(t);
220 }
221 
ddconic_dxdy_at_t(const SkDCurve & c,double t)222 static SkDVector ddconic_dxdy_at_t(const SkDCurve& c, double t) {
223     return c.fConic.dxdyAtT(t);
224 }
225 
ddcubic_dxdy_at_t(const SkDCurve & c,double t)226 static SkDVector ddcubic_dxdy_at_t(const SkDCurve& c, double t) {
227     return c.fCubic.dxdyAtT(t);
228 }
229 
230 static 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 
fline_dxdy_at_t(const SkPoint a[2],SkScalar,double)238 static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
239     return a[1] - a[0];
240 }
241 
fquad_dxdy_at_t(const SkPoint a[3],SkScalar weight,double t)242 static 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 
fconic_dxdy_at_t(const SkPoint a[3],SkScalar weight,double t)246 static 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 
fcubic_dxdy_at_t(const SkPoint a[4],SkScalar weight,double t)250 static 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 
254 static 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 
line_is_vertical(const SkPoint a[2],SkScalar,double startT,double endT)262 static 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 
quad_is_vertical(const SkPoint a[3],SkScalar,double startT,double endT)269 static 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 
conic_is_vertical(const SkPoint a[3],SkScalar weight,double startT,double endT)276 static 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 
cubic_is_vertical(const SkPoint a[4],SkScalar,double startT,double endT)283 static 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 
291 static 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 
line_intersect_ray(const SkPoint a[2],SkScalar,const SkDLine & ray,SkIntersections * i)299 static 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 
quad_intersect_ray(const SkPoint a[3],SkScalar,const SkDLine & ray,SkIntersections * i)306 static 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 
conic_intersect_ray(const SkPoint a[3],SkScalar weight,const SkDLine & ray,SkIntersections * i)313 static 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 
cubic_intersect_ray(const SkPoint a[4],SkScalar,const SkDLine & ray,SkIntersections * i)320 static 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 
327 static 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 
dline_intersect_ray(const SkDCurve & c,const SkDLine & ray,SkIntersections * i)336 static void dline_intersect_ray(const SkDCurve& c, const SkDLine& ray,  SkIntersections* i) {
337     i->intersectRay(c.fLine, ray);
338 }
339 
dquad_intersect_ray(const SkDCurve & c,const SkDLine & ray,SkIntersections * i)340 static void dquad_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
341     i->intersectRay(c.fQuad, ray);
342 }
343 
dconic_intersect_ray(const SkDCurve & c,const SkDLine & ray,SkIntersections * i)344 static void dconic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
345     i->intersectRay(c.fConic, ray);
346 }
347 
dcubic_intersect_ray(const SkDCurve & c,const SkDLine & ray,SkIntersections * i)348 static void dcubic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
349     i->intersectRay(c.fCubic, ray);
350 }
351 
352 static 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 
line_intercept_h(const SkPoint a[2],SkScalar,SkScalar y,double * roots)360 static 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 
line_intercept_v(const SkPoint a[2],SkScalar,SkScalar x,double * roots)366 static 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 
quad_intercept_h(const SkPoint a[2],SkScalar,SkScalar y,double * roots)372 static 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 
quad_intercept_v(const SkPoint a[2],SkScalar,SkScalar x,double * roots)377 static 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 
conic_intercept_h(const SkPoint a[2],SkScalar w,SkScalar y,double * roots)382 static 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 
conic_intercept_v(const SkPoint a[2],SkScalar w,SkScalar x,double * roots)387 static 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 
cubic_intercept_h(const SkPoint a[3],SkScalar,SkScalar y,double * roots)392 static 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 
cubic_intercept_v(const SkPoint a[3],SkScalar,SkScalar x,double * roots)397 static 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 
402 static 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