3 ms·

> One edge case I wound up being due to a floating point arithmetic error, which was fun because my computer science degree finally wound up coming in handy. T

> One edge case I wound up being due to a floating point arithmetic error, which was fun because my computer science degree finally wound up coming in handy. These are everywhere whenever you do anything with vector graphics in the real world. Lots of interesting computational geometry papers end up useless in reality because floating point error kills you if you try to implement the algorithms. It's pretty sad… The other issue that comes up again and again is self-intersecting paths. Most published algorithms you'll find don't bother to support them, which also makes them not very useful in reality because self-intersecting paths are everywhere. I'm very skeptical of clever vector path algorithms these days. The amount of work needed to get them to work in the real world is rarely worth it. Better to spend the time reformulating the problem in such a way as to avoid needing them.

jacobolus 7y ago
From Shewchuk’s thesis: > From the beginning of the implementation of Triangle, and well into the development of Pyramid, floating-point roundoff problems plagued me. Each program would sometimes crash, sometimes find itself stuck in an endless loop, and sometimes produce garbled output. At first I believed that I would be able to fix the problems by understanding how the algorithms went wrong when roundoff error produced incorrect answers, and writing special-case code to handle each potential problem. Some of the robustness problems yielded to this approach, but others did not. Fortunately, Steven Fortune of AT&T Bell Laboratories convinced me, in a few brief but well-worded email messages (and in several longer and equally well-worded technical papers), to choose the alternative path to robustness, which led to the research described in this chapter. For reasons that will become apparent, exact arithmetic is the better approach to solving many, if not all, of the robustness worries associated with triangulation. Of course, what can be done with polygons is often not feasible for more general kids of shapes like parametric cubics. * * * What is a “clever vector path algorithm”, and how do you avoid them?
- pcwalton 7y ago
  Algorithms that gave me floating-point related problems: - Fast polygon triangulation/partitioning. There's a reason why people use ear clipping in practice despite it having bad asymptotic time complexity. Even ear clipping isn't very useful for robust path rendering because it doesn't handle self-intersection. Tiling and stenciling to compute winding numbers is a much more robust approach than tessellation. - Generation of bounding geometry for analytic antialiasing of polygon edges, to work around the lack of conservative rasterization on GPUs. Skia has impressive code that handles this, but it is incredibly painful and I decided it wasn't worth it. - Determining polygon convexity. This even led to a security bug in Skia [1]. - Clipping of Bézier paths, especially in homogeneous coordinates. Yes, this even includes clipping to axis-aligned rects. It's too hard. Convert to triangles or quads and clip those. - Any sort of Boolean operation on Bézier paths, if you want reliable results. Leave those to applications like Illustrator, where artists can notice if the algorithm goes wrong and fix it up manually when it does. [1]: https://googleprojectzero.blogspot.com/2019/02/the-curious-case-of-convexity-confusion.html https://googleprojectzero.blogspot.com/2019/02/the-curious-c...
virtualritz 7y ago
> The other issue that comes up again and again is self-intersecting paths. Most published algorithms you'll find don't bother to support them, which also makes them not very useful in reality because self-intersecting paths are everywhere. Exactly this. This is the biggest challenge when doing useful stuff with curves in graphics design/3D. Curve offsetting is a common tool to produce paths (2D), extrusions & bevels (3D) etc. Whenever the offset distance exceeds the local radius of curvature intersections occur. When you have some clever algorithm to deal with those, e.g. clipping them out, you're then faced with offset curves that have different parameterization than the original. Try to create a patch mesh from those then. This is a huge brain fuck and every time you think you got it worked out another edge case you didn't think about will creep up from out of nowhere.

jacobolus 7y ago

From Shewchuk’s thesis: > From the beginning of the implementation of Triangle, and well into the development of Pyramid, floating-point roundoff problems plagued me. Each program would sometimes crash, sometimes find itself stuck in an endless loop, and sometimes produce garbled output. At first I believed that I would be able to fix the problems by understanding how the algorithms went wrong when roundoff error produced incorrect answers, and writing special-case code to handle each potential problem. Some of the robustness problems yielded to this approach, but others did not. Fortunately, Steven Fortune of AT&T Bell Laboratories convinced me, in a few brief but well-worded email messages (and in several longer and equally well-worded technical papers), to choose the alternative path to robustness, which led to the research described in this chapter. For reasons that will become apparent, exact arithmetic is the better approach to solving many, if not all, of the robustness worries associated with triangulation. Of course, what can be done with polygons is often not feasible for more general kids of shapes like parametric cubics. * * * What is a “clever vector path algorithm”, and how do you avoid them?

pcwalton 7y ago
Algorithms that gave me floating-point related problems: - Fast polygon triangulation/partitioning. There's a reason why people use ear clipping in practice despite it having bad asymptotic time complexity. Even ear clipping isn't very useful for robust path rendering because it doesn't handle self-intersection. Tiling and stenciling to compute winding numbers is a much more robust approach than tessellation. - Generation of bounding geometry for analytic antialiasing of polygon edges, to work around the lack of conservative rasterization on GPUs. Skia has impressive code that handles this, but it is incredibly painful and I decided it wasn't worth it. - Determining polygon convexity. This even led to a security bug in Skia [1]. - Clipping of Bézier paths, especially in homogeneous coordinates. Yes, this even includes clipping to axis-aligned rects. It's too hard. Convert to triangles or quads and clip those. - Any sort of Boolean operation on Bézier paths, if you want reliable results. Leave those to applications like Illustrator, where artists can notice if the algorithm goes wrong and fix it up manually when it does. [1]: https://googleprojectzero.blogspot.com/2019/02/the-curious-case-of-convexity-confusion.html https://googleprojectzero.blogspot.com/2019/02/the-curious-c...

virtualritz 7y ago

> The other issue that comes up again and again is self-intersecting paths. Most published algorithms you'll find don't bother to support them, which also makes them not very useful in reality because self-intersecting paths are everywhere. Exactly this. This is the biggest challenge when doing useful stuff with curves in graphics design/3D. Curve offsetting is a common tool to produce paths (2D), extrusions & bevels (3D) etc. Whenever the offset distance exceeds the local radius of curvature intersections occur. When you have some clever algorithm to deal with those, e.g. clipping them out, you're then faced with offset curves that have different parameterization than the original. Try to create a patch mesh from those then. This is a huge brain fuck and every time you think you got it worked out another edge case you didn't think about will creep up from out of nowhere.