Mark J. Kilgard
2020 · arXiv
Stroking and filling are the two basic rendering operations on paths in vector graphics. The theory of filling a path is well-understood in terms of contour integrals and winding numbers, but when path rendering standards specify stroking, they resort to the analogy of painting pixels with a brush that traces the outline of the path. This means important standards such as PDF, SVG, and PostScript lack a rigorous way to say what samples are inside or outside a stroked path. Our work fills this gap with a principled theory of stroking. Guided by our theory, we develop a novel polar stroking method to render stroked paths robustly with an intuitive way to bound the tessellation error without needing recursion. Because polar stroking guarantees small uniform steps in tangent angle, it provides an efficient way to accumulate arc length along a path for texturing or dashing. While this paper focuses on developing the theory of our polar stroking method, we have successfully implemented our methods on modern programmable GPUs.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
4 selected excerpts · 4 total mentions
Bezier curves can generate degenerate geometry when flattened and stroke geometry has to handle edge cases. See for instance the illustration on the last page of the Polar Stroking paper: https://arxiv.org/pdf/2007.00308 There are also things like interpretting (conflating) coverage as alpha for analytical antialiasing methods, which lead to visible hairline cracks.
I would say the most likely reason is that 2D graphics is just plain hard. Jasper's classic essay[1] goes into more detail. That said, I'd really love to see more stuff along the lines of what you describe. I think Vello could render, for example, something that visually looks like Mini Metro or Mini Motorways. I also of course would be a massive fan of using Euler spirals - the only curve that's truly, really simpler is quadratic Béziers, and making those look good in your application would be hard. I'm about to do a lot of Euler spiral math on GPU as part of the stroke rework, which you may find interesting. Strokes are easier for GPUs than fills, because you don't have…
to worry about the winding number issues (non-convex paths, paths with holes, etc). There are two recent papers, Polar Stroking[2] and Converting stroked primitives to filled primitives[3]. Also check out Freya Holmér's excellent Shapes library[4] (easily integrated with Unity). Tesselating curves via shaders is the future (through mesh shaders in particular), and I've got a colleague working on that, but portable infrastructure seems to me just as thorny a problem as compute. I am very biased, but if it were me I'd try to render the 2D stuff with a 2D renderer like Vello. Best of luck with your project, and I'd be interested in following the progress. Feel free to stop by the Zulip[5] and ask such questions there, as well. [1]: https://blog.mecheye.net/2019/05/why-is-2d-graphics-is-harde... [2]: https://arxiv.org/abs/2007.00308 [3]: http://w3.impa.br/~diego/projects/Neh20/ [4]: https://assetstore.unity.com/packages/tools/particles-effect... [5]: https://xi.zulipchat.com/#narrow/stream/197075-gpu
Mark Kilgard from NVIDIA has been beating this drum for a couple decades. It's not simple. His latest paper is about how to handle stroking of cubic splines: https://arxiv.org/abs/2007.00308 He gives it as a talk, but you have to sign up with NVIDIA: https://developer.nvidia.com/siggraph/2020/video/sig03-vid
Tangentially, huh? So the underlying operation of finding a parallel "curve" is trivial when the curve is a line, as it's just another line. That doesn't mean the problems is simple, though. One challenge (which I didn't address in the post, nor do I have code yet) is dealing with corners, as there are the usual choices of round, miter, and bevel. Of these, only round represents a true Minkowski sum. The others are generally more commonly used. Btw, see "Polar Stroking" [1] for more details on this. I came very close to linking it. The second detail is the "trimming" as the parallel curve paths generally have self-intersections, and very often you don't want those. So in…
the general case you have to do something similar to, say, Skia path ops. It's very difficult to make those operations completely numerically robust, and I think most implementations have gone through some pain as more test cases pop up which break. It is a fascinating area. I'm glad you're curious. [1]: https://arxiv.org/abs/2007.00308
More from the same topics.
Dan Tong, David J. Farnham, Lei Duan +4
Abstract If future net-zero emissions energy systems rely heavily on solar and wind resources, spatial and temporal mismatches between resource availability and electricity demand may challenge system reliability.
Steven M. Paul, Daniel S. Mytelka, Christopher T. Dunwiddie +4