News for hackers. Stuff that matters.
Re:Voronoi Diagrams on the GPU by 33a on Wednesday April 13, 2016 @09:20PM (#11493679)
This isn't actually a voronoi diagram, it is an (approximate) distance transform - though it is still pretty cool!

If you are working on a grid, there are lots of ways to compute distance transforms exactly. An exact and optimal serial algorithm which works for any metric is due to Meijster, and it runs in O(n) time in the number of pixels:

http://parmanoir.com/distance/

Distance transforms are a special kind of (max, +) convolution, and have lots of interesting algebraic properties

Re:Voronoi Diagrams on the GPU by vanderZwan on Thursday April 14, 2016 @03:22AM (#11494860)
The linked paper specifically says "Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform," so are you sure it's not both in this case?
Re:Voronoi Diagrams on the GPU by 33a on Thursday April 14, 2016 @10:42AM (#11497096)
To compute a voronoi diagram, you also need to reconstruct the boundary and topology of all the cells, which is not being done here. Also most algorithms for computing voronoi diagrams do not snap the vertices to integer lattice coordinates.
Re:Voronoi Diagrams on the GPU by vanderZwan on Friday April 15, 2016 @08:42AM (#11503785)
Would it be fair to say this is a fast rasterization algorithm?