it's my first post here, but I've been reading for a couple of months.
And right now I am ready to share some stuff I made. Please feel free to ask, criticize or suggest alternatives :)
A couple of months ago someone here (don't have the link anymore) inspired me to finally sit down and implement a delaunay-triangulation and voronoi from scratch.
What the python-script (drawTriangles.py) does is:
- take an image, extract points dependent on the contrast and color difference of the image (more points on edges or in contrast-rich parts).
- triangulate the points with a delaunay-triangulation (from scratch).
- transform the delaunay-triangles into voronoi-regions.
- render the triangles and voronoi-regions into new images with the average color for each polygon (from the original image).
The delaunay-triangulation runs in Omega(n logn) but I'm not 100% sure if also in O(n logn). The transformation into voronoi-regions runs in O(n).
Please tell me what you think :)
Best regards Maurice
Nice work. The triangulation is a nice structure to get to know. You might be interested in something called data-dependent triangulation. The idea is that non-conventional triangulations (i.e., not Delaunay) make for good interpolating schemas, based on assumptions such as smoothness in the color intensity profile and so on. I wrote a Master's thesis [1] about this among other things such as decimating a dense triangulation mesh in strategic ways (using edge detection).
Thanks :)
Looks really interesting! I will have a look at it when I have a minute!
My master thesis is probably next summer. So I'm looking around for possible subjects at the moment :)
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.
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 :)
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.
I've played with this kind of stuff in the past, it's a lot of fun. Have you tried shading the triangles so each is colored as the interpolation of the color at the vertices?
I've wondered what a video codec for this would look like, compute the triangulation for I frames and in between just tweak the location of the points, when triangulation is totally broken, time for a new I frame. It's somewhat slow to compute, but displays well on hardware optimized for displaying triangles...
Didn't think about that, good idea as a small extension!
But I don't think, a video codec would work. Or maybe just with very few points/triangles. Depending on the point-selection (equally distributed is a lot faster!) it takes some time between 50s to 5 minutes for a triangulation of about 4000 Points.
For just a few hundred it could work, but I don't think it's good enough for real-time.
(Displaying is no concern. You can render thousands of triangles in real-time)
I'm startled at your triangulation time. I last did serious work with Delauney triangulation in 1998 or so, and was triangulating ~1000000 points in a few of hours (on a machine with only 4MiB of RAM)
Never tried so many points, maybe I give it a try later.
I think it's part time the language choice and the fact, that my algorithm probably runs in Omega(n logn) but might not reach O(n logn)...
Maybe you got an idea:
My bottleneck is to find the triangle in which a new point lies.
Right now I go through the triangle-mesh in the direction of the point, hoping to find the right triangle fast. Most of the time, it does ...
A desktop app I built to use this code, generating Voronoi and Delaunay graphs, along with way more robotics/navigation/map generation stuff called MapViewer - http://www.skynet.ie/~sos/mapviewer/main.php
No problem with C or C++ (I am mainly working in C for OpenGL stuff for years).
I chose Python because I wanted to concentrate on the algorithm (didn't know, if there were obstacles along the way...). So in Python I could just go for executable pseudo-code :)
Is it possible to modify the algorithm to use vertex color instead of triangle color? It is possible to do interesting stuff like Homeworld 2 backgrounds.
it's my first post here, but I've been reading for a couple of months.
And right now I am ready to share some stuff I made. Please feel free to ask, criticize or suggest alternatives :)
A couple of months ago someone here (don't have the link anymore) inspired me to finally sit down and implement a delaunay-triangulation and voronoi from scratch.
What the python-script (drawTriangles.py) does is:
- take an image, extract points dependent on the contrast and color difference of the image (more points on edges or in contrast-rich parts).
- triangulate the points with a delaunay-triangulation (from scratch).
- transform the delaunay-triangles into voronoi-regions.
- render the triangles and voronoi-regions into new images with the average color for each polygon (from the original image).
The delaunay-triangulation runs in Omega(n logn) but I'm not 100% sure if also in O(n logn). The transformation into voronoi-regions runs in O(n).
Please tell me what you think :) Best regards Maurice