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 * 9 * This library is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU Library General Public 11 * License as published by the Free Software Foundation; either 12 * version 2 of the License, or (at your option) any later version. 13 * 14 * This library is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * Library General Public License for more details. 18 * 19 * You should have received a copy of the GNU Library General Public License 20 * along with this library; see the file COPYING.LIB. If not, write to 21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 22 * Boston, MA 02110-1301, USA. 23 */ 24 25#include "config.h" 26 27#if ENABLE(FILTERS) 28#include "FETurbulence.h" 29 30#include "Filter.h" 31#include "TextStream.h" 32 33#include <runtime/Uint8ClampedArray.h> 34#include <wtf/MathExtras.h> 35#include <wtf/ParallelJobs.h> 36 37namespace 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*/ 47static const int s_perlinNoise = 4096; 48static const long s_randMaximum = 2147483647; // 2**31 - 1 49static const int s_randAmplitude = 16807; // 7**5; primitive root of m 50static const int s_randQ = 127773; // m / a 51static const int s_randR = 2836; // m % a 52 53FETurbulence::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 64PassRefPtr<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 69TurbulenceType FETurbulence::type() const 70{ 71 return m_type; 72} 73 74bool FETurbulence::setType(TurbulenceType type) 75{ 76 if (m_type == type) 77 return false; 78 m_type = type; 79 return true; 80} 81 82float FETurbulence::baseFrequencyY() const 83{ 84 return m_baseFrequencyY; 85} 86 87bool FETurbulence::setBaseFrequencyY(float baseFrequencyY) 88{ 89 if (m_baseFrequencyY == baseFrequencyY) 90 return false; 91 m_baseFrequencyY = baseFrequencyY; 92 return true; 93} 94 95float FETurbulence::baseFrequencyX() const 96{ 97 return m_baseFrequencyX; 98} 99 100bool FETurbulence::setBaseFrequencyX(float baseFrequencyX) 101{ 102 if (m_baseFrequencyX == baseFrequencyX) 103 return false; 104 m_baseFrequencyX = baseFrequencyX; 105 return true; 106} 107 108float FETurbulence::seed() const 109{ 110 return m_seed; 111} 112 113bool FETurbulence::setSeed(float seed) 114{ 115 if (m_seed == seed) 116 return false; 117 m_seed = seed; 118 return true; 119} 120 121int FETurbulence::numOctaves() const 122{ 123 return m_numOctaves; 124} 125 126bool FETurbulence::setNumOctaves(int numOctaves) 127{ 128 if (m_numOctaves == numOctaves) 129 return false; 130 m_numOctaves = numOctaves; 131 return true; 132} 133 134bool FETurbulence::stitchTiles() const 135{ 136 return m_stitchTiles; 137} 138 139bool 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. 151inline 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 160inline float smoothCurve(float t) 161{ 162 return t * t * (3 - 2 * t); 163} 164 165inline float linearInterpolation(float t, float a, float b) 166{ 167 return a + t * (b - a); 168} 169 170inline 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 209inline 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 217float 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 268unsigned char FETurbulence::calculateTurbulenceValueForPoint(int channel, PaintingData& paintingData, StitchData& stitchData, const FloatPoint& point) 269{ 270 float tileWidth = paintingData.filterSize.width(); 271 float tileHeight = paintingData.filterSize.height(); 272 ASSERT(tileWidth > 0 && tileHeight > 0); 273 float baseFrequencyX = m_baseFrequencyX; 274 float baseFrequencyY = m_baseFrequencyY; 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 332inline void FETurbulence::fillRegion(Uint8ClampedArray* pixelArray, PaintingData& paintingData, int startY, int endY) 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))); 347 } 348 } 349} 350 351void FETurbulence::fillRegionWorker(FillRegionParameters* parameters) 352{ 353 parameters->filter->fillRegion(parameters->pixelArray, *parameters->paintingData, parameters->startY, parameters->endY); 354} 355 356void FETurbulence::platformApplySoftware() 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 370 int optimalThreadNumber = (absolutePaintRect().width() * absolutePaintRect().height()) / s_minimalRectDimension; 371 if (optimalThreadNumber > 1) { 372 // Initialize parallel jobs 373 WTF::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 } 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()); 402} 403 404void FETurbulence::dump() 405{ 406} 407 408static TextStream& operator<<(TextStream& ts, const TurbulenceType& type) 409{ 410 switch (type) { 411 case FETURBULENCE_TYPE_UNKNOWN: 412 ts << "UNKNOWN"; 413 break; 414 case FETURBULENCE_TYPE_TURBULENCE: 415 ts << "TURBULANCE"; 416 break; 417 case FETURBULENCE_TYPE_FRACTALNOISE: 418 ts << "NOISE"; 419 break; 420 } 421 return ts; 422} 423 424TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const 425{ 426 writeIndent(ts, indent); 427 ts << "[feTurbulence"; 428 FilterEffect::externalRepresentation(ts); 429 ts << " type=\"" << type() << "\" " 430 << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" " 431 << "seed=\"" << seed() << "\" " 432 << "numOctaves=\"" << numOctaves() << "\" " 433 << "stitchTiles=\"" << stitchTiles() << "\"]\n"; 434 return ts; 435} 436 437} // namespace WebCore 438 439#endif // ENABLE(FILTERS) 440