5 ms·

While their approach is clever, it is not guaranteed to converge in a fixed number of iterations. Author states that constrained Delaunay Triangulation is "slo

While their approach is clever, it is not guaranteed to converge in a fixed number of iterations. Author states that constrained Delaunay Triangulation is "slow and error-prone". I disagree -- I've implemented parallel and recursive Delaunay on GPU before, and it converges in a fixed number of recursions -- for a taste of the general approach, see here: http://www.comp.nus.edu.sg/~tants/jfa/i3d06-submitted.pdf http://www.comp.nus.edu.sg/~tants/jfa/i3d06-submitted.pdf JFA could certainly be "abused" for this purpose.

vanderZwan 9y ago
For those who don't immediately know what JFA stands for: http://www.comp.nus.edu.sg/~tants/jfa.html http://www.comp.nus.edu.sg/~tants/jfa.html
chrisseaton 9y ago
Thanks for posting this. I was convinced that Delaunay triangulation was a good example of irregular parallelism - something that fundamentally doesn't work well on a GPU, and have been telling people this for years, so I'll look forward to reading the paper. (A Voronoi diagram is just a different way to show a Delaunay triangulation isn't it?)
- opticalflow 9y ago
  I was running this on (high end) GPUs back in 2011, in real-time (30fps), on 1920x1080 video textures. I can confirm that the clever recursion and performance of this is mind-boggling. Oh, and you get a distance transform out of it as an intermediate step, just for giggles. My general take is that while linear kernel-thinking in parallel might get nowhere, this is a prime example of recursion solving the problem when parallelism is available. I wish I could claim to have invented it... :)
  - malux85 9y ago
    That sounds fascinating, can you explain the project a bit more?
    - opticalflow 9y ago
      We were doing GPU-based 2D-3D conversion for HD and 4K and one of the intermediate steps required that we compute a DT (distance transform), and JFA was perfect for this. The DT was used along with a Hough transform (also real-time) to conduct vanishing point and geometry analysis.
- tripzilch 9y ago
  > A Voronoi diagram is just a different way to show a Delaunay triangulation isn't it? Yes, Voronoi and Delaunay are duals of eachother, so you can flip between them. Edges of one turn to vertices of the other and vice versa.
Iv 9y ago
> While their approach is clever, it is not guaranteed to converge in a fixed number of iterations. Are you sure about it? I struggle to find a case where the quadtree version of their algorithm would not converge.
- opticalflow 9y ago
  I didn't mean to imply that there were cases where it would Never converge, just that the number of iterations is not a-priori fixed or predictable.
  - Iv 9y ago
    My intuition is that the worst case scenario would be a fractal-like curve with multiple solutions (imagine a snake-like polygon following a Hilbert pattern). In that case the algorithm would need to explore all of the smallest squares, that gives us a higher bound on the number of iterations. It will be far less in most cases. Would the delaunay-based algorithm be faster in the worst case?

vanderZwan 9y ago

For those who don't immediately know what JFA stands for: http://www.comp.nus.edu.sg/~tants/jfa.html http://www.comp.nus.edu.sg/~tants/jfa.html

chrisseaton 9y ago

Thanks for posting this. I was convinced that Delaunay triangulation was a good example of irregular parallelism - something that fundamentally doesn't work well on a GPU, and have been telling people this for years, so I'll look forward to reading the paper. (A Voronoi diagram is just a different way to show a Delaunay triangulation isn't it?)

opticalflow 9y ago
I was running this on (high end) GPUs back in 2011, in real-time (30fps), on 1920x1080 video textures. I can confirm that the clever recursion and performance of this is mind-boggling. Oh, and you get a distance transform out of it as an intermediate step, just for giggles. My general take is that while linear kernel-thinking in parallel might get nowhere, this is a prime example of recursion solving the problem when parallelism is available. I wish I could claim to have invented it... :)
- malux85 9y ago
  That sounds fascinating, can you explain the project a bit more?
  - opticalflow 9y ago
    We were doing GPU-based 2D-3D conversion for HD and 4K and one of the intermediate steps required that we compute a DT (distance transform), and JFA was perfect for this. The DT was used along with a Hough transform (also real-time) to conduct vanishing point and geometry analysis.
tripzilch 9y ago
> A Voronoi diagram is just a different way to show a Delaunay triangulation isn't it? Yes, Voronoi and Delaunay are duals of eachother, so you can flip between them. Edges of one turn to vertices of the other and vice versa.

Iv 9y ago

> While their approach is clever, it is not guaranteed to converge in a fixed number of iterations. Are you sure about it? I struggle to find a case where the quadtree version of their algorithm would not converge.

opticalflow 9y ago
I didn't mean to imply that there were cases where it would Never converge, just that the number of iterations is not a-priori fixed or predictable.
- Iv 9y ago
  My intuition is that the worst case scenario would be a fractal-like curve with multiple solutions (imagine a snake-like polygon following a Hilbert pattern). In that case the algorithm would need to explore all of the smallest squares, that gives us a higher bound on the number of iterations. It will be far less in most cases. Would the delaunay-based algorithm be faster in the worst case?