GrPathUtils.cpp revision a51ab8416db9772a2eae3122f4f69801642daeb5 
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 SkPath& 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
190void GrPathUtils::QuadUVMatrix::set(const GrPoint qPts[3]) {
191    // can't make this static, no cons :(
192    SkMatrix UVpts;
193#ifndef SK_SCALAR_IS_FLOAT
194    GrCrash("Expected scalar is float.");
195#endif
196    SkMatrix m;
197    // We want M such that M * xy_pt = uv_pt
198    // We know M * control_pts = [0  1/2 1]
199    //                           [0  0   1]
200    //                           [1  1   1]
201    // We invert the control pt matrix and post concat to both sides to get M.
202    UVpts.setAll(0,   GR_ScalarHalf,  GR_Scalar1,
203                 0,               0,  GR_Scalar1,
204                 SkScalarToPersp(GR_Scalar1),
205                 SkScalarToPersp(GR_Scalar1),
206                 SkScalarToPersp(GR_Scalar1));
207    m.setAll(qPts[0].fX, qPts[1].fX, qPts[2].fX,
208             qPts[0].fY, qPts[1].fY, qPts[2].fY,
209             SkScalarToPersp(GR_Scalar1),
210             SkScalarToPersp(GR_Scalar1),
211             SkScalarToPersp(GR_Scalar1));
212    if (!m.invert(&m)) {
213        // The quad is degenerate. Hopefully this is rare. Find the pts that are
214        // farthest apart to compute a line (unless it is really a pt).
215        SkScalar maxD = qPts[0].distanceToSqd(qPts[1]);
216        int maxEdge = 0;
217        SkScalar d = qPts[1].distanceToSqd(qPts[2]);
218        if (d > maxD) {
219            maxD = d;
220            maxEdge = 1;
221        }
222        d = qPts[2].distanceToSqd(qPts[0]);
223        if (d > maxD) {
224            maxD = d;
225            maxEdge = 2;
226        }
227        // We could have a tolerance here, not sure if it would improve anything
228        if (maxD > 0) {
229            // Set the matrix to give (u = 0, v = distance_to_line)
230            GrVec lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
231            // when looking from the point 0 down the line we want positive
232            // distances to be to the left. This matches the non-degenerate
233            // case.
234            lineVec.setOrthog(lineVec, GrPoint::kLeft_Side);
235            lineVec.dot(qPts[0]);
236            // first row
237            fM[0] = 0;
238            fM[1] = 0;
239            fM[2] = 0;
240            // second row
241            fM[3] = lineVec.fX;
242            fM[4] = lineVec.fY;
243            fM[5] = -lineVec.dot(qPts[maxEdge]);
244        } else {
245            // It's a point. It should cover zero area. Just set the matrix such
246            // that (u, v) will always be far away from the quad.
247            fM[0] = 0; fM[1] = 0; fM[2] = 100.f;
248            fM[3] = 0; fM[4] = 0; fM[5] = 100.f;
249        }
250    } else {
251        m.postConcat(UVpts);
252
253        // The matrix should not have perspective.
254        static const GrScalar gTOL = GrFloatToScalar(1.f / 100.f);
255        GrAssert(GrScalarAbs(m.get(SkMatrix::kMPersp0)) < gTOL);
256        GrAssert(GrScalarAbs(m.get(SkMatrix::kMPersp1)) < gTOL);
257
258        // It may not be normalized to have 1.0 in the bottom right
259        float m33 = m.get(SkMatrix::kMPersp2);
260        if (1.f != m33) {
261            m33 = 1.f / m33;
262            fM[0] = m33 * m.get(SkMatrix::kMScaleX);
263            fM[1] = m33 * m.get(SkMatrix::kMSkewX);
264            fM[2] = m33 * m.get(SkMatrix::kMTransX);
265            fM[3] = m33 * m.get(SkMatrix::kMSkewY);
266            fM[4] = m33 * m.get(SkMatrix::kMScaleY);
267            fM[5] = m33 * m.get(SkMatrix::kMTransY);
268        } else {
269            fM[0] = m.get(SkMatrix::kMScaleX);
270            fM[1] = m.get(SkMatrix::kMSkewX);
271            fM[2] = m.get(SkMatrix::kMTransX);
272            fM[3] = m.get(SkMatrix::kMSkewY);
273            fM[4] = m.get(SkMatrix::kMScaleY);
274            fM[5] = m.get(SkMatrix::kMTransY);
275        }
276    }
277}
278
279namespace {
280
281// a is the first control point of the cubic.
282// ab is the vector from a to the second control point.
283// dc is the vector from the fourth to the third control point.
284// d is the fourth control point.
285// p is the candidate quadratic control point.
286// this assumes that the cubic doesn't inflect and is simple
287bool is_point_within_cubic_tangents(const SkPoint& a,
288                                    const SkVector& ab,
289                                    const SkVector& dc,
290                                    const SkPoint& d,
291                                    SkPath::Direction dir,
292                                    const SkPoint p) {
293    SkVector ap = p - a;
294    SkScalar apXab = ap.cross(ab);
295    if (SkPath::kCW_Direction == dir) {
296        if (apXab > 0) {
297            return false;
298        }
299    } else {
300        GrAssert(SkPath::kCCW_Direction == dir);
301        if (apXab < 0) {
302            return false;
303        }
304    }
305
306    SkVector dp = p - d;
307    SkScalar dpXdc = dp.cross(dc);
308    if (SkPath::kCW_Direction == dir) {
309        if (dpXdc < 0) {
310            return false;
311        }
312    } else {
313        GrAssert(SkPath::kCCW_Direction == dir);
314        if (dpXdc > 0) {
315            return false;
316        }
317    }
318    return true;
319}
320
321void convert_noninflect_cubic_to_quads(const SkPoint p[4],
322                                       SkScalar toleranceSqd,
323                                       bool constrainWithinTangents,
324                                       SkPath::Direction dir,
325                                       SkTArray<SkPoint, true>* quads,
326                                       int sublevel = 0) {
327    SkVector ab = p[1] - p[0];
328    SkVector dc = p[2] - p[3];
329
330    if (ab.isZero()) {
331        if (dc.isZero()) {
332            SkPoint* degQuad = quads->push_back_n(3);
333            degQuad[0] = p[0];
334            degQuad[1] = p[0];
335            degQuad[2] = p[3];
336            return;
337        }
338        ab = p[2] - p[0];
339    }
340    if (dc.isZero()) {
341        dc = p[1] - p[3];
342    }
343
344    static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
345    static const int kMaxSubdivs = 10;
346
347    ab.scale(kLengthScale);
348    dc.scale(kLengthScale);
349
350    // e0 and e1 are extrapolations along vectors ab and dc.
351    SkVector c0 = p[0];
352    c0 += ab;
353    SkVector c1 = p[3];
354    c1 += dc;
355
356    SkScalar dSqd = sublevel > kMaxSubdivs ? toleranceSqd : c0.distanceToSqd(c1);
357    if (dSqd < toleranceSqd) {
358        SkPoint cAvg = c0;
359        cAvg += c1;
360        cAvg.scale(SK_ScalarHalf);
361
362        bool subdivide = false;
363
364        if (constrainWithinTangents &&
365            !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
366            // choose a new cAvg that is the intersection of the two tangent
367            // lines.
368            ab.setOrthog(ab);
369            SkScalar z0 = -ab.dot(p[0]);
370            dc.setOrthog(dc);
371            SkScalar z1 = -dc.dot(p[3]);
372            cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY);
373            cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1);
374            SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX);
375            z = SkScalarInvert(z);
376            cAvg.fX *= z;
377            cAvg.fY *= z;
378            if (sublevel <= kMaxSubdivs) {
379                SkScalar d0Sqd = c0.distanceToSqd(cAvg);
380                SkScalar d1Sqd = c1.distanceToSqd(cAvg);
381                // We need to subdivide if d0 + d1 > tolerance but we have the
382                // sqd values. We know the distances and tolerance can't be
383                // negative.
384                // (d0 + d1)^2 > toleranceSqd
385                // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
386                SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd));
387                subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
388            }
389        }
390        if (!subdivide) {
391            SkPoint* pts = quads->push_back_n(3);
392            pts[0] = p[0];
393            pts[1] = cAvg;
394            pts[2] = p[3];
395            return;
396        }
397    }
398    SkPoint choppedPts[7];
399    SkChopCubicAtHalf(p, choppedPts);
400    convert_noninflect_cubic_to_quads(choppedPts + 0,
401                                      toleranceSqd,
402                                      constrainWithinTangents,
403                                      dir,
404                                      quads,
405                                      sublevel + 1);
406    convert_noninflect_cubic_to_quads(choppedPts + 3,
407                                      toleranceSqd,
408                                      constrainWithinTangents,
409                                      dir,
410                                      quads,
411                                      sublevel + 1);
412}
413}
414
415void GrPathUtils::convertCubicToQuads(const GrPoint p[4],
416                                      SkScalar tolScale,
417                                      bool constrainWithinTangents,
418                                      SkPath::Direction dir,
419                                      SkTArray<SkPoint, true>* quads) {
420    SkPoint chopped[10];
421    int count = SkChopCubicAtInflections(p, chopped);
422
423    // base tolerance is 1 pixel.
424    static const SkScalar kTolerance = SK_Scalar1;
425    const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance));
426
427    for (int i = 0; i < count; ++i) {
428        SkPoint* cubic = chopped + 3*i;
429        convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads);
430    }
431
432}
433