Re: Non-uniformity of feTurbulence

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

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


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
>