xref: /external/skia/src/core/SkGeometry.h

/*
 * 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, 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 SkRationalQuad {
    SkPoint  fPts[3];
    SkScalar fW;

    void set(const SkPoint pts[3], SkScalar w) {
        memcpy(fPts, pts, 3 * sizeof(SkPoint));
        fW = w;
    }

    void evalAt(SkScalar t, SkPoint* pt) const;
    void chopAt(SkScalar t, SkRationalQuad dst[2]) const;
    void chop(SkRationalQuad dst[2]) const;

    int computeQuadPOW2(SkScalar tol) const;
    int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;

    bool findXExtrema(SkScalar* t) const;
    bool findYExtrema(SkScalar* t) const;
    bool chopAtXExtrema(SkRationalQuad dst[2]) const;
    bool chopAtYExtrema(SkRationalQuad dst[2]) const;
};

#endif