1 /* 2 * Copyright 2013 Google Inc. 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 #ifndef SkPerlinNoiseShaderImpl_DEFINED 8 #define SkPerlinNoiseShaderImpl_DEFINED 9 10 #include "include/core/SkAlphaType.h" 11 #include "include/core/SkBitmap.h" 12 #include "include/core/SkColorType.h" 13 #include "include/core/SkFlattenable.h" 14 #include "include/core/SkImageInfo.h" 15 #include "include/core/SkPoint.h" 16 #include "include/core/SkScalar.h" 17 #include "include/core/SkSize.h" 18 #include "include/core/SkTypes.h" 19 #include "include/private/base/SkFloatingPoint.h" 20 #include "include/private/base/SkMath.h" 21 #include "include/private/base/SkOnce.h" 22 #include "src/shaders/SkShaderBase.h" 23 24 #include <algorithm> 25 #include <cstdint> 26 #include <cstring> 27 #include <memory> 28 29 class SkReadBuffer; 30 enum class SkPerlinNoiseShaderType; 31 struct SkStageRec; 32 class SkWriteBuffer; 33 34 class SkPerlinNoiseShader : public SkShaderBase { 35 private: 36 static constexpr int kBlockSize = 256; 37 static constexpr int kBlockMask = kBlockSize - 1; 38 static constexpr int kPerlinNoise = 4096; 39 static constexpr int kRandMaximum = SK_MaxS32; // 2**31 - 1 40 41 public: 42 struct StitchData { 43 StitchData() = default; 44 StitchDataStitchData45 StitchData(SkScalar w, SkScalar h) 46 : fWidth(std::min(SkScalarRoundToInt(w), SK_MaxS32 - kPerlinNoise)) 47 , fWrapX(kPerlinNoise + fWidth) 48 , fHeight(std::min(SkScalarRoundToInt(h), SK_MaxS32 - kPerlinNoise)) 49 , fWrapY(kPerlinNoise + fHeight) {} 50 51 bool operator==(const StitchData& other) const { 52 return fWidth == other.fWidth && fWrapX == other.fWrapX && fHeight == other.fHeight && 53 fWrapY == other.fWrapY; 54 } 55 56 int fWidth = 0; // How much to subtract to wrap for stitching. 57 int fWrapX = 0; // Minimum value to wrap. 58 int fHeight = 0; 59 int fWrapY = 0; 60 }; 61 62 struct PaintingData { PaintingDataPaintingData63 PaintingData(const SkISize& tileSize, 64 SkScalar seed, 65 SkScalar baseFrequencyX, 66 SkScalar baseFrequencyY) { 67 fBaseFrequency.set(baseFrequencyX, baseFrequencyY); 68 fTileSize.set(SkScalarRoundToInt(tileSize.fWidth), 69 SkScalarRoundToInt(tileSize.fHeight)); 70 this->init(seed); 71 if (!fTileSize.isEmpty()) { 72 this->stitch(); 73 } 74 } 75 generateBitmapsPaintingData76 void generateBitmaps() { 77 SkImageInfo info = SkImageInfo::MakeA8(kBlockSize, 1); 78 fPermutationsBitmap.installPixels(info, fLatticeSelector, info.minRowBytes()); 79 fPermutationsBitmap.setImmutable(); 80 81 info = SkImageInfo::Make(kBlockSize, 4, kRGBA_8888_SkColorType, kPremul_SkAlphaType); 82 fNoiseBitmap.installPixels(info, fNoise[0][0], info.minRowBytes()); 83 fNoiseBitmap.setImmutable(); 84 } 85 PaintingDataPaintingData86 PaintingData(const PaintingData& that) 87 : fSeed(that.fSeed) 88 , fTileSize(that.fTileSize) 89 , fBaseFrequency(that.fBaseFrequency) 90 , fStitchDataInit(that.fStitchDataInit) 91 , fPermutationsBitmap(that.fPermutationsBitmap) 92 , fNoiseBitmap(that.fNoiseBitmap) { 93 memcpy(fLatticeSelector, that.fLatticeSelector, sizeof(fLatticeSelector)); 94 memcpy(fNoise, that.fNoise, sizeof(fNoise)); 95 } 96 97 int fSeed; 98 uint8_t fLatticeSelector[kBlockSize]; 99 uint16_t fNoise[4][kBlockSize][2]; 100 SkISize fTileSize; 101 SkVector fBaseFrequency; 102 StitchData fStitchDataInit; 103 104 private: 105 SkBitmap fPermutationsBitmap; 106 SkBitmap fNoiseBitmap; 107 randomPaintingData108 int random() { 109 // See https://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement 110 // m = kRandMaximum, 2**31 - 1 (2147483647) 111 static constexpr int kRandAmplitude = 16807; // 7**5; primitive root of m 112 static constexpr int kRandQ = 127773; // m / a 113 static constexpr int kRandR = 2836; // m % a 114 115 int result = kRandAmplitude * (fSeed % kRandQ) - kRandR * (fSeed / kRandQ); 116 if (result <= 0) { 117 result += kRandMaximum; 118 } 119 fSeed = result; 120 return result; 121 } 122 123 // Only called once. Could be part of the constructor. initPaintingData124 void init(SkScalar seed) { 125 // According to the SVG spec, we must truncate (not round) the seed value. 126 fSeed = SkScalarTruncToInt(seed); 127 // The seed value clamp to the range [1, kRandMaximum - 1]. 128 if (fSeed <= 0) { 129 fSeed = -(fSeed % (kRandMaximum - 1)) + 1; 130 } 131 if (fSeed > kRandMaximum - 1) { 132 fSeed = kRandMaximum - 1; 133 } 134 for (int channel = 0; channel < 4; ++channel) { 135 for (int i = 0; i < kBlockSize; ++i) { 136 fLatticeSelector[i] = i; 137 fNoise[channel][i][0] = (random() % (2 * kBlockSize)); 138 fNoise[channel][i][1] = (random() % (2 * kBlockSize)); 139 } 140 } 141 for (int i = kBlockSize - 1; i > 0; --i) { 142 int k = fLatticeSelector[i]; 143 int j = random() % kBlockSize; 144 SkASSERT(j >= 0); 145 SkASSERT(j < kBlockSize); 146 fLatticeSelector[i] = fLatticeSelector[j]; 147 fLatticeSelector[j] = k; 148 } 149 150 // Perform the permutations now 151 { 152 // Copy noise data 153 uint16_t noise[4][kBlockSize][2]; 154 for (int i = 0; i < kBlockSize; ++i) { 155 for (int channel = 0; channel < 4; ++channel) { 156 for (int j = 0; j < 2; ++j) { 157 noise[channel][i][j] = fNoise[channel][i][j]; 158 } 159 } 160 } 161 // Do permutations on noise data 162 for (int i = 0; i < kBlockSize; ++i) { 163 for (int channel = 0; channel < 4; ++channel) { 164 for (int j = 0; j < 2; ++j) { 165 fNoise[channel][i][j] = noise[channel][fLatticeSelector[i]][j]; 166 } 167 } 168 } 169 } 170 171 // Half of the largest possible value for 16 bit unsigned int 172 static constexpr SkScalar kHalfMax16bits = 32767.5f; 173 174 // Compute gradients from permuted noise data 175 static constexpr SkScalar kInvBlockSizef = 1.0 / SkIntToScalar(kBlockSize); 176 for (int channel = 0; channel < 4; ++channel) { 177 for (int i = 0; i < kBlockSize; ++i) { 178 SkPoint gradient = 179 SkPoint::Make((fNoise[channel][i][0] - kBlockSize) * kInvBlockSizef, 180 (fNoise[channel][i][1] - kBlockSize) * kInvBlockSizef); 181 gradient.normalize(); 182 // Put the normalized gradient back into the noise data 183 fNoise[channel][i][0] = SkScalarRoundToInt((gradient.fX + 1) * kHalfMax16bits); 184 fNoise[channel][i][1] = SkScalarRoundToInt((gradient.fY + 1) * kHalfMax16bits); 185 } 186 } 187 } 188 189 // Only called once. Could be part of the constructor. stitchPaintingData190 void stitch() { 191 SkScalar tileWidth = SkIntToScalar(fTileSize.width()); 192 SkScalar tileHeight = SkIntToScalar(fTileSize.height()); 193 SkASSERT(tileWidth > 0 && tileHeight > 0); 194 // When stitching tiled turbulence, the frequencies must be adjusted 195 // so that the tile borders will be continuous. 196 if (fBaseFrequency.fX) { 197 SkScalar lowFrequencx = 198 SkScalarFloorToScalar(tileWidth * fBaseFrequency.fX) / tileWidth; 199 SkScalar highFrequencx = 200 SkScalarCeilToScalar(tileWidth * fBaseFrequency.fX) / tileWidth; 201 // BaseFrequency should be non-negative according to the standard. 202 // lowFrequencx can be 0 if fBaseFrequency.fX is very small. 203 if (sk_ieee_float_divide(fBaseFrequency.fX, lowFrequencx) < 204 highFrequencx / fBaseFrequency.fX) { 205 fBaseFrequency.fX = lowFrequencx; 206 } else { 207 fBaseFrequency.fX = highFrequencx; 208 } 209 } 210 if (fBaseFrequency.fY) { 211 SkScalar lowFrequency = 212 SkScalarFloorToScalar(tileHeight * fBaseFrequency.fY) / tileHeight; 213 SkScalar highFrequency = 214 SkScalarCeilToScalar(tileHeight * fBaseFrequency.fY) / tileHeight; 215 // lowFrequency can be 0 if fBaseFrequency.fY is very small. 216 if (sk_ieee_float_divide(fBaseFrequency.fY, lowFrequency) < 217 highFrequency / fBaseFrequency.fY) { 218 fBaseFrequency.fY = lowFrequency; 219 } else { 220 fBaseFrequency.fY = highFrequency; 221 } 222 } 223 fStitchDataInit = 224 StitchData(tileWidth * fBaseFrequency.fX, tileHeight * fBaseFrequency.fY); 225 } 226 227 public: getPermutationsBitmapPaintingData228 const SkBitmap& getPermutationsBitmap() const { 229 SkASSERT(!fPermutationsBitmap.drawsNothing()); 230 return fPermutationsBitmap; 231 } getNoiseBitmapPaintingData232 const SkBitmap& getNoiseBitmap() const { 233 SkASSERT(!fNoiseBitmap.drawsNothing()); 234 return fNoiseBitmap; 235 } 236 }; // struct PaintingData 237 238 static const int kMaxOctaves = 255; // numOctaves must be <= 0 and <= kMaxOctaves 239 240 SkPerlinNoiseShader(SkPerlinNoiseShaderType type, 241 SkScalar baseFrequencyX, 242 SkScalar baseFrequencyY, 243 int numOctaves, 244 SkScalar seed, 245 const SkISize* tileSize); 246 type()247 ShaderType type() const override { return ShaderType::kPerlinNoise; } 248 noiseType()249 SkPerlinNoiseShaderType noiseType() const { return fType; } numOctaves()250 int numOctaves() const { return fNumOctaves; } stitchTiles()251 bool stitchTiles() const { return fStitchTiles; } tileSize()252 SkISize tileSize() const { return fTileSize; } 253 getPaintingData()254 std::unique_ptr<PaintingData> getPaintingData() const { 255 return std::make_unique<PaintingData>(fTileSize, fSeed, fBaseFrequencyX, fBaseFrequencyY); 256 } 257 258 bool appendStages(const SkStageRec& rec, const SkShaders::MatrixRec& mRec) const override; 259 260 protected: 261 void flatten(SkWriteBuffer&) const override; 262 263 private: 264 SK_FLATTENABLE_HOOKS(SkPerlinNoiseShader) 265 266 const SkPerlinNoiseShaderType fType; 267 const SkScalar fBaseFrequencyX; 268 const SkScalar fBaseFrequencyY; 269 const int fNumOctaves; 270 const SkScalar fSeed; 271 const SkISize fTileSize; 272 const bool fStitchTiles; 273 274 mutable SkOnce fInitPaintingDataOnce; 275 std::unique_ptr<PaintingData> fPaintingData; 276 277 friend void SkRegisterPerlinNoiseShaderFlattenable(); 278 }; 279 280 #endif 281