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 static inline Sk2s from_point(const SkPoint& point) { 15 return Sk2s::Load(&point.fX); 16 } 17 18 static inline SkPoint to_point(const Sk2s& x) { 19 SkPoint point; 20 x.store(&point.fX); 21 return point; 22 } 23 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 { 208 SkConic() {} 209 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 } 215 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 223 void set(const SkPoint pts[3], SkScalar w) { 224 memcpy(fPts, pts, 3 * sizeof(SkPoint)); 225 fW = w; 226 } 227 228 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: 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 */ 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 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 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
