Dual graph in progress

I've been working on a Voronoi-Delaunay dual graph for most of this week and since this is the best results I've had using my own code, I'm curious if anyone would be interested in it. I'm sure there is plenty that needs to be tightened up, but so far it's fairly light weight.

It's using a Bowyer-Watson algorithm, so it's ludicrously easy to understand. It could theoretically be adding points in real time, although I'll need to restructure most of how the graph is extracted.

So anyone interested? It's got plenty of room for improvement since it's mostly just held together with bailing wire, so I would like to know what other people would want out of it. Another thought is a tutorial/demo, as an ex post facto wish fulfillment, which wouldn't be too complicated as most of this probably isn't even 400 lines of code.

Update: It's now safe for human consumption... at least as far as government work is concerned.

All you need to do is slap one of the generator scripts on an empty game object and run it (possibly needing to turn gizmos on if you want to see anything in the game view). The way the dual graph is generated is pretty straight forward, you feed it a bunch of points then give it a kick to run.

Getting data out is a tad bit more complicated. Most of the examples of what to do are in OnDrawGizmos() then GenerateMesh(). None of the examples avoid duplication (if I can remember correctly). In particular the mesh isn't contiguous, and each cell is its own entity as far as vertices are concerned.

But it's mostly there. At this point it's much more of a matter of people translating the output for their own purposes.

 

Just a quick question, what exactly is a Voronoi-Delauny dual graph and what does it do or what's it for? I genuinely have never heard of it before.

 

Delaunay triangulation is basically a graph of points connected together in a way so that every triangle it makes creates a circumcircle (a circle with all the points of a triangle on it's edge) that no other point is inside of.

A Voronoi diagram is it's opposite, where the centers of the circumcircles are used to define edges of a graph that cordons off an area around the original points. It tends to look very cellular and organic, literally. http://pcg.wikidot.com/pcg-algorithm:voronoi-diagram is a good example where it starts to look like skin tissue.

As for what they are used for, they usually find a lot of use in procedural generation (map generation being particularly common). It's kind of a case where once you have it, you find more uses for it like glass fracturing and so on.

 

So far there only seems to be one property of other methods that doesn't work perfectly with this. This method has a habit of not perfectly making the delaunay graph convex. Highly obtuse triangles along the outside aren't guaranteed to be made.

The delaunay graph is the green lines with the voronoi being black. The top image shows it slightly at the top, while the other image has it much more pronounced on the right. This has no impact on the voronoi graph. In fact the voronoi graph illustrates why the connection isn't being made.

There is a work around to improve accuracy, which is basically just making the graph bigger, but I don't think it would be ideal for all situations.

 

Looks great! I would love to see the ability to generate the voronoi regions constrained within the concave polygon. For example in the image above the black lines would not extend beyond the bounds created by the green lines. The immediate application I think of when I consider this is breaking a 2d mesh into pieces, but it could probably be useful for map generation or possibly for making interesting textures.

 

It wouldn't be hard to take the voronoi graph and define only the interior cells. That's just a matter of taking the circumcircles and figuring out if their centers are outside the bounds of the area that's been defined. In that case it would also be fairly easy to define constrained meshes.

I'll probably post the scripts once I've got a mesh of the voronoi graph going. The only problem for now is figuring out a good way to determine what direction the polygons are facing so that the mesh is actually face up.

 

Now with meshes... and crappy textures, but at least uv's are totally working. For now it's only making the mesh out of cells that are closed inside the defined area, so you can still get detached cells like the one on the top right. For now I may not get around to defining the false edges so that it will come out as a square though. I'm kind of just wanting to play around with height maps, now that I've got this far.

Most of the heavy lifting is done, so for now I'll be looking over the code to make it safe for human consumption.

 

It's out. Whether it's a real boy or not is a different matter.

 

i used iniqo quilez gpu voronoi formula and ported it to unity. i think its on here someplace.