Bug 233214 – [GPU Process] [Filters 6/23] Build a postfix expression for applying the FilterEffects of the SVGFilter

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Said Abou-Hallawa]

The goal is to have all inputs of each FilterEffect be applied before applying it. This will eliminate the need to do recursive applying in FilterEffect::apply(). And it will also eliminate the need to store the rectangle of the result of FilterEffect. Once the absolutePaintRect is calculated, the result image can be created.

[Said Abou-Hallawa]

Created attachment 444437 [details]
Patch

[Cameron McCormack (:heycam)]

Comment on attachment 444437 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=444437&action=review

> Source/WebCore/ChangeLog:15
> +        caller knows that applying the filter function was not successful.

"knows whether applying the filter function was successful"

> Source/WebCore/platform/graphics/filters/FEConvolveMatrix.cpp:400
>          // Rare situation, not optimizied for speed

(pre-existing) "optimized"

> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:148
>      if (hasResult())
> -        return;
> +        return true;

Is it the case that we should never call FilterEffect::apply() twice on the same object? Wondering if we should `ASSERT(!hasResult())` here before returning true if we do have a result already.

> Source/WebCore/svg/graphics/filters/SVGFilter.cpp:108
> +    lastEffect()->clearResultsRecursive();

Will you change this in a later patch to be non-recursive?

> Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:186
> +    if (stack.contains(effect))

SVG filters are unlikely to have very deep filter effect trees, but this will cause buildExpression to take O(n^2) time (where n is the depth of the expression tree). Can we either keep a side HashSet or (better) a bool on the FilterEffect that gets set and cleared as the effect is pushed to and popped from the stack?

> Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:189
> +    expression.insert(0, effect);

This will also cause buildExpression to take O(n^2) time (where n is the total number of effects), if we keep inserting items at the front. Instead you could append them to the end, and as a final step, reverse the vector.

[Cameron McCormack (:heycam)]

Comment on attachment 444437 [details]
Patch

r- to see another version with comments addressed.

[Said Abou-Hallawa]

Comment on attachment 444437 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=444437&action=review

>> Source/WebCore/ChangeLog:15
>> +        caller knows that applying the filter function was not successful.
> 
> "knows whether applying the filter function was successful"

Fixed.

>> Source/WebCore/platform/graphics/filters/FEConvolveMatrix.cpp:400
>>          // Rare situation, not optimizied for speed
> 
> (pre-existing) "optimized"

Fixed.

>> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:148
>> +        return true;
> 
> Is it the case that we should never call FilterEffect::apply() twice on the same object? Wondering if we should `ASSERT(!hasResult())` here before returning true if we do have a result already.

Consider the following filter:

<svg width="7.5cm" height="5cm" viewBox="0 0 200 120">
    <defs>
        <filter id="MyFilter" filterUnits="userSpaceOnUse" x="0" y="0" width="200" height="120">
            <feGaussianBlur in="SourceAlpha" stdDeviation="4" result="blur"/>
            <feOffset in="blur" dx="4" dy="4" result="offsetBlur"/>
            <feSpecularLighting in="blur" surfaceScale="5" specularConstant=".75"  specularExponent="20" lighting-color="#bbbbbb" result="specOut">
                <fePointLight x="-5000" y="-10000" z="20000"/>
            </feSpecularLighting>
            <feComposite in="specOut" in2="SourceAlpha" operator="in" result="specOut"/>
            <feComposite in="SourceGraphic" in2="specOut" operator="arithmetic"  k1="0" k2="1" k3="1" k4="0" result="litPaint"/>
            <feMerge>
                <feMergeNode in="offsetBlur"/>
                <feMergeNode in="litPaint"/>
            </feMerge>
        </filter>
    </defs>
</svg>

This should generate the following tree of FilterEffects:
(1) FEMerge

    (2) FEOffset (offsetBlur)

        (3) FEGaussianBlur (blur)

            (4) SourceAlpha

                (5) SoureGraphic

    (6) FEComposite (litPaint)

        (7) SoureGraphic

        (8) FEComposite (specOut 2)

            (9) FESpecularLighting (specOut 1)

                (10) FEGaussianBlur (blur)

                    (11) SourceAlpha

                        (12) SoureGraphic

            (13) SourceAlpha

                (14) SoureGraphic

The order of applying this tree with and without this patch is the following:

(5) SoureGraphic
(4) SourceAlpha
(3) FEGaussianBlur (blur)
(2) FEOffset (offsetBlur)
(7) SoureGraphic
(12) SoureGraphic
(11) SourceAlpha
(10) FEGaussianBlur (blur)
(9) FESpecularLighting (specOut 1)
(14) SoureGraphic
(13) SourceAlpha
(8) FEComposite (specOut 2)
(6) FEComposite (litPaint)
(1) FEMerge

As you can see some FilterEffects are referenced more than once in this order because there are referenced multiple times in the filter. So once a FilterEffect is applied we should return true and this is a legitimate case.

This order of applying the FilterEffects is what SVGFilterBuilder::buildExpression() will return.

>> Source/WebCore/svg/graphics/filters/SVGFilter.cpp:108
>> +    lastEffect()->clearResultsRecursive();
> 
> Will you change this in a later patch to be non-recursive?

Fixed.

>> Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:186
>> +    if (stack.contains(effect))
> 
> SVG filters are unlikely to have very deep filter effect trees, but this will cause buildExpression to take O(n^2) time (where n is the depth of the expression tree). Can we either keep a side HashSet or (better) a bool on the FilterEffect that gets set and cleared as the effect is pushed to and popped from the stack?

buildEffectExpression() just flattens the recursion we used to do in FilterEffect::apply(). We also drop applying the SVG filters if the number nodes in the tree is more than 100 nodes, see SVGFilterBuilder::buildFilterEffects. So the size of expression and stack should not be more than 100 at any point.

>> Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:189
>> +    expression.insert(0, effect);
> 
> This will also cause buildExpression to take O(n^2) time (where n is the total number of effects), if we keep inserting items at the front. Instead you could append them to the end, and as a final step, reverse the vector.

Done.

[Said Abou-Hallawa]

Created attachment 444459 [details]
Patch

[Cameron McCormack (:heycam)]

(In reply to Said Abou-Hallawa from comment #4)
> As you can see some FilterEffects are referenced more than once in this
> order because there are referenced multiple times in the filter. So once a
> FilterEffect is applied we should return true and this is a legitimate case.

I see now.

> > SVG filters are unlikely to have very deep filter effect trees, but this will cause buildExpression to take O(n^2) time (where n is the depth of the expression tree). Can we either keep a side HashSet or (better) a bool on the FilterEffect that gets set and cleared as the effect is pushed to and popped from the stack?
> 
> buildEffectExpression() just flattens the recursion we used to do in
> FilterEffect::apply(). We also drop applying the SVG filters if the number
> nodes in the tree is more than 100 nodes, see
> SVGFilterBuilder::buildFilterEffects. So the size of expression and stack
> should not be more than 100 at any point.

OK so worst case we perform (100 * 99) / 2 = 4950 comparisons while searching through the stack.  Might be worth a comment here to point out that in practice this won't be a problem?

[Cameron McCormack (:heycam)]

(In reply to Cameron McCormack (:heycam) from comment #6)
> OK so worst case we perform (100 * 99) / 2 = 4950 comparisons while
> searching through the stack.  Might be worth a comment here to point out
> that in practice this won't be a problem?

(I meant: (100 * 101) / 2 = 5050.)

[Radar WebKit Bug Importer]

<rdar://problem/85490380>

[EWS]

Committed r285916 (244325@main): <https://commits.webkit.org/244325@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 444459 [details].