[webkit-dev] Accelerated 2D Tesselation Implementation

[Kenneth Russell]

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?

-Ken