[webkit-dev] Accelerated 2D Tesselation Implementation

[Kenneth Russell]

On Fri, Aug 27, 2010 at 4:21 PM, Kenneth Russell <kbr at google.com> wrote:
> On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin <cmarrin at apple.com> wrote:
>>
>> Hi Ken,
>> It would help me, and I think many others, if we could have a discussion of
>> how exactly your tessellation logic works and what it is intended to do. For
>> instance, is the algorithm you're using based on Loop-Blinn? I'm a bit
>> familiar with that algorithm and some of the problems it has with rendering
>> this type of geometry. For instance, there are typically anti-aliasing
>> artifacts at the points where the interior triangles touch the edges. These
>> are described in section 5.1 of the paper and the authors added additional
>> (and not well described) logic to solve the problem.
>> If you could describe your algorithm a bit and show some expected results
>> with typical cases, that would be really helpful.
>> For those not familiar with Loop-Blinn, here is a link to their original
>> paper, presented at Siggraph 2005:
>> Resolution Independent Curve Rendering using Programmable Graphics ...
>> It's a great algorithm for rendering resolution independent 2D objects using
>> the GPU. It has potential to render both 2D shapes (as used in Canvas and
>> SVG) and text glyphs. It's advantage is that once you generate the triangles
>> for the shape, you can render the shape at any resolution. It's disadvantage
>> is that the triangle generation is quite expensive, so mutating shapes can
>> potentially be slower than a simpler resolution dependent tessellation.
>
> The code that is out for review (see
> https://bugs.webkit.org/show_bug.cgi?id=44729 ) is, as described in
> the bug report, precisely an implementation of Loop and Blinn's
> algorithm. It comes from their simplified reformulation in Chapter 25
> of GPU Gems 3, which can be found online at
> http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html .
>
> Their GPU Gems chapter discusses the antialiasing artifacts you
> mention, where interior triangles not handled by their shader touch
> the surface of the shape. They point out that enabling multisampling
> antialiasing solves this problem; the contents of these pixels are
> antialiased via MSAA, and the pixels covered by their shader are
> handled by their antialiasing formula. My own experience has been that
> this works very well; there are no distinguishable bumps or aliasing
> artifacts with both MSAA enabled and using the antialiasing version of
> their shader.
>
> This is actually the second implementation of this algorithm I have
> done. In the first, we did much more experimentation, including trying
> Kokojima et al's stencil buffer algorithm rather than tessellating the
> interior of the shape. We found that the increased fill rate
> requirements of Kokojima's technique was detrimental to performance,
> and that it was better to tessellate to reduce overdraw.
>
> In my first implementation of this algorithm, we found that detecting
> and resolving overlaps of cubic curve control points (section 25.4 in
> the GPU Gems 3 chapter) was by far the most expensive part of the
> algorithm. It is also absolutely necessary in order to handle
> arbitrary inputs. After some investigation I realized that the
> plane-sweep algorithm mapped well to the problem of detecting overlaps
> of control point triangles, and incorporating a variant of this
> algorithm reduced the curve processing time dramatically. This
> optimization is included in the code out for review.
>
> Currently we have hooked up this code to a 2D Canvas implementation,
> and are performing no caching; we tessellate each path as it comes in.
> Performance of the classic SVG butterfly drawn using
> CanvasRenderingContext2D is similar to that of the software renderer,
> although I do not have concrete performance numbers yet. For retained
> mode APIs like SVG where the processing results can be cached easily,
> I expect significant performance improvements based on previous
> experience.
>
> Here is a screenshot from our current implementation:
>
> http://www.rawbw.com/~kbrussel/tmp/butterfly.jpg
>
> This does not have multisampling turned on yet. For comparison, here
> is a screenshot from the version in O3D, which does:
>
> http://www.rawbw.com/~kbrussel/tmp/butterfly-o3d.jpg
>
> Does this help answer your questions?

Since I decided not to attach these files, here are the non-quantized versions:

http://www.rawbw.com/~kbrussel/tmp/butterfly.png
http://www.rawbw.com/~kbrussel/tmp/butterfly-o3d.png

-Ken