/*
* Copyright 2006 The Android Open Source Project
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkDashPathEffect.h"
#include "SkFlattenableBuffers.h"
#include "SkPathMeasure.h"
static inline int is_even(int x) {
return (~x) << 31;
}
static SkScalar FindFirstInterval(const SkScalar intervals[], SkScalar phase,
int32_t* index, int count) {
for (int i = 0; i < count; ++i) {
if (phase > intervals[i]) {
phase -= intervals[i];
} else {
*index = i;
return intervals[i] - phase;
}
}
// If we get here, phase "appears" to be larger than our length. This
// shouldn't happen with perfect precision, but we can accumulate errors
// during the initial length computation (rounding can make our sum be too
// big or too small. In that event, we just have to eat the error here.
*index = 0;
return intervals[0];
}
SkDashPathEffect::SkDashPathEffect(const SkScalar intervals[], int count,
SkScalar phase, bool scaleToFit)
: fScaleToFit(scaleToFit) {
SkASSERT(intervals);
SkASSERT(count > 1 && SkAlign2(count) == count);
fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * count);
fCount = count;
SkScalar len = 0;
for (int i = 0; i < count; i++) {
SkASSERT(intervals[i] >= 0);
fIntervals[i] = intervals[i];
len += intervals[i];
}
fIntervalLength = len;
// watch out for values that might make us go out of bounds
if ((len > 0) && SkScalarIsFinite(phase) && SkScalarIsFinite(len)) {
// Adjust phase to be between 0 and len, "flipping" phase if negative.
// e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80
if (phase < 0) {
phase = -phase;
if (phase > len) {
phase = SkScalarMod(phase, len);
}
phase = len - phase;
// Due to finite precision, it's possible that phase == len,
// even after the subtract (if len >>> phase), so fix that here.
// This fixes http://crbug.com/124652 .
SkASSERT(phase <= len);
if (phase == len) {
phase = 0;
}
} else if (phase >= len) {
phase = SkScalarMod(phase, len);
}
SkASSERT(phase >= 0 && phase < len);
fInitialDashLength = FindFirstInterval(intervals, phase,
&fInitialDashIndex, count);
SkASSERT(fInitialDashLength >= 0);
SkASSERT(fInitialDashIndex >= 0 && fInitialDashIndex < fCount);
} else {
fInitialDashLength = -1; // signal bad dash intervals
}
}
SkDashPathEffect::~SkDashPathEffect() {
sk_free(fIntervals);
}
static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
SkScalar radius = SkScalarHalf(rec.getWidth());
if (0 == radius) {
radius = SK_Scalar1; // hairlines
}
if (SkPaint::kMiter_Join == rec.getJoin()) {
radius = SkScalarMul(radius, rec.getMiter());
}
rect->outset(radius, radius);
}
// Only handles lines for now. If returns true, dstPath is the new (smaller)
// path. If returns false, then dstPath parameter is ignored.
static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
const SkRect* cullRect, SkScalar intervalLength,
SkPath* dstPath) {
if (NULL == cullRect) {
return false;
}
SkPoint pts[2];
if (!srcPath.isLine(pts)) {
return false;
}
SkRect bounds = *cullRect;
outset_for_stroke(&bounds, rec);
SkScalar dx = pts[1].x() - pts[0].x();
SkScalar dy = pts[1].y() - pts[0].y();
// just do horizontal lines for now (lazy)
if (dy) {
return false;
}
SkScalar minX = pts[0].fX;
SkScalar maxX = pts[1].fX;
if (maxX < bounds.fLeft || minX > bounds.fRight) {
return false;
}
if (dx < 0) {
SkTSwap(minX, maxX);
}
// Now we actually perform the chop, removing the excess to the left and
// right of the bounds (keeping our new line "in phase" with the dash,
// hence the (mod intervalLength).
if (minX < bounds.fLeft) {
minX = bounds.fLeft - SkScalarMod(bounds.fLeft - minX,
intervalLength);
}
if (maxX > bounds.fRight) {
maxX = bounds.fRight + SkScalarMod(maxX - bounds.fRight,
intervalLength);
}
SkASSERT(maxX >= minX);
if (dx < 0) {
SkTSwap(minX, maxX);
}
pts[0].fX = minX;
pts[1].fX = maxX;
dstPath->moveTo(pts[0]);
dstPath->lineTo(pts[1]);
return true;
}
class SpecialLineRec {
public:
bool init(const SkPath& src, SkPath* dst, SkStrokeRec* rec,
int intervalCount, SkScalar intervalLength) {
if (rec->isHairlineStyle() || !src.isLine(fPts)) {
return false;
}
// can relax this in the future, if we handle square and round caps
if (SkPaint::kButt_Cap != rec->getCap()) {
return false;
}
SkScalar pathLength = SkPoint::Distance(fPts[0], fPts[1]);
fTangent = fPts[1] - fPts[0];
if (fTangent.isZero()) {
return false;
}
fPathLength = pathLength;
fTangent.scale(SkScalarInvert(pathLength));
fTangent.rotateCCW(&fNormal);
fNormal.scale(SkScalarHalf(rec->getWidth()));
// now estimate how many quads will be added to the path
// resulting segments = pathLen * intervalCount / intervalLen
// resulting points = 4 * segments
SkScalar ptCount = SkScalarMulDiv(pathLength,
SkIntToScalar(intervalCount),
intervalLength);
int n = SkScalarCeilToInt(ptCount) << 2;
dst->incReserve(n);
// we will take care of the stroking
rec->setFillStyle();
return true;
}
void addSegment(SkScalar d0, SkScalar d1, SkPath* path) const {
SkASSERT(d0 < fPathLength);
// clamp the segment to our length
if (d1 > fPathLength) {
d1 = fPathLength;
}
SkScalar x0 = fPts[0].fX + SkScalarMul(fTangent.fX, d0);
SkScalar x1 = fPts[0].fX + SkScalarMul(fTangent.fX, d1);
SkScalar y0 = fPts[0].fY + SkScalarMul(fTangent.fY, d0);
SkScalar y1 = fPts[0].fY + SkScalarMul(fTangent.fY, d1);
SkPoint pts[4];
pts[0].set(x0 + fNormal.fX, y0 + fNormal.fY); // moveTo
pts[1].set(x1 + fNormal.fX, y1 + fNormal.fY); // lineTo
pts[2].set(x1 - fNormal.fX, y1 - fNormal.fY); // lineTo
pts[3].set(x0 - fNormal.fX, y0 - fNormal.fY); // lineTo
path->addPoly(pts, SK_ARRAY_COUNT(pts), false);
}
private:
SkPoint fPts[2];
SkVector fTangent;
SkVector fNormal;
SkScalar fPathLength;
};
bool SkDashPathEffect::filterPath(SkPath* dst, const SkPath& src,
SkStrokeRec* rec, const SkRect* cullRect) const {
// we do nothing if the src wants to be filled, or if our dashlength is 0
if (rec->isFillStyle() || fInitialDashLength < 0) {
return false;
}
const SkScalar* intervals = fIntervals;
SkScalar dashCount = 0;
int segCount = 0;
SkPath cullPathStorage;
const SkPath* srcPtr = &src;
if (cull_path(src, *rec, cullRect, fIntervalLength, &cullPathStorage)) {
srcPtr = &cullPathStorage;
}
SpecialLineRec lineRec;
bool specialLine = lineRec.init(*srcPtr, dst, rec, fCount >> 1, fIntervalLength);
SkPathMeasure meas(*srcPtr, false);
do {
bool skipFirstSegment = meas.isClosed();
bool addedSegment = false;
SkScalar length = meas.getLength();
int index = fInitialDashIndex;
SkScalar scale = SK_Scalar1;
// Since the path length / dash length ratio may be arbitrarily large, we can exert
// significant memory pressure while attempting to build the filtered path. To avoid this,
// we simply give up dashing beyond a certain threshold.
//
// The original bug report (http://crbug.com/165432) is based on a path yielding more than
// 90 million dash segments and crashing the memory allocator. A limit of 1 million
// segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
// maximum dash memory overhead at roughly 17MB per path.
static const SkScalar kMaxDashCount = 1000000;
dashCount += length * (fCount >> 1) / fIntervalLength;
if (dashCount > kMaxDashCount) {
dst->reset();
return false;
}
if (fScaleToFit) {
if (fIntervalLength >= length) {
scale = SkScalarDiv(length, fIntervalLength);
} else {
SkScalar div = SkScalarDiv(length, fIntervalLength);
int n = SkScalarFloor(div);
scale = SkScalarDiv(length, n * fIntervalLength);
}
}
// Using double precision to avoid looping indefinitely due to single precision rounding
// (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
double distance = 0;
double dlen = SkScalarMul(fInitialDashLength, scale);
while (distance < length) {
SkASSERT(dlen >= 0);
addedSegment = false;
if (is_even(index) && dlen > 0 && !skipFirstSegment) {
addedSegment = true;
++segCount;
if (specialLine) {
lineRec.addSegment(SkDoubleToScalar(distance),
SkDoubleToScalar(distance + dlen),
dst);
} else {
meas.getSegment(SkDoubleToScalar(distance),
SkDoubleToScalar(distance + dlen),
dst, true);
}
}
distance += dlen;
// clear this so we only respect it the first time around
skipFirstSegment = false;
// wrap around our intervals array if necessary
index += 1;
SkASSERT(index <= fCount);
if (index == fCount) {
index = 0;
}
// fetch our next dlen
dlen = SkScalarMul(intervals[index], scale);
}
// extend if we ended on a segment and we need to join up with the (skipped) initial segment
if (meas.isClosed() && is_even(fInitialDashIndex) &&
fInitialDashLength > 0) {
meas.getSegment(0, SkScalarMul(fInitialDashLength, scale), dst, !addedSegment);
++segCount;
}
} while (meas.nextContour());
if (segCount > 1) {
dst->setConvexity(SkPath::kConcave_Convexity);
}
return true;
}
// Currently asPoints is more restrictive then it needs to be. In the future
// we need to:
// allow kRound_Cap capping (could allow rotations in the matrix with this)
// allow paths to be returned
bool SkDashPathEffect::asPoints(PointData* results,
const SkPath& src,
const SkStrokeRec& rec,
const SkMatrix& matrix,
const SkRect* cullRect) const {
// width < 0 -> fill && width == 0 -> hairline so requiring width > 0 rules both out
if (fInitialDashLength < 0 || 0 >= rec.getWidth()) {
return false;
}
// TODO: this next test could be eased up. We could allow any number of
// intervals as long as all the ons match and all the offs match.
// Additionally, they do not necessarily need to be integers.
// We cannot allow arbitrary intervals since we want the returned points
// to be uniformly sized.
if (fCount != 2 ||
!SkScalarNearlyEqual(fIntervals[0], fIntervals[1]) ||
!SkScalarIsInt(fIntervals[0]) ||
!SkScalarIsInt(fIntervals[1])) {
return false;
}
// TODO: this next test could be eased up. The rescaling should not impact
// the equality of the ons & offs. However, we would need to remove the
// integer intervals restriction first
if (fScaleToFit) {
return false;
}
SkPoint pts[2];
if (!src.isLine(pts)) {
return false;
}
// TODO: this test could be eased up to allow circles
if (SkPaint::kButt_Cap != rec.getCap()) {
return false;
}
// TODO: this test could be eased up for circles. Rotations could be allowed.
if (!matrix.rectStaysRect()) {
return false;
}
SkScalar length = SkPoint::Distance(pts[1], pts[0]);
SkVector tangent = pts[1] - pts[0];
if (tangent.isZero()) {
return false;
}
tangent.scale(SkScalarInvert(length));
// TODO: make this test for horizontal & vertical lines more robust
bool isXAxis = true;
if (SK_Scalar1 == tangent.fX || -SK_Scalar1 == tangent.fX) {
results->fSize.set(SkScalarHalf(fIntervals[0]), SkScalarHalf(rec.getWidth()));
} else if (SK_Scalar1 == tangent.fY || -SK_Scalar1 == tangent.fY) {
results->fSize.set(SkScalarHalf(rec.getWidth()), SkScalarHalf(fIntervals[0]));
isXAxis = false;
} else if (SkPaint::kRound_Cap != rec.getCap()) {
// Angled lines don't have axis-aligned boxes.
return false;
}
if (NULL != results) {
results->fFlags = 0;
SkScalar clampedInitialDashLength = SkMinScalar(length, fInitialDashLength);
if (SkPaint::kRound_Cap == rec.getCap()) {
results->fFlags |= PointData::kCircles_PointFlag;
}
results->fNumPoints = 0;
SkScalar len2 = length;
if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
SkASSERT(len2 >= clampedInitialDashLength);
if (0 == fInitialDashIndex) {
if (clampedInitialDashLength > 0) {
if (clampedInitialDashLength >= fIntervals[0]) {
++results->fNumPoints; // partial first dash
}
len2 -= clampedInitialDashLength;
}
len2 -= fIntervals[1]; // also skip first space
if (len2 < 0) {
len2 = 0;
}
} else {
len2 -= clampedInitialDashLength; // skip initial partial empty
}
}
int numMidPoints = SkScalarFloorToInt(SkScalarDiv(len2, fIntervalLength));
results->fNumPoints += numMidPoints;
len2 -= numMidPoints * fIntervalLength;
bool partialLast = false;
if (len2 > 0) {
if (len2 < fIntervals[0]) {
partialLast = true;
} else {
++numMidPoints;
++results->fNumPoints;
}
}
results->fPoints = new SkPoint[results->fNumPoints];
SkScalar distance = 0;
int curPt = 0;
if (clampedInitialDashLength > 0 || 0 == fInitialDashIndex) {
SkASSERT(clampedInitialDashLength <= length);
if (0 == fInitialDashIndex) {
if (clampedInitialDashLength > 0) {
// partial first block
SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, SkScalarHalf(clampedInitialDashLength));
SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, SkScalarHalf(clampedInitialDashLength));
SkScalar halfWidth, halfHeight;
if (isXAxis) {
halfWidth = SkScalarHalf(clampedInitialDashLength);
halfHeight = SkScalarHalf(rec.getWidth());
} else {
halfWidth = SkScalarHalf(rec.getWidth());
halfHeight = SkScalarHalf(clampedInitialDashLength);
}
if (clampedInitialDashLength < fIntervals[0]) {
// This one will not be like the others
results->fFirst.addRect(x - halfWidth, y - halfHeight,
x + halfWidth, y + halfHeight);
} else {
SkASSERT(curPt < results->fNumPoints);
results->fPoints[curPt].set(x, y);
++curPt;
}
distance += clampedInitialDashLength;
}
distance += fIntervals[1]; // skip over the next blank block too
} else {
distance += clampedInitialDashLength;
}
}
if (0 != numMidPoints) {
distance += SkScalarHalf(fIntervals[0]);
for (int i = 0; i < numMidPoints; ++i) {
SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance);
SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance);
SkASSERT(curPt < results->fNumPoints);
results->fPoints[curPt].set(x, y);
++curPt;
distance += fIntervalLength;
}
distance -= SkScalarHalf(fIntervals[0]);
}
if (partialLast) {
// partial final block
SkASSERT(SkPaint::kRound_Cap != rec.getCap()); // can't handle partial circles
SkScalar temp = length - distance;
SkASSERT(temp < fIntervals[0]);
SkScalar x = pts[0].fX + SkScalarMul(tangent.fX, distance + SkScalarHalf(temp));
SkScalar y = pts[0].fY + SkScalarMul(tangent.fY, distance + SkScalarHalf(temp));
SkScalar halfWidth, halfHeight;
if (isXAxis) {
halfWidth = SkScalarHalf(temp);
halfHeight = SkScalarHalf(rec.getWidth());
} else {
halfWidth = SkScalarHalf(rec.getWidth());
halfHeight = SkScalarHalf(temp);
}
results->fLast.addRect(x - halfWidth, y - halfHeight,
x + halfWidth, y + halfHeight);
}
SkASSERT(curPt == results->fNumPoints);
}
return true;
}
SkFlattenable::Factory SkDashPathEffect::getFactory() const {
return fInitialDashLength < 0 ? NULL : CreateProc;
}
void SkDashPathEffect::flatten(SkFlattenableWriteBuffer& buffer) const {
SkASSERT(fInitialDashLength >= 0);
this->INHERITED::flatten(buffer);
buffer.writeInt(fInitialDashIndex);
buffer.writeScalar(fInitialDashLength);
buffer.writeScalar(fIntervalLength);
buffer.writeBool(fScaleToFit);
buffer.writeScalarArray(fIntervals, fCount);
}
SkFlattenable* SkDashPathEffect::CreateProc(SkFlattenableReadBuffer& buffer) {
return SkNEW_ARGS(SkDashPathEffect, (buffer));
}
SkDashPathEffect::SkDashPathEffect(SkFlattenableReadBuffer& buffer) : INHERITED(buffer) {
fInitialDashIndex = buffer.readInt();
fInitialDashLength = buffer.readScalar();
fIntervalLength = buffer.readScalar();
fScaleToFit = buffer.readBool();
fCount = buffer.getArrayCount();
fIntervals = (SkScalar*)sk_malloc_throw(sizeof(SkScalar) * fCount);
buffer.readScalarArray(fIntervals, fCount);
}