diff options
Diffstat (limited to 'chromium/third_party/skia/src/core/SkGeometry.h')
| -rw-r--r-- | chromium/third_party/skia/src/core/SkGeometry.h | 316 |
1 files changed, 316 insertions, 0 deletions
diff --git a/chromium/third_party/skia/src/core/SkGeometry.h b/chromium/third_party/skia/src/core/SkGeometry.h new file mode 100644 index 00000000000..119cfc68db5 --- /dev/null +++ b/chromium/third_party/skia/src/core/SkGeometry.h @@ -0,0 +1,316 @@ + +/* + * Copyright 2006 The Android Open Source Project + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + + +#ifndef SkGeometry_DEFINED +#define SkGeometry_DEFINED + +#include "SkMatrix.h" + +/** An XRay is a half-line that runs from the specific point/origin to + +infinity in the X direction. e.g. XRay(3,5) is the half-line + (3,5)....(infinity, 5) + */ +typedef SkPoint SkXRay; + +/** Given a line segment from pts[0] to pts[1], and an xray, return true if + they intersect. Optional outgoing "ambiguous" argument indicates + whether the answer is ambiguous because the query occurred exactly at + one of the endpoints' y coordinates, indicating that another query y + coordinate is preferred for robustness. +*/ +bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], + bool* ambiguous = NULL); + +/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the + equation. +*/ +int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); + +/////////////////////////////////////////////////////////////////////////////// + +/** Set pt to the point on the src quadratic specified by t. t must be + 0 <= t <= 1.0 +*/ +void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, + SkVector* tangent = NULL); +void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, + SkVector* tangent = NULL); + +/** Given a src quadratic bezier, chop it at the specified t value, + where 0 < t < 1, and return the two new quadratics in dst: + dst[0..2] and dst[2..4] +*/ +void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); + +/** Given a src quadratic bezier, chop it at the specified t == 1/2, + The new quads are returned in dst[0..2] and dst[2..4] +*/ +void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); + +/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look + for extrema, and return the number of t-values that are found that represent + these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the + function returns 0. + Returned count tValues[] + 0 ignored + 1 0 < tValues[0] < 1 +*/ +int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); + +/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that + the resulting beziers are monotonic in Y. This is called by the scan converter. + Depending on what is returned, dst[] is treated as follows + 0 dst[0..2] is the original quad + 1 dst[0..2] and dst[2..4] are the two new quads +*/ +int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); +int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); + +/** Given 3 points on a quadratic bezier, if the point of maximum + curvature exists on the segment, returns the t value for this + point along the curve. Otherwise it will return a value of 0. +*/ +float SkFindQuadMaxCurvature(const SkPoint src[3]); + +/** Given 3 points on a quadratic bezier, divide it into 2 quadratics + if the point of maximum curvature exists on the quad segment. + Depending on what is returned, dst[] is treated as follows + 1 dst[0..2] is the original quad + 2 dst[0..2] and dst[2..4] are the two new quads + If dst == null, it is ignored and only the count is returned. +*/ +int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); + +/** Given 3 points on a quadratic bezier, use degree elevation to + convert it into the cubic fitting the same curve. The new cubic + curve is returned in dst[0..3]. +*/ +SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); + +/////////////////////////////////////////////////////////////////////////////// + +/** Convert from parametric from (pts) to polynomial coefficients + coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] +*/ +void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); + +/** Set pt to the point on the src cubic specified by t. t must be + 0 <= t <= 1.0 +*/ +void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, + SkVector* tangentOrNull, SkVector* curvatureOrNull); + +/** Given a src cubic bezier, chop it at the specified t value, + where 0 < t < 1, and return the two new cubics in dst: + dst[0..3] and dst[3..6] +*/ +void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); +/** Given a src cubic bezier, chop it at the specified t values, + where 0 < t < 1, and return the new cubics in dst: + dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)] +*/ +void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[], + int t_count); + +/** Given a src cubic bezier, chop it at the specified t == 1/2, + The new cubics are returned in dst[0..3] and dst[3..6] +*/ +void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); + +/** Given the 4 coefficients for a cubic bezier (either X or Y values), look + for extrema, and return the number of t-values that are found that represent + these extrema. If the cubic has no extrema betwee (0..1) exclusive, the + function returns 0. + Returned count tValues[] + 0 ignored + 1 0 < tValues[0] < 1 + 2 0 < tValues[0] < tValues[1] < 1 +*/ +int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, + SkScalar tValues[2]); + +/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that + the resulting beziers are monotonic in Y. This is called by the scan converter. + Depending on what is returned, dst[] is treated as follows + 0 dst[0..3] is the original cubic + 1 dst[0..3] and dst[3..6] are the two new cubics + 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics + If dst == null, it is ignored and only the count is returned. +*/ +int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); +int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); + +/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the + inflection points. +*/ +int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); + +/** Return 1 for no chop, 2 for having chopped the cubic at a single + inflection point, 3 for having chopped at 2 inflection points. + dst will hold the resulting 1, 2, or 3 cubics. +*/ +int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); + +int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); +int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], + SkScalar tValues[3] = NULL); + +/** Given a monotonic cubic bezier, determine whether an xray intersects the + cubic. + By definition the cubic is open at the starting point; in other + words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the + left of the curve, the line is not considered to cross the curve, + but if it is equal to cubic[3].fY then it is considered to + cross. + Optional outgoing "ambiguous" argument indicates whether the answer is + ambiguous because the query occurred exactly at one of the endpoints' y + coordinates, indicating that another query y coordinate is preferred + for robustness. + */ +bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], + bool* ambiguous = NULL); + +/** Given an arbitrary cubic bezier, return the number of times an xray crosses + the cubic. Valid return values are [0..3] + By definition the cubic is open at the starting point; in other + words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the + left of the curve, the line is not considered to cross the curve, + but if it is equal to cubic[3].fY then it is considered to + cross. + Optional outgoing "ambiguous" argument indicates whether the answer is + ambiguous because the query occurred exactly at one of the endpoints' y + coordinates or at a tangent point, indicating that another query y + coordinate is preferred for robustness. + */ +int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], + bool* ambiguous = NULL); + +/////////////////////////////////////////////////////////////////////////////// + +enum SkRotationDirection { + kCW_SkRotationDirection, + kCCW_SkRotationDirection +}; + +/** Maximum number of points needed in the quadPoints[] parameter for + SkBuildQuadArc() +*/ +#define kSkBuildQuadArcStorage 17 + +/** Given 2 unit vectors and a rotation direction, fill out the specified + array of points with quadratic segments. Return is the number of points + written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } + + matrix, if not null, is appled to the points before they are returned. +*/ +int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, + SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); + +// experimental +struct SkConic { + SkPoint fPts[3]; + SkScalar fW; + + void set(const SkPoint pts[3], SkScalar w) { + memcpy(fPts, pts, 3 * sizeof(SkPoint)); + fW = w; + } + + /** + * Given a t-value [0...1] return its position and/or tangent. + * If pos is not null, return its position at the t-value. + * If tangent is not null, return its tangent at the t-value. NOTE the + * tangent value's length is arbitrary, and only its direction should + * be used. + */ + void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const; + void chopAt(SkScalar t, SkConic dst[2]) const; + void chop(SkConic dst[2]) const; + + void computeAsQuadError(SkVector* err) const; + bool asQuadTol(SkScalar tol) const; + + /** + * return the power-of-2 number of quads needed to approximate this conic + * with a sequence of quads. Will be >= 0. + */ + int computeQuadPOW2(SkScalar tol) const; + + /** + * Chop this conic into N quads, stored continguously in pts[], where + * N = 1 << pow2. The amount of storage needed is (1 + 2 * N) + */ + int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const; + + bool findXExtrema(SkScalar* t) const; + bool findYExtrema(SkScalar* t) const; + bool chopAtXExtrema(SkConic dst[2]) const; + bool chopAtYExtrema(SkConic dst[2]) const; + + void computeTightBounds(SkRect* bounds) const; + void computeFastBounds(SkRect* bounds) const; + + /** Find the parameter value where the conic takes on its maximum curvature. + * + * @param t output scalar for max curvature. Will be unchanged if + * max curvature outside 0..1 range. + * + * @return true if max curvature found inside 0..1 range, false otherwise + */ + bool findMaxCurvature(SkScalar* t) const; +}; + +#include "SkTemplates.h" + +/** + * Help class to allocate storage for approximating a conic with N quads. + */ +class SkAutoConicToQuads { +public: + SkAutoConicToQuads() : fQuadCount(0) {} + + /** + * Given a conic and a tolerance, return the array of points for the + * approximating quad(s). Call countQuads() to know the number of quads + * represented in these points. + * + * The quads are allocated to share end-points. e.g. if there are 4 quads, + * there will be 9 points allocated as follows + * quad[0] == pts[0..2] + * quad[1] == pts[2..4] + * quad[2] == pts[4..6] + * quad[3] == pts[6..8] + */ + const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) { + int pow2 = conic.computeQuadPOW2(tol); + fQuadCount = 1 << pow2; + SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount); + conic.chopIntoQuadsPOW2(pts, pow2); + return pts; + } + + const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight, + SkScalar tol) { + SkConic conic; + conic.set(pts, weight); + return computeQuads(conic, tol); + } + + int countQuads() const { return fQuadCount; } + +private: + enum { + kQuadCount = 8, // should handle most conics + kPointCount = 1 + 2 * kQuadCount, + }; + SkAutoSTMalloc<kPointCount, SkPoint> fStorage; + int fQuadCount; // #quads for current usage +}; + +#endif |