Hacker News Reader

Comment by chrisseaton | Hacker News Reader

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?)

View on HN

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

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

That sounds fascinating, can you explain the project a bit more?

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.

Reply on news.ycombinator.com