Please don't do this. Folks put effort into well-illustrated explanations; if you're going to re-use content, at least put an attribution and link on there!
Matt, I'm very sorry. It was a genuine mistake. I always try hard to attribute sources (as you can see from the references in the doc, and on the couple of hundred other articles on my blog). It was nothing personal, it was an oversight :)
I've corrected this now on the site. Sorry again. Thanks for bringing this to my attention.
Regards
/\/ick
Speaking of attribution, why doesn't that article reference Lloyd's algorithm? https://en.m.wikipedia.org/wiki/Lloyd%27s_algorithm
Still, that's a good stand-alone link – I'll add it to the writeup.
[1] https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord... [2] https://www.cs.princeton.edu/courses/archive/fall00/cs597b/p...
Nothing wrong with using the Wikipedia article as an informal reference, but wherever you reference the other papers, considering linking to Lloyd's IEEE paper directly.
Splitting the centroid computation into a two-pass accumulation is a great idea. Even though that makes for heavy shaders, I imagine it's still faster than doing a buffer read and finding the centroids in one pass via CPU?
I'd also be interested in hearing how you decide on convergence. Are you stoppping after a fixed number of iterations? Or are you able to track the offsets using the GPU - not sure if that is possible since you're writing back into the VBO directly? You probably know from playing with it that Lloyd's algorithm is notorious for very long convergence times. It gets close very quickly, and then can have a super long tail with many small iterations and then sudden large changes long after it seemed like things had settled. It's super fun to watch, especially when you dynamically add points, very reminiscent of cell division -- you should make a video for your project page!
You might be interested in this paper too: http://www.dgp.toronto.edu/papers/ahausner_SIGGRAPH2001.pdf This one uses GPU Voronoi + Lloyd's algorithm to generate mosaic tilings. The neat trick here is to use a Manhattan distance instead of a Euclidean one, in order to get voronoi cells to line up in mostly rectangular grids instead of approximating a hexagonal packing.