blob: 250b0a23245a2b81c22e73fb6e97e70ae0333b19 [file] [log] [blame]
/*
* 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 "SkRect.h"
#include "SkPath.h"
#include "SkTArray.h"
class SkMatrix;
/**
* Utilities for evaluating paths.
*/
namespace GrPathUtils {
SkScalar scaleToleranceToSrc(SkScalar devTol,
const SkMatrix& viewM,
const SkRect& pathBounds);
/// Since we divide by tol if we're computing exact worst-case bounds,
/// very small tolerances will be increased to gMinCurveTol.
int worstCasePointCount(const SkPath&,
int* subpaths,
SkScalar tol);
/// Since we divide by tol if we're computing exact worst-case bounds,
/// very small tolerances will be increased to gMinCurveTol.
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);
/// Since we divide by tol if we're computing exact worst-case bounds,
/// very small tolerances will be increased to gMinCurveTol.
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. This
* has been templated so that the compiler can easliy unroll the loop
* and reorder to avoid stalling for loads. The assumption is that a
* path renderer will have a small fixed number of vertices that it
* uploads for each quad.
*
* N is the number of vertices.
* STRIDE is the size of each vertex.
* UV_OFFSET is the offset of the UV values within each vertex.
* vertices is a pointer to the first vertex.
*/
template <int N, size_t STRIDE, size_t UV_OFFSET>
void apply(const void* vertices) {
intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + UV_OFFSET;
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 < N; ++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:
// K = (klm[0], klm[1], klm[2])
// L = (klm[3], klm[4], klm[5])
// M = (klm[6], klm[7], klm[8])
void getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]);
// 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 (TODO: share endpoints in returned
// array)
// 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.
// Setting constrainWithinTangents to true enforces this property. When this
// is true the cubic must be simple and dir must specify the orientation of
// the cubic. Otherwise, dir is ignored.
void convertCubicToQuads(const SkPoint p[4],
SkScalar tolScale,
bool constrainWithinTangents,
SkPath::Direction dir,
SkTArray<SkPoint, true>* quads);
// 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: ls and ms. We chop the cubic at these values if they are between 0 and 1.
// Return value:
// Value of 3: ls and ms 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 NULL
// Value of 2: Only one of ls and ms are between (0,1), and dst will contain the two cubics,
// dst[0..3] and dst[3..6] if dst is not NULL
// Value of 1: Neither ls or ms are between (0,1), and dst will contain the one original cubic,
// dst[0..3] if dst is not NULL
//
// Optional KLM Calculation:
// The function can also return the KLM linear functionals for the chopped cubic implicit form
// of K^3 - LM.
// It will calculate a single set of KLM values that can be shared by all sub cubics, except
// for the subsection that is "the loop" the K and L values need to be negated.
// Output:
// klm: Holds the values for the linear functionals as:
// K = (klm[0], klm[1], klm[2])
// L = (klm[3], klm[4], klm[5])
// M = (klm[6], klm[7], klm[8])
// klm_rev: These values are flags for the corresponding sub cubic saying whether or not
// the K and L values need to be flipped. A value of -1.f means flip K and L and
// a value of 1.f means do nothing.
// *****DO NOT FLIP M, JUST K AND L*****
//
// Notice that 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.
int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = NULL,
SkScalar klm[9] = NULL, SkScalar klm_rev[3] = NULL);
// Input is p which holds the 4 control points of a non-rational cubic Bezier curve.
// Output is the coefficients of the three linear functionals K, L, & M which
// represent the implicit form of the cubic as f(x,y,w) = K^3 - LM. The w term
// will always be 1. The output is stored in the array klm, where the values are:
// K = (klm[0], klm[1], klm[2])
// L = (klm[3], klm[4], klm[5])
// M = (klm[6], klm[7], klm[8])
//
// Notice that 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.
void getCubicKLM(const SkPoint p[4], SkScalar klm[9]);
// 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);
};
#endif