- From: Yuqian Li <liyuqian@google.com>
- Date: Wed, 1 Mar 2017 12:08:39 -0500
- To: Amelia Bellamy-Royds <amelia.bellamy.royds@gmail.com>
- Cc: www-svg <www-svg@w3.org>
- Message-ID: <CACrk9yTUEFn9FULpQKec=1gnSHY1YLK_T6hvQHGww+zN4gxEkQ@mail.gmail.com>

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 >> > >

Received on Wednesday, 1 March 2017 18:19:19 UTC