michael@0: /* michael@0: * Copyright 2011 Google Inc. michael@0: * michael@0: * Use of this source code is governed by a BSD-style license that can be michael@0: * found in the LICENSE file. michael@0: */ michael@0: michael@0: #ifndef GrPathUtils_DEFINED michael@0: #define GrPathUtils_DEFINED michael@0: michael@0: #include "GrPoint.h" michael@0: #include "SkRect.h" michael@0: #include "SkPath.h" michael@0: #include "SkTArray.h" michael@0: michael@0: class SkMatrix; michael@0: michael@0: /** michael@0: * Utilities for evaluating paths. michael@0: */ michael@0: namespace GrPathUtils { michael@0: SkScalar scaleToleranceToSrc(SkScalar devTol, michael@0: const SkMatrix& viewM, michael@0: const SkRect& pathBounds); michael@0: michael@0: /// Since we divide by tol if we're computing exact worst-case bounds, michael@0: /// very small tolerances will be increased to gMinCurveTol. michael@0: int worstCasePointCount(const SkPath&, michael@0: int* subpaths, michael@0: SkScalar tol); michael@0: michael@0: /// Since we divide by tol if we're computing exact worst-case bounds, michael@0: /// very small tolerances will be increased to gMinCurveTol. michael@0: uint32_t quadraticPointCount(const GrPoint points[], SkScalar tol); michael@0: michael@0: uint32_t generateQuadraticPoints(const GrPoint& p0, michael@0: const GrPoint& p1, michael@0: const GrPoint& p2, michael@0: SkScalar tolSqd, michael@0: GrPoint** points, michael@0: uint32_t pointsLeft); michael@0: michael@0: /// Since we divide by tol if we're computing exact worst-case bounds, michael@0: /// very small tolerances will be increased to gMinCurveTol. michael@0: uint32_t cubicPointCount(const GrPoint points[], SkScalar tol); michael@0: michael@0: uint32_t generateCubicPoints(const GrPoint& p0, michael@0: const GrPoint& p1, michael@0: const GrPoint& p2, michael@0: const GrPoint& p3, michael@0: SkScalar tolSqd, michael@0: GrPoint** points, michael@0: uint32_t pointsLeft); michael@0: michael@0: // A 2x3 matrix that goes from the 2d space coordinates to UV space where michael@0: // u^2-v = 0 specifies the quad. The matrix is determined by the control michael@0: // points of the quadratic. michael@0: class QuadUVMatrix { michael@0: public: michael@0: QuadUVMatrix() {}; michael@0: // Initialize the matrix from the control pts michael@0: QuadUVMatrix(const GrPoint controlPts[3]) { this->set(controlPts); } michael@0: void set(const GrPoint controlPts[3]); michael@0: michael@0: /** michael@0: * Applies the matrix to vertex positions to compute UV coords. This michael@0: * has been templated so that the compiler can easliy unroll the loop michael@0: * and reorder to avoid stalling for loads. The assumption is that a michael@0: * path renderer will have a small fixed number of vertices that it michael@0: * uploads for each quad. michael@0: * michael@0: * N is the number of vertices. michael@0: * STRIDE is the size of each vertex. michael@0: * UV_OFFSET is the offset of the UV values within each vertex. michael@0: * vertices is a pointer to the first vertex. michael@0: */ michael@0: template michael@0: void apply(const void* vertices) { michael@0: intptr_t xyPtr = reinterpret_cast(vertices); michael@0: intptr_t uvPtr = reinterpret_cast(vertices) + UV_OFFSET; michael@0: float sx = fM[0]; michael@0: float kx = fM[1]; michael@0: float tx = fM[2]; michael@0: float ky = fM[3]; michael@0: float sy = fM[4]; michael@0: float ty = fM[5]; michael@0: for (int i = 0; i < N; ++i) { michael@0: const GrPoint* xy = reinterpret_cast(xyPtr); michael@0: GrPoint* uv = reinterpret_cast(uvPtr); michael@0: uv->fX = sx * xy->fX + kx * xy->fY + tx; michael@0: uv->fY = ky * xy->fX + sy * xy->fY + ty; michael@0: xyPtr += STRIDE; michael@0: uvPtr += STRIDE; michael@0: } michael@0: } michael@0: private: michael@0: float fM[6]; michael@0: }; michael@0: michael@0: // Input is 3 control points and a weight for a bezier conic. Calculates the michael@0: // three linear functionals (K,L,M) that represent the implicit equation of the michael@0: // conic, K^2 - LM. michael@0: // michael@0: // Output: michael@0: // K = (klm[0], klm[1], klm[2]) michael@0: // L = (klm[3], klm[4], klm[5]) michael@0: // M = (klm[6], klm[7], klm[8]) michael@0: void getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]); michael@0: michael@0: // Converts a cubic into a sequence of quads. If working in device space michael@0: // use tolScale = 1, otherwise set based on stretchiness of the matrix. The michael@0: // result is sets of 3 points in quads (TODO: share endpoints in returned michael@0: // array) michael@0: // When we approximate a cubic {a,b,c,d} with a quadratic we may have to michael@0: // ensure that the new control point lies between the lines ab and cd. The michael@0: // convex path renderer requires this. It starts with a path where all the michael@0: // control points taken together form a convex polygon. It relies on this michael@0: // property and the quadratic approximation of cubics step cannot alter it. michael@0: // Setting constrainWithinTangents to true enforces this property. When this michael@0: // is true the cubic must be simple and dir must specify the orientation of michael@0: // the cubic. Otherwise, dir is ignored. michael@0: void convertCubicToQuads(const GrPoint p[4], michael@0: SkScalar tolScale, michael@0: bool constrainWithinTangents, michael@0: SkPath::Direction dir, michael@0: SkTArray* quads); michael@0: michael@0: // Chops the cubic bezier passed in by src, at the double point (intersection point) michael@0: // if the curve is a cubic loop. If it is a loop, there will be two parametric values for michael@0: // the double point: ls and ms. We chop the cubic at these values if they are between 0 and 1. michael@0: // Return value: michael@0: // Value of 3: ls and ms are both between (0,1), and dst will contain the three cubics, michael@0: // dst[0..3], dst[3..6], and dst[6..9] if dst is not NULL michael@0: // Value of 2: Only one of ls and ms are between (0,1), and dst will contain the two cubics, michael@0: // dst[0..3] and dst[3..6] if dst is not NULL michael@0: // Value of 1: Neither ls or ms are between (0,1), and dst will contain the one original cubic, michael@0: // dst[0..3] if dst is not NULL michael@0: // michael@0: // Optional KLM Calculation: michael@0: // The function can also return the KLM linear functionals for the chopped cubic implicit form michael@0: // of K^3 - LM. michael@0: // It will calculate a single set of KLM values that can be shared by all sub cubics, except michael@0: // for the subsection that is "the loop" the K and L values need to be negated. michael@0: // Output: michael@0: // klm: Holds the values for the linear functionals as: michael@0: // K = (klm[0], klm[1], klm[2]) michael@0: // L = (klm[3], klm[4], klm[5]) michael@0: // M = (klm[6], klm[7], klm[8]) michael@0: // klm_rev: These values are flags for the corresponding sub cubic saying whether or not michael@0: // the K and L values need to be flipped. A value of -1.f means flip K and L and michael@0: // a value of 1.f means do nothing. michael@0: // *****DO NOT FLIP M, JUST K AND L***** michael@0: // michael@0: // Notice that the klm lines are calculated in the same space as the input control points. michael@0: // If you transform the points the lines will also need to be transformed. This can be done michael@0: // by mapping the lines with the inverse-transpose of the matrix used to map the points. michael@0: int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = NULL, michael@0: SkScalar klm[9] = NULL, SkScalar klm_rev[3] = NULL); michael@0: michael@0: // Input is p which holds the 4 control points of a non-rational cubic Bezier curve. michael@0: // Output is the coefficients of the three linear functionals K, L, & M which michael@0: // represent the implicit form of the cubic as f(x,y,w) = K^3 - LM. The w term michael@0: // will always be 1. The output is stored in the array klm, where the values are: michael@0: // K = (klm[0], klm[1], klm[2]) michael@0: // L = (klm[3], klm[4], klm[5]) michael@0: // M = (klm[6], klm[7], klm[8]) michael@0: // michael@0: // Notice that the klm lines are calculated in the same space as the input control points. michael@0: // If you transform the points the lines will also need to be transformed. This can be done michael@0: // by mapping the lines with the inverse-transpose of the matrix used to map the points. michael@0: void getCubicKLM(const SkPoint p[4], SkScalar klm[9]); michael@0: }; michael@0: #endif