Hacker News Reader

Comment by Lichtso | Hacker News Reader

In 2005 Loop & Blinn [0] found a method to decide if a sample / pixel is inside or outside a bezier curve (independently of other samples, thus possible in a fragment shader) using only a few multiplications and one subtraction per sample.

    - Integral quadratic curve: One multiplication
    - Rational quadratic curve: Two multiplications
    - Integral cubic curve: Three multiplications
    - Rational cubic curve: Four multiplications

[0] https://www.microsoft.com/en-us/research/wp-content/uploads/...

View on HN

It's referenced in slug's algorithm description paper [1], the main disadvantage with Loop-Blinn is the triangulation step that is required, and at small text sizes you lose a bit of performance. Slug only needs to render a quad for each glyph. That is not to say that any one method is better than the other though! They both have advantages and disadvantages. I think the two most advanced techniques for rendering vector graphics on the GPU are "Massively Parallel Vector Graphics" [2] and "Efficient GPU Path Rendering Using Scanline Rasterization" [3]. Though I don't know of any well known usage of them. Maybe it's because it's very hard to implement them, the sources attached to them are not trivial to understand, even if you've read the papers. They also use OpenCL/Cuda if I remember correctly.

[1] "GPU-Centered Font Rendering Directly from Glyph Outlines" http://jcgt.org/published/0006/02/02/

[2] http://w3.impa.br/~diego/projects/GanEtAl14/

[3] http://kunzhou.net/zjugaps/pathrendering/

EDIT: I've only now seen that [2] and [3] are already mentioned in the article

EDIT2: To compensate for my ignorance, I will add that one of the authors of MPVG has a course on rendering vector graphics: http://w3.impa.br/~diego/teaching/vg/

If I understand correctly the second link is basically an extension of Loop-Blinns implicit curve approach with vector textures in order to find the winding counter for each fragment in one pass.

>> Slug only needs to render a quad for each glyph.

I don't know how many glyphs you want to render (to the point that there are so many that you can't read them anymore), but a modern GPU s are heavily optimized for triangle throughput. So 2 or 20 triangles per glyph makes only a little difference. The bigger problem is usually the sample fill rate and memory bandwidth (especially if you have to write to pixels more than once).

I have been eying the scanline-intersection-sort approach (your third link) too. Sadly they have no answer to path stroking (same as everybody else) and it also requires an efficient sorting algorithm for the GPU (implementations of such are hard to come by outside of CUDA, as you mentioned).

Indeed, most techniques that target the GPU have no response to stroking, they recommend generating paths beforehand so that it looks like it's stroked.

And yes, the number of triangles doesn't really make a difference in general, but in Slug's paper they say:

"At small font sizes, these triangles can become very tiny and decrease thread group occupancy on the GPU, reducing performance"

I'm not experienced enough to say how true that is/how much of a difference it makes.

> If I understand correctly the second link is basically an extension of Loop-Blinns implicit curve approach with vector textures in order to find the winding counter for each fragment in one pass.

I've read the paper, but to be honest it's a bit over my head right now, but AFAIK MPVG is an extension to this [1], which looks like it's an extension to Loop-Blinn itself, so I think you're right.

[1] "Random-Access Rendering of General Vector Graphics" http://hhoppe.com/ravg.pdf

Reply on news.ycombinator.com