6 ms·

There are two ways to get winding numbers and then decide on filled or empty by some rule like non-zero or even-odd: a) The winding number of a point is the nu

by Lichtso 6mo ago

There are two ways to get winding numbers and then decide on filled or empty by some rule like non-zero or even-odd: a) The winding number of a point is the number of intersections of a scanline and a closed path. b) The winding number around a point is the total angle subtended by the path at that point. Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues. The approach by loop & blinn uses b) and is thus simpler and more robust. Likewise the patent on that one expired too: https://news.ycombinator.com/item?id=47416736#47420450 https://news.ycombinator.com/item?id=47416736#47420450

jeremiahkellick 6mo ago
Loop and blinn does not compute a winding number using the b) method. It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle, which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases. With Slug, you can use only 1 quad per glyph if you want. Also just to clarify regarding this statement: > Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues Slug does not have numerical precision issues. It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues.
- Lichtso 6mo ago
  > It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle The original paper did assume no overlap yes. But that is not how anybody would implement it. For a long time one would use the stencil buffer with different operations depending on the front-face / back-face (this is where the paths rotation around the sample comes in and what makes this an angle based approach). > which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases. Again, not how anybody would implement this. You can just stream the quadratic bezier curves unprocessed into the vertex shader, literally the simplest thing conceivable. > With Slug, you can use only 1 quad per glyph if you want. Nowadays one would probably implement loop & blinn in a tiled compute shader too (instead of using stencil buffers) to reduce memory bandwidth and over draw. That way you also get one quad per glaph, but without any of the geometry special casing that Slug does. > It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues. Correct, might have worded that badly. Still remains a trade off in a) which b) does not have.
  - jeremiahkellick 6mo ago
    [1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler than the loop and blinn paper. However, if you want to do distance based anti-aliasing rather than supersampling, things are going to get complicated again as you have to expand the shape outline to capture more pixel centers. I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle. I feel like any attempt to do that will approach the complexity of Slug, but maybe it's my own shortcoming that I don't see it. I would love to read more detailed information on that if you have it. [1] https://medium.com/@evanwallace/easy-scalable-text-rendering-on-the-gpu-c3f4d782c5ac https://medium.com/@evanwallace/easy-scalable-text-rendering... [2] https://web.archive.org/web/20180905215805/http://www.glprogramming.com/red/chapter14.html#name13 https://web.archive.org/web/20180905215805/http://www.glprog...
    - Lichtso 6mo ago
      > [1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler Yes, they describe one variation of the angle based method to winding numbers by spanning a triangle fan from an arbitrarily chosen pivot point / vertex. > if you want to do distance based anti-aliasing rather than supersampling Particularly when it comes to rendering vector graphics I think of analytic anti-aliasing methods as somewhat cursed and prefer multisampling [0], at least for magnification. For minification mip-mapping remains the go to solution. However, if you only render 2D text on a 2D plane, which is typically overlap free, then these correctness issues don't matter. > I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle All modern vector renderers I know of avoid triangle rasterization entirely. Like I said, they typically do tiles (screen space partitioned into quads) in a compute shader instead of using the fixed functionality with a fragment / pixel shader. The reason is that nowadays compute is cheap and memory bandwidth is the bottle neck. Thus, it makes sense to load a bunch of overlapping geometry from global memory into workgroup shared memory, render all of it down to pixels in workgroup shared memory, and then only write these pixels back to the framebuffer in global memory. > I feel like any attempt to do that will approach the complexity of Slug A highly optimized implementation might very well, yes. Yet, handling the many cases of intersections of the path and the scanline won't be contributing to the complexity, which is what started this discussion. > I would love to read more detailed information on that if you have it. I implemented the outdated stencil buffer + triangle fan + implicit curves approach [1] if you want to take a look under the hood. The library is quite complex because it also handles the notoriously hard rational cubic bezier curves analytically, which Slug does not even attempt and just approximates. But the integral quadratic bezier curves are very simple and that is what is comparable to the scope Slug covers. It is just a few lines of code for the vertex shader [2], the fragment shader [3] and the vertex buffer setup [4]. Edit: You can even spin loop & blinn into a scanline method / hybrid: They give you the side of the curve your pixel is on [5], which is typically also the thing scanline methods are interested in. They compute the exact intersection location relative to the pixel, only to throw away most of the information and only keep the sign (side the pixel is on). So, that might be the easiest fragment shader vector renderer possible. Put it together in a shader toy [6] a while back. [0]: https://news.ycombinator.com/item?id=46473247#46530503 https://news.ycombinator.com/item?id=46473247#46530503 [1]: https://github.com/Lichtso/contrast_renderer https://github.com/Lichtso/contrast_renderer [2]: https://github.com/Lichtso/contrast_renderer/blob/main/src/shaders.wgsl#L72 https://github.com/Lichtso/contrast_renderer/blob/main/src/s... [3]: https://github.com/Lichtso/contrast_renderer/blob/main/src/shaders.wgsl#L241 https://github.com/Lichtso/contrast_renderer/blob/main/src/s... [4]: https://github.com/Lichtso/contrast_renderer/blob/main/src/fill.rs#L285-L296 https://github.com/Lichtso/contrast_renderer/blob/main/src/f... [5]: https://news.ycombinator.com/item?id=45626037#45627274 https://news.ycombinator.com/item?id=45626037#45627274 [6]: https://www.shadertoy.com/view/fsXcDj https://www.shadertoy.com/view/fsXcDj
elengyel 6mo ago
You don't seem to have grokked the main feature that makes Slug interesting. The algorithm handles every single possible case uniformly through the use of a very fast classification and root eligibility determination technique. On some GPUs (including all NV from the last 10+ years), handling the full set of cases shown on the poster reduces to a single instruction (LOP3). The algorithm also eliminates all numerical precision issues -- provably -- making it the most robust of all time. There are no valid inputs for which the algorithm fails, so to say Loop-Blinn is somehow more robust is incorrect.

by Lichtso 6mo ago

jeremiahkellick 6mo ago

Loop and blinn does not compute a winding number using the b) method. It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle, which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases. With Slug, you can use only 1 quad per glyph if you want. Also just to clarify regarding this statement: > Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues Slug does not have numerical precision issues. It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues.

Lichtso 6mo ago
> It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle The original paper did assume no overlap yes. But that is not how anybody would implement it. For a long time one would use the stencil buffer with different operations depending on the front-face / back-face (this is where the paths rotation around the sample comes in and what makes this an angle based approach). > which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases. Again, not how anybody would implement this. You can just stream the quadratic bezier curves unprocessed into the vertex shader, literally the simplest thing conceivable. > With Slug, you can use only 1 quad per glyph if you want. Nowadays one would probably implement loop & blinn in a tiled compute shader too (instead of using stencil buffers) to reduce memory bandwidth and over draw. That way you also get one quad per glaph, but without any of the geometry special casing that Slug does. > It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues. Correct, might have worded that badly. Still remains a trade off in a) which b) does not have.
- jeremiahkellick 6mo ago
  [1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler than the loop and blinn paper. However, if you want to do distance based anti-aliasing rather than supersampling, things are going to get complicated again as you have to expand the shape outline to capture more pixel centers. I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle. I feel like any attempt to do that will approach the complexity of Slug, but maybe it's my own shortcoming that I don't see it. I would love to read more detailed information on that if you have it. [1] https://medium.com/@evanwallace/easy-scalable-text-rendering-on-the-gpu-c3f4d782c5ac https://medium.com/@evanwallace/easy-scalable-text-rendering... [2] https://web.archive.org/web/20180905215805/http://www.glprogramming.com/red/chapter14.html#name13 https://web.archive.org/web/20180905215805/http://www.glprog...
  - Lichtso 6mo ago
    > [1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler Yes, they describe one variation of the angle based method to winding numbers by spanning a triangle fan from an arbitrarily chosen pivot point / vertex. > if you want to do distance based anti-aliasing rather than supersampling Particularly when it comes to rendering vector graphics I think of analytic anti-aliasing methods as somewhat cursed and prefer multisampling [0], at least for magnification. For minification mip-mapping remains the go to solution. However, if you only render 2D text on a 2D plane, which is typically overlap free, then these correctness issues don't matter. > I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle All modern vector renderers I know of avoid triangle rasterization entirely. Like I said, they typically do tiles (screen space partitioned into quads) in a compute shader instead of using the fixed functionality with a fragment / pixel shader. The reason is that nowadays compute is cheap and memory bandwidth is the bottle neck. Thus, it makes sense to load a bunch of overlapping geometry from global memory into workgroup shared memory, render all of it down to pixels in workgroup shared memory, and then only write these pixels back to the framebuffer in global memory. > I feel like any attempt to do that will approach the complexity of Slug A highly optimized implementation might very well, yes. Yet, handling the many cases of intersections of the path and the scanline won't be contributing to the complexity, which is what started this discussion. > I would love to read more detailed information on that if you have it. I implemented the outdated stencil buffer + triangle fan + implicit curves approach [1] if you want to take a look under the hood. The library is quite complex because it also handles the notoriously hard rational cubic bezier curves analytically, which Slug does not even attempt and just approximates. But the integral quadratic bezier curves are very simple and that is what is comparable to the scope Slug covers. It is just a few lines of code for the vertex shader [2], the fragment shader [3] and the vertex buffer setup [4]. Edit: You can even spin loop & blinn into a scanline method / hybrid: They give you the side of the curve your pixel is on [5], which is typically also the thing scanline methods are interested in. They compute the exact intersection location relative to the pixel, only to throw away most of the information and only keep the sign (side the pixel is on). So, that might be the easiest fragment shader vector renderer possible. Put it together in a shader toy [6] a while back. [0]: https://news.ycombinator.com/item?id=46473247#46530503 https://news.ycombinator.com/item?id=46473247#46530503 [1]: https://github.com/Lichtso/contrast_renderer https://github.com/Lichtso/contrast_renderer [2]: https://github.com/Lichtso/contrast_renderer/blob/main/src/shaders.wgsl#L72 https://github.com/Lichtso/contrast_renderer/blob/main/src/s... [3]: https://github.com/Lichtso/contrast_renderer/blob/main/src/shaders.wgsl#L241 https://github.com/Lichtso/contrast_renderer/blob/main/src/s... [4]: https://github.com/Lichtso/contrast_renderer/blob/main/src/fill.rs#L285-L296 https://github.com/Lichtso/contrast_renderer/blob/main/src/f... [5]: https://news.ycombinator.com/item?id=45626037#45627274 https://news.ycombinator.com/item?id=45626037#45627274 [6]: https://www.shadertoy.com/view/fsXcDj https://www.shadertoy.com/view/fsXcDj

elengyel 6mo ago

You don't seem to have grokked the main feature that makes Slug interesting. The algorithm handles every single possible case uniformly through the use of a very fast classification and root eligibility determination technique. On some GPUs (including all NV from the last 10+ years), handling the full set of cases shown on the poster reduces to a single instruction (LOP3). The algorithm also eliminates all numerical precision issues -- provably -- making it the most robust of all time. There are no valid inputs for which the algorithm fails, so to say Loop-Blinn is somehow more robust is incorrect.