Impressive work, Raph! As I'm sure everyone knows by now, the PostScript imaging model is hard to make work on the GPU, and its traditional geometry pipeline isn't suited well for curves or analytic coverage-based AA.
Since I come from the games space, a lot of my thoughts have been about baking as much data as possible: if we had infinite build time, or artist tooling akin to Maya, how would that help us develop better UIs? If we leave PostScript behind and think about new graphics models, what can we do? So a lot of my own research has been studying really old graphics history, since there's always fun ways of looking at the problem before we settled on one solution. I'll have to collect some of my research and demos and publish it sometime soon.
Although, one thing I've noticed during my time in games is that frame time is the standard. If we speed up our rasterizer, we'll just add more junk to the scene until it hits our 60fps frame target. More blurs! More effects! :)
> its traditional geometry pipeline isn't suited well for curves or analytic coverage-based AA
I actually don't agree with this: Pathfinder shows that analytic AA works quite well with the GPU rasterizer. You simply use a floating-point render target with additive blending to sum signed areas. In fact, as long as you convert to tiles first, which both piet-metal and Pathfinder do, vector rendering is actually a task very well suited for the GPU.
The hard part is that filling a path is a fundamentally sequential operation, since whether a pixel is on or off depends on every other path that intersects the scanline that pixel is on. This means that you either need an expensive sequential pass somewhere, or you lose work efficiency. Both piet-metal and Pathfinder try to strike a balance by doing some parts sequentially and sacrifice some work efficiency, using tiling to keep the efficiency loss bounded. This approach turns out to work well.
> The hard part is that filling a path is a fundamentally sequential operation, since whether a pixel is on or off depends on every other path that intersects the scanline that pixel is on.
I'm not quite sure I get this. Are you simply talking about overdraw optimizations and the requirement for in-order blending here, or something else like even-odd fill rules?
Obviously, the hardware itself has a massive serial component in the form of the ROP which will make sure blend draws retire in-order, and pixel-shader interlock gives you a bit more granular control over the scheduling without relying on the fixed-function ROP unit.
I'm talking about the fill rule (whether even-odd or winding). Given a path outline made of moveto/lineto/etc. commands, you can't tell just by looking locally at a pixel whether it should be filled or not without looking at every path segment that intersects the scanline it's on.
I have no idea what about the topic being discussed here, but this sounds like you basically have to do a:
for each path outline in all path outlines:
for each pixel in all pixels:
check whether pixel is inside/outside the path outline
?
That looks like a massively parallel problem to me: you can parallelize both for loops (all paths in parallel, all pixels in parallel) and then do a reduction for each pixel, which can be a parallel reduction.
Some acceleration data-structures for these kind of problems can also be constructed in parallel and in the GPU (e.g. bounded volume hierarchies), and some methods for inside/outside checking might be more amenable for parallelization than even/odd or winding number (e.g. level-set / signed-distance fields).
> That looks like a massively parallel problem to me: you can parallelize both for loops (all paths in parallel, all pixels in parallel) and then do a reduction for each pixel, which can be a parallel reduction.
The reduction step is still less work-efficient than the sequential algorithm (O(n log n) work vs. O(n)), even if it can be faster due to the increased parallelism.
But yeah, if you go down this road you will eventually end up with a delta coverage algorithm. You've basically described what I'd like to do in Pathfinder for an optional compute-based tiling mode. (Because I have to work on GL3, though, I can't depend on compute shader, so right now I do this work in parallel on CPU.)
> Some acceleration data-structures for these kind of problems can also be constructed in parallel and in the GPU (e.g. bounded volume hierarchies)
Yes, that's the tiling step that both piet-metal and Pathfinder do.
I think it is quite funny that 2D vector graphics, and 3D e.g. computational fluid dynamic simulations, have to, pretty much, solve the same problem.
We use in 3D STL geometrys, NURBS/T-splines from CAD, and signed-distance fields, often all of them simulatenously in the same simulation, and for a big 3D volume (with 10^9-10^10 "cells"/"3d-pixels") we have to figure out whether these are inside or outside. Our 3D domain is adaptive and dynamic to track the movement of bodies and features of the flow, so we have to update it on every iteration, and all of this has to happen in distributed memory on 100.000-1.000.000 cores, without blocking.
There is a lot of research about, e.g., how to update signed-distance fields quickly, in parallel, and distributed memory, when they slightly move or deform, as well as how to use signed distance fields to represent sharp corners or how to extract the input geometry "as accurately as possible" from a signed distance field, as well as how big the maximum error is, etc. The Journal of Computational Physics, Computational Methods in Applied Mechanics, and SIAM journals, are often full with this type of research.
For computer graphics, errors are typically ok. But for engineering applications, the difference between a "sharp" edge and a smoothed one can be a completely different flow field, which result in completely different physical phenomena (e.g. turbulent vs laminar flow), and completely different loads on a structure.
That's tessellation, and it is one approach to vector graphics on GPU. Unfortunately, it's difficult to implement (floating point/fixed point error will frequently ruin your day) and makes it hard to implement analytic antialiasing, which is why Pathfinder doesn't use it. But it is a possible approach.
These are all interesting questions. I've been following some of the stuff on Shadertoy, and I think that points the way. Most is 3d, but not all, and in particular there's a lot to be done with distance fields.
I've been thinking about blur (and mentioned some approximation techniques), but it's expensive in any context. Maybe if we think in shaders instead of the blur tool, we'll find a visual palette that is both fresh and efficient.
Distance fields are great! What do you think an alternative to PostScript's imaging model (Porter/Duff) formulated in terms of signed distance fields would be like?
Much of Photoshop's power comes from representing the selection as first class alpha channels that you can use all of Photoshop's editing and filtering tools on, so you can select something with any of the the selection tools, then take a step back into "quick mask" mode and edit your selection in the "channel" domain, with any of the painting tools or filters, and store selections in extra channels for later use.
I wonder how an image editor like Photoshop (and a rendering model in general) could directly and conveniently support signed distance fields as shapes, selections, and channels, as nicely as it supports alpha channels?
Back in 1993 (5 years after Photoshop was created in 1988), it sounded revolutionary to use texture mapping as a fundamental drawing primitive, because nobody suspected some day everybody'd be carrying around more computrons than an SGI workstation in their phone.
I don't quite know what you mean. I don't think Raph is talking about SDF in the same way that people often talk about it, as a way to use the sampling hardware to improve alpha-tested magnification for fonts and other monochrome shapes. Rather he's talking about computing the distance to a stroke in a shader and using that to approximate a coverage value. You can view that as a type of distance field, and it is, technically, but it's not using the texture mapping hardware as for example the Valve paper does. An image editor that rendered with distance fields in the sense of this article would basically just be a regular vector editor, like Illustrator.
I was thinking that it would be lovely to be able to do the same special effect tricks (outlines, shadows, dialating, glows, bevels, shading, etc) with anything you drew like points, lines, curves, polygons, etc, that (for example) TextMesh Pro can do with text.
There has been research how to do that with adaptively sampled distance fields [1].
The author (Frisken) also created a 2D drawing tool called Mischief, which is an insanely fast vector graphics software. It's available in the Mac App Store if you want to try it. I think Foundry owns the patents now and they are using the technology in their products.
Since I come from the games space, a lot of my thoughts have been about baking as much data as possible: if we had infinite build time, or artist tooling akin to Maya, how would that help us develop better UIs? If we leave PostScript behind and think about new graphics models, what can we do? So a lot of my own research has been studying really old graphics history, since there's always fun ways of looking at the problem before we settled on one solution. I'll have to collect some of my research and demos and publish it sometime soon.
Although, one thing I've noticed during my time in games is that frame time is the standard. If we speed up our rasterizer, we'll just add more junk to the scene until it hits our 60fps frame target. More blurs! More effects! :)