The Tor Browser / file comparison
comparison: gfx/skia/trunk/include/core/SkGeometry.h
gfx/skia/trunk/include/core/SkGeometry.h
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:7eda8b52ef3a |
|---|---|
| 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 |
