/*
|
* Copyright 2011 Google Inc.
|
*
|
* Use of this source code is governed by a BSD-style license that can be
|
* found in the LICENSE file.
|
*/
|
|
#ifndef GrPathUtils_DEFINED
|
#define GrPathUtils_DEFINED
|
|
#include "SkGeometry.h"
|
#include "SkRect.h"
|
#include "SkPathPriv.h"
|
#include "SkTArray.h"
|
|
class SkMatrix;
|
|
/**
|
* Utilities for evaluating paths.
|
*/
|
namespace GrPathUtils {
|
// Very small tolerances will be increased to a minimum threshold value, to avoid division
|
// problems in subsequent math.
|
SkScalar scaleToleranceToSrc(SkScalar devTol,
|
const SkMatrix& viewM,
|
const SkRect& pathBounds);
|
|
int worstCasePointCount(const SkPath&,
|
int* subpaths,
|
SkScalar tol);
|
|
uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
|
|
uint32_t generateQuadraticPoints(const SkPoint& p0,
|
const SkPoint& p1,
|
const SkPoint& p2,
|
SkScalar tolSqd,
|
SkPoint** points,
|
uint32_t pointsLeft);
|
|
uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
|
|
uint32_t generateCubicPoints(const SkPoint& p0,
|
const SkPoint& p1,
|
const SkPoint& p2,
|
const SkPoint& p3,
|
SkScalar tolSqd,
|
SkPoint** points,
|
uint32_t pointsLeft);
|
|
// A 2x3 matrix that goes from the 2d space coordinates to UV space where
|
// u^2-v = 0 specifies the quad. The matrix is determined by the control
|
// points of the quadratic.
|
class QuadUVMatrix {
|
public:
|
QuadUVMatrix() {}
|
// Initialize the matrix from the control pts
|
QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); }
|
void set(const SkPoint controlPts[3]);
|
|
/**
|
* Applies the matrix to vertex positions to compute UV coords.
|
*
|
* vertices is a pointer to the first vertex.
|
* vertexCount is the number of vertices.
|
* stride is the size of each vertex.
|
* uvOffset is the offset of the UV values within each vertex.
|
*/
|
void apply(void* vertices, int vertexCount, size_t stride, size_t uvOffset) const {
|
intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
|
intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + uvOffset;
|
float sx = fM[0];
|
float kx = fM[1];
|
float tx = fM[2];
|
float ky = fM[3];
|
float sy = fM[4];
|
float ty = fM[5];
|
for (int i = 0; i < vertexCount; ++i) {
|
const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr);
|
SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr);
|
uv->fX = sx * xy->fX + kx * xy->fY + tx;
|
uv->fY = ky * xy->fX + sy * xy->fY + ty;
|
xyPtr += stride;
|
uvPtr += stride;
|
}
|
}
|
private:
|
float fM[6];
|
};
|
|
// Input is 3 control points and a weight for a bezier conic. Calculates the
|
// three linear functionals (K,L,M) that represent the implicit equation of the
|
// conic, k^2 - lm.
|
//
|
// Output: klm holds the linear functionals K,L,M as row vectors:
|
//
|
// | ..K.. | | x | | k |
|
// | ..L.. | * | y | == | l |
|
// | ..M.. | | 1 | | m |
|
//
|
void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm);
|
|
// Converts a cubic into a sequence of quads. If working in device space
|
// use tolScale = 1, otherwise set based on stretchiness of the matrix. The
|
// result is sets of 3 points in quads. This will preserve the starting and
|
// ending tangent vectors (modulo FP precision).
|
void convertCubicToQuads(const SkPoint p[4],
|
SkScalar tolScale,
|
SkTArray<SkPoint, true>* quads);
|
|
// When we approximate a cubic {a,b,c,d} with a quadratic we may have to
|
// ensure that the new control point lies between the lines ab and cd. The
|
// convex path renderer requires this. It starts with a path where all the
|
// control points taken together form a convex polygon. It relies on this
|
// property and the quadratic approximation of cubics step cannot alter it.
|
// This variation enforces this constraint. The cubic must be simple and dir
|
// must specify the orientation of the contour containing the cubic.
|
void convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
|
SkScalar tolScale,
|
SkPathPriv::FirstDirection dir,
|
SkTArray<SkPoint, true>* quads);
|
|
enum class ExcludedTerm {
|
kNonInvertible,
|
kQuadraticTerm,
|
kLinearTerm
|
};
|
|
// Computes the inverse-transpose of the cubic's power basis matrix, after removing a specific
|
// row of coefficients.
|
//
|
// E.g. if the cubic is defined in power basis form as follows:
|
//
|
// | x3 y3 0 |
|
// C(t,s) = [t^3 t^2*s t*s^2 s^3] * | x2 y2 0 |
|
// | x1 y1 0 |
|
// | x0 y0 1 |
|
//
|
// And the excluded term is "kQuadraticTerm", then the resulting inverse-transpose will be:
|
//
|
// | x3 y3 0 | -1 T
|
// | x1 y1 0 |
|
// | x0 y0 1 |
|
//
|
// (The term to exclude is chosen based on maximizing the resulting matrix determinant.)
|
//
|
// This can be used to find the KLM linear functionals:
|
//
|
// | ..K.. | | ..kcoeffs.. |
|
// | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix
|
// | ..M.. | | ..mcoeffs.. |
|
//
|
// NOTE: the same term that was excluded here must also be removed from the corresponding column
|
// of the klmcoeffs matrix.
|
//
|
// Returns which row of coefficients was removed, or kNonInvertible if the cubic was degenerate.
|
ExcludedTerm calcCubicInverseTransposePowerBasisMatrix(const SkPoint p[4], SkMatrix* out);
|
|
// Computes the KLM linear functionals for the cubic implicit form. The "right" side of the
|
// curve (when facing in the direction of increasing parameter values) will be the area that
|
// satisfies:
|
//
|
// k^3 < l*m
|
//
|
// Output:
|
//
|
// klm: Holds the linear functionals K,L,M as row vectors:
|
//
|
// | ..K.. | | x | | k |
|
// | ..L.. | * | y | == | l |
|
// | ..M.. | | 1 | | m |
|
//
|
// NOTE: the KLM lines are calculated in the same space as the input control points. If you
|
// transform the points the lines will also need to be transformed. This can be done by mapping
|
// the lines with the inverse-transpose of the matrix used to map the points.
|
//
|
// t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M
|
// intersect with K (See SkClassifyCubic).
|
//
|
// Returns the cubic's classification.
|
SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]);
|
|
// Chops the cubic bezier passed in by src, at the double point (intersection point)
|
// if the curve is a cubic loop. If it is a loop, there will be two parametric values for
|
// the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
|
// Return value:
|
// Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics,
|
// dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr
|
// Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
|
// dst[0..3] and dst[3..6] if dst is not nullptr
|
// Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
|
// src[0..3]
|
//
|
// Output:
|
//
|
// klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().)
|
//
|
// loopIndex: This value will tell the caller which of the chopped sections (if any) are the
|
// actual loop. A value of -1 means there is no loop section. The caller can then use
|
// this value to decide how/if they want to flip the orientation of this section.
|
// The flip should be done by negating the k and l values as follows:
|
//
|
// KLM.postScale(-1, -1)
|
int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
|
int* loopIndex);
|
|
// When tessellating curved paths into linear segments, this defines the maximum distance
|
// in screen space which a segment may deviate from the mathmatically correct value.
|
// Above this value, the segment will be subdivided.
|
// This value was chosen to approximate the supersampling accuracy of the raster path (16
|
// samples, or one quarter pixel).
|
static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
|
|
// We guarantee that no quad or cubic will ever produce more than this many points
|
static const int kMaxPointsPerCurve = 1 << 10;
|
};
|
#endif
|
