1 2 /* 3 * Copyright 2006 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 #ifndef SkGeometry_DEFINED 11 #define SkGeometry_DEFINED 12 13 #include "SkMatrix.h" 14 15 /** An XRay is a half-line that runs from the specific point/origin to 16 +infinity in the X direction. e.g. XRay(3,5) is the half-line 17 (3,5)....(infinity, 5) 18 */ 19 typedef SkPoint SkXRay; 20 21 /** Given a line segment from pts[0] to pts[1], and an xray, return true if 22 they intersect. Optional outgoing "ambiguous" argument indicates 23 whether the answer is ambiguous because the query occurred exactly at 24 one of the endpoints' y coordinates, indicating that another query y 25 coordinate is preferred for robustness. 26 */ 27 bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], 28 bool* ambiguous = NULL); 29 30 /** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the 31 equation. 32 */ 33 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); 34 35 /////////////////////////////////////////////////////////////////////////////// 36 37 /** Set pt to the point on the src quadratic specified by t. t must be 38 0 <= t <= 1.0 39 */ 40 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, 41 SkVector* tangent = NULL); 42 void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, 43 SkVector* tangent = NULL); 44 45 /** Given a src quadratic bezier, chop it at the specified t value, 46 where 0 < t < 1, and return the two new quadratics in dst: 47 dst[0..2] and dst[2..4] 48 */ 49 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); 50 51 /** Given a src quadratic bezier, chop it at the specified t == 1/2, 52 The new quads are returned in dst[0..2] and dst[2..4] 53 */ 54 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); 55 56 /** Given the 3 coefficients for a quadratic bezier (either X or Y values), look 57 for extrema, and return the number of t-values that are found that represent 58 these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the 59 function returns 0. 60 Returned count tValues[] 61 0 ignored 62 1 0 < tValues[0] < 1 63 */ 64 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); 65 66 /** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that 67 the resulting beziers are monotonic in Y. This is called by the scan converter. 68 Depending on what is returned, dst[] is treated as follows 69 0 dst[0..2] is the original quad 70 1 dst[0..2] and dst[2..4] are the two new quads 71 */ 72 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 73 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 74 75 /** Given 3 points on a quadratic bezier, if the point of maximum 76 curvature exists on the segment, returns the t value for this 77 point along the curve. Otherwise it will return a value of 0. 78 */ 79 float SkFindQuadMaxCurvature(const SkPoint src[3]); 80 81 /** Given 3 points on a quadratic bezier, divide it into 2 quadratics 82 if the point of maximum curvature exists on the quad segment. 83 Depending on what is returned, dst[] is treated as follows 84 1 dst[0..2] is the original quad 85 2 dst[0..2] and dst[2..4] are the two new quads 86 If dst == null, it is ignored and only the count is returned. 87 */ 88 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 89 90 /** Given 3 points on a quadratic bezier, use degree elevation to 91 convert it into the cubic fitting the same curve. The new cubic 92 curve is returned in dst[0..3]. 93 */ 94 SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 95 96 /////////////////////////////////////////////////////////////////////////////// 97 98 /** Convert from parametric from (pts) to polynomial coefficients 99 coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 100 */ 101 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); 102 103 /** Set pt to the point on the src cubic specified by t. t must be 104 0 <= t <= 1.0 105 */ 106 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, 107 SkVector* tangentOrNull, SkVector* curvatureOrNull); 108 109 /** Given a src cubic bezier, chop it at the specified t value, 110 where 0 < t < 1, and return the two new cubics in dst: 111 dst[0..3] and dst[3..6] 112 */ 113 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 114 /** Given a src cubic bezier, chop it at the specified t values, 115 where 0 < t < 1, and return the new cubics in dst: 116 dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)] 117 */ 118 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[], 119 int t_count); 120 121 /** Given a src cubic bezier, chop it at the specified t == 1/2, 122 The new cubics are returned in dst[0..3] and dst[3..6] 123 */ 124 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); 125 126 /** Given the 4 coefficients for a cubic bezier (either X or Y values), look 127 for extrema, and return the number of t-values that are found that represent 128 these extrema. If the cubic has no extrema betwee (0..1) exclusive, the 129 function returns 0. 130 Returned count tValues[] 131 0 ignored 132 1 0 < tValues[0] < 1 133 2 0 < tValues[0] < tValues[1] < 1 134 */ 135 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 136 SkScalar tValues[2]); 137 138 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 139 the resulting beziers are monotonic in Y. This is called by the scan converter. 140 Depending on what is returned, dst[] is treated as follows 141 0 dst[0..3] is the original cubic 142 1 dst[0..3] and dst[3..6] are the two new cubics 143 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 144 If dst == null, it is ignored and only the count is returned. 145 */ 146 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 147 int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); 148 149 /** Given a cubic bezier, return 0, 1, or 2 t-values that represent the 150 inflection points. 151 */ 152 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); 153 154 /** Return 1 for no chop, 2 for having chopped the cubic at a single 155 inflection point, 3 for having chopped at 2 inflection points. 156 dst will hold the resulting 1, 2, or 3 cubics. 157 */ 158 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 159 160 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 161 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 162 SkScalar tValues[3] = NULL); 163 164 /** Given a monotonic cubic bezier, determine whether an xray intersects the 165 cubic. 166 By definition the cubic is open at the starting point; in other 167 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 168 left of the curve, the line is not considered to cross the curve, 169 but if it is equal to cubic[3].fY then it is considered to 170 cross. 171 Optional outgoing "ambiguous" argument indicates whether the answer is 172 ambiguous because the query occurred exactly at one of the endpoints' y 173 coordinates, indicating that another query y coordinate is preferred 174 for robustness. 175 */ 176 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], 177 bool* ambiguous = NULL); 178 179 /** Given an arbitrary cubic bezier, return the number of times an xray crosses 180 the cubic. Valid return values are [0..3] 181 By definition the cubic is open at the starting point; in other 182 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 183 left of the curve, the line is not considered to cross the curve, 184 but if it is equal to cubic[3].fY then it is considered to 185 cross. 186 Optional outgoing "ambiguous" argument indicates whether the answer is 187 ambiguous because the query occurred exactly at one of the endpoints' y 188 coordinates or at a tangent point, indicating that another query y 189 coordinate is preferred for robustness. 190 */ 191 int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], 192 bool* ambiguous = NULL); 193 194 /////////////////////////////////////////////////////////////////////////////// 195 196 enum SkRotationDirection { 197 kCW_SkRotationDirection, 198 kCCW_SkRotationDirection 199 }; 200 201 /** Maximum number of points needed in the quadPoints[] parameter for 202 SkBuildQuadArc() 203 */ 204 #define kSkBuildQuadArcStorage 17 205 206 /** Given 2 unit vectors and a rotation direction, fill out the specified 207 array of points with quadratic segments. Return is the number of points 208 written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 209 210 matrix, if not null, is appled to the points before they are returned. 211 */ 212 int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 213 SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 214 215 // experimental 216 struct SkConic { 217 SkPoint fPts[3]; 218 SkScalar fW; 219 220 void set(const SkPoint pts[3], SkScalar w) { 221 memcpy(fPts, pts, 3 * sizeof(SkPoint)); 222 fW = w; 223 } 224 225 /** 226 * Given a t-value [0...1] return its position and/or tangent. 227 * If pos is not null, return its position at the t-value. 228 * If tangent is not null, return its tangent at the t-value. NOTE the 229 * tangent value's length is arbitrary, and only its direction should 230 * be used. 231 */ 232 void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const; 233 void chopAt(SkScalar t, SkConic dst[2]) const; 234 void chop(SkConic dst[2]) const; 235 236 void computeAsQuadError(SkVector* err) const; 237 bool asQuadTol(SkScalar tol) const; 238 239 /** 240 * return the power-of-2 number of quads needed to approximate this conic 241 * with a sequence of quads. Will be >= 0. 242 */ 243 int computeQuadPOW2(SkScalar tol) const; 244 245 /** 246 * Chop this conic into N quads, stored continguously in pts[], where 247 * N = 1 << pow2. The amount of storage needed is (1 + 2 * N) 248 */ 249 int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const; 250 251 bool findXExtrema(SkScalar* t) const; 252 bool findYExtrema(SkScalar* t) const; 253 bool chopAtXExtrema(SkConic dst[2]) const; 254 bool chopAtYExtrema(SkConic dst[2]) const; 255 256 void computeTightBounds(SkRect* bounds) const; 257 void computeFastBounds(SkRect* bounds) const; 258 259 /** Find the parameter value where the conic takes on its maximum curvature. 260 * 261 * @param t output scalar for max curvature. Will be unchanged if 262 * max curvature outside 0..1 range. 263 * 264 * @return true if max curvature found inside 0..1 range, false otherwise 265 */ 266 bool findMaxCurvature(SkScalar* t) const; 267 }; 268 269 #include "SkTemplates.h" 270 271 /** 272 * Help class to allocate storage for approximating a conic with N quads. 273 */ 274 class SkAutoConicToQuads { 275 public: 276 SkAutoConicToQuads() : fQuadCount(0) {} 277 278 /** 279 * Given a conic and a tolerance, return the array of points for the 280 * approximating quad(s). Call countQuads() to know the number of quads 281 * represented in these points. 282 * 283 * The quads are allocated to share end-points. e.g. if there are 4 quads, 284 * there will be 9 points allocated as follows 285 * quad[0] == pts[0..2] 286 * quad[1] == pts[2..4] 287 * quad[2] == pts[4..6] 288 * quad[3] == pts[6..8] 289 */ 290 const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) { 291 int pow2 = conic.computeQuadPOW2(tol); 292 fQuadCount = 1 << pow2; 293 SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount); 294 conic.chopIntoQuadsPOW2(pts, pow2); 295 return pts; 296 } 297 298 const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight, 299 SkScalar tol) { 300 SkConic conic; 301 conic.set(pts, weight); 302 return computeQuads(conic, tol); 303 } 304 305 int countQuads() const { return fQuadCount; } 306 307 private: 308 enum { 309 kQuadCount = 8, // should handle most conics 310 kPointCount = 1 + 2 * kQuadCount, 311 }; 312 SkAutoSTMalloc<kPointCount, SkPoint> fStorage; 313 int fQuadCount; // #quads for current usage 314 }; 315 316 #endif 317
