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