4 ms·

> 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 t

> 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.

pcwalton 7y ago
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.
- kibibu 7y ago
  This might be a case for the kind of preprocessing GP was talking about though, breaking complex winding-based geometry into convex shapes.
  - pcwalton 7y ago
    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.
    - kibibu 7y ago
      Does tessellation not imply triangles? I was imagining convex curved shapes. Could these not be broken on scanlines, avoiding rounding errors?
- fluffything 7y ago
  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).
  - pcwalton 7y ago
    > 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.
    - fluffything 7y ago
      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.

pcwalton 7y ago

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.

kibibu 7y ago
This might be a case for the kind of preprocessing GP was talking about though, breaking complex winding-based geometry into convex shapes.
- pcwalton 7y ago
  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.
  - kibibu 7y ago
    Does tessellation not imply triangles? I was imagining convex curved shapes. Could these not be broken on scanlines, avoiding rounding errors?
fluffything 7y ago
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).
- pcwalton 7y ago
  > 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.
  - fluffything 7y ago
    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.