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