1 /* 2 * Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann <zimmermann (at) kde.org> 3 * Copyright (C) 2004, 2005 Rob Buis <buis (at) kde.org> 4 * Copyright (C) 2005 Eric Seidel <eric (at) webkit.org> 5 * Copyright (C) 2009 Dirk Schulze <krit (at) webkit.org> 6 * Copyright (C) 2010 Renata Hodovan <reni (at) inf.u-szeged.hu> 7 * Copyright (C) 2011 Gabor Loki <loki (at) webkit.org> 8 * Copyright (C) 2013 Google Inc. All rights reserved. 9 * 10 * This library is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU Library General Public 12 * License as published by the Free Software Foundation; either 13 * version 2 of the License, or (at your option) any later version. 14 * 15 * This library is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * Library General Public License for more details. 19 * 20 * You should have received a copy of the GNU Library General Public License 21 * along with this library; see the file COPYING.LIB. If not, write to 22 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 23 * Boston, MA 02110-1301, USA. 24 */ 25 26 #include "config.h" 27 28 #include "core/platform/graphics/filters/FETurbulence.h" 29 #include "SkPerlinNoiseShader.h" 30 #include "SkRectShaderImageFilter.h" 31 #include "core/platform/graphics/filters/Filter.h" 32 #include "core/platform/text/TextStream.h" 33 #include "core/rendering/RenderTreeAsText.h" 34 35 #include "wtf/MathExtras.h" 36 #include "wtf/ParallelJobs.h" 37 #include "wtf/Uint8ClampedArray.h" 38 39 namespace WebCore { 40 41 /* 42 Produces results in the range [1, 2**31 - 2]. Algorithm is: 43 r = (a * r) mod m where a = randAmplitude = 16807 and 44 m = randMaximum = 2**31 - 1 = 2147483647, r = seed. 45 See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988 46 To test: the algorithm should produce the result 1043618065 47 as the 10,000th generated number if the original seed is 1. 48 */ 49 static const int s_perlinNoise = 4096; 50 static const long s_randMaximum = 2147483647; // 2**31 - 1 51 static const int s_randAmplitude = 16807; // 7**5; primitive root of m 52 static const int s_randQ = 127773; // m / a 53 static const int s_randR = 2836; // m % a 54 55 FETurbulence::FETurbulence(Filter* filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles) 56 : FilterEffect(filter) 57 , m_type(type) 58 , m_baseFrequencyX(baseFrequencyX) 59 , m_baseFrequencyY(baseFrequencyY) 60 , m_numOctaves(numOctaves) 61 , m_seed(seed) 62 , m_stitchTiles(stitchTiles) 63 { 64 } 65 66 PassRefPtr<FETurbulence> FETurbulence::create(Filter* filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles) 67 { 68 return adoptRef(new FETurbulence(filter, type, baseFrequencyX, baseFrequencyY, numOctaves, seed, stitchTiles)); 69 } 70 71 TurbulenceType FETurbulence::type() const 72 { 73 return m_type; 74 } 75 76 bool FETurbulence::setType(TurbulenceType type) 77 { 78 if (m_type == type) 79 return false; 80 m_type = type; 81 return true; 82 } 83 84 float FETurbulence::baseFrequencyY() const 85 { 86 return m_baseFrequencyY; 87 } 88 89 bool FETurbulence::setBaseFrequencyY(float baseFrequencyY) 90 { 91 if (m_baseFrequencyY == baseFrequencyY) 92 return false; 93 m_baseFrequencyY = baseFrequencyY; 94 return true; 95 } 96 97 float FETurbulence::baseFrequencyX() const 98 { 99 return m_baseFrequencyX; 100 } 101 102 bool FETurbulence::setBaseFrequencyX(float baseFrequencyX) 103 { 104 if (m_baseFrequencyX == baseFrequencyX) 105 return false; 106 m_baseFrequencyX = baseFrequencyX; 107 return true; 108 } 109 110 float FETurbulence::seed() const 111 { 112 return m_seed; 113 } 114 115 bool FETurbulence::setSeed(float seed) 116 { 117 if (m_seed == seed) 118 return false; 119 m_seed = seed; 120 return true; 121 } 122 123 int FETurbulence::numOctaves() const 124 { 125 return m_numOctaves; 126 } 127 128 bool FETurbulence::setNumOctaves(int numOctaves) 129 { 130 if (m_numOctaves == numOctaves) 131 return false; 132 m_numOctaves = numOctaves; 133 return true; 134 } 135 136 bool FETurbulence::stitchTiles() const 137 { 138 return m_stitchTiles; 139 } 140 141 bool FETurbulence::setStitchTiles(bool stitch) 142 { 143 if (m_stitchTiles == stitch) 144 return false; 145 m_stitchTiles = stitch; 146 return true; 147 } 148 149 // The turbulence calculation code is an adapted version of what appears in the SVG 1.1 specification: 150 // http://www.w3.org/TR/SVG11/filters.html#feTurbulence 151 152 // Compute pseudo random number. 153 inline long FETurbulence::PaintingData::random() 154 { 155 long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ); 156 if (result <= 0) 157 result += s_randMaximum; 158 seed = result; 159 return result; 160 } 161 162 inline float smoothCurve(float t) 163 { 164 return t * t * (3 - 2 * t); 165 } 166 167 inline float linearInterpolation(float t, float a, float b) 168 { 169 return a + t * (b - a); 170 } 171 172 inline void FETurbulence::initPaint(PaintingData& paintingData) 173 { 174 float normalizationFactor; 175 176 // The seed value clamp to the range [1, s_randMaximum - 1]. 177 if (paintingData.seed <= 0) 178 paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1; 179 if (paintingData.seed > s_randMaximum - 1) 180 paintingData.seed = s_randMaximum - 1; 181 182 float* gradient; 183 for (int channel = 0; channel < 4; ++channel) { 184 for (int i = 0; i < s_blockSize; ++i) { 185 paintingData.latticeSelector[i] = i; 186 gradient = paintingData.gradient[channel][i]; 187 gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize; 188 gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize; 189 normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]); 190 gradient[0] /= normalizationFactor; 191 gradient[1] /= normalizationFactor; 192 } 193 } 194 for (int i = s_blockSize - 1; i > 0; --i) { 195 int k = paintingData.latticeSelector[i]; 196 int j = paintingData.random() % s_blockSize; 197 ASSERT(j >= 0); 198 ASSERT(j < 2 * s_blockSize + 2); 199 paintingData.latticeSelector[i] = paintingData.latticeSelector[j]; 200 paintingData.latticeSelector[j] = k; 201 } 202 for (int i = 0; i < s_blockSize + 2; ++i) { 203 paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i]; 204 for (int channel = 0; channel < 4; ++channel) { 205 paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0]; 206 paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1]; 207 } 208 } 209 } 210 211 inline void checkNoise(int& noiseValue, int limitValue, int newValue) 212 { 213 if (noiseValue >= limitValue) 214 noiseValue -= newValue; 215 if (noiseValue >= limitValue - 1) 216 noiseValue -= newValue - 1; 217 } 218 219 float FETurbulence::noise2D(int channel, PaintingData& paintingData, StitchData& stitchData, const FloatPoint& noiseVector) 220 { 221 struct Noise { 222 int noisePositionIntegerValue; 223 float noisePositionFractionValue; 224 225 Noise(float component) 226 { 227 float position = component + s_perlinNoise; 228 noisePositionIntegerValue = static_cast<int>(position); 229 noisePositionFractionValue = position - noisePositionIntegerValue; 230 } 231 }; 232 233 Noise noiseX(noiseVector.x()); 234 Noise noiseY(noiseVector.y()); 235 float* q; 236 float sx, sy, a, b, u, v; 237 238 // If stitching, adjust lattice points accordingly. 239 if (m_stitchTiles) { 240 checkNoise(noiseX.noisePositionIntegerValue, stitchData.wrapX, stitchData.width); 241 checkNoise(noiseY.noisePositionIntegerValue, stitchData.wrapY, stitchData.height); 242 } 243 244 noiseX.noisePositionIntegerValue &= s_blockMask; 245 noiseY.noisePositionIntegerValue &= s_blockMask; 246 int latticeIndex = paintingData.latticeSelector[noiseX.noisePositionIntegerValue]; 247 int nextLatticeIndex = paintingData.latticeSelector[(noiseX.noisePositionIntegerValue + 1) & s_blockMask]; 248 249 sx = smoothCurve(noiseX.noisePositionFractionValue); 250 sy = smoothCurve(noiseY.noisePositionFractionValue); 251 252 // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement. 253 int temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue]; 254 q = paintingData.gradient[channel][temp]; 255 u = noiseX.noisePositionFractionValue * q[0] + noiseY.noisePositionFractionValue * q[1]; 256 temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue]; 257 q = paintingData.gradient[channel][temp]; 258 v = (noiseX.noisePositionFractionValue - 1) * q[0] + noiseY.noisePositionFractionValue * q[1]; 259 a = linearInterpolation(sx, u, v); 260 temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue + 1]; 261 q = paintingData.gradient[channel][temp]; 262 u = noiseX.noisePositionFractionValue * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1]; 263 temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue + 1]; 264 q = paintingData.gradient[channel][temp]; 265 v = (noiseX.noisePositionFractionValue - 1) * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1]; 266 b = linearInterpolation(sx, u, v); 267 return linearInterpolation(sy, a, b); 268 } 269 270 unsigned char FETurbulence::calculateTurbulenceValueForPoint(int channel, PaintingData& paintingData, StitchData& stitchData, const FloatPoint& point, float baseFrequencyX, float baseFrequencyY) 271 { 272 float tileWidth = paintingData.filterSize.width(); 273 float tileHeight = paintingData.filterSize.height(); 274 ASSERT(tileWidth > 0 && tileHeight > 0); 275 // Adjust the base frequencies if necessary for stitching. 276 if (m_stitchTiles) { 277 // When stitching tiled turbulence, the frequencies must be adjusted 278 // so that the tile borders will be continuous. 279 if (baseFrequencyX) { 280 float lowFrequency = floorf(tileWidth * baseFrequencyX) / tileWidth; 281 float highFrequency = ceilf(tileWidth * baseFrequencyX) / tileWidth; 282 // BaseFrequency should be non-negative according to the standard. 283 if (baseFrequencyX / lowFrequency < highFrequency / baseFrequencyX) 284 baseFrequencyX = lowFrequency; 285 else 286 baseFrequencyX = highFrequency; 287 } 288 if (baseFrequencyY) { 289 float lowFrequency = floorf(tileHeight * baseFrequencyY) / tileHeight; 290 float highFrequency = ceilf(tileHeight * baseFrequencyY) / tileHeight; 291 if (baseFrequencyY / lowFrequency < highFrequency / baseFrequencyY) 292 baseFrequencyY = lowFrequency; 293 else 294 baseFrequencyY = highFrequency; 295 } 296 // Set up TurbulenceInitial stitch values. 297 stitchData.width = roundf(tileWidth * baseFrequencyX); 298 stitchData.wrapX = s_perlinNoise + stitchData.width; 299 stitchData.height = roundf(tileHeight * baseFrequencyY); 300 stitchData.wrapY = s_perlinNoise + stitchData.height; 301 } 302 float turbulenceFunctionResult = 0; 303 FloatPoint noiseVector(point.x() * baseFrequencyX, point.y() * baseFrequencyY); 304 float ratio = 1; 305 for (int octave = 0; octave < m_numOctaves; ++octave) { 306 if (m_type == FETURBULENCE_TYPE_FRACTALNOISE) 307 turbulenceFunctionResult += noise2D(channel, paintingData, stitchData, noiseVector) / ratio; 308 else 309 turbulenceFunctionResult += fabsf(noise2D(channel, paintingData, stitchData, noiseVector)) / ratio; 310 noiseVector.setX(noiseVector.x() * 2); 311 noiseVector.setY(noiseVector.y() * 2); 312 ratio *= 2; 313 if (m_stitchTiles) { 314 // Update stitch values. Subtracting s_perlinNoiseoise before the multiplication and 315 // adding it afterward simplifies to subtracting it once. 316 stitchData.width *= 2; 317 stitchData.wrapX = 2 * stitchData.wrapX - s_perlinNoise; 318 stitchData.height *= 2; 319 stitchData.wrapY = 2 * stitchData.wrapY - s_perlinNoise; 320 } 321 } 322 323 // The value of turbulenceFunctionResult comes from ((turbulenceFunctionResult * 255) + 255) / 2 by fractalNoise 324 // and (turbulenceFunctionResult * 255) by turbulence. 325 if (m_type == FETURBULENCE_TYPE_FRACTALNOISE) 326 turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f; 327 // Clamp result 328 turbulenceFunctionResult = std::max(std::min(turbulenceFunctionResult, 1.f), 0.f); 329 return static_cast<unsigned char>(turbulenceFunctionResult * 255); 330 } 331 332 inline void FETurbulence::fillRegion(Uint8ClampedArray* pixelArray, PaintingData& paintingData, int startY, int endY, float baseFrequencyX, float baseFrequencyY) 333 { 334 IntRect filterRegion = absolutePaintRect(); 335 IntPoint point(0, filterRegion.y() + startY); 336 int indexOfPixelChannel = startY * (filterRegion.width() << 2); 337 int channel; 338 StitchData stitchData; 339 340 for (int y = startY; y < endY; ++y) { 341 point.setY(point.y() + 1); 342 point.setX(filterRegion.x()); 343 for (int x = 0; x < filterRegion.width(); ++x) { 344 point.setX(point.x() + 1); 345 for (channel = 0; channel < 4; ++channel, ++indexOfPixelChannel) 346 pixelArray->set(indexOfPixelChannel, calculateTurbulenceValueForPoint(channel, paintingData, stitchData, filter()->mapAbsolutePointToLocalPoint(point), baseFrequencyX, baseFrequencyY)); 347 } 348 } 349 } 350 351 void FETurbulence::fillRegionWorker(FillRegionParameters* parameters) 352 { 353 parameters->filter->fillRegion(parameters->pixelArray, *parameters->paintingData, parameters->startY, parameters->endY, parameters->baseFrequencyX, parameters->baseFrequencyY); 354 } 355 356 void FETurbulence::applySoftware() 357 { 358 Uint8ClampedArray* pixelArray = createUnmultipliedImageResult(); 359 if (!pixelArray) 360 return; 361 362 if (absolutePaintRect().isEmpty()) { 363 pixelArray->zeroFill(); 364 return; 365 } 366 367 PaintingData paintingData(m_seed, roundedIntSize(filterPrimitiveSubregion().size())); 368 initPaint(paintingData); 369 float baseFrequencyX = 1.0f / filter()->applyHorizontalScale(1.0f / m_baseFrequencyX); 370 float baseFrequencyY = 1.0f / filter()->applyVerticalScale(1.0f / m_baseFrequencyY); 371 372 int optimalThreadNumber = (absolutePaintRect().width() * absolutePaintRect().height()) / s_minimalRectDimension; 373 if (optimalThreadNumber > 1) { 374 // Initialize parallel jobs 375 WTF::ParallelJobs<FillRegionParameters> parallelJobs(&WebCore::FETurbulence::fillRegionWorker, optimalThreadNumber); 376 377 // Fill the parameter array 378 int i = parallelJobs.numberOfJobs(); 379 if (i > 1) { 380 // Split the job into "stepY"-sized jobs but there a few jobs that need to be slightly larger since 381 // stepY * jobs < total size. These extras are handled by the remainder "jobsWithExtra". 382 const int stepY = absolutePaintRect().height() / i; 383 const int jobsWithExtra = absolutePaintRect().height() % i; 384 385 int startY = 0; 386 for (; i > 0; --i) { 387 FillRegionParameters& params = parallelJobs.parameter(i-1); 388 params.filter = this; 389 params.pixelArray = pixelArray; 390 params.paintingData = &paintingData; 391 params.startY = startY; 392 startY += i < jobsWithExtra ? stepY + 1 : stepY; 393 params.endY = startY; 394 params.baseFrequencyX = baseFrequencyX; 395 params.baseFrequencyY = baseFrequencyY; 396 } 397 398 // Execute parallel jobs 399 parallelJobs.execute(); 400 return; 401 } 402 } 403 404 // Fallback to single threaded mode if there is no room for a new thread or the paint area is too small. 405 fillRegion(pixelArray, paintingData, 0, absolutePaintRect().height(), baseFrequencyX, baseFrequencyY); 406 } 407 408 SkShader* FETurbulence::createShader(const IntRect& filterRegion) 409 { 410 const SkISize size = SkISize::Make(filterRegion.width(), filterRegion.height()); 411 float baseFrequencyX = 1.0f / filter()->applyHorizontalScale(1.0f / m_baseFrequencyX); 412 const float baseFrequencyY = 1.0f / filter()->applyVerticalScale(1.0f / m_baseFrequencyY); 413 return (type() == FETURBULENCE_TYPE_FRACTALNOISE) ? 414 SkPerlinNoiseShader::CreateFractalNoise(SkFloatToScalar(baseFrequencyX), 415 SkFloatToScalar(baseFrequencyY), numOctaves(), SkFloatToScalar(seed()), 416 stitchTiles() ? &size : 0) : 417 SkPerlinNoiseShader::CreateTubulence(SkFloatToScalar(baseFrequencyX), 418 SkFloatToScalar(baseFrequencyY), numOctaves(), SkFloatToScalar(seed()), 419 stitchTiles() ? &size : 0); 420 } 421 422 bool FETurbulence::applySkia() 423 { 424 // For now, only use the skia implementation for accelerated rendering. 425 if (filter()->renderingMode() != Accelerated) 426 return false; 427 428 ImageBuffer* resultImage = createImageBufferResult(); 429 if (!resultImage) 430 return false; 431 432 const IntRect filterRegion = absolutePaintRect(); 433 434 SkPaint paint; 435 paint.setShader(createShader(filterRegion))->unref(); 436 resultImage->context()->drawRect((SkRect)filterRegion, paint); 437 return true; 438 } 439 440 PassRefPtr<SkImageFilter> FETurbulence::createImageFilter(SkiaImageFilterBuilder* builder) 441 { 442 SkAutoTUnref<SkShader> shader(createShader(IntRect())); 443 return adoptRef(SkRectShaderImageFilter::Create(shader, SkRect())); 444 } 445 446 static TextStream& operator<<(TextStream& ts, const TurbulenceType& type) 447 { 448 switch (type) { 449 case FETURBULENCE_TYPE_UNKNOWN: 450 ts << "UNKNOWN"; 451 break; 452 case FETURBULENCE_TYPE_TURBULENCE: 453 ts << "TURBULENCE"; 454 break; 455 case FETURBULENCE_TYPE_FRACTALNOISE: 456 ts << "NOISE"; 457 break; 458 } 459 return ts; 460 } 461 462 TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const 463 { 464 writeIndent(ts, indent); 465 ts << "[feTurbulence"; 466 FilterEffect::externalRepresentation(ts); 467 ts << " type=\"" << type() << "\" " 468 << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" " 469 << "seed=\"" << seed() << "\" " 470 << "numOctaves=\"" << numOctaves() << "\" " 471 << "stitchTiles=\"" << stitchTiles() << "\"]\n"; 472 return ts; 473 } 474 475 } // namespace WebCore 476
