- From: liyuqian via GitHub <sysbot+gh@w3.org>
- Date: Wed, 01 Mar 2017 17:08:18 +0000
- To: public-fxtf-archive@w3.org
liyuqian has just created a new issue for
https://github.com/w3c/fxtf-drafts:
== [filter-effects] Non-uniformity of feTurbulence ==
As https://www.w3.org/TR/SVG/filters.html#feTurbulenceElement
specifies, feTurbulence creates a Perlin turbulance, which should be
uniform in all directions (fGradient should be uniformly distributed
on a ball).
However, it seems that the specific implementation (source code) in
the W3C Recommendation violates such uniformity: it directly
normalizes a random vector from [-1, -1] x [1, 1] to a unit vector (so
it's uniformly distributed on a box, rather than a ball). It
generates more diagonal gradient than horizontal/vertical ones. In
Perlin's paper, it's recommended to discard vectors with length
greater than 1, and only normalizes the remaining ones to unit vectors
as the random gradient. (There are many ways of generating uniformly
random vectors on a ball; the 3rd answer in this Q/A is what's
described here; it's probably the cheapest one for our 2D cases.)
For the difference, please see the attached images. In
full_original_circle.png, there are more diagonal white lines than
vertical/horizontal lines; if we rotate it by 45 degrees, we notice a
significant increase of vertical/horizontal lines and decrease of
diagonal lines in full_original_circle_45.png. On the other hand, if
we properly do the normalization (discard vectors with length greater
than 1), the full_normalize_circle.png and
full_normalize_circle_45.png both have similar number of diagonal
lines and vertical/horizontal lines.
See also the rotated animation of those two images:
http://jsfiddle.net/Ugc5g/8957/
http://jsfiddle.net/Ugc5g/8958/
The original (non-uniform) perlin noise has a clear spoke in the
center, like an rotating "I". On the other hand, the normalized
(uniform) perlin noise doesn't have that and looks more like a uniform
spinning spiral. I think the later case is what's desired.
The following is the original W3C implementation:
```
for(k = 0; k < 4; k++)
{
for(i = 0; i < BSize; i++)
{
uLatticeSelector[i] = i;
for (j = 0; j < 2; j++)
fGradient[k][i][j] = (double)(((lSeed = random(lSeed)) %
(BSize + BSize)) - BSize) / BSize;
s = double(sqrt(fGradient[k][i][0] * fGradient[k][i][0] +
fGradient[k][i][1] * fGradient[k][i][1]));
fGradient[k][i][0] /= s;
fGradient[k][i][1] /= s;
}
}
```
And here's the properly normalized implementation that generates
gradient uniformly in all directions:
```
for(k = 0; k < 4; k++)
{
for(i = 0; i < BSize; i++)
{
uLatticeSelector[i] = i;
for (j = 0; j < 2; j++)
fGradient[k][i][j] = (double)(((lSeed = random(lSeed)) %
(BSize + BSize)) - BSize) / BSize;
s = double(sqrt(fGradient[k][i][0] * fGradient[k][i][0] +
fGradient[k][i][1] * fGradient[k][i][1]));
if (s > BSize) {
i--; // discard the current random vector; try it again.
continue;
}
fGradient[k][i][0] /= s;
fGradient[k][i][1] /= s;
}
}
```
Note that we only discard with probability (1 - PI / 4) which is about
22%. So the new generation process is at most that much slower. If we
use sin(random_angle), cos(random_angle) to compute the vector, I
think that we would be at least 2x slower because of the costly
sin/cos computations. Anyway, this slowdown only happens in the
initialization, and it does not depend on the actual image size, so I
think it's not a performance hit.
Thanks,
Yuqian
full_original_circle.png
full_original_circle_45.png
full_normalize_circle.png
full_normalize_circle_45.png
Please view or discuss this issue at
https://github.com/w3c/fxtf-drafts/issues/115 using your GitHub
account
Received on Wednesday, 1 March 2017 17:08:27 UTC