Repository navigation
[Impeller] Why did Impeller opt for "triangulation then draw" over "stencil then cover"? #123671
Description
Recently, while reading the code of Skia's new GPU backend "Graphite", I noticed that they did not use a technology like "libtess2" to triangulate paths, but instead used "stencil then cover" or its variants. Details can be found in their code (https://github.com/google/skia/blob/5d8b4bc3c7133e38dcae7b76cd708ed4649c13d1/src/gpu/graphite/Device.cpp#L1103-L1121) and in their implementation of the TessellateWedgesRenderStep (https://github.com/google/skia/blob/main/src/gpu/graphite/render/TessellateWedgesRenderStep.cpp).
In my opinion, "stencil then cover" has many benefits, such as not requiring triangulation techniques like libtess2, thus saving CPU time. Additionally, it can use a single render pass for convex paths without triangulation, and it's easier to design methods for parallel drawing of curves using GPUs without pre-computing vertices through CPU or compute shaders.
Of course, "stencil then cover" also has drawbacks, such as the need for 2-pass or 3-pass when drawing a path. However, since there is no switching of the RenderTarget during the process, it doesn't seem to have a significant impact on performance.
I'm curious as to why Impeller didn't choose the technical solution of "stencil then cover"? @chinmaygarde @bdero, would you mind enlightening me? Thank you!
Activity
jonahwilliams commentedon May 9, 2023
The initial reason for using libtess2 is that it is easy to start with an engine that can render everything that Flutter supports without needing to add special cases. I don't think we're necessarily married to it as an implementation strategy.
Certainly, libtess2 can be very expensive in terms of CPU utilization. I think we have a good path forward for strokes and convex fills, we're in the process of switching those over to simpler routines and leaning more on the GPU to determine geometry.
For concave / complex polygons, in my experience this occur rarely but are very expensive to tessellate. We're certainly open to solutions, provided these solutions are fairly general purpose and don't require a combinatorial explosion of shaders
dnfield commentedon May 9, 2023
For the linked code, it seems like it requires some analytic AA solution. If that's not the case we should explore it more. If it is the case we'd have to figure out some efficient and usable way of doing the AA.
bdero commentedon May 10, 2023
In terms of concrete implementation, my understanding is that stencil-then-cover means using a derivative of this trick. Impeller defers antialiasing to pass resolve time, and so AA shouldn't be a concern.
As Jonah mentioned, for all convex fills, we're adding specialized paths that don't involve running a generic tessellation algorithm.
Concave paths is where "stencil then cover" shines. In the ideal case, we get to trade off running a poorly scaling tessellation algorithm on the CPU for an extra draw call and a bit of stencil overdraw. Clearly a good deal!
What's not clear to me is how we can use a technique like this to efficiently implement the
nonZerowinding mode, which is Flutter's default and thus the common case:evenOdd(not Flutter's default) is trivial to implement with this trick. It would even work for self-intersecting and multi-contour paths. Performing the stencil inversion is key to erasing all of the geometry that lies outside the path. But for the other winding modes (includingnonZero, which is the only other winding mode supported by Flutter's API), even if we dedicated multiple bits in the stencil for counting the overlap, a workable solution to cancel out parts of the geometry fan that lie outside the path isn't obvious to me.One potential way to eke out gains for
nonZeroconcave paths would be to "stencil then cover" only for cases where we can determine that anonZeropath would draw the same if it wasevenOdd, and continue falling back to libtess2 for rarer cases. For example, if the path has one contour and doesn't self-intersect (an expensive check), we can be sure it'll behave the same asevenOdd-- but then we're back in the business of computing path properties that scale poorly, diminishing some of the benefit.dnfield commentedon May 10, 2023
The problem is that if the geometry supplied is a quad, MSAA will only see the edges of the quad - the stencil and cover techniques would be in a fragment stage
bdero commentedon May 10, 2023
The particular variation I'm describing doesn't have this problem.
We first "stencil" by carving out the path on the stencil buffer (with no color attachment) in a way that requires no tessellation, and then "cover" by drawing a quad over the path coverage with a color attachment, culling fragments that lie outside the path just like a regular Impeller clip does. Both the stencil and color are multisample in tile memory.
dnfield commentedon May 10, 2023
I think we could do that in compute, and I think there's probably a way to adapt this similarly for nonZero but need to mull this over.
ColdPaleLight commentedon May 11, 2023
1. Prepare
Split the polygon into triangles, just like mentioned in the article
2. Stencil
Before each stencil operation, ensure that the value on the stencil buffer is 0.
We can observe that some of these triangles are counterclockwise while others are clockwise. Suppose we set the counterclockwise to be the front and the clockwise to be the back, then we can set the front stencil pass op to
IncreaseWrap, and the back stencil pass op toDecreaseWrap. Then draw all the triangles. In the end, all values not equal to 0 in the stencil buffer are the area of the entire polygon3. Cover
Draw a rectangle whose size is the size of the RenderTarget, when drawing, we need to set the compare op of the stencil test to NotEqual, and the stencil ref value to 0, so that the polygon can be drawn.
What is the biggest difficulty for Impeller to implement this method?
One reason I think Impeller doesn't work this way right now is Impeller's Clip implementation. Now Impeller's Clip implementation requires a stencil buffer, and all bits of the stencil buffer need to be used. The stencil then cover will also use all the bits of the stencil buffer, so in the current implementation of Impeller, it is difficult to introduce the algorithm of stencil then cover
Does Skia use stencil then cover, how does it solve the conflict with clip implementation?
Skia's gpu acceleration has two implementations, ganesh and graphite.
In Ganesh, if the stenci buffer is enabled and the stencil buffer participates in the clip, only the highest bit in the stencil buffer value will be used to represent the clip, while the rest of the lower bits can be used for the stencil then cover. For the specific algorithm, please see section 3.4 of this article: https://developer.download.nvidia.cn/devzone/devcenter/gamegraphics/files/opengl/gpupathrender.pdf
In Graphite, clip is implemented using depth test and depth buffer, so there is no conflict anymore.
bdero commentedon May 11, 2023
Oh derp, this was the insight I was missing while visualizing the triangle fan in my mind. Yes, it's easy to implement
nonZerowith this method as well, assuming we can dedicate enough stencil bits to it. Impeller doesn't support separate stencil operations for backfaces and frontfaces at the moment, but we can and should add this, as all graphics backends we'll be targeting indeed support this.I more or less agree with this. A 255 clip stack limit is reasonable, but 8 bits isn't going to be enough if we get into the business of segmenting the stencil buffer to play multiple counting roles. And we can't reach for larger 16 bit stencils.
Yes, this makes sense. It's quite likely we'll need a depth buffer anyhow for the purpose of draw order optimization -- even if we didn't reverse opaque draw calls, some GPUs don't perform HSR if depth testing is disabled. Clips are hard barriers for reversing the draw order, and so cramming both jobs into the depth buffer would be possible without loss of effectiveness.
I'll append a depth-based design to #114402 that includes clipping in the depth buffer (right now it only has a stencil-based proposal, but again, segmenting the stencil buffer isn't really practical for this).
dnfield commentedon May 11, 2023
What if we just used a separate render pass for this?
14 remaining items
jonahwilliams commentedon Nov 1, 2023
We have landed a change that removes stencil storage and replays clips as I described earlier in this issue: #137448
This technically unblocks the foundational work to begin using StC
[Impeller] Switch from transient stencil-only to depth+stencil buffer. (
Reverts "[Impeller] Switch from transient stencil-only to depth+stenc…
[Impeller] Reland: Switch from transient stencil-only to depth+stenci…
[Impeller] Enable depth buffer clipping & Stencil-then-Cover path ren…
[Impeller] Enable depth buffer clipping & Stencil-then-Cover path ren…
[Impeller] Enable depth buffer clipping & Stencil-then-Cover path ren…
Reverts "[Impeller] Enable depth buffer clipping & Stencil-then-Cover…
[Impeller] Enable depth buffer clipping & Stencil-then-Cover path ren…
[Impeller] Enable depth buffer clipping & Stencil-then-Cover path ren…
bdero commentedon Mar 12, 2024
StC was enabled with flutter-team-archive/engine#51219
github-actions commentedon Mar 26, 2024
This thread has been automatically locked since there has not been any recent activity after it was closed. If you are still experiencing a similar issue, please open a new bug, including the output of
flutter doctor -vand a minimal reproduction of the issue.