Sign in to follow this  
ZeiN

Voronoi / Cellular newbie problem

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[i][0]) ** 2 + (y - point[i][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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by ZeiN
That'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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this