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