feTurbulence is not rendered correctly on Retina display
[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-2018 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 <JavaScriptCore/Uint8ClampedArray.h>
31 #include <wtf/MathExtras.h>
32 #include <wtf/ParallelJobs.h>
33 #include <wtf/text/TextStream.h>
34
35 namespace WebCore {
36
37 /*
38     Produces results in the range [1, 2**31 - 2]. Algorithm is:
39     r = (a * r) mod m where a = randAmplitude = 16807 and
40     m = randMaximum = 2**31 - 1 = 2147483647, r = seed.
41     See [Park & Miller], CACM vol. 31 no. 10 p. 1195, Oct. 1988
42     To test: the algorithm should produce the result 1043618065
43     as the 10,000th generated number if the original seed is 1.
44 */
45 static const int s_perlinNoise = 4096;
46 static const long s_randMaximum = 2147483647; // 2**31 - 1
47 static const int s_randAmplitude = 16807; // 7**5; primitive root of m
48 static const int s_randQ = 127773; // m / a
49 static const int s_randR = 2836; // m % a
50
51 FETurbulence::FETurbulence(Filter& filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
52     : FilterEffect(filter)
53     , m_type(type)
54     , m_baseFrequencyX(baseFrequencyX)
55     , m_baseFrequencyY(baseFrequencyY)
56     , m_numOctaves(numOctaves)
57     , m_seed(seed)
58     , m_stitchTiles(stitchTiles)
59 {
60 }
61
62 Ref<FETurbulence> FETurbulence::create(Filter& filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
63 {
64     return adoptRef(*new FETurbulence(filter, type, baseFrequencyX, baseFrequencyY, numOctaves, seed, stitchTiles));
65 }
66
67 bool FETurbulence::setType(TurbulenceType type)
68 {
69     if (m_type == type)
70         return false;
71     m_type = type;
72     return true;
73 }
74
75 bool FETurbulence::setBaseFrequencyY(float baseFrequencyY)
76 {
77     if (m_baseFrequencyY == baseFrequencyY)
78         return false;
79     m_baseFrequencyY = baseFrequencyY;
80     return true;
81 }
82
83 bool FETurbulence::setBaseFrequencyX(float baseFrequencyX)
84 {
85     if (m_baseFrequencyX == baseFrequencyX)
86         return false;
87     m_baseFrequencyX = baseFrequencyX;
88     return true;
89 }
90
91 bool FETurbulence::setSeed(float seed)
92 {
93     if (m_seed == seed)
94         return false;
95     m_seed = seed;
96     return true;
97 }
98
99 bool FETurbulence::setNumOctaves(int numOctaves)
100 {
101     if (m_numOctaves == numOctaves)
102         return false;
103     m_numOctaves = numOctaves;
104     return true;
105 }
106
107 bool FETurbulence::setStitchTiles(bool stitch)
108 {
109     if (m_stitchTiles == stitch)
110         return false;
111     m_stitchTiles = stitch;
112     return true;
113 }
114
115 // The turbulence calculation code is an adapted version of what appears in the SVG 1.1 specification:
116 // http://www.w3.org/TR/SVG11/filters.html#feTurbulence
117
118 // Compute pseudo random number.
119 inline long FETurbulence::PaintingData::random()
120 {
121     long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ);
122     if (result <= 0)
123         result += s_randMaximum;
124     seed = result;
125     return result;
126 }
127
128 inline float smoothCurve(float t)
129 {
130     return t * t * (3 - 2 * t);
131 }
132
133 inline float linearInterpolation(float t, float a, float b)
134 {
135     return a + t * (b - a);
136 }
137
138 void FETurbulence::initPaint(PaintingData& paintingData)
139 {
140     float normalizationFactor;
141
142     // The seed value clamp to the range [1, s_randMaximum - 1].
143     if (paintingData.seed <= 0)
144         paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1;
145     if (paintingData.seed > s_randMaximum - 1)
146         paintingData.seed = s_randMaximum - 1;
147
148     float* gradient;
149     for (int channel = 0; channel < 4; ++channel) {
150         for (int i = 0; i < s_blockSize; ++i) {
151             paintingData.latticeSelector[i] = i;
152             gradient = paintingData.gradient[channel][i];
153             do {
154                 gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
155                 gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
156             } while (!gradient[0] && !gradient[1]);
157             normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]);
158             gradient[0] /= normalizationFactor;
159             gradient[1] /= normalizationFactor;
160         }
161     }
162
163     for (int i = s_blockSize - 1; i > 0; --i) {
164         int k = paintingData.latticeSelector[i];
165         int j = paintingData.random() % s_blockSize;
166         ASSERT(j >= 0);
167         ASSERT(j < 2 * s_blockSize + 2);
168         paintingData.latticeSelector[i] = paintingData.latticeSelector[j];
169         paintingData.latticeSelector[j] = k;
170     }
171
172     for (int i = 0; i < s_blockSize + 2; ++i) {
173         paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i];
174         for (int channel = 0; channel < 4; ++channel) {
175             paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0];
176             paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1];
177         }
178     }
179 }
180
181 FETurbulence::StitchData FETurbulence::computeStitching(IntSize tileSize, float& baseFrequencyX, float& baseFrequencyY) const
182 {
183     if (!m_stitchTiles)
184         return { };
185
186     float tileWidth = tileSize.width();
187     float tileHeight = tileSize.height();
188     ASSERT(tileWidth > 0 && tileHeight > 0);
189
190     // When stitching tiled turbulence, the frequencies must be adjusted
191     // so that the tile borders will be continuous.
192     if (baseFrequencyX) {
193         float lowFrequency = floorf(tileWidth * baseFrequencyX) / tileWidth;
194         float highFrequency = ceilf(tileWidth * baseFrequencyX) / tileWidth;
195         // BaseFrequency should be non-negative according to the standard.
196         if (baseFrequencyX / lowFrequency < highFrequency / baseFrequencyX)
197             baseFrequencyX = lowFrequency;
198         else
199             baseFrequencyX = highFrequency;
200     }
201     if (baseFrequencyY) {
202         float lowFrequency = floorf(tileHeight * baseFrequencyY) / tileHeight;
203         float highFrequency = ceilf(tileHeight * baseFrequencyY) / tileHeight;
204         if (baseFrequencyY / lowFrequency < highFrequency / baseFrequencyY)
205             baseFrequencyY = lowFrequency;
206         else
207             baseFrequencyY = highFrequency;
208     }
209
210     StitchData stitchData;
211     stitchData.width = roundf(tileWidth * baseFrequencyX);
212     stitchData.wrapX = s_perlinNoise + stitchData.width;
213     stitchData.height = roundf(tileHeight * baseFrequencyY);
214     stitchData.wrapY = s_perlinNoise + stitchData.height;
215
216     return stitchData;
217 }
218
219 // This is taken 1:1 from SVG spec: http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement.
220 FloatComponents FETurbulence::noise2D(const PaintingData& paintingData, const StitchData& stitchData, const FloatPoint& noiseVector) const
221 {
222     struct NoisePosition {
223         int index; // bx0, by0 in the spec text.
224         int nextIndex; // bx1, by1 in the spec text.
225         float fraction; // rx0, ry0 in the spec text.
226
227         NoisePosition(float component)
228         {
229             //  t = vec[0] + PerlinN;
230             //  bx0 = (int)t;
231             //  bx1 = bx0+1;
232             //  rx0 = t - (int)t;
233             float position = component + s_perlinNoise;
234             index = static_cast<int>(position);
235             nextIndex = index + 1;
236             fraction = position - index;
237         }
238         
239         void stitch(int size, int wrapSize)
240         {
241             // if (bx0 >= pStitchInfo->nWrapX)
242             //   bx0 -= pStitchInfo->nWidth;
243             if (index >= wrapSize)
244                 index -= size;
245
246             // if (bx1 >= pStitchInfo->nWrapX)
247             //   bx1 -= pStitchInfo->nWidth;
248             if (nextIndex >= wrapSize)
249                 nextIndex -= size;
250         }
251     };
252
253     NoisePosition noiseX(noiseVector.x());
254     NoisePosition noiseY(noiseVector.y());
255
256     // If stitching, adjust lattice points accordingly.
257     if (m_stitchTiles) {
258         noiseX.stitch(stitchData.width, stitchData.wrapX);
259         noiseY.stitch(stitchData.height, stitchData.wrapY);
260     }
261
262     // bx0 &= BM;
263     // bx1 &= BM;
264     // by0 &= BM;
265     // by1 &= BM;
266     noiseX.index &= s_blockMask;
267     noiseX.nextIndex &= s_blockMask;
268     noiseY.index &= s_blockMask;
269     noiseY.nextIndex &= s_blockMask;
270
271     // i = uLatticeSelector[bx0];
272     // j = uLatticeSelector[bx1];
273     int latticeIndex = paintingData.latticeSelector[noiseX.index];
274     int nextLatticeIndex = paintingData.latticeSelector[noiseX.nextIndex];
275
276     // sx = double(s_curve(rx0));
277     // sy = double(s_curve(ry0));
278     float sx = smoothCurve(noiseX.fraction);
279     float sy = smoothCurve(noiseY.fraction);
280
281     auto noiseForChannel = [&](int channel) {
282         // b00 = uLatticeSelector[i + by0]
283         int b00 = paintingData.latticeSelector[latticeIndex + noiseY.index];
284         // q = fGradient[nColorChannel][b00]; u = rx0 * q[0] + ry0 * q[1];
285         const float* q = paintingData.gradient[channel][b00];
286         float u = noiseX.fraction * q[0] + noiseY.fraction * q[1];
287
288         // b10 = uLatticeSelector[j + by0];
289         int b10 = paintingData.latticeSelector[nextLatticeIndex + noiseY.index];
290         // rx1 = rx0 - 1.0f;
291         // q = fGradient[nColorChannel][b10]; v = rx1 * q[0] + ry0 * q[1];
292         q = paintingData.gradient[channel][b10];
293         float v = (noiseX.fraction - 1) * q[0] + noiseY.fraction * q[1];
294         // a = lerp(sx, u, v);
295         float a = linearInterpolation(sx, u, v);
296
297         // b01 = uLatticeSelector[i + by1];
298         int b01 = paintingData.latticeSelector[latticeIndex + noiseY.nextIndex];
299         // ry1 = ry0 - 1.0f;
300         // q = fGradient[nColorChannel][b01]; u = rx0 * q[0] + ry1 * q[1];
301         q = paintingData.gradient[channel][b01];
302         u = noiseX.fraction * q[0] + (noiseY.fraction - 1) * q[1];
303
304         // b11 = uLatticeSelector[j + by1];
305         int b11 = paintingData.latticeSelector[nextLatticeIndex + noiseY.nextIndex];
306         // q = fGradient[nColorChannel][b11]; v = rx1 * q[0] + ry1 * q[1];
307         q = paintingData.gradient[channel][b11];
308         v = (noiseX.fraction - 1) * q[0] + (noiseY.fraction - 1) * q[1];
309         // b = lerp(sx, u, v);
310         float b = linearInterpolation(sx, u, v);
311
312         // return lerp(sy, a, b);
313         return linearInterpolation(sy, a, b);
314     };
315
316     return {
317         noiseForChannel(0),
318         noiseForChannel(1),
319         noiseForChannel(2),
320         noiseForChannel(3)
321     };
322 }
323
324 // https://www.w3.org/TR/SVG/filters.html#feTurbulenceElement describes this conversion to color components.
325 static inline ColorComponents toColorComponents(const FloatComponents& floatComponents)
326 {
327     return {
328         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[0] * 255), 255)),
329         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[1] * 255), 255)),
330         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[2] * 255), 255)),
331         std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[3] * 255), 255))
332     };
333 }
334
335 ColorComponents FETurbulence::calculateTurbulenceValueForPoint(const PaintingData& paintingData, StitchData stitchData, const FloatPoint& point) const
336 {
337     FloatComponents turbulenceFunctionResult;
338     FloatPoint noiseVector(point.x() * paintingData.baseFrequencyX, point.y() * paintingData.baseFrequencyY);
339     float ratio = 1;
340     for (int octave = 0; octave < m_numOctaves; ++octave) {
341         if (m_type == TurbulenceType::FractalNoise)
342             turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector) / ratio;
343         else
344             turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector).abs() / ratio;
345
346         noiseVector.setX(noiseVector.x() * 2);
347         noiseVector.setY(noiseVector.y() * 2);
348         ratio *= 2;
349
350         if (m_stitchTiles) {
351             // Update stitch values. Subtracting s_perlinNoise before the multiplication and
352             // adding it afterward simplifies to subtracting it once.
353             stitchData.width *= 2;
354             stitchData.wrapX = 2 * stitchData.wrapX - s_perlinNoise;
355             stitchData.height *= 2;
356             stitchData.wrapY = 2 * stitchData.wrapY - s_perlinNoise;
357         }
358     }
359
360     // The value of turbulenceFunctionResult comes from ((turbulenceFunctionResult * 255) + 255) / 2 by fractalNoise
361     // and (turbulenceFunctionResult * 255) by turbulence.
362     if (m_type == TurbulenceType::FractalNoise)
363         turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f;
364
365     return toColorComponents(turbulenceFunctionResult);
366 }
367
368 void FETurbulence::fillRegion(Uint8ClampedArray& pixelArray, const PaintingData& paintingData, StitchData stitchData, int startY, int endY) const
369 {
370     ASSERT(endY > startY);
371
372     IntRect filterRegion = absolutePaintRect();
373     filterRegion.scale(filter().filterScale());
374     FloatPoint point(0, filterRegion.y() + startY);
375     int indexOfPixelChannel = startY * (filterRegion.width() << 2);
376     AffineTransform inverseTransfrom = filter().absoluteTransform().inverse().value_or(AffineTransform());
377
378     for (int y = startY; y < endY; ++y) {
379         point.setY(point.y() + 1);
380         point.setX(filterRegion.x());
381         for (int x = 0; x < filterRegion.width(); ++x) {
382             point.setX(point.x() + 1);
383             FloatPoint localPoint = inverseTransfrom.mapPoint(point);
384             ColorComponents values = calculateTurbulenceValueForPoint(paintingData, stitchData, localPoint);
385             pixelArray.setRange(values.components, 4, indexOfPixelChannel);
386             indexOfPixelChannel += 4;
387         }
388     }
389 }
390
391 void FETurbulence::fillRegionWorker(FillRegionParameters* parameters)
392 {
393     parameters->filter->fillRegion(*parameters->pixelArray, *parameters->paintingData, parameters->stitchData, parameters->startY, parameters->endY);
394 }
395
396 void FETurbulence::platformApplySoftware()
397 {
398     Uint8ClampedArray* pixelArray = createUnmultipliedImageResult();
399     if (!pixelArray)
400         return;
401
402     IntSize resultSize(absolutePaintRect().size());
403     resultSize.scale(filter().filterScale());
404
405     if (resultSize.isEmpty()) {
406         pixelArray->zeroFill();
407         return;
408     }
409
410     IntSize tileSize = roundedIntSize(filterPrimitiveSubregion().size());
411
412     float baseFrequencyX = m_baseFrequencyX;
413     float baseFrequencyY = m_baseFrequencyY;
414     StitchData stitchData = computeStitching(tileSize, baseFrequencyX, baseFrequencyY);
415
416     PaintingData paintingData(m_seed, tileSize, baseFrequencyX, baseFrequencyY);
417     initPaint(paintingData);
418
419     auto area = resultSize.area();
420     if (area.hasOverflowed())
421         return;
422
423     int height = resultSize.height();
424
425     unsigned maxNumThreads = height / 8;
426     unsigned optimalThreadNumber = std::min<unsigned>(area.unsafeGet() / s_minimalRectDimension, maxNumThreads);
427     if (optimalThreadNumber > 1) {
428         WTF::ParallelJobs<FillRegionParameters> parallelJobs(&WebCore::FETurbulence::fillRegionWorker, optimalThreadNumber);
429
430         // Fill the parameter array
431         auto numJobs = parallelJobs.numberOfJobs();
432         if (numJobs > 1) {
433             // Split the job into "stepY"-sized jobs, distributing the extra rows into the first "jobsWithExtra" jobs.
434             unsigned stepY = height / numJobs;
435             unsigned jobsWithExtra = height % numJobs;
436             unsigned startY = 0;
437
438             for (unsigned i = 0; i < numJobs; ++i) {
439                 FillRegionParameters& params = parallelJobs.parameter(i);
440                 params.filter = this;
441                 params.pixelArray = pixelArray;
442                 params.paintingData = &paintingData;
443                 params.stitchData = stitchData;
444                 params.startY = startY;
445
446                 unsigned jobHeight = (i < jobsWithExtra) ? stepY + 1 : stepY;
447                 params.endY = params.startY + jobHeight;
448                 startY += jobHeight;
449             }
450
451             parallelJobs.execute();
452             return;
453         }
454     }
455
456     // Fallback to single threaded mode if there is no room for a new thread or the paint area is too small.
457     fillRegion(*pixelArray, paintingData, stitchData, 0, height);
458 }
459
460 static TextStream& operator<<(TextStream& ts, TurbulenceType type)
461 {
462     switch (type) {
463     case TurbulenceType::Unknown:
464         ts << "UNKNOWN";
465         break;
466     case TurbulenceType::Turbulence:
467         ts << "TURBULENCE";
468         break;
469     case TurbulenceType::FractalNoise:
470         ts << "NOISE";
471         break;
472     }
473     return ts;
474 }
475
476 TextStream& FETurbulence::externalRepresentation(TextStream& ts, RepresentationType representation) const
477 {
478     ts << indent << "[feTurbulence";
479     FilterEffect::externalRepresentation(ts, representation);
480     ts << " type=\"" << type() << "\" "
481        << "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" "
482        << "seed=\"" << seed() << "\" "
483        << "numOctaves=\"" << numOctaves() << "\" "
484        << "stitchTiles=\"" << stitchTiles() << "\"]\n";
485     return ts;
486 }
487
488 } // namespace WebCore