src/third_party/WebKit/Source/platform/graphics/filters/FETurbulence.cpp

   1 /*
   2  * Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann <zimmermann@kde.org>
   3  * Copyright (C) 2004, 2005 Rob Buis <buis@kde.org>
   4  * Copyright (C) 2005 Eric Seidel <eric@webkit.org>
   5  * Copyright (C) 2009 Dirk Schulze <krit@webkit.org>
   6  * Copyright (C) 2010 Renata Hodovan <reni@inf.u-szeged.hu>
   7  * Copyright (C) 2011 Gabor Loki <loki@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 blink {
  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
 368     int optimalThreadNumber = (absolutePaintRect().width() * absolutePaintRect().height()) / s_minimalRectDimension;
 369     if (optimalThreadNumber > 1) {
 370         // Initialize parallel jobs
 371         ParallelJobs<FillRegionParameters> parallelJobs(&FETurbulence::fillRegionWorker, optimalThreadNumber);
 372
 373         // Fill the parameter array
 374         int i = parallelJobs.numberOfJobs();
 375         if (i > 1) {
 376             // Split the job into "stepY"-sized jobs but there a few jobs that need to be slightly larger since
 377             // stepY * jobs < total size. These extras are handled by the remainder "jobsWithExtra".
 378             const int stepY = absolutePaintRect().height() / i;
 379             const int jobsWithExtra = absolutePaintRect().height() % i;
 380
 381             int startY = 0;
 382             for (; i > 0; --i) {
 383                 FillRegionParameters& params = parallelJobs.parameter(i-1);
 384                 params.filter = this;
 385                 params.pixelArray = pixelArray;
 386                 params.paintingData = &paintingData;
 387                 params.startY = startY;
 388                 startY += i < jobsWithExtra ? stepY + 1 : stepY;
 389                 params.endY = startY;
 390                 params.baseFrequencyX = m_baseFrequencyX;
 391                 params.baseFrequencyY = m_baseFrequencyY;
 392             }
 393
 394             // Execute parallel jobs
 395             parallelJobs.execute();
 396             return;
 397         }
 398     }
 399
 400     // Fallback to single threaded mode if there is no room for a new thread or the paint area is too small.
 401     fillRegion(pixelArray, paintingData, 0, absolutePaintRect().height(), m_baseFrequencyX, m_baseFrequencyY);
 402 }
 403
 404 SkShader* FETurbulence::createShader()
 405 {
 406     const SkISize size = SkISize::Make(effectBoundaries().width(), effectBoundaries().height());
 407     // Frequency should be scaled by page zoom, but not by primitiveUnits.
 408     // So we apply only the transform scale (as Filter::apply*Scale() do)
 409     // and not the target bounding box scale (as SVGFilter::apply*Scale()
 410     // would do). Note also that we divide by the scale since this is
 411     // a frequency, not a period.
 412     const AffineTransform& absoluteTransform = filter()->absoluteTransform();
 413     float baseFrequencyX = m_baseFrequencyX / absoluteTransform.a();
 414     float baseFrequencyY = m_baseFrequencyY / absoluteTransform.d();
 415     return (type() == FETURBULENCE_TYPE_FRACTALNOISE) ?
 416         SkPerlinNoiseShader::CreateFractalNoise(SkFloatToScalar(baseFrequencyX),
 417             SkFloatToScalar(baseFrequencyY), numOctaves(), SkFloatToScalar(seed()),
 418             stitchTiles() ? &size : 0) :
 419         SkPerlinNoiseShader::CreateTurbulence(SkFloatToScalar(baseFrequencyX),
 420             SkFloatToScalar(baseFrequencyY), numOctaves(), SkFloatToScalar(seed()),
 421             stitchTiles() ? &size : 0);
 422 }
 423
 424 PassRefPtr<SkImageFilter> FETurbulence::createImageFilter(SkiaImageFilterBuilder* builder)
 425 {
 426     SkAutoTUnref<SkShader> shader(createShader());
 427     SkImageFilter::CropRect rect = getCropRect(builder->cropOffset());
 428     return adoptRef(SkRectShaderImageFilter::Create(shader, &rect));
 429 }
 430
 431 static TextStream& operator<<(TextStream& ts, const TurbulenceType& type)
 432 {
 433     switch (type) {
 434     case FETURBULENCE_TYPE_UNKNOWN:
 435         ts << "UNKNOWN";
 436         break;
 437     case FETURBULENCE_TYPE_TURBULENCE:
 438         ts << "TURBULENCE";
 439         break;
 440     case FETURBULENCE_TYPE_FRACTALNOISE:
 441         ts << "NOISE";
 442         break;
 443     }
 444     return ts;
 445 }
 446
 447 TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const
 448 {
 449     writeIndent(ts, indent);
 450     ts << "[feTurbulence";
 451     FilterEffect::externalRepresentation(ts);
 452     ts << " type=\"" << type() << "\" "
 453        << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" "
 454        << "seed=\"" << seed() << "\" "
 455        << "numOctaves=\"" << numOctaves() << "\" "
 456        << "stitchTiles=\"" << stitchTiles() << "\"]\n";
 457     return ts;
 458 }
 459
 460 } // namespace blink