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).
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.
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...
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.
[+] [-] EllipticCurve|10 years ago|reply
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
[+] [-] arketyp|10 years ago|reply
[1] http://uu.diva-portal.org/smash/record.jsf?pid=diva2%3A85902...
[Edit: My old blog with plenty of pictures: https://femtondev.wordpress.com/ ]
[+] [-] dahart|10 years ago|reply
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.
[+] [-] pacaro|10 years ago|reply
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...
[+] [-] nacs|10 years ago|reply
There's a bunch here for those who didn't dig through the repo (many are at huge resolutions for those on mobile 10k x 7k pixels and such):
https://github.com/MauriceGit/Delaunay_Triangulation/tree/ma...
[+] [-] shaneos|10 years ago|reply
In case C++ is your jam, ten years or so ago I adapted Steven Fortunes highly efficient sweep line algorithm to C++.
Some info here - http://www.skynet.ie/~sos/mapviewer/voronoi.php
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
Code on Sourceforge (yes, 10 years ago people) - http://www.skynet.ie/~sos/mapviewer/voronoi.php
[+] [-] EllipticCurve|10 years ago|reply
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 :)
[+] [-] ingenter|10 years ago|reply
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.
http://simonschreibt.de/gat/homeworld-2-backgrounds/
[+] [-] EllipticCurve|10 years ago|reply
Yes, it's possible and quite easy to do so :)
I make a list of things to do - Homeworld 2 is on it ;)
[+] [-] NarcolepticFrog|10 years ago|reply
Looks like yours is quite a bit more polished :)
[+] [-] unknown|10 years ago|reply
[deleted]
[+] [-] EllipticCurve|10 years ago|reply
[+] [-] jheriko|10 years ago|reply