# Voronoi / Cellular newbie problem

This topic is 3404 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'm a hobbyist programmer who likes to try different things (should be red as "I'm not an experimented programmer"). So I decided to try all this procedural stuff like noise and such. I did start with a Diamond-Square algorithm, works very well, but now I'm stuck on what seems to be a very basic thing : voronoi/cellular texture or any other way you like to call it. There seems to be a problem with the way I use the nearest distance point to get the pixel color but I can't find the solution. I tried numerous things without luck... Here's the python code (only the interesting part) :
	# Worley's Voronoi algorithm
def voronoi_diagram(self, region=4):

region_size = floor(self.size / region)
point = []

# Random distribution accross every region
for x in xrange(region):
for y in xrange(region):
px = int(randrange(region_size) + (region_size * x))
py = int(randrange(region_size) + (region_size * y))
point.append((px, py))

# Fill colors in
for x in xrange(self.size):
for y in xrange(self.size):

d1 = self.size
d2 = self.size

# Search for the closest point to (x,y) - brut method
for i in xrange(len(point)):
_d = sqrt((x - point[0]) ** 2 + (y - point[1]) ** 2)
if d1 > _d:
d1 = _d
elif d2 > _d:
d2 = _d

c = d2 - d1
self.image.putpixel((x, y), c)

And here's an image output (yeah, it's messed up) : So, could anyone help me with that ? It may be a stupid question but I can't resolve it... Thanks, ZeiN

##### Share on other sites
The brute-force closest point search looks suspect. Why do you need both 'd1' and 'd2'? What purpose does the if-else serve? Why do you subtract them? If you want, you can just render the distance to the closest point, and you'll get a gradient image with brighter bands where the borders are and black bands closer to the points. Or you can also associate each point with a color, and just render that point's color for all the pixels it's closest to. This will give you a very clear diagram.

Now I'm not sure how you'd do this in Python, but rendering Voronoi diagrams using a traditional rasterization approach is actually quite trivial. Let's say you're looking down at the plane containing the points. For each point, render a cone with the apex at that point, and the center axis facing away from you and parallel to your view vector, with a 45° inner angle. So long as you give all the cones a different color and a sufficiently large height and tessellation to intersect all the other cones, you'll end up with a Voronoi diagram :) If you want, you can also render the normals and do a post-process edge-detection pass to get the actual borders. See the paper Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware for details. It actually contains quite a bit of neat stuff.

##### Share on other sites
Hi,

Thanks for the answer. Actually I didn't make my first post very clear, sorry about that.

Quote:
 If you want, you can just render the distance to the closest point, and you'll get a gradient image with brighter bands where the borders are and black bands closer to the points.

Yes, it works, but it's not what i'm looking for. About the one color per point, I did it first as a test and it works, but now I'd like something like that :

I did some search and found some informations in mailing lists. This kind of voronoi gradient can be done with d2 - d1, d1 being the distance to the closest point to the pixel and d2 the second closest one. Unfortunatly, it doesn't work for me. I also found some informations here but without any implementation success. That's why I guess I'm doing something wrong in my code but can't figure out what... And I'm starting to feel dumb as it doesn't seem complicated at all in theory.

I'm using python because I like it and it makes prototyping easy for me :) I'm not doing that for a big project, I'm just toying around with procedural textures because I find them interesting. You could see that as a personnal exercise.

Your linked paper is nice too, althought it's not what I'm really trying to do.

Thanks for your help, much appreciated :)

##### Share on other sites
Quote:
 Original post by ZeiNThat's why I guess I'm doing something wrong in my code but can't figure out what...

There is a logic error in your closest point search algorithm. To really implement a brute force algorithm for finding d1 and d2, gather all the distances to a vector or an array, sort it in ascending order and take the first two elements. This is not what your current code ends up doing in practice.

##### Share on other sites
Thanks, that was the problem :)