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 * 8 * This library is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Library General Public 10 * License as published by the Free Software Foundation; either 11 * version 2 of the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Library General Public License for more details. 17 * 18 * You should have received a copy of the GNU Library General Public License 19 * along with this library; see the file COPYING.LIB. If not, write to 20 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 21 * Boston, MA 02110-1301, USA. 22 */ 23 24 #include "config.h" 25 26 #if ENABLE(FILTERS) 27 #include "FETurbulence.h" 28 29 #include "Filter.h" 30 #include "RenderTreeAsText.h" 31 #include "TextStream.h" 32 33 #include <wtf/ByteArray.h> 34 #include <wtf/MathExtras.h> 35 36 namespace WebCore { 37 38 /* 39 Produces results in the range [1, 2**31 - 2]. Algorithm is: 40 r = (a * r) mod m where a = randAmplitude = 16807 and 41 m = randMaximum = 2**31 - 1 = 2147483647, r = seed. 42 See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988 43 To test: the algorithm should produce the result 1043618065 44 as the 10,000th generated number if the original seed is 1. 45 */ 46 static const int s_perlinNoise = 4096; 47 static const long s_randMaximum = 2147483647; // 2**31 - 1 48 static const int s_randAmplitude = 16807; // 7**5; primitive root of m 49 static const int s_randQ = 127773; // m / a 50 static const int s_randR = 2836; // m % a 51 52 FETurbulence::FETurbulence(Filter* filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles) 53 : FilterEffect(filter) 54 , m_type(type) 55 , m_baseFrequencyX(baseFrequencyX) 56 , m_baseFrequencyY(baseFrequencyY) 57 , m_numOctaves(numOctaves) 58 , m_seed(seed) 59 , m_stitchTiles(stitchTiles) 60 { 61 } 62 63 PassRefPtr<FETurbulence> FETurbulence::create(Filter* filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles) 64 { 65 return adoptRef(new FETurbulence(filter, type, baseFrequencyX, baseFrequencyY, numOctaves, seed, stitchTiles)); 66 } 67 68 TurbulenceType FETurbulence::type() const 69 { 70 return m_type; 71 } 72 73 bool FETurbulence::setType(TurbulenceType type) 74 { 75 if (m_type == type) 76 return false; 77 m_type = type; 78 return true; 79 } 80 81 float FETurbulence::baseFrequencyY() const 82 { 83 return m_baseFrequencyY; 84 } 85 86 bool FETurbulence::setBaseFrequencyY(float baseFrequencyY) 87 { 88 if (m_baseFrequencyY == baseFrequencyY) 89 return false; 90 m_baseFrequencyY = baseFrequencyY; 91 return true; 92 } 93 94 float FETurbulence::baseFrequencyX() const 95 { 96 return m_baseFrequencyX; 97 } 98 99 bool FETurbulence::setBaseFrequencyX(float baseFrequencyX) 100 { 101 if (m_baseFrequencyX == baseFrequencyX) 102 return false; 103 m_baseFrequencyX = baseFrequencyX; 104 return true; 105 } 106 107 float FETurbulence::seed() const 108 { 109 return m_seed; 110 } 111 112 bool FETurbulence::setSeed(float seed) 113 { 114 if (m_seed == seed) 115 return false; 116 m_seed = seed; 117 return true; 118 } 119 120 int FETurbulence::numOctaves() const 121 { 122 return m_numOctaves; 123 } 124 125 bool FETurbulence::setNumOctaves(int numOctaves) 126 { 127 if (m_numOctaves == numOctaves) 128 return false; 129 m_numOctaves = numOctaves; 130 return true; 131 } 132 133 bool FETurbulence::stitchTiles() const 134 { 135 return m_stitchTiles; 136 } 137 138 bool FETurbulence::setStitchTiles(bool stitch) 139 { 140 if (m_stitchTiles == stitch) 141 return false; 142 m_stitchTiles = stitch; 143 return true; 144 } 145 146 // The turbulence calculation code is an adapted version of what appears in the SVG 1.1 specification: 147 // http://www.w3.org/TR/SVG11/filters.html#feTurbulence 148 149 FETurbulence::PaintingData::PaintingData(long paintingSeed, const IntSize& paintingSize) 150 : seed(paintingSeed) 151 , width(0) 152 , height(0) 153 , wrapX(0) 154 , wrapY(0) 155 , channel(0) 156 , filterSize(paintingSize) 157 { 158 } 159 160 // Compute pseudo random number. 161 inline long FETurbulence::PaintingData::random() 162 { 163 long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ); 164 if (result <= 0) 165 result += s_randMaximum; 166 seed = result; 167 return result; 168 } 169 170 inline float smoothCurve(float t) 171 { 172 return t * t * (3 - 2 * t); 173 } 174 175 inline float linearInterpolation(float t, float a, float b) 176 { 177 return a + t * (b - a); 178 } 179 180 inline void FETurbulence::initPaint(PaintingData& paintingData) 181 { 182 float normalizationFactor; 183 184 // The seed value clamp to the range [1, s_randMaximum - 1]. 185 if (paintingData.seed <= 0) 186 paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1; 187 if (paintingData.seed > s_randMaximum - 1) 188 paintingData.seed = s_randMaximum - 1; 189 190 float* gradient; 191 for (int channel = 0; channel < 4; ++channel) { 192 for (int i = 0; i < s_blockSize; ++i) { 193 paintingData.latticeSelector[i] = i; 194 gradient = paintingData.gradient[channel][i]; 195 gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize; 196 gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize; 197 normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]); 198 gradient[0] /= normalizationFactor; 199 gradient[1] /= normalizationFactor; 200 } 201 } 202 for (int i = s_blockSize - 1; i > 0; --i) { 203 int k = paintingData.latticeSelector[i]; 204 int j = paintingData.random() % s_blockSize; 205 ASSERT(j >= 0); 206 ASSERT(j < 2 * s_blockSize + 2); 207 paintingData.latticeSelector[i] = paintingData.latticeSelector[j]; 208 paintingData.latticeSelector[j] = k; 209 } 210 for (int i = 0; i < s_blockSize + 2; ++i) { 211 paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i]; 212 for (int channel = 0; channel < 4; ++channel) { 213 paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0]; 214 paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1]; 215 } 216 } 217 } 218 219 inline void checkNoise(int& noiseValue, int limitValue, int newValue) 220 { 221 if (noiseValue >= limitValue) 222 noiseValue -= newValue; 223 if (noiseValue >= limitValue - 1) 224 noiseValue -= newValue - 1; 225 } 226 227 float FETurbulence::noise2D(PaintingData& paintingData, const FloatPoint& noiseVector) 228 { 229 struct Noise { 230 int noisePositionIntegerValue; 231 float noisePositionFractionValue; 232 233 Noise(float component) 234 { 235 float position = component + s_perlinNoise; 236 noisePositionIntegerValue = static_cast<int>(position); 237 noisePositionFractionValue = position - noisePositionIntegerValue; 238 } 239 }; 240 241 Noise noiseX(noiseVector.x()); 242 Noise noiseY(noiseVector.y()); 243 float* q; 244 float sx, sy, a, b, u, v; 245 246 // If stitching, adjust lattice points accordingly. 247 if (m_stitchTiles) { 248 checkNoise(noiseX.noisePositionIntegerValue, paintingData.wrapX, paintingData.width); 249 checkNoise(noiseY.noisePositionIntegerValue, paintingData.wrapY, paintingData.height); 250 } 251 252 noiseX.noisePositionIntegerValue &= s_blockMask; 253 noiseY.noisePositionIntegerValue &= s_blockMask; 254 int latticeIndex = paintingData.latticeSelector[noiseX.noisePositionIntegerValue]; 255 int nextLatticeIndex = paintingData.latticeSelector[(noiseX.noisePositionIntegerValue + 1) & s_blockMask]; 256 257 sx = smoothCurve(noiseX.noisePositionFractionValue); 258 sy = smoothCurve(noiseY.noisePositionFractionValue); 259 260 // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement. 261 int temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue]; 262 q = paintingData.gradient[paintingData.channel][temp]; 263 u = noiseX.noisePositionFractionValue * q[0] + noiseY.noisePositionFractionValue * q[1]; 264 temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue]; 265 q = paintingData.gradient[paintingData.channel][temp]; 266 v = (noiseX.noisePositionFractionValue - 1) * q[0] + noiseY.noisePositionFractionValue * q[1]; 267 a = linearInterpolation(sx, u, v); 268 temp = paintingData.latticeSelector[latticeIndex + noiseY.noisePositionIntegerValue + 1]; 269 q = paintingData.gradient[paintingData.channel][temp]; 270 u = noiseX.noisePositionFractionValue * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1]; 271 temp = paintingData.latticeSelector[nextLatticeIndex + noiseY.noisePositionIntegerValue + 1]; 272 q = paintingData.gradient[paintingData.channel][temp]; 273 v = (noiseX.noisePositionFractionValue - 1) * q[0] + (noiseY.noisePositionFractionValue - 1) * q[1]; 274 b = linearInterpolation(sx, u, v); 275 return linearInterpolation(sy, a, b); 276 } 277 278 unsigned char FETurbulence::calculateTurbulenceValueForPoint(PaintingData& paintingData, const FloatPoint& point) 279 { 280 float tileWidth = paintingData.filterSize.width(); 281 ASSERT(tileWidth > 0); 282 float tileHeight = paintingData.filterSize.height(); 283 ASSERT(tileHeight > 0); 284 // Adjust the base frequencies if necessary for stitching. 285 if (m_stitchTiles) { 286 // When stitching tiled turbulence, the frequencies must be adjusted 287 // so that the tile borders will be continuous. 288 if (m_baseFrequencyX) { 289 float lowFrequency = floorf(tileWidth * m_baseFrequencyX) / tileWidth; 290 float highFrequency = ceilf(tileWidth * m_baseFrequencyX) / tileWidth; 291 // BaseFrequency should be non-negative according to the standard. 292 if (m_baseFrequencyX / lowFrequency < highFrequency / m_baseFrequencyX) 293 m_baseFrequencyX = lowFrequency; 294 else 295 m_baseFrequencyX = highFrequency; 296 } 297 if (m_baseFrequencyY) { 298 float lowFrequency = floorf(tileHeight * m_baseFrequencyY) / tileHeight; 299 float highFrequency = ceilf(tileHeight * m_baseFrequencyY) / tileHeight; 300 if (m_baseFrequencyY / lowFrequency < highFrequency / m_baseFrequencyY) 301 m_baseFrequencyY = lowFrequency; 302 else 303 m_baseFrequencyY = highFrequency; 304 } 305 // Set up TurbulenceInitial stitch values. 306 paintingData.width = roundf(tileWidth * m_baseFrequencyX); 307 paintingData.wrapX = s_perlinNoise + paintingData.width; 308 paintingData.height = roundf(tileHeight * m_baseFrequencyY); 309 paintingData.wrapY = s_perlinNoise + paintingData.height; 310 } 311 float turbulenceFunctionResult = 0; 312 FloatPoint noiseVector(point.x() * m_baseFrequencyX, point.y() * m_baseFrequencyY); 313 float ratio = 1; 314 for (int octave = 0; octave < m_numOctaves; ++octave) { 315 if (m_type == FETURBULENCE_TYPE_FRACTALNOISE) 316 turbulenceFunctionResult += noise2D(paintingData, noiseVector) / ratio; 317 else 318 turbulenceFunctionResult += fabsf(noise2D(paintingData, noiseVector)) / ratio; 319 noiseVector.setX(noiseVector.x() * 2); 320 noiseVector.setY(noiseVector.y() * 2); 321 ratio *= 2; 322 if (m_stitchTiles) { 323 // Update stitch values. Subtracting s_perlinNoiseoise before the multiplication and 324 // adding it afterward simplifies to subtracting it once. 325 paintingData.width *= 2; 326 paintingData.wrapX = 2 * paintingData.wrapX - s_perlinNoise; 327 paintingData.height *= 2; 328 paintingData.wrapY = 2 * paintingData.wrapY - s_perlinNoise; 329 } 330 } 331 332 // The value of turbulenceFunctionResult comes from ((turbulenceFunctionResult * 255) + 255) / 2 by fractalNoise 333 // and (turbulenceFunctionResult * 255) by turbulence. 334 if (m_type == FETURBULENCE_TYPE_FRACTALNOISE) 335 turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f; 336 // Clamp result 337 turbulenceFunctionResult = std::max(std::min(turbulenceFunctionResult, 1.f), 0.f); 338 return static_cast<unsigned char>(turbulenceFunctionResult * 255); 339 } 340 341 void FETurbulence::apply() 342 { 343 if (hasResult()) 344 return; 345 ByteArray* pixelArray = createUnmultipliedImageResult(); 346 if (!pixelArray) 347 return; 348 349 if (absolutePaintRect().isEmpty()) 350 return; 351 352 PaintingData paintingData(m_seed, roundedIntSize(filterPrimitiveSubregion().size())); 353 initPaint(paintingData); 354 355 FloatRect filterRegion = absolutePaintRect(); 356 FloatPoint point; 357 point.setY(filterRegion.y()); 358 int indexOfPixelChannel = 0; 359 for (int y = 0; y < absolutePaintRect().height(); ++y) { 360 point.setY(point.y() + 1); 361 point.setX(filterRegion.x()); 362 for (int x = 0; x < absolutePaintRect().width(); ++x) { 363 point.setX(point.x() + 1); 364 for (paintingData.channel = 0; paintingData.channel < 4; ++paintingData.channel, ++indexOfPixelChannel) 365 pixelArray->set(indexOfPixelChannel, calculateTurbulenceValueForPoint(paintingData, filter()->mapAbsolutePointToLocalPoint(point))); 366 } 367 } 368 } 369 370 void FETurbulence::dump() 371 { 372 } 373 374 static TextStream& operator<<(TextStream& ts, const TurbulenceType& type) 375 { 376 switch (type) { 377 case FETURBULENCE_TYPE_UNKNOWN: 378 ts << "UNKNOWN"; 379 break; 380 case FETURBULENCE_TYPE_TURBULENCE: 381 ts << "TURBULANCE"; 382 break; 383 case FETURBULENCE_TYPE_FRACTALNOISE: 384 ts << "NOISE"; 385 break; 386 } 387 return ts; 388 } 389 390 TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const 391 { 392 writeIndent(ts, indent); 393 ts << "[feTurbulence"; 394 FilterEffect::externalRepresentation(ts); 395 ts << " type=\"" << type() << "\" " 396 << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" " 397 << "seed=\"" << seed() << "\" " 398 << "numOctaves=\"" << numOctaves() << "\" " 399 << "stitchTiles=\"" << stitchTiles() << "\"]\n"; 400 return ts; 401 } 402 403 } // namespace WebCore 404 405 #endif // ENABLE(FILTERS) 406
