1
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10#include "GrPathUtils.h"
11#include "GrPoint.h"
12#include "SkGeometry.h"
13
14GrScalar GrPathUtils::scaleToleranceToSrc(GrScalar devTol,
15                                          const GrMatrix& viewM,
16                                          const GrRect& pathBounds) {
17    // In order to tesselate the path we get a bound on how much the matrix can
18    // stretch when mapping to screen coordinates.
19    GrScalar stretch = viewM.getMaxStretch();
20    GrScalar srcTol = devTol;
21
22    if (stretch < 0) {
23        // take worst case mapRadius amoung four corners.
24        // (less than perfect)
25        for (int i = 0; i < 4; ++i) {
26            GrMatrix mat;
27            mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
28                             (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
29            mat.postConcat(viewM);
30            stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
31        }
32    }
33    srcTol = GrScalarDiv(srcTol, stretch);
34    return srcTol;
35}
36
37static const int MAX_POINTS_PER_CURVE = 1 << 10;
38static const GrScalar gMinCurveTol = GrFloatToScalar(0.0001f);
39
40uint32_t GrPathUtils::quadraticPointCount(const GrPoint points[],
41                                          GrScalar tol) {
42    if (tol < gMinCurveTol) {
43        tol = gMinCurveTol;
44    }
45    GrAssert(tol > 0);
46
47    GrScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
48    if (d <= tol) {
49        return 1;
50    } else {
51        // Each time we subdivide, d should be cut in 4. So we need to
52        // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
53        // points.
54        // 2^(log4(x)) = sqrt(x);
55        int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
56        int pow2 = GrNextPow2(temp);
57        // Because of NaNs & INFs we can wind up with a degenerate temp
58        // such that pow2 comes out negative. Also, our point generator
59        // will always output at least one pt.
60        if (pow2 < 1) {
61            pow2 = 1;
62        }
63        return GrMin(pow2, MAX_POINTS_PER_CURVE);
64    }
65}
66
67uint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0,
68                                              const GrPoint& p1,
69                                              const GrPoint& p2,
70                                              GrScalar tolSqd,
71                                              GrPoint** points,
72                                              uint32_t pointsLeft) {
73    if (pointsLeft < 2 ||
74        (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
75        (*points)[0] = p2;
76        *points += 1;
77        return 1;
78    }
79
80    GrPoint q[] = {
81        { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
82        { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
83    };
84    GrPoint r = { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) };
85
86    pointsLeft >>= 1;
87    uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
88    uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
89    return a + b;
90}
91
92uint32_t GrPathUtils::cubicPointCount(const GrPoint points[],
93                                           GrScalar tol) {
94    if (tol < gMinCurveTol) {
95        tol = gMinCurveTol;
96    }
97    GrAssert(tol > 0);
98
99    GrScalar d = GrMax(
100        points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
101        points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
102    d = SkScalarSqrt(d);
103    if (d <= tol) {
104        return 1;
105    } else {
106        int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
107        int pow2 = GrNextPow2(temp);
108        // Because of NaNs & INFs we can wind up with a degenerate temp
109        // such that pow2 comes out negative. Also, our point generator
110        // will always output at least one pt.
111        if (pow2 < 1) {
112            pow2 = 1;
113        }
114        return GrMin(pow2, MAX_POINTS_PER_CURVE);
115    }
116}
117
118uint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0,
119                                          const GrPoint& p1,
120                                          const GrPoint& p2,
121                                          const GrPoint& p3,
122                                          GrScalar tolSqd,
123                                          GrPoint** points,
124                                          uint32_t pointsLeft) {
125    if (pointsLeft < 2 ||
126        (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
127         p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
128            (*points)[0] = p3;
129            *points += 1;
130            return 1;
131        }
132    GrPoint q[] = {
133        { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
134        { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
135        { GrScalarAve(p2.fX, p3.fX), GrScalarAve(p2.fY, p3.fY) }
136    };
137    GrPoint r[] = {
138        { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) },
139        { GrScalarAve(q[1].fX, q[2].fX), GrScalarAve(q[1].fY, q[2].fY) }
140    };
141    GrPoint s = { GrScalarAve(r[0].fX, r[1].fX), GrScalarAve(r[0].fY, r[1].fY) };
142    pointsLeft >>= 1;
143    uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
144    uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
145    return a + b;
146}
147
148int GrPathUtils::worstCasePointCount(const GrPath& path, int* subpaths,
149                                     GrScalar tol) {
150    if (tol < gMinCurveTol) {
151        tol = gMinCurveTol;
152    }
153    GrAssert(tol > 0);
154
155    int pointCount = 0;
156    *subpaths = 1;
157
158    bool first = true;
159
160    SkPath::Iter iter(path, false);
161    GrPathCmd cmd;
162
163    GrPoint pts[4];
164    while ((cmd = (GrPathCmd)iter.next(pts)) != kEnd_PathCmd) {
165
166        switch (cmd) {
167            case kLine_PathCmd:
168                pointCount += 1;
169                break;
170            case kQuadratic_PathCmd:
171                pointCount += quadraticPointCount(pts, tol);
172                break;
173            case kCubic_PathCmd:
174                pointCount += cubicPointCount(pts, tol);
175                break;
176            case kMove_PathCmd:
177                pointCount += 1;
178                if (!first) {
179                    ++(*subpaths);
180                }
181                break;
182            default:
183                break;
184        }
185        first = false;
186    }
187    return pointCount;
188}
189
190namespace {
191// The matrix computed for quadDesignSpaceToUVCoordsMatrix should never really
192// have perspective and we really want to avoid perspective matrix muls.
193//  However, the first two entries of the perspective row may be really close to
194// 0 and the third may not be 1 due to a scale on the entire matrix.
195inline void fixup_matrix(GrMatrix* mat) {
196#ifndef SK_SCALAR_IS_FLOAT
197    GrCrash("Expected scalar is float.");
198#endif
199     static const GrScalar gTOL = 1.f / 100.f;
200    GrAssert(GrScalarAbs(mat->get(SkMatrix::kMPersp0)) < gTOL);
201    GrAssert(GrScalarAbs(mat->get(SkMatrix::kMPersp1)) < gTOL);
202    float m33 = mat->get(SkMatrix::kMPersp2);
203    if (1.f != m33) {
204        m33 = 1.f / m33;
205        mat->setAll(m33 * mat->get(SkMatrix::kMScaleX),
206                    m33 * mat->get(SkMatrix::kMSkewX),
207                    m33 * mat->get(SkMatrix::kMTransX),
208                    m33 * mat->get(SkMatrix::kMSkewY),
209                    m33 * mat->get(SkMatrix::kMScaleY),
210                    m33 * mat->get(SkMatrix::kMTransY),
211                    0.f, 0.f, 1.f);
212    } else {
213        mat->setPerspX(0);
214        mat->setPerspY(0);
215    }
216}
217}
218
219// Compute a matrix that goes from the 2d space coordinates to UV space where
220// u^2-v = 0 specifies the quad.
221void GrPathUtils::quadDesignSpaceToUVCoordsMatrix(const SkPoint qPts[3],
222                                                  GrMatrix* matrix) {
223    // can't make this static, no cons :(
224    SkMatrix UVpts;
225#ifndef SK_SCALAR_IS_FLOAT
226    GrCrash("Expected scalar is float.");
227#endif
228    // We want M such that M * xy_pt = uv_pt
229    // We know M * control_pts = [0  1/2 1]
230    //                           [0  0   1]
231    //                           [1  1   1]
232    // We invert the control pt matrix and post concat to both sides to get M.
233    UVpts.setAll(0,   0.5f,  1.f,
234                 0,   0,     1.f,
235                 1.f, 1.f,   1.f);
236    matrix->setAll(qPts[0].fX, qPts[1].fX, qPts[2].fX,
237                   qPts[0].fY, qPts[1].fY, qPts[2].fY,
238                   1.f,        1.f,        1.f);
239    if (!matrix->invert(matrix)) {
240        // The quad is degenerate. Hopefully this is rare. Find the pts that are
241        // farthest apart to compute a line (unless it is really a pt).
242        SkScalar maxD = qPts[0].distanceToSqd(qPts[1]);
243        int maxEdge = 0;
244        SkScalar d = qPts[1].distanceToSqd(qPts[2]);
245        if (d > maxD) {
246            maxD = d;
247            maxEdge = 1;
248        }
249        d = qPts[2].distanceToSqd(qPts[0]);
250        if (d > maxD) {
251            maxD = d;
252            maxEdge = 2;
253        }
254        // We could have a tolerance here, not sure if it would improve anything
255        if (maxD > 0) {
256            // Set the matrix to give (u = 0, v = distance_to_line)
257            GrVec lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
258            // when looking from the point 0 down the line we want positive
259            // distances to be to the left. This matches the non-degenerate
260            // case.
261            lineVec.setOrthog(lineVec, GrPoint::kLeft_Side);
262            lineVec.dot(qPts[0]);
263            matrix->setAll(0, 0, 0,
264                           lineVec.fX, lineVec.fY, -lineVec.dot(qPts[maxEdge]),
265                           0, 0, 1.f);
266        } else {
267            // It's a point. It should cover zero area. Just set the matrix such
268            // that (u, v) will always be far away from the quad.
269            matrix->setAll(0, 0, 100 * SK_Scalar1,
270                           0, 0, 100 * SK_Scalar1,
271                           0, 0, 1.f);
272        }
273    } else {
274        matrix->postConcat(UVpts);
275        fixup_matrix(matrix);
276    }
277}
278
279namespace {
280void convert_noninflect_cubic_to_quads(const SkPoint p[4],
281                                       SkScalar tolScale,
282                                       SkTArray<SkPoint, true>* quads,
283                                       int sublevel = 0) {
284    SkVector ab = p[1];
285    ab -= p[0];
286    SkVector dc = p[2];
287    dc -= p[3];
288
289    static const SkScalar gLengthScale = 3 * SK_Scalar1 / 2;
290    // base tolerance is 2 pixels in dev coords.
291    const SkScalar distanceSqdTol = SkScalarMul(tolScale, 1 * SK_Scalar1);
292    static const int kMaxSubdivs = 10;
293
294    ab.scale(gLengthScale);
295    dc.scale(gLengthScale);
296
297    SkVector c0 = p[0];
298    c0 += ab;
299    SkVector c1 = p[3];
300    c1 += dc;
301
302    SkScalar dSqd = c0.distanceToSqd(c1);
303    if (sublevel > kMaxSubdivs || dSqd <= distanceSqdTol) {
304        SkPoint cAvg = c0;
305        cAvg += c1;
306        cAvg.scale(SK_ScalarHalf);
307
308        SkPoint* pts = quads->push_back_n(3);
309        pts[0] = p[0];
310        pts[1] = cAvg;
311        pts[2] = p[3];
312
313        return;
314    } else {
315        SkPoint choppedPts[7];
316        SkChopCubicAtHalf(p, choppedPts);
317        convert_noninflect_cubic_to_quads(choppedPts + 0, tolScale,
318                                          quads, sublevel + 1);
319        convert_noninflect_cubic_to_quads(choppedPts + 3, tolScale,
320                                          quads, sublevel + 1);
321    }
322}
323}
324
325void GrPathUtils::convertCubicToQuads(const GrPoint p[4],
326                                      SkScalar tolScale,
327                                      SkTArray<SkPoint, true>* quads) {
328    SkPoint chopped[10];
329    int count = SkChopCubicAtInflections(p, chopped);
330
331    for (int i = 0; i < count; ++i) {
332        SkPoint* cubic = chopped + 3*i;
333        convert_noninflect_cubic_to_quads(cubic, tolScale, quads);
334    }
335
336}
337