Home | History | Annotate | Download | only in src 
      1 /*
      2     Copyright 2011 Google Inc.
      3 
      4     Licensed under the Apache License, Version 2.0 (the "License");
      5     you may not use this file except in compliance with the License.
      6     You may obtain a copy of the License at
      7 
      8          http://www.apache.org/licenses/LICENSE-2.0
      9 
     10     Unless required by applicable law or agreed to in writing, software
     11     distributed under the License is distributed on an "AS IS" BASIS,
     12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13     See the License for the specific language governing permissions and
     14     limitations under the License.
     15  */
     16 
     17 #include "GrPathUtils.h"
     18 #include "GrPoint.h"
     19 
     20 const GrScalar GrPathUtils::gTolerance = GR_Scalar1;
     21 
     22 static const uint32_t MAX_POINTS_PER_CURVE = 1 << 10;
     23 
     24 uint32_t GrPathUtils::quadraticPointCount(const GrPoint points[],
     25                                              GrScalar tol) {
     26     GrScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
     27     if (d < tol) {
     28         return 1;
     29     } else {
     30         // Each time we subdivide, d should be cut in 4. So we need to
     31         // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
     32         // points.
     33         // 2^(log4(x)) = sqrt(x);
     34         int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
     35         return GrMin(GrNextPow2(temp), MAX_POINTS_PER_CURVE);
     36     }
     37 }
     38 
     39 uint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0,
     40                                                  const GrPoint& p1,
     41                                                  const GrPoint& p2,
     42                                                  GrScalar tolSqd,
     43                                                  GrPoint** points,
     44                                                  uint32_t pointsLeft) {
     45     if (pointsLeft < 2 ||
     46         (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
     47         (*points)[0] = p2;
     48         *points += 1;
     49         return 1;
     50     }
     51 
     52     GrPoint q[] = {
     53         { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
     54         { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
     55     };
     56     GrPoint r = { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) };
     57 
     58     pointsLeft >>= 1;
     59     uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
     60     uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
     61     return a + b;
     62 }
     63 
     64 uint32_t GrPathUtils::cubicPointCount(const GrPoint points[],
     65                                            GrScalar tol) {
     66     GrScalar d = GrMax(points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
     67                        points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
     68     d = SkScalarSqrt(d);
     69     if (d < tol) {
     70         return 1;
     71     } else {
     72         int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
     73         return GrMin(GrNextPow2(temp), MAX_POINTS_PER_CURVE);
     74     }
     75 }
     76 
     77 uint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0,
     78                                              const GrPoint& p1,
     79                                              const GrPoint& p2,
     80                                              const GrPoint& p3,
     81                                              GrScalar tolSqd,
     82                                              GrPoint** points,
     83                                              uint32_t pointsLeft) {
     84     if (pointsLeft < 2 ||
     85         (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
     86          p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
     87             (*points)[0] = p3;
     88             *points += 1;
     89             return 1;
     90         }
     91     GrPoint q[] = {
     92         { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
     93         { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
     94         { GrScalarAve(p2.fX, p3.fX), GrScalarAve(p2.fY, p3.fY) }
     95     };
     96     GrPoint r[] = {
     97         { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) },
     98         { GrScalarAve(q[1].fX, q[2].fX), GrScalarAve(q[1].fY, q[2].fY) }
     99     };
    100     GrPoint s = { GrScalarAve(r[0].fX, r[1].fX), GrScalarAve(r[0].fY, r[1].fY) };
    101     pointsLeft >>= 1;
    102     uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
    103     uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
    104     return a + b;
    105 }
    106 
    107 int GrPathUtils::worstCasePointCount(const GrPath& path, int* subpaths,
    108                                      GrScalar tol) {
    109     int pointCount = 0;
    110     *subpaths = 1;
    111 
    112     bool first = true;
    113 
    114     SkPath::Iter iter(path, true);
    115     GrPathCmd cmd;
    116 
    117     GrPoint pts[4];
    118     while ((cmd = (GrPathCmd)iter.next(pts)) != kEnd_PathCmd) {
    119 
    120         switch (cmd) {
    121             case kLine_PathCmd:
    122                 pointCount += 1;
    123                 break;
    124             case kQuadratic_PathCmd:
    125                 pointCount += quadraticPointCount(pts, tol);
    126                 break;
    127             case kCubic_PathCmd:
    128                 pointCount += cubicPointCount(pts, tol);
    129                 break;
    130             case kMove_PathCmd:
    131                 pointCount += 1;
    132                 if (!first) {
    133                     ++(*subpaths);
    134                 }
    135                 break;
    136             default:
    137                 break;
    138         }
    139         first = false;
    140     }
    141     return pointCount;
    142 }
    143