[webkit-dev] Accelerated 2D Tesselation Implementation

[Nico Weber]

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.

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