1 /*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8
9 #include "include/core/SkPathMeasure.h"
10 #include "include/core/SkStrokeRec.h"
11 #include "include/effects/SkDiscretePathEffect.h"
12 #include "include/private/SkFixed.h"
13 #include "src/core/SkPathEffectBase.h"
14 #include "src/core/SkPointPriv.h"
15 #include "src/core/SkReadBuffer.h"
16 #include "src/core/SkWriteBuffer.h"
17
18 /** \class LCGRandom
19
20 Utility class that implements pseudo random 32bit numbers using a fast
21 linear equation. Unlike rand(), this class holds its own seed (initially
22 set to 0), so that multiple instances can be used with no side-effects.
23
24 Copied from the original implementation of SkRandom. Only contains the
25 methods used by SkDiscretePathEffect::filterPath, with methods that were
26 not called directly moved to private.
27 */
28 class LCGRandom {
29 public:
LCGRandom(uint32_t seed)30 LCGRandom(uint32_t seed) : fSeed(seed) {}
31
32 /** Return the next pseudo random number expressed as a SkScalar
33 in the range [-SK_Scalar1..SK_Scalar1).
34 */
nextSScalar1()35 SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
36
37 private:
38 /** Return the next pseudo random number as an unsigned 32bit value.
39 */
nextU()40 uint32_t nextU() { uint32_t r = fSeed * kMul + kAdd; fSeed = r; return r; }
41
42 /** Return the next pseudo random number as a signed 32bit value.
43 */
nextS()44 int32_t nextS() { return (int32_t)this->nextU(); }
45
46 /** Return the next pseudo random number expressed as a signed SkFixed
47 in the range [-SK_Fixed1..SK_Fixed1).
48 */
nextSFixed1()49 SkFixed nextSFixed1() { return this->nextS() >> 15; }
50
51 // See "Numerical Recipes in C", 1992 page 284 for these constants
52 enum {
53 kMul = 1664525,
54 kAdd = 1013904223
55 };
56 uint32_t fSeed;
57 };
58
Perterb(SkPoint * p,const SkVector & tangent,SkScalar scale)59 static void Perterb(SkPoint* p, const SkVector& tangent, SkScalar scale) {
60 SkVector normal = tangent;
61 SkPointPriv::RotateCCW(&normal);
62 normal.setLength(scale);
63 *p += normal;
64 }
65
66 class SK_API SkDiscretePathEffectImpl : public SkPathEffectBase {
67 public:
SkDiscretePathEffectImpl(SkScalar segLength,SkScalar deviation,uint32_t seedAssist)68 SkDiscretePathEffectImpl(SkScalar segLength, SkScalar deviation, uint32_t seedAssist)
69 : fSegLength(segLength), fPerterb(deviation), fSeedAssist(seedAssist)
70 {
71 SkASSERT(SkScalarIsFinite(segLength));
72 SkASSERT(SkScalarIsFinite(deviation));
73 SkASSERT(segLength > SK_ScalarNearlyZero);
74 }
75
onFilterPath(SkPath * dst,const SkPath & src,SkStrokeRec * rec,const SkRect *,const SkMatrix &) const76 bool onFilterPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
77 const SkRect*, const SkMatrix&) const override {
78 bool doFill = rec->isFillStyle();
79
80 SkPathMeasure meas(src, doFill);
81
82 /* Caller may supply their own seed assist, which by default is 0 */
83 uint32_t seed = fSeedAssist ^ SkScalarRoundToInt(meas.getLength());
84
85 LCGRandom rand(seed ^ ((seed << 16) | (seed >> 16)));
86 SkScalar scale = fPerterb;
87 SkPoint p;
88 SkVector v;
89
90 do {
91 SkScalar length = meas.getLength();
92 #if defined(SK_BUILD_FOR_FUZZER)
93 if (length > 1000) {
94 return false;
95 }
96 #endif
97
98 if (fSegLength * (2 + doFill) > length) {
99 meas.getSegment(0, length, dst, true); // to short for us to mangle
100 } else {
101 int n = SkScalarRoundToInt(length / fSegLength);
102 constexpr int kMaxReasonableIterations = 100000;
103 n = std::min(n, kMaxReasonableIterations);
104 SkScalar delta = length / n;
105 SkScalar distance = 0;
106
107 if (meas.isClosed()) {
108 n -= 1;
109 distance += delta/2;
110 }
111
112 if (meas.getPosTan(distance, &p, &v)) {
113 Perterb(&p, v, rand.nextSScalar1() * scale);
114 dst->moveTo(p);
115 }
116 while (--n >= 0) {
117 distance += delta;
118 if (meas.getPosTan(distance, &p, &v)) {
119 Perterb(&p, v, rand.nextSScalar1() * scale);
120 dst->lineTo(p);
121 }
122 }
123 if (meas.isClosed()) {
124 dst->close();
125 }
126 }
127 } while (meas.nextContour());
128 return true;
129 }
130
computeFastBounds(SkRect * bounds) const131 bool computeFastBounds(SkRect* bounds) const override {
132 if (bounds) {
133 SkScalar maxOutset = SkScalarAbs(fPerterb);
134 bounds->outset(maxOutset, maxOutset);
135 }
136 return true;
137 }
138
CreateProc(SkReadBuffer & buffer)139 static sk_sp<SkFlattenable> CreateProc(SkReadBuffer& buffer) {
140 SkScalar segLength = buffer.readScalar();
141 SkScalar perterb = buffer.readScalar();
142 uint32_t seed = buffer.readUInt();
143 return SkDiscretePathEffect::Make(segLength, perterb, seed);
144 }
145
flatten(SkWriteBuffer & buffer) const146 void flatten(SkWriteBuffer& buffer) const override {
147 buffer.writeScalar(fSegLength);
148 buffer.writeScalar(fPerterb);
149 buffer.writeUInt(fSeedAssist);
150 }
151
getFactory() const152 Factory getFactory() const override { return CreateProc; }
getTypeName() const153 const char* getTypeName() const override { return "SkDiscretePathEffect"; }
154
155 private:
156 const SkScalar fSegLength,
157 fPerterb;
158 /* Caller-supplied 32 bit seed assist */
159 const uint32_t fSeedAssist;
160
161 using INHERITED = SkPathEffectBase;
162 };
163
164 //////////////////////////////////////////////////////////////////////////////////////////////////
165
Make(SkScalar segLength,SkScalar deviation,uint32_t seedAssist)166 sk_sp<SkPathEffect> SkDiscretePathEffect::Make(SkScalar segLength, SkScalar deviation,
167 uint32_t seedAssist) {
168 if (!SkScalarIsFinite(segLength) || !SkScalarIsFinite(deviation)) {
169 return nullptr;
170 }
171 if (segLength <= SK_ScalarNearlyZero) {
172 return nullptr;
173 }
174 return sk_sp<SkPathEffect>(new SkDiscretePathEffectImpl(segLength, deviation, seedAssist));
175 }
176
RegisterFlattenables()177 void SkDiscretePathEffect::RegisterFlattenables() {
178 SkFlattenable::Register("SkDiscretePathEffect", SkDiscretePathEffectImpl::CreateProc);
179 }
180