Line data Source code
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 :
14 2713 : static inline Sk2s from_point(const SkPoint& point) {
15 2713 : return Sk2s::Load(&point);
16 : }
17 :
18 426 : static inline SkPoint to_point(const Sk2s& x) {
19 : SkPoint point;
20 : x.store(&point);
21 426 : return point;
22 : }
23 :
24 418 : static Sk2s times_2(const Sk2s& value) {
25 418 : 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 {
183 0 : SkConic() {}
184 0 : SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
185 0 : fPts[0] = p0;
186 0 : fPts[1] = p1;
187 0 : fPts[2] = p2;
188 0 : fW = w;
189 0 : }
190 0 : SkConic(const SkPoint pts[3], SkScalar w) {
191 0 : memcpy(fPts, pts, sizeof(fPts));
192 0 : fW = w;
193 0 : }
194 :
195 : SkPoint fPts[3];
196 : SkScalar fW;
197 :
198 0 : void set(const SkPoint pts[3], SkScalar w) {
199 0 : memcpy(fPts, pts, 3 * sizeof(SkPoint));
200 0 : fW = w;
201 0 : }
202 :
203 0 : void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
204 0 : fPts[0] = p0;
205 0 : fPts[1] = p1;
206 0 : fPts[2] = p2;
207 0 : fW = w;
208 0 : }
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
267 : namespace {
268 :
269 : /**
270 : * use for : eval(t) == A * t^2 + B * t + C
271 : */
272 : struct SkQuadCoeff {
273 192 : SkQuadCoeff() {}
274 :
275 0 : SkQuadCoeff(const Sk2s& A, const Sk2s& B, const Sk2s& C)
276 0 : : fA(A)
277 : , fB(B)
278 0 : , fC(C)
279 : {
280 0 : }
281 :
282 48 : SkQuadCoeff(const SkPoint src[3]) {
283 16 : fC = from_point(src[0]);
284 16 : Sk2s P1 = from_point(src[1]);
285 16 : Sk2s P2 = from_point(src[2]);
286 32 : fB = times_2(P1 - fC);
287 48 : fA = P2 - times_2(P1) + fC;
288 16 : }
289 :
290 64 : Sk2s eval(SkScalar t) {
291 : Sk2s tt(t);
292 64 : return eval(tt);
293 : }
294 :
295 64 : Sk2s eval(const Sk2s& tt) {
296 320 : return (fA * tt + fB) * tt + fC;
297 : }
298 :
299 : Sk2s fA;
300 : Sk2s fB;
301 : Sk2s fC;
302 : };
303 :
304 : struct SkConicCoeff {
305 0 : SkConicCoeff(const SkConic& conic) {
306 0 : Sk2s p0 = from_point(conic.fPts[0]);
307 0 : Sk2s p1 = from_point(conic.fPts[1]);
308 0 : Sk2s p2 = from_point(conic.fPts[2]);
309 0 : Sk2s ww(conic.fW);
310 :
311 0 : Sk2s p1w = p1 * ww;
312 0 : fNumer.fC = p0;
313 0 : fNumer.fA = p2 - times_2(p1w) + p0;
314 0 : fNumer.fB = times_2(p1w - p0);
315 :
316 0 : fDenom.fC = Sk2s(1);
317 0 : fDenom.fB = times_2(ww - fDenom.fC);
318 0 : fDenom.fA = Sk2s(0) - fDenom.fB;
319 0 : }
320 :
321 0 : Sk2s eval(SkScalar t) {
322 : Sk2s tt(t);
323 0 : Sk2s numer = fNumer.eval(tt);
324 0 : Sk2s denom = fDenom.eval(tt);
325 0 : return numer / denom;
326 : }
327 :
328 : SkQuadCoeff fNumer;
329 : SkQuadCoeff fDenom;
330 : };
331 :
332 : struct SkCubicCoeff {
333 1160 : SkCubicCoeff(const SkPoint src[4]) {
334 290 : Sk2s P0 = from_point(src[0]);
335 290 : Sk2s P1 = from_point(src[1]);
336 290 : Sk2s P2 = from_point(src[2]);
337 290 : Sk2s P3 = from_point(src[3]);
338 : Sk2s three(3);
339 1160 : fA = P3 + three * (P1 - P2) - P0;
340 1160 : fB = three * (P2 - times_2(P1) + P0);
341 580 : fC = three * (P1 - P0);
342 290 : fD = P0;
343 290 : }
344 :
345 290 : Sk2s eval(SkScalar t) {
346 : Sk2s tt(t);
347 290 : return eval(tt);
348 : }
349 :
350 290 : Sk2s eval(const Sk2s& t) {
351 2030 : 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 66 : class SkAutoConicToQuads {
368 : public:
369 66 : 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 0 : const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
384 0 : int pow2 = conic.computeQuadPOW2(tol);
385 0 : fQuadCount = 1 << pow2;
386 0 : SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
387 0 : fQuadCount = conic.chopIntoQuadsPOW2(pts, pow2);
388 0 : return pts;
389 : }
390 :
391 0 : const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
392 : SkScalar tol) {
393 0 : SkConic conic;
394 0 : conic.set(pts, weight);
395 0 : return computeQuads(conic, tol);
396 : }
397 :
398 0 : 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
|
