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