News for hackers. Stuff that matters.
Re:A new algorithm for finding a visual center of a polygon by chrisseaton on Saturday May 20, 2017 @06:25PM (#14384680)
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?)
Re:A new algorithm for finding a visual center of a polygon by tripzilch on Sunday May 28, 2017 @11:31AM (#14434747)
> 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.

Re:A new algorithm for finding a visual center of a polygon by opticalflow on Saturday May 20, 2017 @06:52PM (#14384790)
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... :)
Re:A new algorithm for finding a visual center of a polygon by malux85 on Saturday May 20, 2017 @08:48PM (#14385173)
That sounds fascinating, can you explain the project a bit more?
Re:A new algorithm for finding a visual center of a polygon by opticalflow on Sunday May 21, 2017 @10:02AM (#14387337)
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.