1/*
2 * Copyright 2006 The Android Open Source Project
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
8#ifndef SkGeometry_DEFINED
9#define SkGeometry_DEFINED
10
11#include "SkMatrix.h"
12#include "SkNx.h"
13
14static inline Sk2s from_point(const SkPoint& point) {
15    return Sk2s::Load(&point.fX);
16}
17
18static inline SkPoint to_point(const Sk2s& x) {
19    SkPoint point;
20    x.store(&point.fX);
21    return point;
22}
23
24static inline Sk2s sk2s_cubic_eval(const Sk2s& A, const Sk2s& B, const Sk2s& C, const Sk2s& D,
25                                   const Sk2s& t) {
26    return ((A * t + B) * t + C) * t + D;
27}
28
29/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
30    equation.
31*/
32int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
33
34///////////////////////////////////////////////////////////////////////////////
35
36SkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t);
37SkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t);
38
39/** Set pt to the point on the src quadratic specified by t. t must be
40    0 <= t <= 1.0
41*/
42void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = NULL);
43
44/**
45 *  output is : eval(t) == coeff[0] * t^2 + coeff[1] * t + coeff[2]
46 */
47void SkQuadToCoeff(const SkPoint pts[3], SkPoint coeff[3]);
48
49/**
50 *  output is : eval(t) == coeff[0] * t^3 + coeff[1] * t^2 + coeff[2] * t + coeff[3]
51 */
52void SkCubicToCoeff(const SkPoint pts[4], SkPoint coeff[4]);
53
54/** Given a src quadratic bezier, chop it at the specified t value,
55    where 0 < t < 1, and return the two new quadratics in dst:
56    dst[0..2] and dst[2..4]
57*/
58void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t);
59
60/** Given a src quadratic bezier, chop it at the specified t == 1/2,
61    The new quads are returned in dst[0..2] and dst[2..4]
62*/
63void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]);
64
65/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look
66    for extrema, and return the number of t-values that are found that represent
67    these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the
68    function returns 0.
69    Returned count      tValues[]
70    0                   ignored
71    1                   0 < tValues[0] < 1
72*/
73int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]);
74
75/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that
76    the resulting beziers are monotonic in Y. This is called by the scan converter.
77    Depending on what is returned, dst[] is treated as follows
78    0   dst[0..2] is the original quad
79    1   dst[0..2] and dst[2..4] are the two new quads
80*/
81int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
82int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]);
83
84/** Given 3 points on a quadratic bezier, if the point of maximum
85    curvature exists on the segment, returns the t value for this
86    point along the curve. Otherwise it will return a value of 0.
87*/
88SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]);
89
90/** Given 3 points on a quadratic bezier, divide it into 2 quadratics
91    if the point of maximum curvature exists on the quad segment.
92    Depending on what is returned, dst[] is treated as follows
93    1   dst[0..2] is the original quad
94    2   dst[0..2] and dst[2..4] are the two new quads
95    If dst == null, it is ignored and only the count is returned.
96*/
97int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]);
98
99/** Given 3 points on a quadratic bezier, use degree elevation to
100    convert it into the cubic fitting the same curve. The new cubic
101    curve is returned in dst[0..3].
102*/
103SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]);
104
105///////////////////////////////////////////////////////////////////////////////
106
107/** Set pt to the point on the src cubic specified by t. t must be
108    0 <= t <= 1.0
109*/
110void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull,
111                   SkVector* tangentOrNull, SkVector* curvatureOrNull);
112
113/** Given a src cubic bezier, chop it at the specified t value,
114    where 0 < t < 1, and return the two new cubics in dst:
115    dst[0..3] and dst[3..6]
116*/
117void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t);
118
119/** Given a src cubic bezier, chop it at the specified t values,
120    where 0 < t < 1, and return the new cubics in dst:
121    dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)]
122*/
123void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[],
124                   int t_count);
125
126/** Given a src cubic bezier, chop it at the specified t == 1/2,
127    The new cubics are returned in dst[0..3] and dst[3..6]
128*/
129void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]);
130
131/** Given the 4 coefficients for a cubic bezier (either X or Y values), look
132    for extrema, and return the number of t-values that are found that represent
133    these extrema. If the cubic has no extrema betwee (0..1) exclusive, the
134    function returns 0.
135    Returned count      tValues[]
136    0                   ignored
137    1                   0 < tValues[0] < 1
138    2                   0 < tValues[0] < tValues[1] < 1
139*/
140int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
141                       SkScalar tValues[2]);
142
143/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
144    the resulting beziers are monotonic in Y. This is called by the scan converter.
145    Depending on what is returned, dst[] is treated as follows
146    0   dst[0..3] is the original cubic
147    1   dst[0..3] and dst[3..6] are the two new cubics
148    2   dst[0..3], dst[3..6], dst[6..9] are the three new cubics
149    If dst == null, it is ignored and only the count is returned.
150*/
151int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
152int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]);
153
154/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the
155    inflection points.
156*/
157int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]);
158
159/** Return 1 for no chop, 2 for having chopped the cubic at a single
160    inflection point, 3 for having chopped at 2 inflection points.
161    dst will hold the resulting 1, 2, or 3 cubics.
162*/
163int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
164
165int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
166int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
167                              SkScalar tValues[3] = NULL);
168
169bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]);
170bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
171
172enum SkCubicType {
173    kSerpentine_SkCubicType,
174    kCusp_SkCubicType,
175    kLoop_SkCubicType,
176    kQuadratic_SkCubicType,
177    kLine_SkCubicType,
178    kPoint_SkCubicType
179};
180
181/** Returns the cubic classification. Pass scratch storage for computing inflection data,
182    which can be used with additional work to find the loop intersections and so on.
183*/
184SkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar inflection[3]);
185
186///////////////////////////////////////////////////////////////////////////////
187
188enum SkRotationDirection {
189    kCW_SkRotationDirection,
190    kCCW_SkRotationDirection
191};
192
193/** Maximum number of points needed in the quadPoints[] parameter for
194    SkBuildQuadArc()
195*/
196#define kSkBuildQuadArcStorage  17
197
198/** Given 2 unit vectors and a rotation direction, fill out the specified
199    array of points with quadratic segments. Return is the number of points
200    written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage }
201
202    matrix, if not null, is appled to the points before they are returned.
203*/
204int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop,
205                   SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]);
206
207struct SkConic {
208    SkConic() {}
209    SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
210        fPts[0] = p0;
211        fPts[1] = p1;
212        fPts[2] = p2;
213        fW = w;
214    }
215    SkConic(const SkPoint pts[3], SkScalar w) {
216        memcpy(fPts, pts, sizeof(fPts));
217        fW = w;
218    }
219
220    SkPoint  fPts[3];
221    SkScalar fW;
222
223    void set(const SkPoint pts[3], SkScalar w) {
224        memcpy(fPts, pts, 3 * sizeof(SkPoint));
225        fW = w;
226    }
227
228    void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
229        fPts[0] = p0;
230        fPts[1] = p1;
231        fPts[2] = p2;
232        fW = w;
233    }
234
235    /**
236     *  Given a t-value [0...1] return its position and/or tangent.
237     *  If pos is not null, return its position at the t-value.
238     *  If tangent is not null, return its tangent at the t-value. NOTE the
239     *  tangent value's length is arbitrary, and only its direction should
240     *  be used.
241     */
242    void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const;
243    void chopAt(SkScalar t, SkConic dst[2]) const;
244    void chop(SkConic dst[2]) const;
245
246    SkPoint evalAt(SkScalar t) const;
247    SkVector evalTangentAt(SkScalar t) const;
248
249    void computeAsQuadError(SkVector* err) const;
250    bool asQuadTol(SkScalar tol) const;
251
252    /**
253     *  return the power-of-2 number of quads needed to approximate this conic
254     *  with a sequence of quads. Will be >= 0.
255     */
256    int computeQuadPOW2(SkScalar tol) const;
257
258    /**
259     *  Chop this conic into N quads, stored continguously in pts[], where
260     *  N = 1 << pow2. The amount of storage needed is (1 + 2 * N)
261     */
262    int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
263
264    bool findXExtrema(SkScalar* t) const;
265    bool findYExtrema(SkScalar* t) const;
266    bool chopAtXExtrema(SkConic dst[2]) const;
267    bool chopAtYExtrema(SkConic dst[2]) const;
268
269    void computeTightBounds(SkRect* bounds) const;
270    void computeFastBounds(SkRect* bounds) const;
271
272    /** Find the parameter value where the conic takes on its maximum curvature.
273     *
274     *  @param t   output scalar for max curvature.  Will be unchanged if
275     *             max curvature outside 0..1 range.
276     *
277     *  @return  true if max curvature found inside 0..1 range, false otherwise
278     */
279    bool findMaxCurvature(SkScalar* t) const;
280
281    static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&);
282
283    enum {
284        kMaxConicsForArc = 5
285    };
286    static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection,
287                            const SkMatrix*, SkConic conics[kMaxConicsForArc]);
288};
289
290#include "SkTemplates.h"
291
292/**
293 *  Help class to allocate storage for approximating a conic with N quads.
294 */
295class SkAutoConicToQuads {
296public:
297    SkAutoConicToQuads() : fQuadCount(0) {}
298
299    /**
300     *  Given a conic and a tolerance, return the array of points for the
301     *  approximating quad(s). Call countQuads() to know the number of quads
302     *  represented in these points.
303     *
304     *  The quads are allocated to share end-points. e.g. if there are 4 quads,
305     *  there will be 9 points allocated as follows
306     *      quad[0] == pts[0..2]
307     *      quad[1] == pts[2..4]
308     *      quad[2] == pts[4..6]
309     *      quad[3] == pts[6..8]
310     */
311    const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
312        int pow2 = conic.computeQuadPOW2(tol);
313        fQuadCount = 1 << pow2;
314        SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
315        conic.chopIntoQuadsPOW2(pts, pow2);
316        return pts;
317    }
318
319    const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
320                                SkScalar tol) {
321        SkConic conic;
322        conic.set(pts, weight);
323        return computeQuads(conic, tol);
324    }
325
326    int countQuads() const { return fQuadCount; }
327
328private:
329    enum {
330        kQuadCount = 8, // should handle most conics
331        kPointCount = 1 + 2 * kQuadCount,
332    };
333    SkAutoSTMalloc<kPointCount, SkPoint> fStorage;
334    int fQuadCount; // #quads for current usage
335};
336
337#endif
338