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 "include/core/SkMatrix.h"
12#include "include/private/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*/
92void 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/** Returns t value of cusp if cubic has one; returns -1 otherwise.
158 */
159SkScalar SkFindCubicCusp(const SkPoint src[4]);
160
161bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]);
162bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
163
164enum class SkCubicType {
165 kSerpentine,
166 kLoop,
167 kLocalCusp, // Cusp at a non-infinite parameter value with an inflection at t=infinity.
168 kCuspAtInfinity, // Cusp with a cusp at t=infinity and a local inflection.
169 kQuadratic,
170 kLineOrPoint
171};
172
173static inline bool SkCubicIsDegenerate(SkCubicType type) {
174 switch (type) {
175 case SkCubicType::kSerpentine:
176 case SkCubicType::kLoop:
177 case SkCubicType::kLocalCusp:
178 case SkCubicType::kCuspAtInfinity:
179 return false;
180 case SkCubicType::kQuadratic:
181 case SkCubicType::kLineOrPoint:
182 return true;
183 }
184 SK_ABORT("Invalid SkCubicType");
185}
186
187static inline const char* SkCubicTypeName(SkCubicType type) {
188 switch (type) {
189 case SkCubicType::kSerpentine: return "kSerpentine";
190 case SkCubicType::kLoop: return "kLoop";
191 case SkCubicType::kLocalCusp: return "kLocalCusp";
192 case SkCubicType::kCuspAtInfinity: return "kCuspAtInfinity";
193 case SkCubicType::kQuadratic: return "kQuadratic";
194 case SkCubicType::kLineOrPoint: return "kLineOrPoint";
195 }
196 SK_ABORT("Invalid SkCubicType");
197}
198
199/** Returns the cubic classification.
200
201 t[],s[] are set to the two homogeneous parameter values at which points the lines L & M
202 intersect with K, sorted from smallest to largest and oriented so positive values of the
203 implicit are on the "left" side. For a serpentine curve they are the inflection points. For a
204 loop they are the double point. For a local cusp, they are both equal and denote the cusp point.
205 For a cusp at an infinite parameter value, one will be the local inflection point and the other
206 +inf (t,s = 1,0). If the curve is degenerate (i.e. quadratic or linear) they are both set to a
207 parameter value of +inf (t,s = 1,0).
208
209 d[] is filled with the cubic inflection function coefficients. See "Resolution Independent
210 Curve Rendering using Programmable Graphics Hardware", 4.2 Curve Categorization:
211
212 If the input points contain infinities or NaN, the return values are undefined.
213
214 https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
215*/
216SkCubicType SkClassifyCubic(const SkPoint p[4], double t[2] = nullptr, double s[2] = nullptr,
217 double d[4] = nullptr);
218
219///////////////////////////////////////////////////////////////////////////////
220
221enum SkRotationDirection {
222 kCW_SkRotationDirection,
223 kCCW_SkRotationDirection
224};
225
226struct SkConic {
227 SkConic() {}
228 SkConic(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 SkConic(const SkPoint pts[3], SkScalar w) {
235 memcpy(fPts, pts, sizeof(fPts));
236 fW = w;
237 }
238
239 SkPoint fPts[3];
240 SkScalar fW;
241
242 void set(const SkPoint pts[3], SkScalar w) {
243 memcpy(fPts, pts, 3 * sizeof(SkPoint));
244 fW = w;
245 }
246
247 void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
248 fPts[0] = p0;
249 fPts[1] = p1;
250 fPts[2] = p2;
251 fW = w;
252 }
253
254 /**
255 * Given a t-value [0...1] return its position and/or tangent.
256 * If pos is not null, return its position at the t-value.
257 * If tangent is not null, return its tangent at the t-value. NOTE the
258 * tangent value's length is arbitrary, and only its direction should
259 * be used.
260 */
261 void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = nullptr) const;
262 bool SK_WARN_UNUSED_RESULT chopAt(SkScalar t, SkConic dst[2]) const;
263 void chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const;
264 void chop(SkConic dst[2]) const;
265
266 SkPoint evalAt(SkScalar t) const;
267 SkVector evalTangentAt(SkScalar t) const;
268
269 void computeAsQuadError(SkVector* err) const;
270 bool asQuadTol(SkScalar tol) const;
271
272 /**
273 * return the power-of-2 number of quads needed to approximate this conic
274 * with a sequence of quads. Will be >= 0.
275 */
276 int SK_SPI computeQuadPOW2(SkScalar tol) const;
277
278 /**
279 * Chop this conic into N quads, stored continguously in pts[], where
280 * N = 1 << pow2. The amount of storage needed is (1 + 2 * N)
281 */
282 int SK_SPI SK_WARN_UNUSED_RESULT chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
283
284 bool findXExtrema(SkScalar* t) const;
285 bool findYExtrema(SkScalar* t) const;
286 bool chopAtXExtrema(SkConic dst[2]) const;
287 bool chopAtYExtrema(SkConic dst[2]) const;
288
289 void computeTightBounds(SkRect* bounds) const;
290 void computeFastBounds(SkRect* bounds) const;
291
292 /** Find the parameter value where the conic takes on its maximum curvature.
293 *
294 * @param t output scalar for max curvature. Will be unchanged if
295 * max curvature outside 0..1 range.
296 *
297 * @return true if max curvature found inside 0..1 range, false otherwise
298 */
299// bool findMaxCurvature(SkScalar* t) const; // unimplemented
300
301 static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&);
302
303 enum {
304 kMaxConicsForArc = 5
305 };
306 static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection,
307 const SkMatrix*, SkConic conics[kMaxConicsForArc]);
308};
309
310// inline helpers are contained in a namespace to avoid external leakage to fragile SkNx members
311namespace { // NOLINT(google-build-namespaces)
312
313/**
314 * use for : eval(t) == A * t^2 + B * t + C
315 */
316struct SkQuadCoeff {
317 SkQuadCoeff() {}
318
319 SkQuadCoeff(const Sk2s& A, const Sk2s& B, const Sk2s& C)
320 : fA(A)
321 , fB(B)
322 , fC(C)
323 {
324 }
325
326 SkQuadCoeff(const SkPoint src[3]) {
327 fC = from_point(src[0]);
328 Sk2s P1 = from_point(src[1]);
329 Sk2s P2 = from_point(src[2]);
330 fB = times_2(P1 - fC);
331 fA = P2 - times_2(P1) + fC;
332 }
333
334 Sk2s eval(SkScalar t) {
335 Sk2s tt(t);
336 return eval(tt);
337 }
338
339 Sk2s eval(const Sk2s& tt) {
340 return (fA * tt + fB) * tt + fC;
341 }
342
343 Sk2s fA;
344 Sk2s fB;
345 Sk2s fC;
346};
347
348struct SkConicCoeff {
349 SkConicCoeff(const SkConic& conic) {
350 Sk2s p0 = from_point(conic.fPts[0]);
351 Sk2s p1 = from_point(conic.fPts[1]);
352 Sk2s p2 = from_point(conic.fPts[2]);
353 Sk2s ww(conic.fW);
354
355 Sk2s p1w = p1 * ww;
356 fNumer.fC = p0;
357 fNumer.fA = p2 - times_2(p1w) + p0;
358 fNumer.fB = times_2(p1w - p0);
359
360 fDenom.fC = Sk2s(1);
361 fDenom.fB = times_2(ww - fDenom.fC);
362 fDenom.fA = Sk2s(0) - fDenom.fB;
363 }
364
365 Sk2s eval(SkScalar t) {
366 Sk2s tt(t);
367 Sk2s numer = fNumer.eval(tt);
368 Sk2s denom = fDenom.eval(tt);
369 return numer / denom;
370 }
371
372 SkQuadCoeff fNumer;
373 SkQuadCoeff fDenom;
374};
375
376struct SkCubicCoeff {
377 SkCubicCoeff(const SkPoint src[4]) {
378 Sk2s P0 = from_point(src[0]);
379 Sk2s P1 = from_point(src[1]);
380 Sk2s P2 = from_point(src[2]);
381 Sk2s P3 = from_point(src[3]);
382 Sk2s three(3);
383 fA = P3 + three * (P1 - P2) - P0;
384 fB = three * (P2 - times_2(P1) + P0);
385 fC = three * (P1 - P0);
386 fD = P0;
387 }
388
389 Sk2s eval(SkScalar t) {
390 Sk2s tt(t);
391 return eval(tt);
392 }
393
394 Sk2s eval(const Sk2s& t) {
395 return ((fA * t + fB) * t + fC) * t + fD;
396 }
397
398 Sk2s fA;
399 Sk2s fB;
400 Sk2s fC;
401 Sk2s fD;
402};
403
404}
405
406#include "include/private/SkTemplates.h"
407
408/**
409 * Help class to allocate storage for approximating a conic with N quads.
410 */
411class SkAutoConicToQuads {
412public:
413 SkAutoConicToQuads() : fQuadCount(0) {}
414
415 /**
416 * Given a conic and a tolerance, return the array of points for the
417 * approximating quad(s). Call countQuads() to know the number of quads
418 * represented in these points.
419 *
420 * The quads are allocated to share end-points. e.g. if there are 4 quads,
421 * there will be 9 points allocated as follows
422 * quad[0] == pts[0..2]
423 * quad[1] == pts[2..4]
424 * quad[2] == pts[4..6]
425 * quad[3] == pts[6..8]
426 */
427 const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
428 int pow2 = conic.computeQuadPOW2(tol);
429 fQuadCount = 1 << pow2;
430 SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
431 fQuadCount = conic.chopIntoQuadsPOW2(pts, pow2);
432 return pts;
433 }
434
435 const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
436 SkScalar tol) {
437 SkConic conic;
438 conic.set(pts, weight);
439 return computeQuads(conic, tol);
440 }
441
442 int countQuads() const { return fQuadCount; }
443
444private:
445 enum {
446 kQuadCount = 8, // should handle most conics
447 kPointCount = 1 + 2 * kQuadCount,
448 };
449 SkAutoSTMalloc<kPointCount, SkPoint> fStorage;
450 int fQuadCount; // #quads for current usage
451};
452
453#endif
454