1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/core/SkGeometry.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,316 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#ifndef SkGeometry_DEFINED
1.14 +#define SkGeometry_DEFINED
1.15 +
1.16 +#include "SkMatrix.h"
1.17 +
1.18 +/** An XRay is a half-line that runs from the specific point/origin to
1.19 + +infinity in the X direction. e.g. XRay(3,5) is the half-line
1.20 + (3,5)....(infinity, 5)
1.21 + */
1.22 +typedef SkPoint SkXRay;
1.23 +
1.24 +/** Given a line segment from pts[0] to pts[1], and an xray, return true if
1.25 + they intersect. Optional outgoing "ambiguous" argument indicates
1.26 + whether the answer is ambiguous because the query occurred exactly at
1.27 + one of the endpoints' y coordinates, indicating that another query y
1.28 + coordinate is preferred for robustness.
1.29 +*/
1.30 +bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2],
1.31 + bool* ambiguous = NULL);
1.32 +
1.33 +/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
1.34 + equation.
1.35 +*/
1.36 +int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
1.37 +
1.38 +///////////////////////////////////////////////////////////////////////////////
1.39 +
1.40 +/** Set pt to the point on the src quadratic specified by t. t must be
1.41 + 0 <= t <= 1.0
1.42 +*/
1.43 +void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt,
1.44 + SkVector* tangent = NULL);
1.45 +void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt,
1.46 + SkVector* tangent = NULL);
1.47 +
1.48 +/** Given a src quadratic bezier, chop it at the specified t value,
1.49 + where 0 < t < 1, and return the two new quadratics in dst:
1.50 + dst[0..2] and dst[2..4]
1.51 +*/
1.52 +void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t);
1.53 +
1.54 +/** Given a src quadratic bezier, chop it at the specified t == 1/2,
1.55 + The new quads are returned in dst[0..2] and dst[2..4]
1.56 +*/
1.57 +void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]);
1.58 +
1.59 +/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look
1.60 + for extrema, and return the number of t-values that are found that represent
1.61 + these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the
1.62 + function returns 0.
1.63 + Returned count tValues[]
1.64 + 0 ignored
1.65 + 1 0 < tValues[0] < 1
1.66 +*/
1.67 +int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]);
1.68 +
1.69 +/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that
1.70 + the resulting beziers are monotonic in Y. This is called by the scan converter.
1.71 + Depending on what is returned, dst[] is treated as follows
1.72 + 0 dst[0..2] is the original quad
1.73 + 1 dst[0..2] and dst[2..4] are the two new quads
1.74 +*/
1.75 +int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
1.76 +int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]);
1.77 +
1.78 +/** Given 3 points on a quadratic bezier, if the point of maximum
1.79 + curvature exists on the segment, returns the t value for this
1.80 + point along the curve. Otherwise it will return a value of 0.
1.81 +*/
1.82 +float SkFindQuadMaxCurvature(const SkPoint src[3]);
1.83 +
1.84 +/** Given 3 points on a quadratic bezier, divide it into 2 quadratics
1.85 + if the point of maximum curvature exists on the quad segment.
1.86 + Depending on what is returned, dst[] is treated as follows
1.87 + 1 dst[0..2] is the original quad
1.88 + 2 dst[0..2] and dst[2..4] are the two new quads
1.89 + If dst == null, it is ignored and only the count is returned.
1.90 +*/
1.91 +int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]);
1.92 +
1.93 +/** Given 3 points on a quadratic bezier, use degree elevation to
1.94 + convert it into the cubic fitting the same curve. The new cubic
1.95 + curve is returned in dst[0..3].
1.96 +*/
1.97 +SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]);
1.98 +
1.99 +///////////////////////////////////////////////////////////////////////////////
1.100 +
1.101 +/** Convert from parametric from (pts) to polynomial coefficients
1.102 + coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3]
1.103 +*/
1.104 +void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]);
1.105 +
1.106 +/** Set pt to the point on the src cubic specified by t. t must be
1.107 + 0 <= t <= 1.0
1.108 +*/
1.109 +void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull,
1.110 + SkVector* tangentOrNull, SkVector* curvatureOrNull);
1.111 +
1.112 +/** Given a src cubic bezier, chop it at the specified t value,
1.113 + where 0 < t < 1, and return the two new cubics in dst:
1.114 + dst[0..3] and dst[3..6]
1.115 +*/
1.116 +void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t);
1.117 +/** Given a src cubic bezier, chop it at the specified t values,
1.118 + where 0 < t < 1, and return the new cubics in dst:
1.119 + dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)]
1.120 +*/
1.121 +void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[],
1.122 + int t_count);
1.123 +
1.124 +/** Given a src cubic bezier, chop it at the specified t == 1/2,
1.125 + The new cubics are returned in dst[0..3] and dst[3..6]
1.126 +*/
1.127 +void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]);
1.128 +
1.129 +/** Given the 4 coefficients for a cubic bezier (either X or Y values), look
1.130 + for extrema, and return the number of t-values that are found that represent
1.131 + these extrema. If the cubic has no extrema betwee (0..1) exclusive, the
1.132 + function returns 0.
1.133 + Returned count tValues[]
1.134 + 0 ignored
1.135 + 1 0 < tValues[0] < 1
1.136 + 2 0 < tValues[0] < tValues[1] < 1
1.137 +*/
1.138 +int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
1.139 + SkScalar tValues[2]);
1.140 +
1.141 +/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
1.142 + the resulting beziers are monotonic in Y. This is called by the scan converter.
1.143 + Depending on what is returned, dst[] is treated as follows
1.144 + 0 dst[0..3] is the original cubic
1.145 + 1 dst[0..3] and dst[3..6] are the two new cubics
1.146 + 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics
1.147 + If dst == null, it is ignored and only the count is returned.
1.148 +*/
1.149 +int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
1.150 +int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]);
1.151 +
1.152 +/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the
1.153 + inflection points.
1.154 +*/
1.155 +int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]);
1.156 +
1.157 +/** Return 1 for no chop, 2 for having chopped the cubic at a single
1.158 + inflection point, 3 for having chopped at 2 inflection points.
1.159 + dst will hold the resulting 1, 2, or 3 cubics.
1.160 +*/
1.161 +int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
1.162 +
1.163 +int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
1.164 +int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
1.165 + SkScalar tValues[3] = NULL);
1.166 +
1.167 +/** Given a monotonic cubic bezier, determine whether an xray intersects the
1.168 + cubic.
1.169 + By definition the cubic is open at the starting point; in other
1.170 + words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the
1.171 + left of the curve, the line is not considered to cross the curve,
1.172 + but if it is equal to cubic[3].fY then it is considered to
1.173 + cross.
1.174 + Optional outgoing "ambiguous" argument indicates whether the answer is
1.175 + ambiguous because the query occurred exactly at one of the endpoints' y
1.176 + coordinates, indicating that another query y coordinate is preferred
1.177 + for robustness.
1.178 + */
1.179 +bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4],
1.180 + bool* ambiguous = NULL);
1.181 +
1.182 +/** Given an arbitrary cubic bezier, return the number of times an xray crosses
1.183 + the cubic. Valid return values are [0..3]
1.184 + By definition the cubic is open at the starting point; in other
1.185 + words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the
1.186 + left of the curve, the line is not considered to cross the curve,
1.187 + but if it is equal to cubic[3].fY then it is considered to
1.188 + cross.
1.189 + Optional outgoing "ambiguous" argument indicates whether the answer is
1.190 + ambiguous because the query occurred exactly at one of the endpoints' y
1.191 + coordinates or at a tangent point, indicating that another query y
1.192 + coordinate is preferred for robustness.
1.193 + */
1.194 +int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4],
1.195 + bool* ambiguous = NULL);
1.196 +
1.197 +///////////////////////////////////////////////////////////////////////////////
1.198 +
1.199 +enum SkRotationDirection {
1.200 + kCW_SkRotationDirection,
1.201 + kCCW_SkRotationDirection
1.202 +};
1.203 +
1.204 +/** Maximum number of points needed in the quadPoints[] parameter for
1.205 + SkBuildQuadArc()
1.206 +*/
1.207 +#define kSkBuildQuadArcStorage 17
1.208 +
1.209 +/** Given 2 unit vectors and a rotation direction, fill out the specified
1.210 + array of points with quadratic segments. Return is the number of points
1.211 + written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage }
1.212 +
1.213 + matrix, if not null, is appled to the points before they are returned.
1.214 +*/
1.215 +int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop,
1.216 + SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]);
1.217 +
1.218 +// experimental
1.219 +struct SkConic {
1.220 + SkPoint fPts[3];
1.221 + SkScalar fW;
1.222 +
1.223 + void set(const SkPoint pts[3], SkScalar w) {
1.224 + memcpy(fPts, pts, 3 * sizeof(SkPoint));
1.225 + fW = w;
1.226 + }
1.227 +
1.228 + /**
1.229 + * Given a t-value [0...1] return its position and/or tangent.
1.230 + * If pos is not null, return its position at the t-value.
1.231 + * If tangent is not null, return its tangent at the t-value. NOTE the
1.232 + * tangent value's length is arbitrary, and only its direction should
1.233 + * be used.
1.234 + */
1.235 + void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const;
1.236 + void chopAt(SkScalar t, SkConic dst[2]) const;
1.237 + void chop(SkConic dst[2]) const;
1.238 +
1.239 + void computeAsQuadError(SkVector* err) const;
1.240 + bool asQuadTol(SkScalar tol) const;
1.241 +
1.242 + /**
1.243 + * return the power-of-2 number of quads needed to approximate this conic
1.244 + * with a sequence of quads. Will be >= 0.
1.245 + */
1.246 + int computeQuadPOW2(SkScalar tol) const;
1.247 +
1.248 + /**
1.249 + * Chop this conic into N quads, stored continguously in pts[], where
1.250 + * N = 1 << pow2. The amount of storage needed is (1 + 2 * N)
1.251 + */
1.252 + int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
1.253 +
1.254 + bool findXExtrema(SkScalar* t) const;
1.255 + bool findYExtrema(SkScalar* t) const;
1.256 + bool chopAtXExtrema(SkConic dst[2]) const;
1.257 + bool chopAtYExtrema(SkConic dst[2]) const;
1.258 +
1.259 + void computeTightBounds(SkRect* bounds) const;
1.260 + void computeFastBounds(SkRect* bounds) const;
1.261 +
1.262 + /** Find the parameter value where the conic takes on its maximum curvature.
1.263 + *
1.264 + * @param t output scalar for max curvature. Will be unchanged if
1.265 + * max curvature outside 0..1 range.
1.266 + *
1.267 + * @return true if max curvature found inside 0..1 range, false otherwise
1.268 + */
1.269 + bool findMaxCurvature(SkScalar* t) const;
1.270 +};
1.271 +
1.272 +#include "SkTemplates.h"
1.273 +
1.274 +/**
1.275 + * Help class to allocate storage for approximating a conic with N quads.
1.276 + */
1.277 +class SkAutoConicToQuads {
1.278 +public:
1.279 + SkAutoConicToQuads() : fQuadCount(0) {}
1.280 +
1.281 + /**
1.282 + * Given a conic and a tolerance, return the array of points for the
1.283 + * approximating quad(s). Call countQuads() to know the number of quads
1.284 + * represented in these points.
1.285 + *
1.286 + * The quads are allocated to share end-points. e.g. if there are 4 quads,
1.287 + * there will be 9 points allocated as follows
1.288 + * quad[0] == pts[0..2]
1.289 + * quad[1] == pts[2..4]
1.290 + * quad[2] == pts[4..6]
1.291 + * quad[3] == pts[6..8]
1.292 + */
1.293 + const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
1.294 + int pow2 = conic.computeQuadPOW2(tol);
1.295 + fQuadCount = 1 << pow2;
1.296 + SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
1.297 + conic.chopIntoQuadsPOW2(pts, pow2);
1.298 + return pts;
1.299 + }
1.300 +
1.301 + const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
1.302 + SkScalar tol) {
1.303 + SkConic conic;
1.304 + conic.set(pts, weight);
1.305 + return computeQuads(conic, tol);
1.306 + }
1.307 +
1.308 + int countQuads() const { return fQuadCount; }
1.309 +
1.310 +private:
1.311 + enum {
1.312 + kQuadCount = 8, // should handle most conics
1.313 + kPointCount = 1 + 2 * kQuadCount,
1.314 + };
1.315 + SkAutoSTMalloc<kPointCount, SkPoint> fStorage;
1.316 + int fQuadCount; // #quads for current usage
1.317 +};
1.318 +
1.319 +#endif
