blob: 71f6e0b9c1ef4ff240ace9da79f8643960263d6c [file] [log] [blame]
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +00001/*
epoger@google.comec3ed6a2011-07-28 14:26:00 +00002 * Copyright 2011 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +00006 */
7
8#ifndef GrPathUtils_DEFINED
9#define GrPathUtils_DEFINED
10
commit-bot@chromium.orgfd03d4a2013-07-17 21:39:42 +000011#include "GrPoint.h"
12#include "SkRect.h"
bsalomon@google.com8d033a12012-04-27 15:52:53 +000013#include "SkPath.h"
bsalomon@google.com69cc6ad2012-01-17 14:25:10 +000014#include "SkTArray.h"
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +000015
bsalomon@google.comb9086a02012-11-01 18:02:54 +000016class SkMatrix;
17
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +000018/**
19 * Utilities for evaluating paths.
20 */
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000021namespace GrPathUtils {
bsalomon@google.com81712882012-11-01 17:12:34 +000022 SkScalar scaleToleranceToSrc(SkScalar devTol,
bsalomon@google.comb9086a02012-11-01 18:02:54 +000023 const SkMatrix& viewM,
commit-bot@chromium.orgfd03d4a2013-07-17 21:39:42 +000024 const SkRect& pathBounds);
tomhudson@google.comc10a8882011-06-28 15:19:32 +000025
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000026 /// Since we divide by tol if we're computing exact worst-case bounds,
27 /// very small tolerances will be increased to gMinCurveTol.
bsalomon@google.com8d033a12012-04-27 15:52:53 +000028 int worstCasePointCount(const SkPath&,
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000029 int* subpaths,
bsalomon@google.com81712882012-11-01 17:12:34 +000030 SkScalar tol);
bsalomon@google.com19713172012-03-15 13:51:08 +000031
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000032 /// Since we divide by tol if we're computing exact worst-case bounds,
33 /// very small tolerances will be increased to gMinCurveTol.
bsalomon@google.com81712882012-11-01 17:12:34 +000034 uint32_t quadraticPointCount(const GrPoint points[], SkScalar tol);
bsalomon@google.com19713172012-03-15 13:51:08 +000035
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000036 uint32_t generateQuadraticPoints(const GrPoint& p0,
37 const GrPoint& p1,
38 const GrPoint& p2,
bsalomon@google.com81712882012-11-01 17:12:34 +000039 SkScalar tolSqd,
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000040 GrPoint** points,
41 uint32_t pointsLeft);
bsalomon@google.com19713172012-03-15 13:51:08 +000042
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000043 /// Since we divide by tol if we're computing exact worst-case bounds,
44 /// very small tolerances will be increased to gMinCurveTol.
bsalomon@google.com81712882012-11-01 17:12:34 +000045 uint32_t cubicPointCount(const GrPoint points[], SkScalar tol);
bsalomon@google.com19713172012-03-15 13:51:08 +000046
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000047 uint32_t generateCubicPoints(const GrPoint& p0,
48 const GrPoint& p1,
49 const GrPoint& p2,
50 const GrPoint& p3,
bsalomon@google.com81712882012-11-01 17:12:34 +000051 SkScalar tolSqd,
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000052 GrPoint** points,
53 uint32_t pointsLeft);
bsalomon@google.com19713172012-03-15 13:51:08 +000054
55 // A 2x3 matrix that goes from the 2d space coordinates to UV space where
56 // u^2-v = 0 specifies the quad. The matrix is determined by the control
57 // points of the quadratic.
58 class QuadUVMatrix {
59 public:
60 QuadUVMatrix() {};
61 // Initialize the matrix from the control pts
62 QuadUVMatrix(const GrPoint controlPts[3]) { this->set(controlPts); }
63 void set(const GrPoint controlPts[3]);
64
65 /**
66 * Applies the matrix to vertex positions to compute UV coords. This
67 * has been templated so that the compiler can easliy unroll the loop
68 * and reorder to avoid stalling for loads. The assumption is that a
69 * path renderer will have a small fixed number of vertices that it
70 * uploads for each quad.
71 *
72 * N is the number of vertices.
73 * STRIDE is the size of each vertex.
74 * UV_OFFSET is the offset of the UV values within each vertex.
75 * vertices is a pointer to the first vertex.
76 */
77 template <int N, size_t STRIDE, size_t UV_OFFSET>
78 void apply(const void* vertices) {
79 intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
80 intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + UV_OFFSET;
81 float sx = fM[0];
82 float kx = fM[1];
83 float tx = fM[2];
84 float ky = fM[3];
85 float sy = fM[4];
86 float ty = fM[5];
87 for (int i = 0; i < N; ++i) {
88 const GrPoint* xy = reinterpret_cast<const GrPoint*>(xyPtr);
89 GrPoint* uv = reinterpret_cast<GrPoint*>(uvPtr);
90 uv->fX = sx * xy->fX + kx * xy->fY + tx;
91 uv->fY = ky * xy->fX + sy * xy->fY + ty;
92 xyPtr += STRIDE;
93 uvPtr += STRIDE;
94 }
95 }
96 private:
97 float fM[6];
98 };
99
commit-bot@chromium.org13948402013-08-20 17:55:43 +0000100 // Input is 3 control points and a weight for a bezier conic. Calculates the
101 // three linear functionals (K,L,M) that represent the implicit equation of the
102 // conic, K^2 - LM.
103 //
104 // Output:
105 // K = (klm[0], klm[1], klm[2])
106 // L = (klm[3], klm[4], klm[5])
107 // M = (klm[6], klm[7], klm[8])
108 void getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]);
bsalomon@google.coma51ab842012-07-10 19:53:34 +0000109
bsalomon@google.com69cc6ad2012-01-17 14:25:10 +0000110 // Converts a cubic into a sequence of quads. If working in device space
111 // use tolScale = 1, otherwise set based on stretchiness of the matrix. The
112 // result is sets of 3 points in quads (TODO: share endpoints in returned
113 // array)
bsalomon@google.coma51ab842012-07-10 19:53:34 +0000114 // When we approximate a cubic {a,b,c,d} with a quadratic we may have to
115 // ensure that the new control point lies between the lines ab and cd. The
116 // convex path renderer requires this. It starts with a path where all the
117 // control points taken together form a convex polygon. It relies on this
118 // property and the quadratic approximation of cubics step cannot alter it.
119 // Setting constrainWithinTangents to true enforces this property. When this
120 // is true the cubic must be simple and dir must specify the orientation of
121 // the cubic. Otherwise, dir is ignored.
bsalomon@google.com69cc6ad2012-01-17 14:25:10 +0000122 void convertCubicToQuads(const GrPoint p[4],
123 SkScalar tolScale,
bsalomon@google.coma51ab842012-07-10 19:53:34 +0000124 bool constrainWithinTangents,
125 SkPath::Direction dir,
bsalomon@google.com69cc6ad2012-01-17 14:25:10 +0000126 SkTArray<SkPoint, true>* quads);
commit-bot@chromium.org858638d2013-08-20 14:45:45 +0000127
128 // Chops the cubic bezier passed in by src, at the double point (intersection point)
129 // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
130 // the double point: ls and ms. We chop the cubic at these values if they are between 0 and 1.
131 // Return value:
132 // Value of 3: ls and ms are both between (0,1), and dst will contain the three cubics,
133 // dst[0..3], dst[3..6], and dst[6..9] if dst is not NULL
134 // Value of 2: Only one of ls and ms are between (0,1), and dst will contain the two cubics,
135 // dst[0..3] and dst[3..6] if dst is not NULL
136 // Value of 1: Neither ls or ms are between (0,1), and dst will contain the one original cubic,
137 // dst[0..3] if dst is not NULL
138 //
139 // Optional KLM Calculation:
140 // The function can also return the KLM linear functionals for the chopped cubic implicit form
141 // of K^3 - LM.
142 // It will calculate a single set of KLM values that can be shared by all sub cubics, except
143 // for the subsection that is "the loop" the K and L values need to be negated.
144 // Output:
145 // klm: Holds the values for the linear functionals as:
146 // K = (klm[0], klm[1], klm[2])
147 // L = (klm[3], klm[4], klm[5])
148 // M = (klm[6], klm[7], klm[8])
149 // klm_rev: These values are flags for the corresponding sub cubic saying whether or not
150 // the K and L values need to be flipped. A value of -1.f means flip K and L and
151 // a value of 1.f means do nothing.
152 // *****DO NOT FLIP M, JUST K AND L*****
153 //
154 // Notice that the klm lines are calculated in the same space as the input control points.
155 // If you transform the points the lines will also need to be transformed. This can be done
156 // by mapping the lines with the inverse-transpose of the matrix used to map the points.
157 int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = NULL,
158 SkScalar klm[9] = NULL, SkScalar klm_rev[3] = NULL);
159
160 // Input is p which holds the 4 control points of a non-rational cubic Bezier curve.
161 // Output is the coefficients of the three linear functionals K, L, & M which
162 // represent the implicit form of the cubic as f(x,y,w) = K^3 - LM. The w term
163 // will always be 1. The output is stored in the array klm, where the values are:
164 // K = (klm[0], klm[1], klm[2])
165 // L = (klm[3], klm[4], klm[5])
166 // M = (klm[6], klm[7], klm[8])
167 //
168 // Notice that the klm lines are calculated in the same space as the input control points.
169 // If you transform the points the lines will also need to be transformed. This can be done
170 // by mapping the lines with the inverse-transpose of the matrix used to map the points.
171 void getCubicKLM(const SkPoint p[4], SkScalar klm[9]);
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +0000172};
173#endif