FEGaussianBlur: unify and const-ify calculateKernelSize
[WebKit-https.git] / Source / WebCore / 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  *
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
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)
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
332 inline 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
351 void FETurbulence::fillRegionWorker(FillRegionParameters* parameters)
352 {
353     parameters->filter->fillRegion(parameters->pixelArray, *parameters->paintingData, parameters->startY, parameters->endY);
354 }
355
356 void 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
404 void FETurbulence::dump()
405 {
406 }
407
408 static 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
424 TextStream& 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)