feTurbulence with stitchTiles is broken
[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  * Copyright (C) 2017 Apple Inc.
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Library General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Library General Public License for more details.
19  *
20  * You should have received a copy of the GNU Library General Public License
21  * along with this library; see the file COPYING.LIB.  If not, write to
22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
23  * Boston, MA 02110-1301, USA.
24  */
25
26 #include "config.h"
27 #include "FETurbulence.h"
28
29 #include "Filter.h"
30 #include <wtf/text/TextStream.h>
31
32 #include <runtime/Uint8ClampedArray.h>
33 #include <wtf/MathExtras.h>
34 #include <wtf/ParallelJobs.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 Ref<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 bool FETurbulence::setType(TurbulenceType type)
69 {
70     if (m_type == type)
71         return false;
72     m_type = type;
73     return true;
74 }
75
76 bool FETurbulence::setBaseFrequencyY(float baseFrequencyY)
77 {
78     if (m_baseFrequencyY == baseFrequencyY)
79         return false;
80     m_baseFrequencyY = baseFrequencyY;
81     return true;
82 }
83
84 bool FETurbulence::setBaseFrequencyX(float baseFrequencyX)
85 {
86     if (m_baseFrequencyX == baseFrequencyX)
87         return false;
88     m_baseFrequencyX = baseFrequencyX;
89     return true;
90 }
91
92 bool FETurbulence::setSeed(float seed)
93 {
94     if (m_seed == seed)
95         return false;
96     m_seed = seed;
97     return true;
98 }
99
100 bool FETurbulence::setNumOctaves(int numOctaves)
101 {
102     if (m_numOctaves == numOctaves)
103         return false;
104     m_numOctaves = numOctaves;
105     return true;
106 }
107
108 bool FETurbulence::setStitchTiles(bool stitch)
109 {
110     if (m_stitchTiles == stitch)
111         return false;
112     m_stitchTiles = stitch;
113     return true;
114 }
115
116 // The turbulence calculation code is an adapted version of what appears in the SVG 1.1 specification:
117 // http://www.w3.org/TR/SVG11/filters.html#feTurbulence
118
119 // Compute pseudo random number.
120 inline long FETurbulence::PaintingData::random()
121 {
122     long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ);
123     if (result <= 0)
124         result += s_randMaximum;
125     seed = result;
126     return result;
127 }
128
129 inline float smoothCurve(float t)
130 {
131     return t * t * (3 - 2 * t);
132 }
133
134 inline float linearInterpolation(float t, float a, float b)
135 {
136     return a + t * (b - a);
137 }
138
139 void FETurbulence::initPaint(PaintingData& paintingData)
140 {
141     float normalizationFactor;
142
143     // The seed value clamp to the range [1, s_randMaximum - 1].
144     if (paintingData.seed <= 0)
145         paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1;
146     if (paintingData.seed > s_randMaximum - 1)
147         paintingData.seed = s_randMaximum - 1;
148
149     float* gradient;
150     for (int channel = 0; channel < 4; ++channel) {
151         for (int i = 0; i < s_blockSize; ++i) {
152             paintingData.latticeSelector[i] = i;
153             gradient = paintingData.gradient[channel][i];
154             do {
155                 gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
156                 gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
157             } while (!gradient[0] && !gradient[1]);
158             normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]);
159             gradient[0] /= normalizationFactor;
160             gradient[1] /= normalizationFactor;
161         }
162     }
163
164     for (int i = s_blockSize - 1; i > 0; --i) {
165         int k = paintingData.latticeSelector[i];
166         int j = paintingData.random() % s_blockSize;
167         ASSERT(j >= 0);
168         ASSERT(j < 2 * s_blockSize + 2);
169         paintingData.latticeSelector[i] = paintingData.latticeSelector[j];
170         paintingData.latticeSelector[j] = k;
171     }
172
173     for (int i = 0; i < s_blockSize + 2; ++i) {
174         paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i];
175         for (int channel = 0; channel < 4; ++channel) {
176             paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0];
177             paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1];
178         }
179     }
180 }
181
182 // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement.
183 FloatComponents FETurbulence::noise2D(const PaintingData& paintingData, const StitchData& stitchData, const FloatPoint& noiseVector) const
184 {
185     struct NoisePosition {
186         int index; // bx0, by0 in the spec text.
187         int nextIndex; // bx1, by1 in the spec text.
188         float fraction; // rx0, ry0 in the spec text.
189
190         NoisePosition(float component)
191         {
192             //  t = vec[0] + PerlinN;
193             //  bx0 = (int)t;
194             //  bx1 = bx0+1;
195             //  rx0 = t - (int)t;
196             float position = component + s_perlinNoise;
197             index = static_cast<int>(position);
198             nextIndex = index + 1;
199             fraction = position - index;
200         }
201         
202         void stitch(int size, int wrapSize)
203         {
204             // if (bx0 >= pStitchInfo->nWrapX)
205             //   bx0 -= pStitchInfo->nWidth;
206             if (index >= wrapSize)
207                 index -= size;
208
209             // if (bx1 >= pStitchInfo->nWrapX)
210             //   bx1 -= pStitchInfo->nWidth;
211             if (nextIndex >= wrapSize)
212                 nextIndex -= size;
213         }
214     };
215
216     NoisePosition noiseX(noiseVector.x());
217     NoisePosition noiseY(noiseVector.y());
218
219     // If stitching, adjust lattice points accordingly.
220     if (m_stitchTiles) {
221         noiseX.stitch(stitchData.width, stitchData.wrapX);
222         noiseY.stitch(stitchData.height, stitchData.wrapY);
223     }
224
225     // bx0 &= BM;
226     // bx1 &= BM;
227     // by0 &= BM;
228     // by1 &= BM;
229     noiseX.index &= s_blockMask;
230     noiseX.nextIndex &= s_blockMask;
231     noiseY.index &= s_blockMask;
232     noiseY.nextIndex &= s_blockMask;
233
234     // i = uLatticeSelector[bx0];
235     // j = uLatticeSelector[bx1];
236     int latticeIndex = paintingData.latticeSelector[noiseX.index];
237     int nextLatticeIndex = paintingData.latticeSelector[noiseX.nextIndex];
238
239     // sx = double(s_curve(rx0));
240     // sy = double(s_curve(ry0));
241     float sx = smoothCurve(noiseX.fraction);
242     float sy = smoothCurve(noiseY.fraction);
243
244     auto noiseForChannel = [&](int channel) {
245         // b00 = uLatticeSelector[i + by0]
246         int b00 = paintingData.latticeSelector[latticeIndex + noiseY.index];
247         // q = fGradient[nColorChannel][b00]; u = rx0 * q[0] + ry0 * q[1];
248         const float* q = paintingData.gradient[channel][b00];
249         float u = noiseX.fraction * q[0] + noiseY.fraction * q[1];
250
251         // b10 = uLatticeSelector[j + by0];
252         int b10 = paintingData.latticeSelector[nextLatticeIndex + noiseY.index];
253         // rx1 = rx0 - 1.0f;
254         // q = fGradient[nColorChannel][b10]; v = rx1 * q[0] + ry0 * q[1];
255         q = paintingData.gradient[channel][b10];
256         float v = (noiseX.fraction - 1) * q[0] + noiseY.fraction * q[1];
257         // a = lerp(sx, u, v);
258         float a = linearInterpolation(sx, u, v);
259
260         // b01 = uLatticeSelector[i + by1];
261         int b01 = paintingData.latticeSelector[latticeIndex + noiseY.nextIndex];
262         // ry1 = ry0 - 1.0f;
263         // q = fGradient[nColorChannel][b01]; u = rx0 * q[0] + ry1 * q[1];
264         q = paintingData.gradient[channel][b01];
265         u = noiseX.fraction * q[0] + (noiseY.fraction - 1) * q[1];
266
267         // b11 = uLatticeSelector[j + by1];
268         int b11 = paintingData.latticeSelector[nextLatticeIndex + noiseY.nextIndex];
269         // q = fGradient[nColorChannel][b11]; v = rx1 * q[0] + ry1 * q[1];
270         q = paintingData.gradient[channel][b11];
271         v = (noiseX.fraction - 1) * q[0] + (noiseY.fraction - 1) * q[1];
272         // b = lerp(sx, u, v);
273         float b = linearInterpolation(sx, u, v);
274
275         // return lerp(sy, a, b);
276         return linearInterpolation(sy, a, b);
277     };
278
279     return {
280         noiseForChannel(0),
281         noiseForChannel(1),
282         noiseForChannel(2),
283         noiseForChannel(3)
284     };
285 }
286
287 ColorComponents FETurbulence::calculateTurbulenceValueForPoint(const PaintingData& paintingData, StitchData& stitchData, const FloatPoint& point) const
288 {
289     float tileWidth = paintingData.filterSize.width();
290     float tileHeight = paintingData.filterSize.height();
291     ASSERT(tileWidth > 0 && tileHeight > 0);
292     
293     float baseFrequencyX = m_baseFrequencyX;
294     float baseFrequencyY = m_baseFrequencyY;
295
296     // Adjust the base frequencies if necessary for stitching.
297     if (m_stitchTiles) {
298         // When stitching tiled turbulence, the frequencies must be adjusted
299         // so that the tile borders will be continuous.
300         if (baseFrequencyX) {
301             float lowFrequency = floorf(tileWidth * baseFrequencyX) / tileWidth;
302             float highFrequency = ceilf(tileWidth * baseFrequencyX) / tileWidth;
303             // BaseFrequency should be non-negative according to the standard.
304             if (baseFrequencyX / lowFrequency < highFrequency / baseFrequencyX)
305                 baseFrequencyX = lowFrequency;
306             else
307                 baseFrequencyX = highFrequency;
308         }
309         if (baseFrequencyY) {
310             float lowFrequency = floorf(tileHeight * baseFrequencyY) / tileHeight;
311             float highFrequency = ceilf(tileHeight * baseFrequencyY) / tileHeight;
312             if (baseFrequencyY / lowFrequency < highFrequency / baseFrequencyY)
313                 baseFrequencyY = lowFrequency;
314             else
315                 baseFrequencyY = highFrequency;
316         }
317         // Set up TurbulenceInitial stitch values.
318         stitchData.width = roundf(tileWidth * baseFrequencyX);
319         stitchData.wrapX = s_perlinNoise + stitchData.width;
320         stitchData.height = roundf(tileHeight * baseFrequencyY);
321         stitchData.wrapY = s_perlinNoise + stitchData.height;
322     }
323
324     FloatComponents turbulenceFunctionResult;
325     FloatPoint noiseVector(point.x() * baseFrequencyX, point.y() * baseFrequencyY);
326     float ratio = 1;
327     for (int octave = 0; octave < m_numOctaves; ++octave) {
328         if (m_type == FETURBULENCE_TYPE_FRACTALNOISE)
329             turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector) / ratio;
330         else
331             turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector).abs() / ratio;
332
333         noiseVector.setX(noiseVector.x() * 2);
334         noiseVector.setY(noiseVector.y() * 2);
335         ratio *= 2;
336
337         if (m_stitchTiles) {
338             // Update stitch values. Subtracting s_perlinNoiseoise before the multiplication and
339             // adding it afterward simplifies to subtracting it once.
340             stitchData.width *= 2;
341             stitchData.wrapX = 2 * stitchData.wrapX - s_perlinNoise;
342             stitchData.height *= 2;
343             stitchData.wrapY = 2 * stitchData.wrapY - s_perlinNoise;
344         }
345     }
346
347     // The value of turbulenceFunctionResult comes from ((turbulenceFunctionResult * 255) + 255) / 2 by fractalNoise
348     // and (turbulenceFunctionResult * 255) by turbulence.
349     if (m_type == FETURBULENCE_TYPE_FRACTALNOISE)
350         turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f;
351
352     return turbulenceFunctionResult;
353 }
354
355 void FETurbulence::fillRegion(Uint8ClampedArray* pixelArray, const PaintingData& paintingData, int startY, int endY) const
356 {
357     IntRect filterRegion = absolutePaintRect();
358     FloatPoint point(0, filterRegion.y() + startY);
359     int indexOfPixelChannel = startY * (filterRegion.width() << 2);
360     StitchData stitchData;
361     AffineTransform inverseTransfrom = filter().absoluteTransform().inverse().value_or(AffineTransform());
362
363     for (int y = startY; y < endY; ++y) {
364         point.setY(point.y() + 1);
365         point.setX(filterRegion.x());
366         for (int x = 0; x < filterRegion.width(); ++x) {
367             point.setX(point.x() + 1);
368             FloatPoint localPoint = inverseTransfrom.mapPoint(point);
369             ColorComponents values = calculateTurbulenceValueForPoint(paintingData, stitchData, localPoint);
370             pixelArray->set(indexOfPixelChannel++, values.components[0]);
371             pixelArray->set(indexOfPixelChannel++, values.components[1]);
372             pixelArray->set(indexOfPixelChannel++, values.components[2]);
373             pixelArray->set(indexOfPixelChannel++, values.components[3]);
374         }
375     }
376 }
377
378 void FETurbulence::fillRegionWorker(FillRegionParameters* parameters)
379 {
380     parameters->filter->fillRegion(parameters->pixelArray, *parameters->paintingData, parameters->startY, parameters->endY);
381 }
382
383 void FETurbulence::platformApplySoftware()
384 {
385     Uint8ClampedArray* pixelArray = createUnmultipliedImageResult();
386     if (!pixelArray)
387         return;
388
389     if (absolutePaintRect().isEmpty()) {
390         pixelArray->zeroFill();
391         return;
392     }
393
394     PaintingData paintingData(m_seed, roundedIntSize(filterPrimitiveSubregion().size()));
395     initPaint(paintingData);
396
397     int optimalThreadNumber = (absolutePaintRect().width() * absolutePaintRect().height()) / s_minimalRectDimension;
398     if (optimalThreadNumber > 1) {
399         // Initialize parallel jobs
400         WTF::ParallelJobs<FillRegionParameters> parallelJobs(&WebCore::FETurbulence::fillRegionWorker, optimalThreadNumber);
401
402         // Fill the parameter array
403         int i = parallelJobs.numberOfJobs();
404         if (i > 1) {
405             // Split the job into "stepY"-sized jobs but there a few jobs that need to be slightly larger since
406             // stepY * jobs < total size. These extras are handled by the remainder "jobsWithExtra".
407             const int stepY = absolutePaintRect().height() / i;
408             const int jobsWithExtra = absolutePaintRect().height() % i;
409
410             int startY = 0;
411             for (; i > 0; --i) {
412                 FillRegionParameters& params = parallelJobs.parameter(i - 1);
413                 params.filter = this;
414                 params.pixelArray = pixelArray;
415                 params.paintingData = &paintingData;
416                 params.startY = startY;
417                 startY += i < jobsWithExtra ? stepY + 1 : stepY;
418                 params.endY = startY;
419             }
420
421             // Execute parallel jobs
422             parallelJobs.execute();
423             return;
424         }
425     }
426
427     // Fallback to single threaded mode if there is no room for a new thread or the paint area is too small.
428     fillRegion(pixelArray, paintingData, 0, absolutePaintRect().height());
429 }
430
431 void FETurbulence::dump()
432 {
433 }
434
435 static TextStream& operator<<(TextStream& ts, const TurbulenceType& type)
436 {
437     switch (type) {
438     case FETURBULENCE_TYPE_UNKNOWN:
439         ts << "UNKNOWN";
440         break;
441     case FETURBULENCE_TYPE_TURBULENCE:
442         ts << "TURBULANCE";
443         break;
444     case FETURBULENCE_TYPE_FRACTALNOISE:
445         ts << "NOISE";
446         break;
447     }
448     return ts;
449 }
450
451 TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const
452 {
453     writeIndent(ts, indent);
454     ts << "[feTurbulence";
455     FilterEffect::externalRepresentation(ts);
456     ts << " type=\"" << type() << "\" "
457        << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" "
458        << "seed=\"" << seed() << "\" "
459        << "numOctaves=\"" << numOctaves() << "\" "
460        << "stitchTiles=\"" << stitchTiles() << "\"]\n";
461     return ts;
462 }
463
464 } // namespace WebCore