[webkit-dev] Accelerated 2D Tesselation Implementation

[Chris Marrin]

On Aug 27, 2010, at 10:59 AM, Nico Weber wrote:

> On Fri, Aug 27, 2010 at 10:51 AM, Chris Marrin <cmarrin at apple.com> wrote:
>> 
>> On Aug 27, 2010, at 10:32 AM, Nico Weber 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.
>>> 
>>> I think there's a variant of the algorithm that uses the stencil
>>> buffer polygon rendering method (
>>> http://zrusin.blogspot.com/2006/07/hardware-accelerated-polygon-rendering.html
>>> ) instead of triangulation. The paper I think I read on that only
>>> covered quadratic splines, but maybe somehow has extended that method
>>> to cubic splines by now?
>> 
>> It looks like that technique deals with polygons, so as long as you convert the shape to a piecewise linear curve it seems like it can handle any curve form, right?
> 
> What I linked is how to render polygons with the z buffer.
> http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html says:
> 
> """Recently, Kokojima et al. 2006 presented a variant on our approach
> for quadratic splines that used the stencil buffer to avoid
> triangulation. Their idea is to connect all points on the curve path
> and draw them as a triangle fan into the stencil buffer with the
> invert operator. Only pixels drawn an odd number of times will be
> nonzero, thus giving the correct image of concavities and holes. Next,
> they draw the curve segments, treating them all as convex quadratic
> elements. This will either add to or carve away a curved portion of
> the shape. A quad large enough to cover the extent of the stencil
> buffer is then drawn to the frame buffer with a stencil test. The
> result is the same as ours without triangulation or subdivision, and
> needing only one quadratic curve orientation. Furthermore, eliminating
> the triangulation steps makes high-performance rendering of dynamic
> curves possible. The disadvantage of their approach is that two passes
> over the curve data are needed. For static curves, they are trading
> performance for implementation overhead."""
> 
> Maybe someone extended Kokojima et al's work to cover cubic splines.

Ok, that makes sense. One thing that strikes me about that technique is that it touches many pixels outside the actual shape. Some edge cases could have overdraw of several hundred, which seems like it would affect performance. But I have not seen any data about this.

-----
~Chris
cmarrin at apple.com