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);
16 }
17
to_point(const Sk2s & x)18 static inline SkPoint to_point(const Sk2s& x) {
19 SkPoint point;
20 x.store(&point);
21 return point;
22 }
23
times_2(const Sk2s & value)24 static 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 */
31 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
32
33 ///////////////////////////////////////////////////////////////////////////////
34
35 SkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t);
36 SkPoint 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 */
41 void 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 */
47 void 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 */
52 void 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 */
62 int 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 */
70 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
71 int 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 */
77 SkScalar 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 */
86 int 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 */
92 SK_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 */
99 void 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 */
106 void 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 */
112 void 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 */
118 void 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 */
129 int 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 */
140 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
141 int 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 */
146 int 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 */
152 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
153
154 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
155 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
156 SkScalar tValues[3] = nullptr);
157
158 bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]);
159 bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
160
161 enum 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 */
173 SkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar inflection[3]);
174
175 ///////////////////////////////////////////////////////////////////////////////
176
177 enum SkRotationDirection {
178 kCW_SkRotationDirection,
179 kCCW_SkRotationDirection
180 };
181
182 struct SkConic {
SkConicSkConic183 SkConic() {}
SkConicSkConic184 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 }
SkConicSkConic190 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
setSkConic198 void set(const SkPoint pts[3], SkScalar w) {
199 memcpy(fPts, pts, 3 * sizeof(SkPoint));
200 fW = w;
201 }
202
setSkConic203 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 void 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 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
267 namespace {
268
269 /**
270 * use for : eval(t) == A * t^2 + B * t + C
271 */
272 struct SkQuadCoeff {
SkQuadCoeffSkQuadCoeff273 SkQuadCoeff() {}
274
SkQuadCoeffSkQuadCoeff275 SkQuadCoeff(const Sk2s& A, const Sk2s& B, const Sk2s& C)
276 : fA(A)
277 , fB(B)
278 , fC(C)
279 {
280 }
281
SkQuadCoeffSkQuadCoeff282 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
evalSkQuadCoeff290 Sk2s eval(SkScalar t) {
291 Sk2s tt(t);
292 return eval(tt);
293 }
294
evalSkQuadCoeff295 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
304 struct SkConicCoeff {
SkConicCoeffSkConicCoeff305 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
evalSkConicCoeff321 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
332 struct SkCubicCoeff {
SkCubicCoeffSkCubicCoeff333 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
evalSkCubicCoeff345 Sk2s eval(SkScalar t) {
346 Sk2s tt(t);
347 return eval(tt);
348 }
349
evalSkCubicCoeff350 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 */
367 class SkAutoConicToQuads {
368 public:
SkAutoConicToQuads()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 */
computeQuads(const SkConic & conic,SkScalar tol)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 conic.chopIntoQuadsPOW2(pts, pow2);
388 return pts;
389 }
390
computeQuads(const SkPoint pts[3],SkScalar weight,SkScalar tol)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
countQuads()398 int countQuads() const { return fQuadCount; }
399
400 private:
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