SkGeometry.h revision 7839ce1af63bf12fe7b3caa866970bbbb3afb13d
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 */ 19typedef 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*/ 27bool 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*/ 33int 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*/ 40void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, 41 SkVector* tangent = NULL); 42void 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*/ 49void 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*/ 54void 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*/ 64int 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*/ 72int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 73int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 74 75/** Given 3 points on a quadratic bezier, divide it into 2 quadratics 76 if the point of maximum curvature exists on the quad segment. 77 Depending on what is returned, dst[] is treated as follows 78 1 dst[0..2] is the original quad 79 2 dst[0..2] and dst[2..4] are the two new quads 80 If dst == null, it is ignored and only the count is returned. 81*/ 82int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 83 84/** Given 3 points on a quadratic bezier, use degree elevation to 85 convert it into the cubic fitting the same curve. The new cubic 86 curve is returned in dst[0..3]. 87*/ 88SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 89 90/////////////////////////////////////////////////////////////////////////////// 91 92/** Convert from parametric from (pts) to polynomial coefficients 93 coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 94*/ 95void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); 96 97/** Set pt to the point on the src cubic specified by t. t must be 98 0 <= t <= 1.0 99*/ 100void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, 101 SkVector* tangentOrNull, SkVector* curvatureOrNull); 102 103/** Given a src cubic bezier, chop it at the specified t value, 104 where 0 < t < 1, and return the two new cubics in dst: 105 dst[0..3] and dst[3..6] 106*/ 107void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 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*/ 112void 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*/ 118void 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*/ 129int 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*/ 140int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 141int 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*/ 146int 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*/ 152int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 153 154int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 155int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 156 SkScalar tValues[3] = NULL); 157 158/** Given a monotonic cubic bezier, determine whether an xray intersects the 159 cubic. 160 By definition the cubic is open at the starting point; in other 161 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 162 left of the curve, the line is not considered to cross the curve, 163 but if it is equal to cubic[3].fY then it is considered to 164 cross. 165 Optional outgoing "ambiguous" argument indicates whether the answer is 166 ambiguous because the query occurred exactly at one of the endpoints' y 167 coordinates, indicating that another query y coordinate is preferred 168 for robustness. 169 */ 170bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], 171 bool* ambiguous = NULL); 172 173/** Given an arbitrary cubic bezier, return the number of times an xray crosses 174 the cubic. Valid return values are [0..3] 175 By definition the cubic is open at the starting point; in other 176 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 177 left of the curve, the line is not considered to cross the curve, 178 but if it is equal to cubic[3].fY then it is considered to 179 cross. 180 Optional outgoing "ambiguous" argument indicates whether the answer is 181 ambiguous because the query occurred exactly at one of the endpoints' y 182 coordinates or at a tangent point, indicating that another query y 183 coordinate is preferred for robustness. 184 */ 185int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], 186 bool* ambiguous = NULL); 187 188/////////////////////////////////////////////////////////////////////////////// 189 190enum SkRotationDirection { 191 kCW_SkRotationDirection, 192 kCCW_SkRotationDirection 193}; 194 195/** Maximum number of points needed in the quadPoints[] parameter for 196 SkBuildQuadArc() 197*/ 198#define kSkBuildQuadArcStorage 17 199 200/** Given 2 unit vectors and a rotation direction, fill out the specified 201 array of points with quadratic segments. Return is the number of points 202 written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 203 204 matrix, if not null, is appled to the points before they are returned. 205*/ 206int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 207 SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 208 209// experimental 210struct SkConic { 211 SkPoint fPts[3]; 212 SkScalar fW; 213 214 void set(const SkPoint pts[3], SkScalar w) { 215 memcpy(fPts, pts, 3 * sizeof(SkPoint)); 216 fW = w; 217 } 218 219 /** 220 * Given a t-value [0...1] return its position and/or tangent. 221 * If pos is not null, return its position at the t-value. 222 * If tangent is not null, return its tangent at the t-value. NOTE the 223 * tangent value's length is arbitrary, and only its direction should 224 * be used. 225 */ 226 void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const; 227 void chopAt(SkScalar t, SkConic dst[2]) const; 228 void chop(SkConic dst[2]) const; 229 230 void computeAsQuadError(SkVector* err) const; 231 bool asQuadTol(SkScalar tol) const; 232 233 int computeQuadPOW2(SkScalar tol) const; 234 int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const; 235 236 bool findXExtrema(SkScalar* t) const; 237 bool findYExtrema(SkScalar* t) const; 238 bool chopAtXExtrema(SkConic dst[2]) const; 239 bool chopAtYExtrema(SkConic dst[2]) const; 240 241 void computeTightBounds(SkRect* bounds) const; 242 void computeFastBounds(SkRect* bounds) const; 243}; 244 245#endif 246