Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
I'm trying to generate voroni diagrams which works fine, now I need to subdivide the voroni diagrams but ignore the bounding boxes that I define. Hence subdividing all the points that are outside predefined 2D Bounding boxes. I'm looking for an algorithm for that purpose.
PS: The picture is not an accurate subdivision, but I hope you get the idea.
Game Programming is the process of converting dead pictures to live ones .
AhmedSaleh said: now I need to subdivide the voroni diagrams but ignore the bounding boxes that I define. Hence subdividing all the points that are outside predefined 2D Bounding boxes.
A point can't be subdivided. So assume your goal is to subdivide the regions fro each point? But only outside the box?
This could be as simple as adding random points, but rejecting those inside the box. And then calculate new regions. But there would be need to calculate regions before having all the new points at all. So i guess that's not really what you want.
So you want certain shapes, e.g. some boxes or circles, where no points appear? This would be as easy as i've said. Just, simple algorithms based on samples in a regular grid (e.g. Worley Noise), would no longer work so quickly. To find all adjacent points, you would need to make the search radius as large as the largest shape.
But the major issue i expect is results not pleasing to the eye if you generate your points just randomly. Some points become very close to each other, causing irregular voronoi regions which don't look good. They are long ant thin for example.
To avoid this, we can want to use points with a Poisson Disk distribution. The image above looks like they did this. And you want variable density of points as well, which can translate to having poisson samples of variable radius for the disk.
Some images to make clear what i mean:
You can imagine the right points give much nicer voronoi regions.
Example for non uniform denisty distributions. You would get large regions in the bright sections, and small regions in the dark sections. (There should be a zoom to the image so we could see the greys are caused from variable density of just points.
This is actually a better example for that.)
Poisson Disk Samples are easy to generate by starting with random samples and then doing a collision alike relaxation technique. But for realtime this would be challenging.
Basically I want to generate a pattern like the following:
I'm not exactly sure what you are looking for. Is it this last pic you posted? It seems like you are just doing a Voronoi diagram but increasing the size of the dividing lines and making them hollow. I do something like that here, but they aren't so wide and aren't hollow in this case:
This is done in a rather complicated shader that is designed to do detailed Voronoi over a planet sized sphere. Most of the complexity however just as to deal with the fact that it's a sphere and I have to do this over a very large area with minimal double precision support. If you just want to make a Voronoi pattern with wide edges, it should be pretty simple. Of course, I'm doing this on a bit map. if you trying to generate actual edges with points and lines, it's a different algorithm.
The other thing that's different is as I mentioned your transition lines are hollow with draw edges on the outside. I think this is probably doable too. You might need a few more checks for each pixel. My code uses a triangular jitter grid to generate the initial points and returns the 7 closest points to any pixel. You might be able to use something similar. For non-spherical stuff a normal jitter grid should be OK.
Gnollrunner said: I'm not exactly sure what you are looking for.
I think what's special is that there are no points generated inside the 3 circles, causing smaller and larger regions (although not very visible in the final result). That's where my proposals come from at least.
I'm gonna use that library, the author suggested to use that method, but he doesn't answer anymore, do you have an idea on how to do that using his clipping approach ?
AhmedSaleh said: do you have an idea on how to do that using his clipping approach ?
I neither know what you are missing from the library, nor how it works.
But personally i would do it slightly different: Make a Voronoi Triangulation (the blue lines), but then only create the Dual of the resulting mesh (connecting triangle centers across edges). Unlike Voronoi Regions, this avoids the cases of having some very short edges and looks more regular, and it's also easier to do.
