[webkit-dev] Accelerated 2D Tesselation Implementation

[Dong Seong Hwang]

I think Mr. Russell has changed tesseleration code from glu tesseleration to
LoopBlinn algorithm.
Does it mean that LoopBlinn algorithm is better than glu tesseleration? If
yes, why?
You mentioned your second trial was Kokojima's algorithm that was
detrimental to performance.
Why is the LoopBlinn algorithm better than glu tesseleration although
Kokojima's
algorithm is horrible?
I think Kokojima's algorithm is faster than LoopBlinn algorithm.
And what are "really horrible edge cases" on Kokojima's algorithm?

2010/8/28 Chris Marrin <cmarrin at apple.com>

>
> On Aug 27, 2010, at 4:21 PM, Kenneth Russell 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 .
>
> Ok, great, thanks. That makes everything much more clear.
>
> >
> > 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.
>
> Yeah, this is what I thought might be the solution. The problem with
> multisampling is that it's not hardware accelerated everywhere and where it
> is, it increases expense in both storage and rendering time. I'm not saying
> this is a showstopper, it's just an issue.
>
> So here's my concern. If you have to multisample for anti-aliasing anyway,
> why not just tesselate the shape at an appropriate sampling resolution and
> multisample the resulting triangle rendering. That would have the
> disadvantage of not being resolution independent, but it would be much
> simpler. And you can control the re-tessellation by oversampling the curve
> and only re-tesselating every few frames (maybe in the background) or only
> re-tesselating when not animating, or something like that. Would it be
> significantly faster or slower? Would the quality be better or worse? We'd
> have to run some tests. I just don't want to jump into a big expensive
> algorithm when something simpler would suffice.
>
> >
> > 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.
>
> Yeah, I can see that algorithm have some really horrible edge cases.
>
> >
> > 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.
>
> I look forward to seeing some live demos and some performance numbers.
>
> I really think the best way to proceed is to do the work in a branch. I
> really want to see the results. But I don't want to commit WebKit to all
> this code until we know this is the right way forward.
>
> -----
> ~Chris
> cmarrin at apple.com
>
>
>
>
> _______________________________________________
> webkit-dev mailing list
> webkit-dev at lists.webkit.org
> http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20110513/7e9be0f9/attachment.html>