Seed 514 in feTurbulence causes squares

[Ryan Richards]

Certain seed numbers cause squares to appear in the feTurbulence filter.

These are the first few:

514,1977,2337,4777,8032,9615,14783,14862,14921,18607,19537,19852,19955,22456,23056,26678,27351,29383,29560,29929

514 is the only one that will occur in the filter editor, the seed slider capped at 1000. Editing the source, or opening a file with the other seeds will show the bug.

Windows Vista, Inkscape 0.48.5 r10040

[jazzynico (jazzynico)]

Reproduced on Windows XP, Inkscape 0.48.5 and trunk revision 13828.

[jazzynico (jazzynico)]

Not sure it's Inkscape's fault. Opening the SVG file in Firefox and Chrome show the same squares.

[jazzynico (jazzynico)]

Another example with octave set to 10, to show more squares with different sizes.

[jazzynico (jazzynico)]

Related report in Mozilla's bug tracker:
https://bugzilla.mozilla.org/show_bug.cgi?id=862225

Related discussion in the SVG devs list:
https://<email address hidden>/msg16062.html

[jazzynico (jazzynico)]

Also reproduced with Batik 1.7 (Squiggle), but NOT with Opera.

[Ryan Richards (ryan-richards)]

The voids are fully transparent black. Its not just the alpha channel.

[Ryan Richards (ryan-richards)]

The bug is in the svg spec reference code. Its the interger division in the random function.

[Ryan Richards (ryan-richards)]

I've found the problem. With the affected seed numbers both values in fGradient table are 0 for some of pairs.

Something to the effect of

if (fGradient[k][i][0] == 0 && fGradient[k][i][1] == 0)
 {
  fGradient[k][i][0] = 1;
  fGradient[k][i][1] = 1;
 }

needs to be added after line 220 of nr-filter-turbulence.cpp

[Alvin Penner (apenner)]

@Ryan, I am having difficulty locating the variable fGradient in the Inkscape repository at:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/files/head:/src/display/nr-filter-turbulence.cpp

could you indicate where the file nr-filter-turbulence.cpp is located?

[Ryan Richards (ryan-richards)]

its fGradient in the spec, in the file you linked, the results of lines 67 and 68 are what need to be check for double zeros

[Ryan Richards (ryan-richards)]

Or a ternary on lines 72 and 73. That could do it too.

[jazzynico (jazzynico)]

Patch for the trunk attached.
Tested successfully on Crunchbang Waldorf, Inkscape trunk revision 13831.

Thanks for your investigations, Ryan!

[su_v (suv-lp)]

On 2015-01-02 03:18 (+0100), Ryan Richards wrote:
> The bug is in the svg spec reference code. Its the interger division in
> the random function.

Just curious: if the error is in the SVG 1.1 spec, shouldn't it get changed on that level first, before individual SVG renderers modify the filter primitive on their own (perhaps each rewriting the spec slightly differently)?

Is the error still present in the draft version of the SVG 2.0 spec (or rather in the now separated Filter Effects 1.0 spec)?
<http://www.w3.org/TR/SVG2/filters.html> refers to <http://www.w3.org/TR/filter-effects/>

SVG 1.1:
<http://www.w3.org/TR/SVG11/filters.html#feTurbulenceElement>

Filter Effects 1.0 (Draft):
<http://www.w3.org/TR/2012/WD-filter-effects-20121025/#feTurbulenceElement>

[Alvin Penner (apenner)]

>> Is the error still present in the draft version of the SVG 2.0 spec ?

as far as I can tell, the same error is present in both of the above references. The problem is going to show up in the statement
fGradient[k][i][0] /= s;
This statement can potentially lead to a zero-over-zero division, which is indeterminate, and which could easily be interpreted differently by different renderers. Inkscape for example, generates nan in this case. The above patch avoids this issue.

It looks like the original intent was to generate an array of unit vectors with random orientation angles. If this was the case, then it might have been better to first generate a random array of angles from 0 to 360 degrees, and then produce the unit vector from them using sin(theta) and cos(theta). However for reasons of compatibility, perhaps it is too late to rethink this code, since the above patch appears to apply absolutely seamlessly as far as I could tell, by inspecting a few test cases with and without the patch.

[Ryan Richards (ryan-richards)]

I don't know C++, or the internals of Inkscape. I'm working with a JS port of the code in the SVG spec trying to fix this bug that's everywhere. I put it on GitHub ( https://github.com/Ani-Mayhem-Com/feTurbulence )
Putting

fGradient[k][i][0] = (fGradient[k][i][0] / s ? fGradient[k][i][0] / s : 0);
fGradient[k][i][1] = (fGradient[k][i][1] / s ? fGradient[k][i][1] / s : 0);

after the failed zero devision instead of feeding a pair of 1's before. This puts the pair of zeros into the array. If this actually works, I think that should be the solution as it restores the results of the random function.

[Alvin Penner (apenner)]

just my 2 cents worth, but I think the original patch in comment 10 was better than comment 18. The point is that 0/0 is indeterminate and should never be allowed to happen, and it should not be used as a switch criterion.

[Ryan Richards (ryan-richards)]

Both remove the squares. However, they do produce different result. In the case of seed 514 the problem ocurrs in the alpha channel. I was only testing in the alpha channel because thats what I was using. I just started working on a script to find all the 'bad seeds'. From 1 to 1000 I got 346 and 514. I was hoping for 514 because I knew it was bad. But 346, that was a new one. Plugged it into Inkscape and I get magenta squares. I suspect I'm going to find more bad seeds.

[Ryan Richards (ryan-richards)]

There are a great many more that I had initially found. Those under 10,000 went from 6 on the alpha channel to thirty-one accross all four channels.

346, 514, 1155, 1519, 1690, 1977, 2327, 2337, 2399, 2860, 2999, 3099, 4777, 4952, 5673, 6265, 7185, 7259, 7371, 7383, 7717, 7847, 8032, 8350, 8676, 8963, 8997, 9080, 9403, 9615, 9685

[Ryan Richards (ryan-richards)]

I'm running a program right now (60 hours left to go) to find them all. It's kicking out a lot of bad seeds, looking to end at about 10,000,00 or so. The first one I tested, 385182227, its a doozy. My canvas render, firefox, inkscape, Opera Next, and Opera all show different results. Batik matches Inkscape, in showing yellow squares. Anyone know anyone in the working group?

[Tavmjong Bah (tavmjong-free)]

Bug reported to <email address hidden> (the mailing list for the SVG/CSS joint task force responsible for CSS Filters).

See: http://lists.w3.org/Archives/Public/public-fx/2015JanMar/0000.html

Tav (Inkscape rep to SVG working group)

[Jaspervdg (jaspervdg)]

Instead of setting the gradient to a constant value, I would recommend simply using rejection sampling (which is more or less the standard solution to this type of problem). This would NOT affect seeds without this issue, while avoiding introducing bias (which setting the gradient to a constant value might do). This would involve changing out the existing for-loop filling the gradient for something like this piece of code:

      do {
        for (j = 0; j < 2; j++)
          fGradient[k][i][j] = (double)(((lSeed = random(lSeed)) % (BSize + BSize)) - BSize) / BSize;
      } while(fGradient[k][i][0] == 0 && fGradient[k][i][1] == 0);

(In case any one is wondering, this is highly unlikely to be slow, given that the probability of getting two zeros is about 1 in 65536.)

[Ryan Richards (ryan-richards)]

Thats better than just setting it to 1, but is it better than getting the 0, that should be in the gradient, past the division error?

And, getting two zeros is 1 in 256.

[Alvin Penner (apenner)]

>> but is it better than getting the 0, that should be in the gradient, past the division error?

um, we should not be thinking of this as a division error. The expression 1/0 can be correctly called a division error. The expression 0/0 is more accurately called indeterminate, meaning we don't know what it is, meaning different renderers will treat it differently.
The whole purpose of this code is to produce a unit vector of length 1. You cannot do that if both x and y are 0.

[Ryan Richards (ryan-richards)]

Yes, indeterminate. I was refering to the problem with with code being the error. After all the math is done, the final values put into the gradient array are from -1 to 1. There no need to prevent a pair of zeros at that point.

[Ryan Richards (ryan-richards)]

This looks nicer
fGradient[k][i][0] = (fGradient[k][i][0] == 0 ? 0: fGradient[k][i][0] / s);
fGradient[k][i][1] = (fGradient[k][i][1] == 0 ? 0: fGradient[k][i][1] / s);

[Jaspervdg (jaspervdg)]

As Alvin Penner mentioned, the purpose of the code is explicitly to produce a vector of length 1, setting the gradient to zero does not accomplish this goal (the length is then zero). Also, the vectors should be uniformly distributed around the sphere, so setting the gradient to some arbitrary fixed value like (1,0) or (0,1) is also not really a suitable solution. The "default" way of solving this problem is called rejection sampling and basically consists of just trying until you get it "right", this works because it does not change the relative frequencies of values other than those that are thrown away. (To some extent, as Perlin recognized in later work, it would be even easier/better to just use a fixed SET of well-distributed vectors, but that is not really an option here, as it would break backwards compatibility.)

Anyway, given that the original behaviour was without a doubt unintentional, I went ahead and committed a (small) patch using rejection sampling. I tried it on the example given above, and the problem indeed disappeared. I also verified that normal feTurbulence rendering was not broken, by trying the example given in the spec (which still renders exactly as it should).

[su_v (suv-lp)]

Fix committed to trunk in r13844:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/13844

[Ryan Richards (ryan-richards)]

Rejection sampling changes the entire output, rather than just filling in the blanks.

[Jaspervdg (jaspervdg)]

True, but ONLY for those seeds that had problems. Given that the blanks were a pretty severe artifact, I would not consider this a huge problem. Also, although ideally we want to be as backwards compatible as possible, the overall appearance is determined more by the other parameters than by the seed. If you just vary the seed you basically get different instantiations of the same kind of noise. Still, it is fairly easy to modify the code so that this does not happen (basically the idea would be to repeatedly loop over the vectors to fill in any remaining zeros, instead of having the do-loop per vector, ideally this should be done AFTER "shuffling lattice selectors", to avoid influencing those as well).

[Tavmjong Bah (tavmjong-free)]

The CSS Filter Effects specification (Editor's Draft[1]) has been amended to include Jasper's fix in comment #24. (Filter effects have been moved from the SVG spec to a separate CSS spec so that HTML can use filter effects too. SVG 2 references the new CSS spec.)

[1] http://dev.w3.org/fxtf/filters/#feTurbulenceElement

[ScislaC (scislac)]

Backported to 0.91.x in r13702.