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