1 /* libs/graphics/sgl/SkGeometry.h 2 ** 3 ** Copyright 2006, The Android Open Source Project 4 ** 5 ** Licensed under the Apache License, Version 2.0 (the "License"); 6 ** you may not use this file except in compliance with the License. 7 ** You may obtain a copy of the License at 8 ** 9 ** http://www.apache.org/licenses/LICENSE-2.0 10 ** 11 ** Unless required by applicable law or agreed to in writing, software 12 ** distributed under the License is distributed on an "AS IS" BASIS, 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 ** See the License for the specific language governing permissions and 15 ** limitations under the License. 16 */ 17 18 #ifndef SkGeometry_DEFINED 19 #define SkGeometry_DEFINED 20 21 #include "SkMatrix.h" 22 23 /** An XRay is a half-line that runs from the specific point/origin to 24 +infinity in the X direction. e.g. XRay(3,5) is the half-line 25 (3,5)....(infinity, 5) 26 */ 27 typedef SkPoint SkXRay; 28 29 /** Given a line segment from pts[0] to pts[1], and an xray, return true if 30 they intersect. Optional outgoing "ambiguous" argument indicates 31 whether the answer is ambiguous because the query occurred exactly at 32 one of the endpoints' y coordinates, indicating that another query y 33 coordinate is preferred for robustness. 34 */ 35 bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], 36 bool* ambiguous = NULL); 37 38 /** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the 39 equation. 40 */ 41 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); 42 43 /////////////////////////////////////////////////////////////////////////////// 44 45 /** Set pt to the point on the src quadratic specified by t. t must be 46 0 <= t <= 1.0 47 */ 48 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, 49 SkVector* tangent = NULL); 50 void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, 51 SkVector* tangent = NULL); 52 53 /** Given a src quadratic bezier, chop it at the specified t value, 54 where 0 < t < 1, and return the two new quadratics in dst: 55 dst[0..2] and dst[2..4] 56 */ 57 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); 58 59 /** Given a src quadratic bezier, chop it at the specified t == 1/2, 60 The new quads are returned in dst[0..2] and dst[2..4] 61 */ 62 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); 63 64 /** Given the 3 coefficients for a quadratic bezier (either X or Y values), look 65 for extrema, and return the number of t-values that are found that represent 66 these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the 67 function returns 0. 68 Returned count tValues[] 69 0 ignored 70 1 0 < tValues[0] < 1 71 */ 72 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); 73 74 /** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that 75 the resulting beziers are monotonic in Y. This is called by the scan converter. 76 Depending on what is returned, dst[] is treated as follows 77 0 dst[0..2] is the original quad 78 1 dst[0..2] and dst[2..4] are the two new quads 79 */ 80 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 81 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 82 83 /** Given 3 points on a quadratic bezier, divide it into 2 quadratics 84 if the point of maximum curvature exists on the quad segment. 85 Depending on what is returned, dst[] is treated as follows 86 1 dst[0..2] is the original quad 87 2 dst[0..2] and dst[2..4] are the two new quads 88 If dst == null, it is ignored and only the count is returned. 89 */ 90 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 91 92 /** Given 3 points on a quadratic bezier, use degree elevation to 93 convert it into the cubic fitting the same curve. The new cubic 94 curve is returned in dst[0..3]. 95 */ 96 SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 97 98 /////////////////////////////////////////////////////////////////////////////// 99 100 /** Convert from parametric from (pts) to polynomial coefficients 101 coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 102 */ 103 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); 104 105 /** Set pt to the point on the src cubic specified by t. t must be 106 0 <= t <= 1.0 107 */ 108 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, 109 SkVector* tangentOrNull, SkVector* curvatureOrNull); 110 111 /** Given a src cubic bezier, chop it at the specified t value, 112 where 0 < t < 1, and return the two new cubics in dst: 113 dst[0..3] and dst[3..6] 114 */ 115 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 116 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], const SkScalar t[], 117 int t_count); 118 119 /** Given a src cubic bezier, chop it at the specified t == 1/2, 120 The new cubics are returned in dst[0..3] and dst[3..6] 121 */ 122 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); 123 124 /** Given the 4 coefficients for a cubic bezier (either X or Y values), look 125 for extrema, and return the number of t-values that are found that represent 126 these extrema. If the cubic has no extrema betwee (0..1) exclusive, the 127 function returns 0. 128 Returned count tValues[] 129 0 ignored 130 1 0 < tValues[0] < 1 131 2 0 < tValues[0] < tValues[1] < 1 132 */ 133 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 134 SkScalar tValues[2]); 135 136 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 137 the resulting beziers are monotonic in Y. This is called by the scan converter. 138 Depending on what is returned, dst[] is treated as follows 139 0 dst[0..3] is the original cubic 140 1 dst[0..3] and dst[3..6] are the two new cubics 141 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 142 If dst == null, it is ignored and only the count is returned. 143 */ 144 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 145 int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); 146 147 /** Given a cubic bezier, return 0, 1, or 2 t-values that represent the 148 inflection points. 149 */ 150 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); 151 152 /** Return 1 for no chop, or 2 for having chopped the cubic at its 153 inflection point. 154 */ 155 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 156 157 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 158 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 159 SkScalar tValues[3] = NULL); 160 161 /** Given a monotonic cubic bezier, determine whether an xray intersects the 162 cubic. 163 By definition the cubic is open at the starting point; in other 164 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 165 left of the curve, the line is not considered to cross the curve, 166 but if it is equal to cubic[3].fY then it is considered to 167 cross. 168 Optional outgoing "ambiguous" argument indicates whether the answer is 169 ambiguous because the query occurred exactly at one of the endpoints' y 170 coordinates, indicating that another query y coordinate is preferred 171 for robustness. 172 */ 173 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], 174 bool* ambiguous = NULL); 175 176 /** Given an arbitrary cubic bezier, return the number of times an xray crosses 177 the cubic. Valid return values are [0..3] 178 By definition the cubic is open at the starting point; in other 179 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 180 left of the curve, the line is not considered to cross the curve, 181 but if it is equal to cubic[3].fY then it is considered to 182 cross. 183 Optional outgoing "ambiguous" argument indicates whether the answer is 184 ambiguous because the query occurred exactly at one of the endpoints' y 185 coordinates or at a tangent point, indicating that another query y 186 coordinate is preferred for robustness. 187 */ 188 int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], 189 bool* ambiguous = NULL); 190 191 /////////////////////////////////////////////////////////////////////////////// 192 193 enum SkRotationDirection { 194 kCW_SkRotationDirection, 195 kCCW_SkRotationDirection 196 }; 197 198 /** Maximum number of points needed in the quadPoints[] parameter for 199 SkBuildQuadArc() 200 */ 201 #define kSkBuildQuadArcStorage 17 202 203 /** Given 2 unit vectors and a rotation direction, fill out the specified 204 array of points with quadratic segments. Return is the number of points 205 written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 206 207 matrix, if not null, is appled to the points before they are returned. 208 */ 209 int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 210 SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 211 212 #endif 213