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 14 GrScalar 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 37 static const int MAX_POINTS_PER_CURVE = 1 << 10; 38 static const GrScalar gMinCurveTol = GrFloatToScalar(0.0001f); 39 40 uint32_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 67 uint32_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 92 uint32_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 118 uint32_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 148 int 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 190 namespace { 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. 195 inline 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. 221 void 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 279 namespace { 280 void 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 325 void 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
