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
from_point(const SkPoint & point)14 static inline Sk2s from_point(const SkPoint& point) {
15 return Sk2s::Load(&point.fX);
16 }
17
to_point(const Sk2s & x)18 static inline SkPoint to_point(const Sk2s& x) {
19 SkPoint point;
20 x.store(&point.fX);
21 return point;
22 }
23
sk2s_cubic_eval(const Sk2s & A,const Sk2s & B,const Sk2s & C,const Sk2s & D,const Sk2s & t)24 static 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 */
32 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
33
34 ///////////////////////////////////////////////////////////////////////////////
35
36 SkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t);
37 SkPoint 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 */
42 void 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 */
47 void 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 */
52 void 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 */
58 void 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 */
63 void 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 */
73 int 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 */
81 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
82 int 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 */
88 SkScalar 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 */
97 int 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 */
103 SK_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 */
110 void 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 */
117 void 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 */
123 void 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 */
129 void 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 */
140 int 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 */
151 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
152 int 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 */
157 int 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 */
163 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
164
165 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
166 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
167 SkScalar tValues[3] = NULL);
168
169 bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]);
170 bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
171
172 enum 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 */
184 SkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar inflection[3]);
185
186 ///////////////////////////////////////////////////////////////////////////////
187
188 enum 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 */
204 int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop,
205 SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]);
206
207 struct SkConic {
SkConicSkConic208 SkConic() {}
SkConicSkConic209 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 }
SkConicSkConic215 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
setSkConic223 void set(const SkPoint pts[3], SkScalar w) {
224 memcpy(fPts, pts, 3 * sizeof(SkPoint));
225 fW = w;
226 }
227
setSkConic228 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 */
295 class SkAutoConicToQuads {
296 public:
SkAutoConicToQuads()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 */
computeQuads(const SkConic & conic,SkScalar tol)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
computeQuads(const SkPoint pts[3],SkScalar weight,SkScalar tol)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
countQuads()326 int countQuads() const { return fQuadCount; }
327
328 private:
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