1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2008 The Android Open Source Project 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPathMeasure.h" 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkGeometry.h" 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPath.h" 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTSearch.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15220f926d9d4b38a9018c922c095847bbd261f583reed// these must be 0,1,2,3 since they are in our 2-bit field 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comenum { 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kLine_SegType, 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kQuad_SegType, 19220f926d9d4b38a9018c922c095847bbd261f583reed kCubic_SegType, 20220f926d9d4b38a9018c922c095847bbd261f583reed kConic_SegType, 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define kMaxTValue 32767 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline SkScalar tValue2Scalar(int t) { 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((unsigned)t <= kMaxTValue); 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return t * 3.05185e-5f; // t / 32767 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkScalar SkPathMeasure::Segment::getScalarT() const { 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return tValue2Scalar(fTValue); 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comconst SkPathMeasure::Segment* SkPathMeasure::NextSegment(const Segment* seg) { 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned ptIndex = seg->fPtIndex; 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ++seg; 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (seg->fPtIndex == ptIndex); 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return seg; 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int tspan_big_enough(int tspan) { 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((unsigned)tspan <= kMaxTValue); 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return tspan >> 10; 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// can't use tangents, since we need [0..1..................2] to be seen 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// as definitely not a line (it is when drawn, but not parametrically) 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// so we compare midpoints 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define CHEAP_DIST_LIMIT (SK_Scalar1/2) // just made this value up 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic bool quad_too_curvy(const SkPoint pts[3]) { 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // diff = (a/4 + b/2 + c/4) - (a/2 + c/2) 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // diff = -a/4 + b/2 - c/4 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar dx = SkScalarHalf(pts[1].fX) - 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX)); 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar dy = SkScalarHalf(pts[1].fY) - 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY)); 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy)); 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return dist > CHEAP_DIST_LIMIT; 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic bool cheap_dist_exceeds_limit(const SkPoint& pt, 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x, SkScalar y) { 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY)); 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // just made up the 1/2 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return dist > CHEAP_DIST_LIMIT; 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic bool cubic_too_curvy(const SkPoint pts[4]) { 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return cheap_dist_exceeds_limit(pts[1], 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3), 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3)) 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com || 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cheap_dist_exceeds_limit(pts[2], 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3), 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3)); 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3], 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar distance, int mint, int maxt, int ptIndex) { 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) { 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[5]; 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int halft = (mint + maxt) >> 1; 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAtHalf(pts, tmp); 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex); 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex); 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar d = SkPoint::Distance(pts[0], pts[2]); 95ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com SkScalar prevD = distance; 96ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com distance += d; 97ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com if (distance > prevD) { 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Segment* seg = fSegments.append(); 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fDistance = distance; 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fPtIndex = ptIndex; 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fType = kQuad_SegType; 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fTValue = maxt; 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return distance; 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108220f926d9d4b38a9018c922c095847bbd261f583reedSkScalar SkPathMeasure::compute_conic_segs(const SkConic& conic, 109220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar distance, int mint, int maxt, int ptIndex) { 110220f926d9d4b38a9018c922c095847bbd261f583reed if (tspan_big_enough(maxt - mint) && quad_too_curvy(conic.fPts)) { 111220f926d9d4b38a9018c922c095847bbd261f583reed SkConic tmp[2]; 112220f926d9d4b38a9018c922c095847bbd261f583reed conic.chop(tmp); 113220f926d9d4b38a9018c922c095847bbd261f583reed 114220f926d9d4b38a9018c922c095847bbd261f583reed int halft = (mint + maxt) >> 1; 115220f926d9d4b38a9018c922c095847bbd261f583reed distance = this->compute_conic_segs(tmp[0], distance, mint, halft, ptIndex); 116220f926d9d4b38a9018c922c095847bbd261f583reed distance = this->compute_conic_segs(tmp[1], distance, halft, maxt, ptIndex); 117220f926d9d4b38a9018c922c095847bbd261f583reed } else { 118220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar d = SkPoint::Distance(conic.fPts[0], conic.fPts[2]); 119220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar prevD = distance; 120220f926d9d4b38a9018c922c095847bbd261f583reed distance += d; 121220f926d9d4b38a9018c922c095847bbd261f583reed if (distance > prevD) { 122220f926d9d4b38a9018c922c095847bbd261f583reed Segment* seg = fSegments.append(); 123220f926d9d4b38a9018c922c095847bbd261f583reed seg->fDistance = distance; 124220f926d9d4b38a9018c922c095847bbd261f583reed seg->fPtIndex = ptIndex; 125220f926d9d4b38a9018c922c095847bbd261f583reed seg->fType = kConic_SegType; 126220f926d9d4b38a9018c922c095847bbd261f583reed seg->fTValue = maxt; 127220f926d9d4b38a9018c922c095847bbd261f583reed } 128220f926d9d4b38a9018c922c095847bbd261f583reed } 129220f926d9d4b38a9018c922c095847bbd261f583reed return distance; 130220f926d9d4b38a9018c922c095847bbd261f583reed} 131220f926d9d4b38a9018c922c095847bbd261f583reed 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4], 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar distance, int mint, int maxt, int ptIndex) { 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) { 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[7]; 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int halft = (mint + maxt) >> 1; 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAtHalf(pts, tmp); 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex); 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex); 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar d = SkPoint::Distance(pts[0], pts[3]); 143ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com SkScalar prevD = distance; 144ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com distance += d; 145ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com if (distance > prevD) { 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Segment* seg = fSegments.append(); 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fDistance = distance; 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fPtIndex = ptIndex; 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fType = kCubic_SegType; 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fTValue = maxt; 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return distance; 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkPathMeasure::buildSegments() { 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint pts[4]; 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int ptIndex = fFirstPtIndex; 159fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com SkScalar distance = 0; 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool isClosed = fForceClosed; 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool firstMoveTo = ptIndex < 0; 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Segment* seg; 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 164fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com /* Note: 165fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com * as we accumulate distance, we have to check that the result of += 166fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com * actually made it larger, since a very small delta might be > 0, but 167fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com * still have no effect on distance (if distance >>> delta). 168ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com * 169ded44149856373072a8c6d2b2eacb213a1273a6ereed@google.com * We do this check below, and in compute_quad_segs and compute_cubic_segs 170fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com */ 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fSegments.reset(); 172a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org bool done = false; 173a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org do { 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com switch (fIter.next(pts)) { 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkPath::kMove_Verb: 176a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org ptIndex += 1; 177a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org fPts.append(1, pts); 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!firstMoveTo) { 179a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org done = true; 180a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org break; 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 182a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org firstMoveTo = false; 183a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org break; 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 185fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com case SkPath::kLine_Verb: { 186fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com SkScalar d = SkPoint::Distance(pts[0], pts[1]); 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(d >= 0); 188fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com SkScalar prevD = distance; 189a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org distance += d; 190fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com if (distance > prevD) { 191fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com seg = fSegments.append(); 192fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com seg->fDistance = distance; 193fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com seg->fPtIndex = ptIndex; 194fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com seg->fType = kLine_SegType; 195fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com seg->fTValue = kMaxTValue; 196fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com fPts.append(1, pts + 1); 197fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com ptIndex++; 198fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com } 199fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com } break; 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 201fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com case SkPath::kQuad_Verb: { 202fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com SkScalar prevD = distance; 203220f926d9d4b38a9018c922c095847bbd261f583reed distance = this->compute_quad_segs(pts, distance, 0, kMaxTValue, ptIndex); 204fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com if (distance > prevD) { 205fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com fPts.append(2, pts + 1); 206fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com ptIndex += 2; 207fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com } 208fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com } break; 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 210220f926d9d4b38a9018c922c095847bbd261f583reed case SkPath::kConic_Verb: { 211220f926d9d4b38a9018c922c095847bbd261f583reed const SkConic conic(pts, fIter.conicWeight()); 212220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar prevD = distance; 213220f926d9d4b38a9018c922c095847bbd261f583reed distance = this->compute_conic_segs(conic, distance, 0, kMaxTValue, ptIndex); 214220f926d9d4b38a9018c922c095847bbd261f583reed if (distance > prevD) { 215220f926d9d4b38a9018c922c095847bbd261f583reed // we store the conic weight in our next point, followed by the last 2 pts 216220f926d9d4b38a9018c922c095847bbd261f583reed // thus to reconstitue a conic, you'd need to say 217220f926d9d4b38a9018c922c095847bbd261f583reed // SkConic(pts[0], pts[2], pts[3], weight = pts[1].fX) 218220f926d9d4b38a9018c922c095847bbd261f583reed fPts.append()->set(conic.fW, 0); 219220f926d9d4b38a9018c922c095847bbd261f583reed fPts.append(2, pts + 1); 220220f926d9d4b38a9018c922c095847bbd261f583reed ptIndex += 3; 221220f926d9d4b38a9018c922c095847bbd261f583reed } 222220f926d9d4b38a9018c922c095847bbd261f583reed } break; 223220f926d9d4b38a9018c922c095847bbd261f583reed 224fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com case SkPath::kCubic_Verb: { 225fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com SkScalar prevD = distance; 226220f926d9d4b38a9018c922c095847bbd261f583reed distance = this->compute_cubic_segs(pts, distance, 0, kMaxTValue, ptIndex); 227fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com if (distance > prevD) { 228fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com fPts.append(3, pts + 1); 229fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com ptIndex += 3; 230fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com } 231fab1ddd3a8893db58b2ce0afd28ecc73412ee871reed@google.com } break; 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkPath::kClose_Verb: 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com isClosed = true; 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 236fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkPath::kDone_Verb: 238a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org done = true; 239a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org break; 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 241a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org } while (!done); 242a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLength = distance; 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fIsClosed = isClosed; 245a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org fFirstPtIndex = ptIndex; 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* seg = fSegments.begin(); 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* stop = fSegments.end(); 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned ptIndex = 0; 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar distance = 0; 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (seg < stop) { 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg->fDistance > distance); 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg->fPtIndex >= ptIndex); 2578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg->fTValue > 0); 2588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* s = seg; 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) { 2618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(s[0].fType == s[1].fType); 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(s[0].fTValue < s[1].fTValue); 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com s += 1; 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = seg->fDistance; 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ptIndex = seg->fPtIndex; 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg += 1; 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // SkDebugf("\n"); 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 2738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2755b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.comstatic void compute_pos_tan(const SkPoint pts[], int segType, 2765b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com SkScalar t, SkPoint* pos, SkVector* tangent) { 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com switch (segType) { 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case kLine_SegType: 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (pos) { 280a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t), 2815b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com SkScalarInterp(pts[0].fY, pts[1].fY, t)); 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tangent) { 284a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY); 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case kQuad_SegType: 2888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkEvalQuadAt(pts, t, pos, tangent); 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tangent) { 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->normalize(); 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 293220f926d9d4b38a9018c922c095847bbd261f583reed case kConic_SegType: { 294220f926d9d4b38a9018c922c095847bbd261f583reed SkConic(pts[0], pts[2], pts[3], pts[1].fX).evalAt(t, pos, tangent); 295220f926d9d4b38a9018c922c095847bbd261f583reed if (tangent) { 296220f926d9d4b38a9018c922c095847bbd261f583reed tangent->normalize(); 297220f926d9d4b38a9018c922c095847bbd261f583reed } 298220f926d9d4b38a9018c922c095847bbd261f583reed } break; 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case kCubic_SegType: 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkEvalCubicAt(pts, t, pos, tangent, NULL); 3018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tangent) { 3028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->normalize(); 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 3058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com default: 3060c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unknown segType"); 3078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3105b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.comstatic void seg_to(const SkPoint pts[], int segType, 3115b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com SkScalar startT, SkScalar stopT, SkPath* dst) { 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(startT >= 0 && startT <= SK_Scalar1); 3138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(stopT >= 0 && stopT <= SK_Scalar1); 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(startT <= stopT); 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 316de1837bb96b0f72dad7482786d6e577013d4a85breed@google.com if (startT == stopT) { 317de1837bb96b0f72dad7482786d6e577013d4a85breed@google.com return; // should we report this, to undo a moveTo? 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 320220f926d9d4b38a9018c922c095847bbd261f583reed SkPoint tmp0[7], tmp1[7]; 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com switch (segType) { 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case kLine_SegType: 324f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (SK_Scalar1 == stopT) { 325a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org dst->lineTo(pts[1]); 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 327a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT), 328a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org SkScalarInterp(pts[0].fY, pts[1].fY, stopT)); 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 3318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case kQuad_SegType: 332f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (0 == startT) { 333f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (SK_Scalar1 == stopT) { 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->quadTo(pts[1], pts[2]); 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(pts, tmp0, stopT); 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->quadTo(tmp0[1], tmp0[2]); 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(pts, tmp0, startT); 341f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (SK_Scalar1 == stopT) { 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->quadTo(tmp0[3], tmp0[4]); 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 34480ea19ca4bdd68c1493666a5fe7e4ce9d43ded8breed SkChopQuadAt(&tmp0[2], tmp1, (stopT - startT) / (1 - startT)); 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->quadTo(tmp1[1], tmp1[2]); 3468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 349220f926d9d4b38a9018c922c095847bbd261f583reed case kConic_SegType: { 350220f926d9d4b38a9018c922c095847bbd261f583reed SkConic conic(pts[0], pts[2], pts[3], pts[1].fX); 351220f926d9d4b38a9018c922c095847bbd261f583reed 352220f926d9d4b38a9018c922c095847bbd261f583reed if (0 == startT) { 353220f926d9d4b38a9018c922c095847bbd261f583reed if (SK_Scalar1 == stopT) { 354220f926d9d4b38a9018c922c095847bbd261f583reed dst->conicTo(conic.fPts[1], conic.fPts[2], conic.fW); 355220f926d9d4b38a9018c922c095847bbd261f583reed } else { 356220f926d9d4b38a9018c922c095847bbd261f583reed SkConic tmp[2]; 357220f926d9d4b38a9018c922c095847bbd261f583reed conic.chopAt(stopT, tmp); 358220f926d9d4b38a9018c922c095847bbd261f583reed dst->conicTo(tmp[0].fPts[1], tmp[0].fPts[2], tmp[0].fW); 359220f926d9d4b38a9018c922c095847bbd261f583reed } 360220f926d9d4b38a9018c922c095847bbd261f583reed } else { 361220f926d9d4b38a9018c922c095847bbd261f583reed SkConic tmp1[2]; 362220f926d9d4b38a9018c922c095847bbd261f583reed conic.chopAt(startT, tmp1); 363220f926d9d4b38a9018c922c095847bbd261f583reed if (SK_Scalar1 == stopT) { 364220f926d9d4b38a9018c922c095847bbd261f583reed dst->conicTo(tmp1[1].fPts[1], tmp1[1].fPts[2], tmp1[1].fW); 365220f926d9d4b38a9018c922c095847bbd261f583reed } else { 366220f926d9d4b38a9018c922c095847bbd261f583reed SkConic tmp2[2]; 367220f926d9d4b38a9018c922c095847bbd261f583reed tmp1[1].chopAt((stopT - startT) / (SK_Scalar1 - startT), tmp2); 368220f926d9d4b38a9018c922c095847bbd261f583reed dst->conicTo(tmp2[0].fPts[1], tmp2[0].fPts[2], tmp2[0].fW); 369220f926d9d4b38a9018c922c095847bbd261f583reed } 370220f926d9d4b38a9018c922c095847bbd261f583reed } 371220f926d9d4b38a9018c922c095847bbd261f583reed } break; 3728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case kCubic_SegType: 373f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (0 == startT) { 374f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (SK_Scalar1 == stopT) { 3758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->cubicTo(pts[1], pts[2], pts[3]); 3768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(pts, tmp0, stopT); 3788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]); 3798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(pts, tmp0, startT); 382f33612b923c3d065aabda6967247771d9aa6172creed@google.com if (SK_Scalar1 == stopT) { 3838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]); 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 38580ea19ca4bdd68c1493666a5fe7e4ce9d43ded8breed SkChopCubicAt(&tmp0[3], tmp1, (stopT - startT) / (1 - startT)); 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]); 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 3908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com default: 3910c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unknown segType"); 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_throw(); 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////////////// 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////////////// 3988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkPathMeasure::SkPathMeasure() { 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath = NULL; 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLength = -1; // signal we need to compute it 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fForceClosed = false; 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFirstPtIndex = -1; 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) { 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath = &path; 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLength = -1; // signal we need to compute it 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fForceClosed = forceClosed; 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFirstPtIndex = -1; 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fIter.setPath(path, forceClosed); 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkPathMeasure::~SkPathMeasure() {} 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Assign a new path, or null to have none. 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkPathMeasure::setPath(const SkPath* path, bool forceClosed) { 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath = path; 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLength = -1; // signal we need to compute it 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fForceClosed = forceClosed; 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFirstPtIndex = -1; 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (path) { 4268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fIter.setPath(*path, forceClosed); 4278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fSegments.reset(); 429a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org fPts.reset(); 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkScalar SkPathMeasure::getLength() { 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fPath == NULL) { 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fLength < 0) { 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->buildSegments(); 4388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fLength >= 0); 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fLength; 4418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 44383e22e407e48acc4e23774edb2241c6a111e1db9reedtemplate <typename T, typename K> 44483e22e407e48acc4e23774edb2241c6a111e1db9reedint SkTKSearch(const T base[], int count, const K& key) { 44583e22e407e48acc4e23774edb2241c6a111e1db9reed SkASSERT(count >= 0); 44683e22e407e48acc4e23774edb2241c6a111e1db9reed if (count <= 0) { 44783e22e407e48acc4e23774edb2241c6a111e1db9reed return ~0; 44883e22e407e48acc4e23774edb2241c6a111e1db9reed } 44983e22e407e48acc4e23774edb2241c6a111e1db9reed 45083e22e407e48acc4e23774edb2241c6a111e1db9reed SkASSERT(base != NULL); // base may be NULL if count is zero 45183e22e407e48acc4e23774edb2241c6a111e1db9reed 45283e22e407e48acc4e23774edb2241c6a111e1db9reed int lo = 0; 45383e22e407e48acc4e23774edb2241c6a111e1db9reed int hi = count - 1; 45483e22e407e48acc4e23774edb2241c6a111e1db9reed 45583e22e407e48acc4e23774edb2241c6a111e1db9reed while (lo < hi) { 45683e22e407e48acc4e23774edb2241c6a111e1db9reed int mid = (hi + lo) >> 1; 45783e22e407e48acc4e23774edb2241c6a111e1db9reed if (base[mid].fDistance < key) { 45883e22e407e48acc4e23774edb2241c6a111e1db9reed lo = mid + 1; 45983e22e407e48acc4e23774edb2241c6a111e1db9reed } else { 46083e22e407e48acc4e23774edb2241c6a111e1db9reed hi = mid; 46183e22e407e48acc4e23774edb2241c6a111e1db9reed } 46283e22e407e48acc4e23774edb2241c6a111e1db9reed } 46383e22e407e48acc4e23774edb2241c6a111e1db9reed 46483e22e407e48acc4e23774edb2241c6a111e1db9reed if (base[hi].fDistance < key) { 46583e22e407e48acc4e23774edb2241c6a111e1db9reed hi += 1; 46683e22e407e48acc4e23774edb2241c6a111e1db9reed hi = ~hi; 46783e22e407e48acc4e23774edb2241c6a111e1db9reed } else if (key < base[hi].fDistance) { 46883e22e407e48acc4e23774edb2241c6a111e1db9reed hi = ~hi; 46983e22e407e48acc4e23774edb2241c6a111e1db9reed } 47083e22e407e48acc4e23774edb2241c6a111e1db9reed return hi; 47183e22e407e48acc4e23774edb2241c6a111e1db9reed} 47283e22e407e48acc4e23774edb2241c6a111e1db9reed 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comconst SkPathMeasure::Segment* SkPathMeasure::distanceToSegment( 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar distance, SkScalar* t) { 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(SkScalar length = ) this->getLength(); 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(distance >= 0 && distance <= length); 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* seg = fSegments.begin(); 4798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = fSegments.count(); 4808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 48183e22e407e48acc4e23774edb2241c6a111e1db9reed int index = SkTKSearch<Segment, SkScalar>(seg, count, distance); 4828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // don't care if we hit an exact match or not, so we xor index if it is negative 4838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com index ^= (index >> 31); 4848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg = &seg[index]; 4858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now interpolate t-values with the prev segment (if possible) 4878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar startT = 0, startD = 0; 4888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check if the prev segment is legal, and references the same set of points 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (index > 0) { 4908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com startD = seg[-1].fDistance; 4918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (seg[-1].fPtIndex == seg->fPtIndex) { 4928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg[-1].fType == seg->fType); 4938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com startT = seg[-1].getScalarT(); 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg->getScalarT() > startT); 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(distance >= startD); 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg->fDistance > startD); 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *t = startT + SkScalarMulDiv(seg->getScalarT() - startT, 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance - startD, 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fDistance - startD); 5048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return seg; 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos, 5088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkVector* tangent) { 509dfef456f183713da8c05fe5f3d252736a7776c8cdjsollen@google.com if (NULL == fPath) { 5108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar length = this->getLength(); // call this to force computing it 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = fSegments.count(); 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count == 0 || length == 0) { 517a6d04d90e2f0a35698a7380cef8d622a8ee0b33fschenney@chromium.org return false; 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // pin the distance to a legal range 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (distance < 0) { 5228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = 0; 5238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (distance > length) { 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com distance = length; 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 526fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t; 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* seg = this->distanceToSegment(distance, &t); 5298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5305b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent); 5318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix, 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com MatrixFlags flags) { 536dfef456f183713da8c05fe5f3d252736a7776c8cdjsollen@google.com if (NULL == fPath) { 537dfef456f183713da8c05fe5f3d252736a7776c8cdjsollen@google.com return false; 538dfef456f183713da8c05fe5f3d252736a7776c8cdjsollen@google.com } 539dfef456f183713da8c05fe5f3d252736a7776c8cdjsollen@google.com 5408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint position; 5418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkVector tangent; 5428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->getPosTan(distance, &position, &tangent)) { 5448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (matrix) { 5458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (flags & kGetTangent_MatrixFlag) { 5468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix->setSinCos(tangent.fY, tangent.fX, 0, 0); 5478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 5488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix->reset(); 5498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (flags & kGetPosition_MatrixFlag) { 5518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix->postTranslate(position.fX, position.fY); 5528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 5578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst, 5608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool startWithMoveTo) { 5618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(dst); 5628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar length = this->getLength(); // ensure we have built our segments 5648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (startD < 0) { 5668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com startD = 0; 5678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (stopD > length) { 5698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com stopD = length; 5708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (startD >= stopD) { 5728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 5738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint p; 5768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar startT, stopT; 5778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* seg = this->distanceToSegment(startD, &startT); 5788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* stopSeg = this->distanceToSegment(stopD, &stopT); 5798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(seg <= stopSeg); 5808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (startWithMoveTo) { 5825b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, NULL); 5838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst->moveTo(p); 5848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (seg->fPtIndex == stopSeg->fPtIndex) { 5875b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com seg_to(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst); 5888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 5898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 5905b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com seg_to(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst); 5918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg = SkPathMeasure::NextSegment(seg); 5928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com startT = 0; 5938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (seg->fPtIndex < stopSeg->fPtIndex); 5945b94153a7b039a9269a8aabbe8f0da0e878e3978reed@google.com seg_to(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst); 5958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPathMeasure::isClosed() { 6008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (void)this->getLength(); 6018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fIsClosed; 6028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Move to the next contour in the path. Return true if one exists, or false if 6058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com we're done with the path. 6068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 6078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPathMeasure::nextContour() { 6088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLength = -1; 6098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->getLength() > 0; 6108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 6138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 6148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 6168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkPathMeasure::dump() { 6188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count()); 6198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < fSegments.count(); i++) { 6218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Segment* seg = &fSegments[i]; 6228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n", 6238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com i, seg->fDistance, seg->fPtIndex, seg->getScalarT(), 6248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com seg->fType); 6258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 629