Re: Non-uniformity of feTurbulence

Hi Amelia,

Please see my replies below.

On Tue, Feb 28, 2017 at 5:41 PM, Amelia Bellamy-Royds <
amelia.bellamy.royds@gmail.com> wrote:

> Hi Yuqian,
>
> Technical issues with the Filters specification are now managed on GitHub,
> in the shared repo with CSS. Are you able to post this there?
> https://github.com/w3c/fxtf-drafts/issues
>
Sure , done.

>
> Some questions to address, if you hope to convince implementations to
> change:
>
>    - Can you estimate how much of a performance impact this change would
>    have? (That is, what proportion of vectors would need to be discarded &
>    re-sampled?)
>
> 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.

>
>    -
>    - Can you give practical graphical examples of where it would create a
>    noticeable impact on the final result?
>
> 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.

>
>    -
>
>
> By the way, since you've clearly dissected the algorithm more closely than
> I have, I'd be glad if you could take a look at this issue I posted last
> week: https://github.com/w3c/fxtf-drafts/issues/112
>
> Best,
> Amelia Bellamy-Royds
>
> On 21 February 2017 at 11:51, Yuqian Li <liyuqian@google.com> wrote:
>
>> 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
>> <http://math.stackexchange.com/questions/44689/how-to-find-a-random-axis-or-unit-vector-in-3d> 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.
>>
>> 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;
>>     }
>>   }
>>
>> Thanks,
>> Yuqian
>>
>
>