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 ax xray, return true if 30 they intersect. 31 */ 32 bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]); 33 34 /** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the 35 equation. 36 */ 37 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); 38 39 /////////////////////////////////////////////////////////////////////////////// 40 41 /** Set pt to the point on the src quadratic specified by t. t must be 42 0 <= t <= 1.0 43 */ 44 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = NULL); 45 void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent = NULL); 46 47 /** Given a src quadratic bezier, chop it at the specified t value, 48 where 0 < t < 1, and return the two new quadratics in dst: 49 dst[0..2] and dst[2..4] 50 */ 51 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); 52 53 /** Given a src quadratic bezier, chop it at the specified t == 1/2, 54 The new quads are returned in dst[0..2] and dst[2..4] 55 */ 56 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); 57 58 /** Given the 3 coefficients for a quadratic bezier (either X or Y values), look 59 for extrema, and return the number of t-values that are found that represent 60 these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the 61 function returns 0. 62 Returned count tValues[] 63 0 ignored 64 1 0 < tValues[0] < 1 65 */ 66 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); 67 68 /** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that 69 the resulting beziers are monotonic in Y. This is called by the scan converter. 70 Depending on what is returned, dst[] is treated as follows 71 0 dst[0..2] is the original quad 72 1 dst[0..2] and dst[2..4] are the two new quads 73 */ 74 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 75 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 76 77 /** Given 3 points on a quadratic bezier, divide it into 2 quadratics 78 if the point of maximum curvature exists on the quad segment. 79 Depending on what is returned, dst[] is treated as follows 80 1 dst[0..2] is the original quad 81 2 dst[0..2] and dst[2..4] are the two new quads 82 If dst == null, it is ignored and only the count is returned. 83 */ 84 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 85 86 /** Given 3 points on a quadratic bezier, use degree elevation to 87 convert it into the cubic fitting the same curve. The new cubic 88 curve is returned in dst[0..3]. 89 */ 90 void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 91 92 //////////////////////////////////////////////////////////////////////////////////////// 93 94 /** Convert from parametric from (pts) to polynomial coefficients 95 coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 96 */ 97 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); 98 99 /** Set pt to the point on the src cubic specified by t. t must be 100 0 <= t <= 1.0 101 */ 102 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, SkVector* tangentOrNull, SkVector* curvatureOrNull); 103 104 /** Given a src cubic bezier, chop it at the specified t value, 105 where 0 < t < 1, and return the two new cubics in dst: 106 dst[0..3] and dst[3..6] 107 */ 108 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 109 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], const SkScalar t[], int t_count); 110 111 /** Given a src cubic bezier, chop it at the specified t == 1/2, 112 The new cubics are returned in dst[0..3] and dst[3..6] 113 */ 114 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); 115 116 /** Given the 4 coefficients for a cubic bezier (either X or Y values), look 117 for extrema, and return the number of t-values that are found that represent 118 these extrema. If the cubic has no extrema betwee (0..1) exclusive, the 119 function returns 0. 120 Returned count tValues[] 121 0 ignored 122 1 0 < tValues[0] < 1 123 2 0 < tValues[0] < tValues[1] < 1 124 */ 125 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2]); 126 127 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 128 the resulting beziers are monotonic in Y. This is called by the scan converter. 129 Depending on what is returned, dst[] is treated as follows 130 0 dst[0..3] is the original cubic 131 1 dst[0..3] and dst[3..6] are the two new cubics 132 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 133 If dst == null, it is ignored and only the count is returned. 134 */ 135 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 136 int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); 137 138 /** Given a cubic bezier, return 0, 1, or 2 t-values that represent the 139 inflection points. 140 */ 141 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); 142 143 /** Return 1 for no chop, or 2 for having chopped the cubic at its 144 inflection point. 145 */ 146 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 147 148 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 149 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3] = NULL); 150 151 /** Given a monotonic cubic bezier, determine whether an xray intersects the 152 cubic. 153 By definition the cubic is open at the starting point; in other 154 words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 155 left of the curve, the line is not considered to cross the curve, 156 but if it is equal to cubic[3].fY then it is considered to 157 cross. 158 */ 159 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]); 160 161 /** Given an arbitrary cubic bezier, return the number of times an xray crosses 162 the cubic. Valid return values are [0..3] 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 */ 169 int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4]); 170 171 /////////////////////////////////////////////////////////////////////////////////////////// 172 173 enum SkRotationDirection { 174 kCW_SkRotationDirection, 175 kCCW_SkRotationDirection 176 }; 177 178 /** Maximum number of points needed in the quadPoints[] parameter for 179 SkBuildQuadArc() 180 */ 181 #define kSkBuildQuadArcStorage 17 182 183 /** Given 2 unit vectors and a rotation direction, fill out the specified 184 array of points with quadratic segments. Return is the number of points 185 written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 186 187 matrix, if not null, is appled to the points before they are returned. 188 */ 189 int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, SkRotationDirection, 190 const SkMatrix* matrix, SkPoint quadPoints[]); 191 192 #endif 193
