3 ms·
It's a super fun project, thanks for sharing! I think you might have fun with some variations too: One way you can use the Voronoi diagram to influence your p
by dahart 11y ago
It's a super fun project, thanks for sharing!
I think you might have fun with some variations too:
One way you can use the Voronoi diagram to influence your point selection is Lloyd's algorithm: iterate one or more times, and at each step, move each point to the center of mass of its associated Voronoi cell. It's super simple to do once you have a Voronoi tessellator, and spreads your points out beautifully. Wicked fun to watch and play with interactively, and often surprising how long convergence can take. (though just one or two iterations will often get you most of the way there, and make things look really nice.)
For point selection, try rejection sampling according to brightness. Combine with Lloyd's algorithm for a good time.
An altogether separate approach, but one to still implement and compare, is to render Voronoi tiled images using webgl or some other 3D rasterizer. You can do it in linear time by drawing a cone at each point, somewhat larger than you expect the cells to be, and the z-buffer will create the Voronoi effect for you.
Also, since you have the Delaunay/Voronoi mesh, you can, among other fun things to do with them, easily use a simple recursive maze generator to knock out edges and make big organic mazes. Combine with the image based point selection you used and/or the techniques I mentioned above, and you can make some pretty cool mazes.
- EllipticCurve 11y agoYou're welcome and thanks for all the ideas!!! Moving the points to the center of each voronoi-cell sounds like a really fun (and easy) addition to the project, I will get on that the next couple of days! I came across rejection-sampling before, might have a closer look at it! I worked quite a lot on OpenGL-stuff with and without shaders. So that actually combines some more interests of mine quite well, thank you :)
- dahart 11y agoIn that case, you might have a bunch of fun combining your interests implementing this paper: http://www.dgp.toronto.edu/papers/ahausner_SIGGRAPH2001.pdf http://www.dgp.toronto.edu/papers/ahausner_SIGGRAPH2001.pdf For rejection sampling, btw, there is an infinite variety of ways to do it. Rejection can be used to generate a Poisson distribution, by enforcing a minimum radius from other points, which has a somewhat similar result to a converged Lloyds algorithm. But you can also sample randomly from the 2d brightness function that is an image. You can also combine those two things to get well spaced points whose density is proportional to brightness, by enforcing a minimum radius that is proportional to brightness. (Or inverse brightness!) And best of all, it's ridiculously easy to implement. For an extra good time, you can learn how to importance sample that distribution directly, an alternative to rejection sampling that doesn't waste any points. Glad to hear you're digging it, I love this kind of stuff! Send me a link if/when you get some results with Lloyd's.