2d0b62c5c9099faa9161a00895f392eaabd1029e
[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 FETurbulence::StitchData FETurbulence::computeStitching(IntSize tileSize, float& baseFrequencyX, float& baseFrequencyY) const
183 {
184     if (!m_stitchTiles)
185         return { };
186
187     float tileWidth = tileSize.width();
188     float tileHeight = tileSize.height();
189     ASSERT(tileWidth > 0 && tileHeight > 0);
190
191     // When stitching tiled turbulence, the frequencies must be adjusted
192     // so that the tile borders will be continuous.
193     if (baseFrequencyX) {
194         float lowFrequency = floorf(tileWidth * baseFrequencyX) / tileWidth;
195         float highFrequency = ceilf(tileWidth * baseFrequencyX) / tileWidth;
196         // BaseFrequency should be non-negative according to the standard.
197         if (baseFrequencyX / lowFrequency < highFrequency / baseFrequencyX)
198             baseFrequencyX = lowFrequency;
199         else
200             baseFrequencyX = highFrequency;
201     }
202     if (baseFrequencyY) {
203         float lowFrequency = floorf(tileHeight * baseFrequencyY) / tileHeight;
204         float highFrequency = ceilf(tileHeight * baseFrequencyY) / tileHeight;
205         if (baseFrequencyY / lowFrequency < highFrequency / baseFrequencyY)
206             baseFrequencyY = lowFrequency;
207         else
208             baseFrequencyY = highFrequency;
209     }
210
211     StitchData stitchData;
212     stitchData.width = roundf(tileWidth * baseFrequencyX);
213     stitchData.wrapX = s_perlinNoise + stitchData.width;
214     stitchData.height = roundf(tileHeight * baseFrequencyY);
215     stitchData.wrapY = s_perlinNoise + stitchData.height;
216
217     return stitchData;
218 }
219
220 // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement.
221 FloatComponents FETurbulence::noise2D(const PaintingData& paintingData, const StitchData& stitchData, const FloatPoint& noiseVector) const
222 {
223     struct NoisePosition {
224         int index; // bx0, by0 in the spec text.
225         int nextIndex; // bx1, by1 in the spec text.
226         float fraction; // rx0, ry0 in the spec text.
227
228         NoisePosition(float component)
229         {
230             //  t = vec[0] + PerlinN;
231             //  bx0 = (int)t;
232             //  bx1 = bx0+1;
233             //  rx0 = t - (int)t;
234             float position = component + s_perlinNoise;
235             index = static_cast<int>(position);
236             nextIndex = index + 1;
237             fraction = position - index;
238         }
239         
240         void stitch(int size, int wrapSize)
241         {
242             // if (bx0 >= pStitchInfo->nWrapX)
243             //   bx0 -= pStitchInfo->nWidth;
244             if (index >= wrapSize)
245                 index -= size;
246
247             // if (bx1 >= pStitchInfo->nWrapX)
248             //   bx1 -= pStitchInfo->nWidth;
249             if (nextIndex >= wrapSize)
250                 nextIndex -= size;
251         }
252     };
253
254     NoisePosition noiseX(noiseVector.x());
255     NoisePosition noiseY(noiseVector.y());
256
257     // If stitching, adjust lattice points accordingly.
258     if (m_stitchTiles) {
259         noiseX.stitch(stitchData.width, stitchData.wrapX);
260         noiseY.stitch(stitchData.height, stitchData.wrapY);
261     }
262
263     // bx0 &= BM;
264     // bx1 &= BM;
265     // by0 &= BM;
266     // by1 &= BM;
267     noiseX.index &= s_blockMask;
268     noiseX.nextIndex &= s_blockMask;
269     noiseY.index &= s_blockMask;
270     noiseY.nextIndex &= s_blockMask;
271
272     // i = uLatticeSelector[bx0];
273     // j = uLatticeSelector[bx1];
274     int latticeIndex = paintingData.latticeSelector[noiseX.index];
275     int nextLatticeIndex = paintingData.latticeSelector[noiseX.nextIndex];
276
277     // sx = double(s_curve(rx0));
278     // sy = double(s_curve(ry0));
279     float sx = smoothCurve(noiseX.fraction);
280     float sy = smoothCurve(noiseY.fraction);
281
282     auto noiseForChannel = [&](int channel) {
283         // b00 = uLatticeSelector[i + by0]
284         int b00 = paintingData.latticeSelector[latticeIndex + noiseY.index];
285         // q = fGradient[nColorChannel][b00]; u = rx0 * q[0] + ry0 * q[1];
286         const float* q = paintingData.gradient[channel][b00];
287         float u = noiseX.fraction * q[0] + noiseY.fraction * q[1];
288
289         // b10 = uLatticeSelector[j + by0];
290         int b10 = paintingData.latticeSelector[nextLatticeIndex + noiseY.index];
291         // rx1 = rx0 - 1.0f;
292         // q = fGradient[nColorChannel][b10]; v = rx1 * q[0] + ry0 * q[1];
293         q = paintingData.gradient[channel][b10];
294         float v = (noiseX.fraction - 1) * q[0] + noiseY.fraction * q[1];
295         // a = lerp(sx, u, v);
296         float a = linearInterpolation(sx, u, v);
297
298         // b01 = uLatticeSelector[i + by1];
299         int b01 = paintingData.latticeSelector[latticeIndex + noiseY.nextIndex];
300         // ry1 = ry0 - 1.0f;
301         // q = fGradient[nColorChannel][b01]; u = rx0 * q[0] + ry1 * q[1];
302         q = paintingData.gradient[channel][b01];
303         u = noiseX.fraction * q[0] + (noiseY.fraction - 1) * q[1];
304
305         // b11 = uLatticeSelector[j + by1];
306         int b11 = paintingData.latticeSelector[nextLatticeIndex + noiseY.nextIndex];
307         // q = fGradient[nColorChannel][b11]; v = rx1 * q[0] + ry1 * q[1];
308         q = paintingData.gradient[channel][b11];
309         v = (noiseX.fraction - 1) * q[0] + (noiseY.fraction - 1) * q[1];
310         // b = lerp(sx, u, v);
311         float b = linearInterpolation(sx, u, v);
312
313         // return lerp(sy, a, b);
314         return linearInterpolation(sy, a, b);
315     };
316
317     return {
318         noiseForChannel(0),
319         noiseForChannel(1),
320         noiseForChannel(2),
321         noiseForChannel(3)
322     };
323 }
324
325 // https://www.w3.org/TR/SVG/filters.html#feTurbulenceElement describes this conversion to color components.
326 static inline ColorComponents toColorComponents(const FloatComponents& floatComponents)
327 {
328     return {
329         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[0] * 255), 255)),
330         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[1] * 255), 255)),
331         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[2] * 255), 255)),
332         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[3] * 255), 255))
333     };
334 }
335
336 ColorComponents FETurbulence::calculateTurbulenceValueForPoint(const PaintingData& paintingData, StitchData stitchData, const FloatPoint& point) const
337 {
338     FloatComponents turbulenceFunctionResult;
339     FloatPoint noiseVector(point.x() * paintingData.baseFrequencyX, point.y() * paintingData.baseFrequencyY);
340     float ratio = 1;
341     for (int octave = 0; octave < m_numOctaves; ++octave) {
342         if (m_type == TurbulenceType::FractalNoise)
343             turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector) / ratio;
344         else
345             turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector).abs() / ratio;
346
347         noiseVector.setX(noiseVector.x() * 2);
348         noiseVector.setY(noiseVector.y() * 2);
349         ratio *= 2;
350
351         if (m_stitchTiles) {
352             // Update stitch values. Subtracting s_perlinNoise before the multiplication and
353             // adding it afterward simplifies to subtracting it once.
354             stitchData.width *= 2;
355             stitchData.wrapX = 2 * stitchData.wrapX - s_perlinNoise;
356             stitchData.height *= 2;
357             stitchData.wrapY = 2 * stitchData.wrapY - s_perlinNoise;
358         }
359     }
360
361     // The value of turbulenceFunctionResult comes from ((turbulenceFunctionResult * 255) + 255) / 2 by fractalNoise
362     // and (turbulenceFunctionResult * 255) by turbulence.
363     if (m_type == TurbulenceType::FractalNoise)
364         turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f;
365
366     return toColorComponents(turbulenceFunctionResult);
367 }
368
369 void FETurbulence::fillRegion(Uint8ClampedArray* pixelArray, const PaintingData& paintingData, StitchData stitchData, int startY, int endY) const
370 {
371     IntRect filterRegion = absolutePaintRect();
372     FloatPoint point(0, filterRegion.y() + startY);
373     int indexOfPixelChannel = startY * (filterRegion.width() << 2);
374     AffineTransform inverseTransfrom = filter().absoluteTransform().inverse().value_or(AffineTransform());
375
376     for (int y = startY; y < endY; ++y) {
377         point.setY(point.y() + 1);
378         point.setX(filterRegion.x());
379         for (int x = 0; x < filterRegion.width(); ++x) {
380             point.setX(point.x() + 1);
381             FloatPoint localPoint = inverseTransfrom.mapPoint(point);
382             ColorComponents values = calculateTurbulenceValueForPoint(paintingData, stitchData, localPoint);
383             pixelArray->setRange(values.components, 4, indexOfPixelChannel);
384             indexOfPixelChannel += 4;
385         }
386     }
387 }
388
389 void FETurbulence::fillRegionWorker(FillRegionParameters* parameters)
390 {
391     parameters->filter->fillRegion(parameters->pixelArray, *parameters->paintingData, parameters->stitchData, parameters->startY, parameters->endY);
392 }
393
394 void FETurbulence::platformApplySoftware()
395 {
396     Uint8ClampedArray* pixelArray = createUnmultipliedImageResult();
397     if (!pixelArray)
398         return;
399
400     if (absolutePaintRect().isEmpty()) {
401         pixelArray->zeroFill();
402         return;
403     }
404
405     IntSize tileSize = roundedIntSize(filterPrimitiveSubregion().size());
406
407     float baseFrequencyX = m_baseFrequencyX;
408     float baseFrequencyY = m_baseFrequencyY;
409     StitchData stitchData = computeStitching(tileSize, baseFrequencyX, baseFrequencyY);
410
411     PaintingData paintingData(m_seed, tileSize, baseFrequencyX, baseFrequencyY);
412     initPaint(paintingData);
413
414     int height = absolutePaintRect().height();
415
416     auto area = absolutePaintRect().area();
417     if (area.hasOverflowed())
418         return;
419
420     unsigned optimalThreadNumber = area.unsafeGet() / s_minimalRectDimension;
421     if (optimalThreadNumber > 1) {
422         WTF::ParallelJobs<FillRegionParameters> parallelJobs(&WebCore::FETurbulence::fillRegionWorker, optimalThreadNumber);
423
424         // Fill the parameter array
425         unsigned numJobs = parallelJobs.numberOfJobs();
426         if (numJobs > 1) {
427             // Split the job into "stepY"-sized jobs, distributing the extra rows into the first "jobsWithExtra" jobs.
428             unsigned stepY = height / numJobs;
429             unsigned jobsWithExtra = height % numJobs;
430             unsigned startY = 0;
431
432             for (unsigned i = 0; i < numJobs; ++i) {
433                 FillRegionParameters& params = parallelJobs.parameter(i);
434                 params.filter = this;
435                 params.pixelArray = pixelArray;
436                 params.paintingData = &paintingData;
437                 params.stitchData = stitchData;
438                 params.startY = startY;
439
440                 unsigned jobHeight = (i < jobsWithExtra) ? stepY + 1 : stepY;
441                 params.endY = params.startY + jobHeight;
442                 startY += jobHeight;
443             }
444
445             parallelJobs.execute();
446             return;
447         }
448     }
449
450     // Fallback to single threaded mode if there is no room for a new thread or the paint area is too small.
451     fillRegion(pixelArray, paintingData, stitchData, 0, height);
452 }
453
454 static TextStream& operator<<(TextStream& ts, const TurbulenceType& type)
455 {
456     switch (type) {
457     case TurbulenceType::Unknown:
458         ts << "UNKNOWN";
459         break;
460     case TurbulenceType::Turbulence:
461         ts << "TURBULENCE";
462         break;
463     case TurbulenceType::FractalNoise:
464         ts << "NOISE";
465         break;
466     }
467     return ts;
468 }
469
470 TextStream& FETurbulence::externalRepresentation(TextStream& ts, int indent) const
471 {
472     writeIndent(ts, indent);
473     ts << "[feTurbulence";
474     FilterEffect::externalRepresentation(ts);
475     ts << " type=\"" << type() << "\" "
476        << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" "
477        << "seed=\"" << seed() << "\" "
478        << "numOctaves=\"" << numOctaves() << "\" "
479        << "stitchTiles=\"" << stitchTiles() << "\"]\n";
480     return ts;
481 }
482
483 } // namespace WebCore