| |
| /* |
| * 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; |
| }; |
| |
| #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 |