1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkPathMeasure.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,537 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2008 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkPathMeasure.h"
1.14 +#include "SkGeometry.h"
1.15 +#include "SkPath.h"
1.16 +#include "SkTSearch.h"
1.17 +
1.18 +// these must be 0,1,2 since they are in our 2-bit field
1.19 +enum {
1.20 + kLine_SegType,
1.21 + kQuad_SegType,
1.22 + kCubic_SegType
1.23 +};
1.24 +
1.25 +#define kMaxTValue 32767
1.26 +
1.27 +static inline SkScalar tValue2Scalar(int t) {
1.28 + SkASSERT((unsigned)t <= kMaxTValue);
1.29 + return t * 3.05185e-5f; // t / 32767
1.30 +}
1.31 +
1.32 +SkScalar SkPathMeasure::Segment::getScalarT() const {
1.33 + return tValue2Scalar(fTValue);
1.34 +}
1.35 +
1.36 +const SkPathMeasure::Segment* SkPathMeasure::NextSegment(const Segment* seg) {
1.37 + unsigned ptIndex = seg->fPtIndex;
1.38 +
1.39 + do {
1.40 + ++seg;
1.41 + } while (seg->fPtIndex == ptIndex);
1.42 + return seg;
1.43 +}
1.44 +
1.45 +///////////////////////////////////////////////////////////////////////////////
1.46 +
1.47 +static inline int tspan_big_enough(int tspan) {
1.48 + SkASSERT((unsigned)tspan <= kMaxTValue);
1.49 + return tspan >> 10;
1.50 +}
1.51 +
1.52 +// can't use tangents, since we need [0..1..................2] to be seen
1.53 +// as definitely not a line (it is when drawn, but not parametrically)
1.54 +// so we compare midpoints
1.55 +#define CHEAP_DIST_LIMIT (SK_Scalar1/2) // just made this value up
1.56 +
1.57 +static bool quad_too_curvy(const SkPoint pts[3]) {
1.58 + // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
1.59 + // diff = -a/4 + b/2 - c/4
1.60 + SkScalar dx = SkScalarHalf(pts[1].fX) -
1.61 + SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
1.62 + SkScalar dy = SkScalarHalf(pts[1].fY) -
1.63 + SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
1.64 +
1.65 + SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy));
1.66 + return dist > CHEAP_DIST_LIMIT;
1.67 +}
1.68 +
1.69 +static bool cheap_dist_exceeds_limit(const SkPoint& pt,
1.70 + SkScalar x, SkScalar y) {
1.71 + SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
1.72 + // just made up the 1/2
1.73 + return dist > CHEAP_DIST_LIMIT;
1.74 +}
1.75 +
1.76 +static bool cubic_too_curvy(const SkPoint pts[4]) {
1.77 + return cheap_dist_exceeds_limit(pts[1],
1.78 + SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
1.79 + SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3))
1.80 + ||
1.81 + cheap_dist_exceeds_limit(pts[2],
1.82 + SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
1.83 + SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3));
1.84 +}
1.85 +
1.86 +SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3],
1.87 + SkScalar distance, int mint, int maxt, int ptIndex) {
1.88 + if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) {
1.89 + SkPoint tmp[5];
1.90 + int halft = (mint + maxt) >> 1;
1.91 +
1.92 + SkChopQuadAtHalf(pts, tmp);
1.93 + distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
1.94 + distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
1.95 + } else {
1.96 + SkScalar d = SkPoint::Distance(pts[0], pts[2]);
1.97 + SkScalar prevD = distance;
1.98 + distance += d;
1.99 + if (distance > prevD) {
1.100 + Segment* seg = fSegments.append();
1.101 + seg->fDistance = distance;
1.102 + seg->fPtIndex = ptIndex;
1.103 + seg->fType = kQuad_SegType;
1.104 + seg->fTValue = maxt;
1.105 + }
1.106 + }
1.107 + return distance;
1.108 +}
1.109 +
1.110 +SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4],
1.111 + SkScalar distance, int mint, int maxt, int ptIndex) {
1.112 + if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) {
1.113 + SkPoint tmp[7];
1.114 + int halft = (mint + maxt) >> 1;
1.115 +
1.116 + SkChopCubicAtHalf(pts, tmp);
1.117 + distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
1.118 + distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
1.119 + } else {
1.120 + SkScalar d = SkPoint::Distance(pts[0], pts[3]);
1.121 + SkScalar prevD = distance;
1.122 + distance += d;
1.123 + if (distance > prevD) {
1.124 + Segment* seg = fSegments.append();
1.125 + seg->fDistance = distance;
1.126 + seg->fPtIndex = ptIndex;
1.127 + seg->fType = kCubic_SegType;
1.128 + seg->fTValue = maxt;
1.129 + }
1.130 + }
1.131 + return distance;
1.132 +}
1.133 +
1.134 +void SkPathMeasure::buildSegments() {
1.135 + SkPoint pts[4];
1.136 + int ptIndex = fFirstPtIndex;
1.137 + SkScalar distance = 0;
1.138 + bool isClosed = fForceClosed;
1.139 + bool firstMoveTo = ptIndex < 0;
1.140 + Segment* seg;
1.141 +
1.142 + /* Note:
1.143 + * as we accumulate distance, we have to check that the result of +=
1.144 + * actually made it larger, since a very small delta might be > 0, but
1.145 + * still have no effect on distance (if distance >>> delta).
1.146 + *
1.147 + * We do this check below, and in compute_quad_segs and compute_cubic_segs
1.148 + */
1.149 + fSegments.reset();
1.150 + bool done = false;
1.151 + do {
1.152 + switch (fIter.next(pts)) {
1.153 + case SkPath::kConic_Verb:
1.154 + SkASSERT(0);
1.155 + break;
1.156 + case SkPath::kMove_Verb:
1.157 + ptIndex += 1;
1.158 + fPts.append(1, pts);
1.159 + if (!firstMoveTo) {
1.160 + done = true;
1.161 + break;
1.162 + }
1.163 + firstMoveTo = false;
1.164 + break;
1.165 +
1.166 + case SkPath::kLine_Verb: {
1.167 + SkScalar d = SkPoint::Distance(pts[0], pts[1]);
1.168 + SkASSERT(d >= 0);
1.169 + SkScalar prevD = distance;
1.170 + distance += d;
1.171 + if (distance > prevD) {
1.172 + seg = fSegments.append();
1.173 + seg->fDistance = distance;
1.174 + seg->fPtIndex = ptIndex;
1.175 + seg->fType = kLine_SegType;
1.176 + seg->fTValue = kMaxTValue;
1.177 + fPts.append(1, pts + 1);
1.178 + ptIndex++;
1.179 + }
1.180 + } break;
1.181 +
1.182 + case SkPath::kQuad_Verb: {
1.183 + SkScalar prevD = distance;
1.184 + distance = this->compute_quad_segs(pts, distance, 0,
1.185 + kMaxTValue, ptIndex);
1.186 + if (distance > prevD) {
1.187 + fPts.append(2, pts + 1);
1.188 + ptIndex += 2;
1.189 + }
1.190 + } break;
1.191 +
1.192 + case SkPath::kCubic_Verb: {
1.193 + SkScalar prevD = distance;
1.194 + distance = this->compute_cubic_segs(pts, distance, 0,
1.195 + kMaxTValue, ptIndex);
1.196 + if (distance > prevD) {
1.197 + fPts.append(3, pts + 1);
1.198 + ptIndex += 3;
1.199 + }
1.200 + } break;
1.201 +
1.202 + case SkPath::kClose_Verb:
1.203 + isClosed = true;
1.204 + break;
1.205 +
1.206 + case SkPath::kDone_Verb:
1.207 + done = true;
1.208 + break;
1.209 + }
1.210 + } while (!done);
1.211 +
1.212 + fLength = distance;
1.213 + fIsClosed = isClosed;
1.214 + fFirstPtIndex = ptIndex;
1.215 +
1.216 +#ifdef SK_DEBUG
1.217 + {
1.218 + const Segment* seg = fSegments.begin();
1.219 + const Segment* stop = fSegments.end();
1.220 + unsigned ptIndex = 0;
1.221 + SkScalar distance = 0;
1.222 +
1.223 + while (seg < stop) {
1.224 + SkASSERT(seg->fDistance > distance);
1.225 + SkASSERT(seg->fPtIndex >= ptIndex);
1.226 + SkASSERT(seg->fTValue > 0);
1.227 +
1.228 + const Segment* s = seg;
1.229 + while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) {
1.230 + SkASSERT(s[0].fType == s[1].fType);
1.231 + SkASSERT(s[0].fTValue < s[1].fTValue);
1.232 + s += 1;
1.233 + }
1.234 +
1.235 + distance = seg->fDistance;
1.236 + ptIndex = seg->fPtIndex;
1.237 + seg += 1;
1.238 + }
1.239 + // SkDebugf("\n");
1.240 + }
1.241 +#endif
1.242 +}
1.243 +
1.244 +static void compute_pos_tan(const SkPoint pts[], int segType,
1.245 + SkScalar t, SkPoint* pos, SkVector* tangent) {
1.246 + switch (segType) {
1.247 + case kLine_SegType:
1.248 + if (pos) {
1.249 + pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
1.250 + SkScalarInterp(pts[0].fY, pts[1].fY, t));
1.251 + }
1.252 + if (tangent) {
1.253 + tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
1.254 + }
1.255 + break;
1.256 + case kQuad_SegType:
1.257 + SkEvalQuadAt(pts, t, pos, tangent);
1.258 + if (tangent) {
1.259 + tangent->normalize();
1.260 + }
1.261 + break;
1.262 + case kCubic_SegType:
1.263 + SkEvalCubicAt(pts, t, pos, tangent, NULL);
1.264 + if (tangent) {
1.265 + tangent->normalize();
1.266 + }
1.267 + break;
1.268 + default:
1.269 + SkDEBUGFAIL("unknown segType");
1.270 + }
1.271 +}
1.272 +
1.273 +static void seg_to(const SkPoint pts[], int segType,
1.274 + SkScalar startT, SkScalar stopT, SkPath* dst) {
1.275 + SkASSERT(startT >= 0 && startT <= SK_Scalar1);
1.276 + SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
1.277 + SkASSERT(startT <= stopT);
1.278 +
1.279 + if (startT == stopT) {
1.280 + return; // should we report this, to undo a moveTo?
1.281 + }
1.282 +
1.283 + SkPoint tmp0[7], tmp1[7];
1.284 +
1.285 + switch (segType) {
1.286 + case kLine_SegType:
1.287 + if (SK_Scalar1 == stopT) {
1.288 + dst->lineTo(pts[1]);
1.289 + } else {
1.290 + dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
1.291 + SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
1.292 + }
1.293 + break;
1.294 + case kQuad_SegType:
1.295 + if (0 == startT) {
1.296 + if (SK_Scalar1 == stopT) {
1.297 + dst->quadTo(pts[1], pts[2]);
1.298 + } else {
1.299 + SkChopQuadAt(pts, tmp0, stopT);
1.300 + dst->quadTo(tmp0[1], tmp0[2]);
1.301 + }
1.302 + } else {
1.303 + SkChopQuadAt(pts, tmp0, startT);
1.304 + if (SK_Scalar1 == stopT) {
1.305 + dst->quadTo(tmp0[3], tmp0[4]);
1.306 + } else {
1.307 + SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT,
1.308 + SK_Scalar1 - startT));
1.309 + dst->quadTo(tmp1[1], tmp1[2]);
1.310 + }
1.311 + }
1.312 + break;
1.313 + case kCubic_SegType:
1.314 + if (0 == startT) {
1.315 + if (SK_Scalar1 == stopT) {
1.316 + dst->cubicTo(pts[1], pts[2], pts[3]);
1.317 + } else {
1.318 + SkChopCubicAt(pts, tmp0, stopT);
1.319 + dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
1.320 + }
1.321 + } else {
1.322 + SkChopCubicAt(pts, tmp0, startT);
1.323 + if (SK_Scalar1 == stopT) {
1.324 + dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
1.325 + } else {
1.326 + SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT,
1.327 + SK_Scalar1 - startT));
1.328 + dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
1.329 + }
1.330 + }
1.331 + break;
1.332 + default:
1.333 + SkDEBUGFAIL("unknown segType");
1.334 + sk_throw();
1.335 + }
1.336 +}
1.337 +
1.338 +////////////////////////////////////////////////////////////////////////////////
1.339 +////////////////////////////////////////////////////////////////////////////////
1.340 +
1.341 +SkPathMeasure::SkPathMeasure() {
1.342 + fPath = NULL;
1.343 + fLength = -1; // signal we need to compute it
1.344 + fForceClosed = false;
1.345 + fFirstPtIndex = -1;
1.346 +}
1.347 +
1.348 +SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) {
1.349 + fPath = &path;
1.350 + fLength = -1; // signal we need to compute it
1.351 + fForceClosed = forceClosed;
1.352 + fFirstPtIndex = -1;
1.353 +
1.354 + fIter.setPath(path, forceClosed);
1.355 +}
1.356 +
1.357 +SkPathMeasure::~SkPathMeasure() {}
1.358 +
1.359 +/** Assign a new path, or null to have none.
1.360 +*/
1.361 +void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) {
1.362 + fPath = path;
1.363 + fLength = -1; // signal we need to compute it
1.364 + fForceClosed = forceClosed;
1.365 + fFirstPtIndex = -1;
1.366 +
1.367 + if (path) {
1.368 + fIter.setPath(*path, forceClosed);
1.369 + }
1.370 + fSegments.reset();
1.371 + fPts.reset();
1.372 +}
1.373 +
1.374 +SkScalar SkPathMeasure::getLength() {
1.375 + if (fPath == NULL) {
1.376 + return 0;
1.377 + }
1.378 + if (fLength < 0) {
1.379 + this->buildSegments();
1.380 + }
1.381 + SkASSERT(fLength >= 0);
1.382 + return fLength;
1.383 +}
1.384 +
1.385 +const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment(
1.386 + SkScalar distance, SkScalar* t) {
1.387 + SkDEBUGCODE(SkScalar length = ) this->getLength();
1.388 + SkASSERT(distance >= 0 && distance <= length);
1.389 +
1.390 + const Segment* seg = fSegments.begin();
1.391 + int count = fSegments.count();
1.392 +
1.393 + int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance, sizeof(Segment));
1.394 + // don't care if we hit an exact match or not, so we xor index if it is negative
1.395 + index ^= (index >> 31);
1.396 + seg = &seg[index];
1.397 +
1.398 + // now interpolate t-values with the prev segment (if possible)
1.399 + SkScalar startT = 0, startD = 0;
1.400 + // check if the prev segment is legal, and references the same set of points
1.401 + if (index > 0) {
1.402 + startD = seg[-1].fDistance;
1.403 + if (seg[-1].fPtIndex == seg->fPtIndex) {
1.404 + SkASSERT(seg[-1].fType == seg->fType);
1.405 + startT = seg[-1].getScalarT();
1.406 + }
1.407 + }
1.408 +
1.409 + SkASSERT(seg->getScalarT() > startT);
1.410 + SkASSERT(distance >= startD);
1.411 + SkASSERT(seg->fDistance > startD);
1.412 +
1.413 + *t = startT + SkScalarMulDiv(seg->getScalarT() - startT,
1.414 + distance - startD,
1.415 + seg->fDistance - startD);
1.416 + return seg;
1.417 +}
1.418 +
1.419 +bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos,
1.420 + SkVector* tangent) {
1.421 + if (NULL == fPath) {
1.422 + return false;
1.423 + }
1.424 +
1.425 + SkScalar length = this->getLength(); // call this to force computing it
1.426 + int count = fSegments.count();
1.427 +
1.428 + if (count == 0 || length == 0) {
1.429 + return false;
1.430 + }
1.431 +
1.432 + // pin the distance to a legal range
1.433 + if (distance < 0) {
1.434 + distance = 0;
1.435 + } else if (distance > length) {
1.436 + distance = length;
1.437 + }
1.438 +
1.439 + SkScalar t;
1.440 + const Segment* seg = this->distanceToSegment(distance, &t);
1.441 +
1.442 + compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
1.443 + return true;
1.444 +}
1.445 +
1.446 +bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix,
1.447 + MatrixFlags flags) {
1.448 + if (NULL == fPath) {
1.449 + return false;
1.450 + }
1.451 +
1.452 + SkPoint position;
1.453 + SkVector tangent;
1.454 +
1.455 + if (this->getPosTan(distance, &position, &tangent)) {
1.456 + if (matrix) {
1.457 + if (flags & kGetTangent_MatrixFlag) {
1.458 + matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
1.459 + } else {
1.460 + matrix->reset();
1.461 + }
1.462 + if (flags & kGetPosition_MatrixFlag) {
1.463 + matrix->postTranslate(position.fX, position.fY);
1.464 + }
1.465 + }
1.466 + return true;
1.467 + }
1.468 + return false;
1.469 +}
1.470 +
1.471 +bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
1.472 + bool startWithMoveTo) {
1.473 + SkASSERT(dst);
1.474 +
1.475 + SkScalar length = this->getLength(); // ensure we have built our segments
1.476 +
1.477 + if (startD < 0) {
1.478 + startD = 0;
1.479 + }
1.480 + if (stopD > length) {
1.481 + stopD = length;
1.482 + }
1.483 + if (startD >= stopD) {
1.484 + return false;
1.485 + }
1.486 +
1.487 + SkPoint p;
1.488 + SkScalar startT, stopT;
1.489 + const Segment* seg = this->distanceToSegment(startD, &startT);
1.490 + const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
1.491 + SkASSERT(seg <= stopSeg);
1.492 +
1.493 + if (startWithMoveTo) {
1.494 + compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, NULL);
1.495 + dst->moveTo(p);
1.496 + }
1.497 +
1.498 + if (seg->fPtIndex == stopSeg->fPtIndex) {
1.499 + seg_to(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
1.500 + } else {
1.501 + do {
1.502 + seg_to(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
1.503 + seg = SkPathMeasure::NextSegment(seg);
1.504 + startT = 0;
1.505 + } while (seg->fPtIndex < stopSeg->fPtIndex);
1.506 + seg_to(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
1.507 + }
1.508 + return true;
1.509 +}
1.510 +
1.511 +bool SkPathMeasure::isClosed() {
1.512 + (void)this->getLength();
1.513 + return fIsClosed;
1.514 +}
1.515 +
1.516 +/** Move to the next contour in the path. Return true if one exists, or false if
1.517 + we're done with the path.
1.518 +*/
1.519 +bool SkPathMeasure::nextContour() {
1.520 + fLength = -1;
1.521 + return this->getLength() > 0;
1.522 +}
1.523 +
1.524 +///////////////////////////////////////////////////////////////////////////////
1.525 +///////////////////////////////////////////////////////////////////////////////
1.526 +
1.527 +#ifdef SK_DEBUG
1.528 +
1.529 +void SkPathMeasure::dump() {
1.530 + SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count());
1.531 +
1.532 + for (int i = 0; i < fSegments.count(); i++) {
1.533 + const Segment* seg = &fSegments[i];
1.534 + SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n",
1.535 + i, seg->fDistance, seg->fPtIndex, seg->getScalarT(),
1.536 + seg->fType);
1.537 + }
1.538 +}
1.539 +
1.540 +#endif
