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, 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 */ 82 int 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 */ 88 SK_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 */ 95 void 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 */ 100 void 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 */ 107 void 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 */ 112 void 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 */ 118 void 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 */ 129 int 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 */ 140 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 141 int 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 */ 146 int 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 */ 152 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 153 154 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 155 int 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 */ 170 bool 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 */ 185 int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], 186 bool* ambiguous = NULL); 187 188 /////////////////////////////////////////////////////////////////////////////// 189 190 enum 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 */ 206 int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 207 SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 208 209 #endif 210