3 ms·
Thanks for posting this. I was convinced that Delaunay triangulation was a good example of irregular parallelism - something that fundamentally doesn't work wel
by chrisseaton 10y 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 10y agoI 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 10y agoThat sounds fascinating, can you explain the project a bit more?
- opticalflow 10y agoWe 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.