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 *
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
36namespace 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*/
46static const int s_perlinNoise = 4096;
47static const long s_randMaximum = 2147483647; // 2**31 - 1
48static const int s_randAmplitude = 16807; // 7**5; primitive root of m
49static const int s_randQ = 127773; // m / a
50static const int s_randR = 2836; // m % a
51
52FETurbulence::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
63PassRefPtr<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
68TurbulenceType FETurbulence::type() const
69{
70    return m_type;
71}
72
73bool FETurbulence::setType(TurbulenceType type)
74{
75    if (m_type == type)
76        return false;
77    m_type = type;
78    return true;
79}
80
81float FETurbulence::baseFrequencyY() const
82{
83    return m_baseFrequencyY;
84}
85
86bool FETurbulence::setBaseFrequencyY(float baseFrequencyY)
87{
88    if (m_baseFrequencyY == baseFrequencyY)
89        return false;
90    m_baseFrequencyY = baseFrequencyY;
91    return true;
92}
93
94float FETurbulence::baseFrequencyX() const
95{
96    return m_baseFrequencyX;
97}
98
99bool FETurbulence::setBaseFrequencyX(float baseFrequencyX)
100{
101    if (m_baseFrequencyX == baseFrequencyX)
102        return false;
103    m_baseFrequencyX = baseFrequencyX;
104    return true;
105}
106
107float FETurbulence::seed() const
108{
109    return m_seed;
110}
111
112bool FETurbulence::setSeed(float seed)
113{
114    if (m_seed == seed)
115        return false;
116    m_seed = seed;
117    return true;
118}
119
120int FETurbulence::numOctaves() const
121{
122    return m_numOctaves;
123}
124
125bool FETurbulence::setNumOctaves(int numOctaves)
126{
127    if (m_numOctaves == numOctaves)
128        return false;
129    m_numOctaves = numOctaves;
130    return true;
131}
132
133bool FETurbulence::stitchTiles() const
134{
135    return m_stitchTiles;
136}
137
138bool 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
149FETurbulence::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.
161inline 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
170inline float smoothCurve(float t)
171{
172    return t * t * (3 - 2 * t);
173}
174
175inline float linearInterpolation(float t, float a, float b)
176{
177    return a + t * (b - a);
178}
179
180inline 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
219inline 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
227float 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
278unsigned 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
341void 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
370void FETurbulence::dump()
371{
372}
373
374static 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
390TextStream& 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