#include "config.h"
#include "FETurbulence.h"
#include "Filter.h"
#include <JavaScriptCore/Uint8ClampedArray.h>
#include <wtf/MathExtras.h>
#include <wtf/ParallelJobs.h>
#include <wtf/text/TextStream.h>
namespace WebCore {
static const int s_perlinNoise = 4096;
static const long s_randMaximum = 2147483647; static const int s_randAmplitude = 16807; static const int s_randQ = 127773; static const int s_randR = 2836;
FETurbulence::FETurbulence(Filter& filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
: FilterEffect(filter)
, m_type(type)
, m_baseFrequencyX(baseFrequencyX)
, m_baseFrequencyY(baseFrequencyY)
, m_numOctaves(numOctaves)
, m_seed(seed)
, m_stitchTiles(stitchTiles)
{
}
Ref<FETurbulence> FETurbulence::create(Filter& filter, TurbulenceType type, float baseFrequencyX, float baseFrequencyY, int numOctaves, float seed, bool stitchTiles)
{
return adoptRef(*new FETurbulence(filter, type, baseFrequencyX, baseFrequencyY, numOctaves, seed, stitchTiles));
}
bool FETurbulence::setType(TurbulenceType type)
{
if (m_type == type)
return false;
m_type = type;
return true;
}
bool FETurbulence::setBaseFrequencyY(float baseFrequencyY)
{
if (m_baseFrequencyY == baseFrequencyY)
return false;
m_baseFrequencyY = baseFrequencyY;
return true;
}
bool FETurbulence::setBaseFrequencyX(float baseFrequencyX)
{
if (m_baseFrequencyX == baseFrequencyX)
return false;
m_baseFrequencyX = baseFrequencyX;
return true;
}
bool FETurbulence::setSeed(float seed)
{
if (m_seed == seed)
return false;
m_seed = seed;
return true;
}
bool FETurbulence::setNumOctaves(int numOctaves)
{
if (m_numOctaves == numOctaves)
return false;
m_numOctaves = numOctaves;
return true;
}
bool FETurbulence::setStitchTiles(bool stitch)
{
if (m_stitchTiles == stitch)
return false;
m_stitchTiles = stitch;
return true;
}
inline long FETurbulence::PaintingData::random()
{
long result = s_randAmplitude * (seed % s_randQ) - s_randR * (seed / s_randQ);
if (result <= 0)
result += s_randMaximum;
seed = result;
return result;
}
inline float smoothCurve(float t)
{
return t * t * (3 - 2 * t);
}
inline float linearInterpolation(float t, float a, float b)
{
return a + t * (b - a);
}
void FETurbulence::initPaint(PaintingData& paintingData)
{
float normalizationFactor;
if (paintingData.seed <= 0)
paintingData.seed = -(paintingData.seed % (s_randMaximum - 1)) + 1;
if (paintingData.seed > s_randMaximum - 1)
paintingData.seed = s_randMaximum - 1;
float* gradient;
for (int channel = 0; channel < 4; ++channel) {
for (int i = 0; i < s_blockSize; ++i) {
paintingData.latticeSelector[i] = i;
gradient = paintingData.gradient[channel][i];
do {
gradient[0] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
gradient[1] = static_cast<float>((paintingData.random() % (2 * s_blockSize)) - s_blockSize) / s_blockSize;
} while (!gradient[0] && !gradient[1]);
normalizationFactor = sqrtf(gradient[0] * gradient[0] + gradient[1] * gradient[1]);
gradient[0] /= normalizationFactor;
gradient[1] /= normalizationFactor;
}
}
for (int i = s_blockSize - 1; i > 0; --i) {
int k = paintingData.latticeSelector[i];
int j = paintingData.random() % s_blockSize;
ASSERT(j >= 0);
ASSERT(j < 2 * s_blockSize + 2);
paintingData.latticeSelector[i] = paintingData.latticeSelector[j];
paintingData.latticeSelector[j] = k;
}
for (int i = 0; i < s_blockSize + 2; ++i) {
paintingData.latticeSelector[s_blockSize + i] = paintingData.latticeSelector[i];
for (int channel = 0; channel < 4; ++channel) {
paintingData.gradient[channel][s_blockSize + i][0] = paintingData.gradient[channel][i][0];
paintingData.gradient[channel][s_blockSize + i][1] = paintingData.gradient[channel][i][1];
}
}
}
FETurbulence::StitchData FETurbulence::computeStitching(IntSize tileSize, float& baseFrequencyX, float& baseFrequencyY) const
{
if (!m_stitchTiles)
return { };
float tileWidth = tileSize.width();
float tileHeight = tileSize.height();
ASSERT(tileWidth > 0 && tileHeight > 0);
if (baseFrequencyX) {
float lowFrequency = floorf(tileWidth * baseFrequencyX) / tileWidth;
float highFrequency = ceilf(tileWidth * baseFrequencyX) / tileWidth;
if (baseFrequencyX / lowFrequency < highFrequency / baseFrequencyX)
baseFrequencyX = lowFrequency;
else
baseFrequencyX = highFrequency;
}
if (baseFrequencyY) {
float lowFrequency = floorf(tileHeight * baseFrequencyY) / tileHeight;
float highFrequency = ceilf(tileHeight * baseFrequencyY) / tileHeight;
if (baseFrequencyY / lowFrequency < highFrequency / baseFrequencyY)
baseFrequencyY = lowFrequency;
else
baseFrequencyY = highFrequency;
}
StitchData stitchData;
stitchData.width = roundf(tileWidth * baseFrequencyX);
stitchData.wrapX = s_perlinNoise + stitchData.width;
stitchData.height = roundf(tileHeight * baseFrequencyY);
stitchData.wrapY = s_perlinNoise + stitchData.height;
return stitchData;
}
FloatComponents FETurbulence::noise2D(const PaintingData& paintingData, const StitchData& stitchData, const FloatPoint& noiseVector) const
{
struct NoisePosition {
int index; int nextIndex; float fraction;
NoisePosition(float component)
{
float position = component + s_perlinNoise;
index = static_cast<int>(position);
nextIndex = index + 1;
fraction = position - index;
}
void stitch(int size, int wrapSize)
{
if (index >= wrapSize)
index -= size;
if (nextIndex >= wrapSize)
nextIndex -= size;
}
};
NoisePosition noiseX(noiseVector.x());
NoisePosition noiseY(noiseVector.y());
if (m_stitchTiles) {
noiseX.stitch(stitchData.width, stitchData.wrapX);
noiseY.stitch(stitchData.height, stitchData.wrapY);
}
noiseX.index &= s_blockMask;
noiseX.nextIndex &= s_blockMask;
noiseY.index &= s_blockMask;
noiseY.nextIndex &= s_blockMask;
int latticeIndex = paintingData.latticeSelector[noiseX.index];
int nextLatticeIndex = paintingData.latticeSelector[noiseX.nextIndex];
float sx = smoothCurve(noiseX.fraction);
float sy = smoothCurve(noiseY.fraction);
auto noiseForChannel = [&](int channel) {
int b00 = paintingData.latticeSelector[latticeIndex + noiseY.index];
const float* q = paintingData.gradient[channel][b00];
float u = noiseX.fraction * q[0] + noiseY.fraction * q[1];
int b10 = paintingData.latticeSelector[nextLatticeIndex + noiseY.index];
q = paintingData.gradient[channel][b10];
float v = (noiseX.fraction - 1) * q[0] + noiseY.fraction * q[1];
float a = linearInterpolation(sx, u, v);
int b01 = paintingData.latticeSelector[latticeIndex + noiseY.nextIndex];
q = paintingData.gradient[channel][b01];
u = noiseX.fraction * q[0] + (noiseY.fraction - 1) * q[1];
int b11 = paintingData.latticeSelector[nextLatticeIndex + noiseY.nextIndex];
q = paintingData.gradient[channel][b11];
v = (noiseX.fraction - 1) * q[0] + (noiseY.fraction - 1) * q[1];
float b = linearInterpolation(sx, u, v);
return linearInterpolation(sy, a, b);
};
return {
noiseForChannel(0),
noiseForChannel(1),
noiseForChannel(2),
noiseForChannel(3)
};
}
static inline ColorComponents toColorComponents(const FloatComponents& floatComponents)
{
return {
std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[0] * 255), 255)),
std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[1] * 255), 255)),
std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[2] * 255), 255)),
std::max<uint8_t>(0, std::min(static_cast<int>(floatComponents.components[3] * 255), 255))
};
}
ColorComponents FETurbulence::calculateTurbulenceValueForPoint(const PaintingData& paintingData, StitchData stitchData, const FloatPoint& point) const
{
FloatComponents turbulenceFunctionResult;
FloatPoint noiseVector(point.x() * paintingData.baseFrequencyX, point.y() * paintingData.baseFrequencyY);
float ratio = 1;
for (int octave = 0; octave < m_numOctaves; ++octave) {
if (m_type == TurbulenceType::FractalNoise)
turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector) / ratio;
else
turbulenceFunctionResult += noise2D(paintingData, stitchData, noiseVector).abs() / ratio;
noiseVector.setX(noiseVector.x() * 2);
noiseVector.setY(noiseVector.y() * 2);
ratio *= 2;
if (m_stitchTiles) {
stitchData.width *= 2;
stitchData.wrapX = 2 * stitchData.wrapX - s_perlinNoise;
stitchData.height *= 2;
stitchData.wrapY = 2 * stitchData.wrapY - s_perlinNoise;
}
}
if (m_type == TurbulenceType::FractalNoise)
turbulenceFunctionResult = turbulenceFunctionResult * 0.5f + 0.5f;
return toColorComponents(turbulenceFunctionResult);
}
void FETurbulence::fillRegion(Uint8ClampedArray& pixelArray, const PaintingData& paintingData, StitchData stitchData, int startY, int endY) const
{
ASSERT(endY > startY);
IntRect filterRegion = absolutePaintRect();
filterRegion.scale(filter().filterScale());
FloatPoint point(0, filterRegion.y() + startY);
int indexOfPixelChannel = startY * (filterRegion.width() << 2);
AffineTransform inverseTransfrom = filter().absoluteTransform().inverse().valueOr(AffineTransform());
for (int y = startY; y < endY; ++y) {
point.setY(point.y() + 1);
point.setX(filterRegion.x());
for (int x = 0; x < filterRegion.width(); ++x) {
point.setX(point.x() + 1);
FloatPoint localPoint = inverseTransfrom.mapPoint(point);
ColorComponents values = calculateTurbulenceValueForPoint(paintingData, stitchData, localPoint);
pixelArray.setRange(values.components, 4, indexOfPixelChannel);
indexOfPixelChannel += 4;
}
}
}
void FETurbulence::fillRegionWorker(FillRegionParameters* parameters)
{
parameters->filter->fillRegion(*parameters->pixelArray, *parameters->paintingData, parameters->stitchData, parameters->startY, parameters->endY);
}
void FETurbulence::platformApplySoftware()
{
Uint8ClampedArray* pixelArray = createUnmultipliedImageResult();
if (!pixelArray)
return;
IntSize resultSize(absolutePaintRect().size());
resultSize.scale(filter().filterScale());
if (resultSize.isEmpty()) {
pixelArray->zeroFill();
return;
}
IntSize tileSize = roundedIntSize(filterPrimitiveSubregion().size());
float baseFrequencyX = m_baseFrequencyX;
float baseFrequencyY = m_baseFrequencyY;
StitchData stitchData = computeStitching(tileSize, baseFrequencyX, baseFrequencyY);
PaintingData paintingData(m_seed, tileSize, baseFrequencyX, baseFrequencyY);
initPaint(paintingData);
auto area = resultSize.area();
if (area.hasOverflowed())
return;
int height = resultSize.height();
unsigned maxNumThreads = height / 8;
unsigned optimalThreadNumber = std::min<unsigned>(area.unsafeGet() / s_minimalRectDimension, maxNumThreads);
if (optimalThreadNumber > 1) {
WTF::ParallelJobs<FillRegionParameters> parallelJobs(&WebCore::FETurbulence::fillRegionWorker, optimalThreadNumber);
auto numJobs = parallelJobs.numberOfJobs();
if (numJobs > 1) {
unsigned stepY = height / numJobs;
unsigned jobsWithExtra = height % numJobs;
unsigned startY = 0;
for (unsigned i = 0; i < numJobs; ++i) {
FillRegionParameters& params = parallelJobs.parameter(i);
params.filter = this;
params.pixelArray = pixelArray;
params.paintingData = &paintingData;
params.stitchData = stitchData;
params.startY = startY;
unsigned jobHeight = (i < jobsWithExtra) ? stepY + 1 : stepY;
params.endY = params.startY + jobHeight;
startY += jobHeight;
}
parallelJobs.execute();
return;
}
}
fillRegion(*pixelArray, paintingData, stitchData, 0, height);
}
static TextStream& operator<<(TextStream& ts, TurbulenceType type)
{
switch (type) {
case TurbulenceType::Unknown:
ts << "UNKNOWN";
break;
case TurbulenceType::Turbulence:
ts << "TURBULENCE";
break;
case TurbulenceType::FractalNoise:
ts << "NOISE";
break;
}
return ts;
}
TextStream& FETurbulence::externalRepresentation(TextStream& ts, RepresentationType representation) const
{
ts << indent << "[feTurbulence";
FilterEffect::externalRepresentation(ts, representation);
ts << " type=\"" << type() << "\" "
<< "baseFrequency=\"" << baseFrequencyX() << ", " << baseFrequencyY() << "\" "
<< "seed=\"" << seed() << "\" "
<< "numOctaves=\"" << numOctaves() << "\" "
<< "stitchTiles=\"" << stitchTiles() << "\"]\n";
return ts;
}
}