SkGeometry.h revision 639a82855b94b93c4fa45560e67df8ec4a8bbb3a
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 13/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the 14 equation. 15*/ 16int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); 17 18/////////////////////////////////////////////////////////////////////////////// 19 20SkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t); 21SkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t); 22 23/** Set pt to the point on the src quadratic specified by t. t must be 24 0 <= t <= 1.0 25*/ 26void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = NULL); 27 28/** Given a src quadratic bezier, chop it at the specified t value, 29 where 0 < t < 1, and return the two new quadratics in dst: 30 dst[0..2] and dst[2..4] 31*/ 32void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); 33 34/** Given a src quadratic bezier, chop it at the specified t == 1/2, 35 The new quads are returned in dst[0..2] and dst[2..4] 36*/ 37void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); 38 39/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look 40 for extrema, and return the number of t-values that are found that represent 41 these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the 42 function returns 0. 43 Returned count tValues[] 44 0 ignored 45 1 0 < tValues[0] < 1 46*/ 47int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); 48 49/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that 50 the resulting beziers are monotonic in Y. This is called by the scan converter. 51 Depending on what is returned, dst[] is treated as follows 52 0 dst[0..2] is the original quad 53 1 dst[0..2] and dst[2..4] are the two new quads 54*/ 55int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 56int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 57 58/** Given 3 points on a quadratic bezier, if the point of maximum 59 curvature exists on the segment, returns the t value for this 60 point along the curve. Otherwise it will return a value of 0. 61*/ 62SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]); 63 64/** Given 3 points on a quadratic bezier, divide it into 2 quadratics 65 if the point of maximum curvature exists on the quad segment. 66 Depending on what is returned, dst[] is treated as follows 67 1 dst[0..2] is the original quad 68 2 dst[0..2] and dst[2..4] are the two new quads 69 If dst == null, it is ignored and only the count is returned. 70*/ 71int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 72 73/** Given 3 points on a quadratic bezier, use degree elevation to 74 convert it into the cubic fitting the same curve. The new cubic 75 curve is returned in dst[0..3]. 76*/ 77SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 78 79/////////////////////////////////////////////////////////////////////////////// 80 81/** Convert from parametric from (pts) to polynomial coefficients 82 coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 83*/ 84void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); 85 86/** Set pt to the point on the src cubic specified by t. t must be 87 0 <= t <= 1.0 88*/ 89void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, 90 SkVector* tangentOrNull, SkVector* curvatureOrNull); 91 92/** Given a src cubic bezier, chop it at the specified t value, 93 where 0 < t < 1, and return the two new cubics in dst: 94 dst[0..3] and dst[3..6] 95*/ 96void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 97 98/** Given a src cubic bezier, chop it at the specified t values, 99 where 0 < t < 1, and return the new cubics in dst: 100 dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)] 101*/ 102void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[], 103 int t_count); 104 105/** Given a src cubic bezier, chop it at the specified t == 1/2, 106 The new cubics are returned in dst[0..3] and dst[3..6] 107*/ 108void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); 109 110/** Given the 4 coefficients for a cubic bezier (either X or Y values), look 111 for extrema, and return the number of t-values that are found that represent 112 these extrema. If the cubic has no extrema betwee (0..1) exclusive, the 113 function returns 0. 114 Returned count tValues[] 115 0 ignored 116 1 0 < tValues[0] < 1 117 2 0 < tValues[0] < tValues[1] < 1 118*/ 119int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 120 SkScalar tValues[2]); 121 122/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 123 the resulting beziers are monotonic in Y. This is called by the scan converter. 124 Depending on what is returned, dst[] is treated as follows 125 0 dst[0..3] is the original cubic 126 1 dst[0..3] and dst[3..6] are the two new cubics 127 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 128 If dst == null, it is ignored and only the count is returned. 129*/ 130int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 131int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); 132 133/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the 134 inflection points. 135*/ 136int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); 137 138/** Return 1 for no chop, 2 for having chopped the cubic at a single 139 inflection point, 3 for having chopped at 2 inflection points. 140 dst will hold the resulting 1, 2, or 3 cubics. 141*/ 142int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 143 144int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 145int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 146 SkScalar tValues[3] = NULL); 147 148enum SkCubicType { 149 kSerpentine_SkCubicType, 150 kCusp_SkCubicType, 151 kLoop_SkCubicType, 152 kQuadratic_SkCubicType, 153 kLine_SkCubicType, 154 kPoint_SkCubicType 155}; 156 157/** Returns the cubic classification. Pass scratch storage for computing inflection data, 158 which can be used with additional work to find the loop intersections and so on. 159*/ 160SkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar inflection[3]); 161 162/////////////////////////////////////////////////////////////////////////////// 163 164enum SkRotationDirection { 165 kCW_SkRotationDirection, 166 kCCW_SkRotationDirection 167}; 168 169/** Maximum number of points needed in the quadPoints[] parameter for 170 SkBuildQuadArc() 171*/ 172#define kSkBuildQuadArcStorage 17 173 174/** Given 2 unit vectors and a rotation direction, fill out the specified 175 array of points with quadratic segments. Return is the number of points 176 written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 177 178 matrix, if not null, is appled to the points before they are returned. 179*/ 180int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 181 SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 182 183struct SkConic { 184 SkConic() {} 185 SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) { 186 fPts[0] = p0; 187 fPts[1] = p1; 188 fPts[2] = p2; 189 fW = w; 190 } 191 SkConic(const SkPoint pts[3], SkScalar w) { 192 memcpy(fPts, pts, sizeof(fPts)); 193 fW = w; 194 } 195 196 SkPoint fPts[3]; 197 SkScalar fW; 198 199 void set(const SkPoint pts[3], SkScalar w) { 200 memcpy(fPts, pts, 3 * sizeof(SkPoint)); 201 fW = w; 202 } 203 204 void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) { 205 fPts[0] = p0; 206 fPts[1] = p1; 207 fPts[2] = p2; 208 fW = w; 209 } 210 211 /** 212 * Given a t-value [0...1] return its position and/or tangent. 213 * If pos is not null, return its position at the t-value. 214 * If tangent is not null, return its tangent at the t-value. NOTE the 215 * tangent value's length is arbitrary, and only its direction should 216 * be used. 217 */ 218 void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const; 219 void chopAt(SkScalar t, SkConic dst[2]) 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; 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#include "SkTemplates.h" 267 268/** 269 * Help class to allocate storage for approximating a conic with N quads. 270 */ 271class SkAutoConicToQuads { 272public: 273 SkAutoConicToQuads() : fQuadCount(0) {} 274 275 /** 276 * Given a conic and a tolerance, return the array of points for the 277 * approximating quad(s). Call countQuads() to know the number of quads 278 * represented in these points. 279 * 280 * The quads are allocated to share end-points. e.g. if there are 4 quads, 281 * there will be 9 points allocated as follows 282 * quad[0] == pts[0..2] 283 * quad[1] == pts[2..4] 284 * quad[2] == pts[4..6] 285 * quad[3] == pts[6..8] 286 */ 287 const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) { 288 int pow2 = conic.computeQuadPOW2(tol); 289 fQuadCount = 1 << pow2; 290 SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount); 291 conic.chopIntoQuadsPOW2(pts, pow2); 292 return pts; 293 } 294 295 const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight, 296 SkScalar tol) { 297 SkConic conic; 298 conic.set(pts, weight); 299 return computeQuads(conic, tol); 300 } 301 302 int countQuads() const { return fQuadCount; } 303 304private: 305 enum { 306 kQuadCount = 8, // should handle most conics 307 kPointCount = 1 + 2 * kQuadCount, 308 }; 309 SkAutoSTMalloc<kPointCount, SkPoint> fStorage; 310 int fQuadCount; // #quads for current usage 311}; 312 313#endif 314