Delaunay - Voronoi Diagram library for Unity

I needed a delaunay library for my own, but didn't found any that was meeting my requirment, so I ended up porting as3delaunay library to c#. I also added a Lloyd relaxation function to it.

So I though that I could post it. If anyone need it, go ahead it's completly free.

Download link:csDelaunay Library

It's pretty straighforward to use, but here is an exemple:

Code (csharp):

1.  
2. using UnityEngine;
3. using System.Collections.Generic;
4.  
5. using csDelaunay;
6.  
7. public class VoronoiDiagram : MonoBehaviour {
8.  
9.     // The number of polygons/sites we want
10.     public int polygonNumber = 200;
11.  
12.     // This is where we will store the resulting data
13.     private Dictionary<Vector2f, Site> sites;
14.     private List<Edge> edges;
15.  
16.     void Start() {
17.         // Create your sites (lets call that the center of your polygons)
18.         List<Vector2f> points = CreateRandomPoint();
19.        
20.         // Create the bounds of the voronoi diagram
21.         // Use Rectf instead of Rect; it's a struct just like Rect and does pretty much the same,
22.         // but like that it allows you to run the delaunay library outside of unity (which mean also in another tread)
23.         Rectf bounds = new Rectf(0,0,512,512);
24.        
25.         // There is a two ways you can create the voronoi diagram: with or without the lloyd relaxation
26.         // Here I used it with 2 iterations of the lloyd relaxation
27.         Voronoi voronoi = new Voronoi(points,bounds,5);
28.  
29.         // But you could also create it without lloyd relaxtion and call that function later if you want
30.         //Voronoi voronoi = new Voronoi(points,bounds);
31.         //voronoi.LloydRelaxation(5);
32.  
33.         // Now retreive the edges from it, and the new sites position if you used lloyd relaxtion
34.         sites = voronoi.SitesIndexedByLocation;
35.         edges = voronoi.Edges;
36.  
37.         DisplayVoronoiDiagram();
38.     }
39.    
40.     private List<Vector2f> CreateRandomPoint() {
41.         // Use Vector2f, instead of Vector2
42.         // Vector2f is pretty much the same than Vector2, but like you could run Voronoi in another thread
43.         List<Vector2f> points = new List<Vector2f>();
44.         for (int i = 0; i < polygonNumber; i++) {
45.             points.Add(new Vector2f(Random.Range(0,512), Random.Range(0,512)));
46.         }
47.  
48.         return points;
49.     }
50.  
51.     // Here is a very simple way to display the result using a simple bresenham line algorithm
52.     // Just attach this script to a quad
53.     private void DisplayVoronoiDiagram() {
54.         Texture2D tx = new Texture2D(512,512);
55.         foreach (KeyValuePair<Vector2f,Site> kv in sites) {
56.             tx.SetPixel((int)kv.Key.x, (int)kv.Key.y, Color.red);
57.         }
58.         foreach (Edge edge in edges) {
59.             // if the edge doesn't have clippedEnds, if was not within the bounds, dont draw it
60.             if (edge.ClippedEnds == null) continue;
61.  
62.             DrawLine(edge.ClippedEnds[LR.LEFT], edge.ClippedEnds[LR.RIGHT], tx, Color.black);
63.         }
64.         tx.Apply();
65.  
66.         this.renderer.material.mainTexture = tx;
67.     }
68.  
69.     // Bresenham line algorithm
70.     private void DrawLine(Vector2f p0, Vector2f p1, Texture2D tx, Color c, int offset = 0) {
71.         int x0 = (int)p0.x;
72.         int y0 = (int)p0.y;
73.         int x1 = (int)p1.x;
74.         int y1 = (int)p1.y;
75.        
76.         int dx = Mathf.Abs(x1-x0);
77.         int dy = Mathf.Abs(y1-y0);
78.         int sx = x0 < x1 ? 1 : -1;
79.         int sy = y0 < y1 ? 1 : -1;
80.         int err = dx-dy;
81.        
82.         while (true) {
83.             tx.SetPixel(x0+offset,y0+offset,c);
84.            
85.             if (x0 == x1 && y0 == y1) break;
86.             int e2 = 2*err;
87.             if (e2 > -dy) {
88.                 err -= dy;
89.                 x0 += sx;
90.             }
91.             if (e2 < dx) {
92.                 err += dx;
93.                 y0 += sy;
94.             }
95.         }
96.     }
97. }      
98.  

More info on Voronoi Diagram: Voronoi diagram wiki
And lloyd relaxation: Lloyd's_algorithm wiki

and another time the library download link: csDelaunay Library

 

I was just in the process of rewriting this to try out some map stuff from the Polygonal Map Gen article by Amitp.

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

You saved me quite a bit of time. Thank you.

 

Very cool! Does this work with iOS too (AOT compiling)?

 

It looks like the triangulation is choking somewhere along the line if you try and pass it square or hexagon points. I haven't had a chance to dig deeper to find out where though. Just a head's up.

 

Ok thanks for letting me know. I had only tested it with random point. I'll try to take a look into it once I can.

 

I know this thread is a bit old, but I was just working with an implementation of this code, and I wondered if anyone else was having the problem where it only works some of the time. Occasionally, without Lloyd Relaxation applied, the resulting texture is a mess. With the relaxation algorithm, it will throw an error.

Other times it works brilliantly and couldn't be more perfect for what I'm working on, but I can't sort out what the issue is.

Thanks in advance!

 

I have this same problem. Please let me know if you have found a solution. The problem with the error is coming from (Voronoi.cs) the fact that a collection is empty, and there is part of the code attempting to access the last element. region[region.Count - 1] throws an error when region.Count = 0. I don't know why sometimes this works and sometimes this doesn't. The other issue you had I remember having too a long time ago. It was an issue with VoronoiDiagram.cs (the code he posted directly here. In it on line 85 there is:
if (x0 == x1 y0 == y1) break;

I am assuming there might have been an html encoding problem? Anyway, i originally filled it in as
if (x0 == x1 || y0 == y1) break;
got wacky results then to :
if (x0 == x1 && y0 == y1) break;
and got expected output. If anyone finds the problem with the collection being empty please let me know! (And the github author perhaps?)

On another note:
I am working on an idea where I would like each polygon to be its own unity object (so that I can work easily with hovering, clicking, changing colors and what not, instead of drawing all the polygons onto one plane. Anyone have any ideas?

 

Hey everyone. Pardon the dumb question, but after I generate a voronoi diagram as a data structure (e.g.: a series of points / edges / triangles as Vector2's), how do I actually go about rendering different textures in each tile?

http://forum.unity3d.com/threads/i-...no-idea-how-to-render-it.291939/#post-1926295

 

https://github.com/jceipek/Unity-delaunay

I've successfully implemented this library for meshes creation. Nice!
Had to add corners manually, since there were no corners inside vertices/edges arrays.

But I still getting this error sometimes:
in VoronoiCellVertex.cs

Code (CSharp):

1. /** this is ONLY an error if all 3 edges existed; otherwise its an expected outcome */
2. Debug.LogError ("Cannot find another edge from this vertex (" + this + ") that borders cell: " + targetCell);

in such situation diagram looks like this (Gizmos)

you can see unfinished sites on the right.

I can control it with more predictable points. But I would like to choose completely random points at first place.



Update:
https://github.com/adamgit/Unity-delaunay works better but still has same problem

Code (CSharp):

1. Debug.LogError ("Cannot find another edge from this vertex (" + this + ") that borders cell: " + targetCell);

and yes. map doesn't look right again





Could somebody help me, please?

 

I had completly forgotten about that Delaunay implementation I had done, sorry guys.

I finally corrected the error with the Lloyd relaxation (the index out of bounds exception). The GitHub should now be bug free (crossing my fingers).

And yea, exactly just like lordnorth found out

Code (csharp):

1.  
2. if (x0 == x1  y0 == y1) break;
3.  

in the sample code I gave in the main post, was meant to be

Code (csharp):

1.  
2. if (x0 == x1 && y0 == 1) break;
3.  

Corrected it in my post.

If you find any other bug let me know plz. I should now receive email notification if someone post in this thread.

 

Hello,

As you asked, there is still a bug with "not random" points. I play a bit with random points with no problems, but I try to control the generation with square points and other regular shape but the diagram was messed up !

I'll give a more detail example in the day.

 

I give voronoi this list of point (as a List<Vector2> object) :
1,1 3,3 5,5 7,7 7,1 3,5 5,3 1,7

I render the diagram, everything works fine :

I just add a point in the center (coord 4,4), and here is the problem !


(we don't see the red point at the center because edges are drawing after sites centers)

At first I thought about a scale problem, as my numbers are small, but whatever zoom I apply the problem is still the same. (current textures have x8 zoom)

So here is a test case that show the problem.
I'll try to find the fix, but if you have an idea and still look by here you surely save me some time !!
Fortunes algorithm makes me fear !

 

I just find the problem !
in vertex.cs you've got a line to test if halfedge are parallel :

Code (CSharp):

1. line 85:      if (Math.Pow(-1.0, 10) < determinant && determinant < Math.Pow(1.0, -10)) {

This looks strange, I put

Code (CSharp):

1. line 85:      if (Math.Abs(determinant) < 0.0000000001f) {

And the triangulation doesn't mess up anymore !!

 

Is there a way to create a mesh from each tile generated by this algorithm?

 

Sorry for bump a really old thread, but I think this is very useful for some things! And I think it's better to reopen a created thread than create an other one about the same topic.

Well, what I want to say is that I need to fill a site with one color. I mean, set a color to all differents geometric sites. ¿Do you know how?

 

I don't know if original author is still watching this topic, but may be someone else also can help me. I used csDelaunay Library by PouletFrit and find some strange bug there. Sometimes, I as far as I could understand, Vertex calculated wrong and I get Site with 0 Edges, some (I think this is the remains of original Edges of the Site) EdgeOrientation and 0 Region points. I couldn't find a place where this is happening, but may be someone can help me? This situation is more common if I use a lot random points for Site centers, but sometimes it happen even with 300 points.

Another case is that sometimes edge ends also calculated wrong and this leads to really messed up edges in diagram. I think that the cause of these two cases is the same.

 

Did anyone figure out how to retrieve all the edges of each site, not only the ones within texture space? I'm trying to make the voronoi cells clickable but while it's easy to do for the inner ones by retrieving their key-value.Value.Edges list, the outer-most ones can't be processed that way as they only include those few edges that are visible so you can't close the polygon collider.

 

Have you tried adding border cells around your graph and ignoring those cells?

Or .. this article is rather dense but touches on it: http://blog.ivank.net/fortunes-algorithm-and-implementation.html

Can you select the 'infinite' edges of the diagram, iterate through and basically just do a simple triangulation to close it? You would basically be connecting edge pairs together in a clockwise(?) motion around the graph.

 

for 2017, although marked as not maintained,

this:

https://github.com/jceipek/Unity-delaunay

does seem to be the most reliable / usable Delauney triangulation, for Unity3D !

Has anyone looked through these lately and found the most reliable one?

 

Hi everyone!
So I'm working on an editor tool that allows the user to draw closed bezier splines and then generates a flat mesh that fills in this shape. I simply walk along these beziers and get a point at regular intervals to define the outline, and figured I could generate a mesh with these. Seems like an easy thing for Delaunay libraries, right?
Unfortunately I'm not much of a programmer and simply can't wrap my head around how to use these libraries.
I'm currently trying out JCeipek's library (linked by Fattie up here) but since his demo only shows how to get a Voronoi web and show nothing about the Delaunay part of his library as far as I can tell, I'm not exactly helped with that.
If any of you could tell me what exactly I need to use of these libraries I'd be super grateful.

IDEALLY, I'd like a method int[] GenerateTrianglesWithDelaunay(Vector3[] verts) that simply takes all my verts and gives me the data I can immediately plug in Unity's Mesh.Triangles.

 

heh - that is *very difficult* my man. My company would charge a client six figures to do that, in context.

Your problem is let us say a bit beyond Delauney per se. You have a lot of work ahead of you

Is it possible this would help to begin with? Since your post is, really, not on this topic, perhaps just start a new post ..

http://www.cs.cmu.edu/~quake/triangle.html

Notice that project includes a "mesh generator" (the thing you want) and a Delauney system (not, really, what you want). I suggest a new topic.

 

Hi Fattie,
Thanks for clearing that up, seems I really misunderstood what Delauney entails then. I'll take a look at Triangle!

Late-night edit: with a little more searching around I found people who could show me to convert Triangle's stuff to Unity. Thanks again for pointing me in the right direction, Fattie!

 

You should've shared this stuff =)

 

Hey!
Well, it's not really on-topic here, but I'll help you on your way at the risk of facing everyone's ire.
As long as you're trying to make 2D meshes it's really not too complicated.

Download one of the Triangle conversions for Unity (some assets like Anima2D come shipped with it as well).
I believe I used this one: https://github.com/rslnautic/TriangleNet-Unity
inside you find a Triangulation class with static method Triangulate.
If you feed that method a list of points (and optionally another list of a list of points for holes) it'll return a List<int> and a List<Vector3>, you simply create a new mesh like this:

var mesh = new Mesh();

mesh.SetVertices(List<Vector3>);

mesh.triangles = List<int>.ToArray();

And then you save this mesh to your assets for easy access.

 

FYI in case someone else hits this. Triangle.Net uses id's tied to GetHashCode(), and will start producing duplicate verts once you create more then int max. And it has a lot of dependent code I thought it should be an easy fix but it's not.

 

Hi everyone !

First, thanks for all of this.

Second, I've a problem for iterate a big graph. It's take a long time... 95s for an iteration with 10000 points, and I would like more...
I'm not sure if it's the good method, but I've produce this function for iterate :

Code (CSharp):

1.  
2. private void Iterate()
3.     {
4.         if (m_voronoi != null)
5.         {
6.             for (int i = 0; i < m_points.Count; ++i)
7.             {
8.                 List<LineSegment> lineSegments = m_voronoi.VoronoiBoundaryForSite(m_points[i]);
9.  
10.                 Vector2 center = Vector2.zero;
11.  
12.                 for (int j = 0; j < lineSegments.Count; ++j)
13.                 {
14.                     center += ((Vector2)lineSegments[j].p0 + (Vector2)lineSegments[j].p1) * 0.5f;
15.                 }
16.  
17.                 center /= (lineSegments.Count);
18.  
19.                 m_points[i] = center;
20.             }
21.  
22.             m_voronoi.Dispose();
23.         }
24.  
25.         m_voronoi = new Delaunay.Voronoi(m_points, null, new Rect(0, 0, m_mapWidth, m_mapHeight));
26.         m_edges = m_voronoi.VoronoiDiagram();
27.     }
28.  

It's appear that is VoronoiBoundaryForSite who take cpu time. (Multiply by the loop, of course)

It's a good method ?
Could you help me for optimize this ?

Thanks in advance.

 

did you use deep Profiler to see whats the most expensive part?


some micro-optimization ideas:
- cache counts for both loops: for (int i = 0,len = m_points.Count; i < len; ++i)
- work with .x .y .z separately (or don't use vectors at all if possible, just floats like center_x, center_y.., but then would need to modify rest of the code too..)
- is that cast needed? (Vector2)
- declare List<LineSegment> lineSegments in class
- declare this in class Vector2 center = Vector2.zero;
- instead of new Rect(), reuse one declared in class level

 

Thanks mgear,

I don't use the deep Profiler, but with logs it's appear clearly that is the method VoronoiBoundaryForSite. Inside this method it've some compute, but I don't think is very optimizable.
So, first, I want to know if my method for iterate the voronoï graph (like the Lloyd wiki link) is a good way ?
If it's ok, I process to micro-optimization.

Also, thanks for all of your offer. I try that !

 

Hello. I have a simple question. How to know if a point in inside a site ?
Something like

Code (CSharp):

1. List<Site> sites = voronoi.SitesIndexedByLocation;
2. Vector2f myPoint = new Vector2f(124,35);
3.  
4. foreach(Site s in sites)
5. {
6.   if(s.Contains(myPoint)
7.     Debug.Log($"your point in inside site {s.siteIndex}");
8. }

 

Hello, there is a problem that I seem to have with making the library work in the way I want it. I have narrowed down the problem and it seems that sometimes edges that are supposed to be connected to each other (the way I am trying to figure that out is by seeing if they share a vector2f between them) are instead displayed as not being connected at all. Sometimes they accidentally create a vector2f that is ever-so-slightly different, but apparently that is more than enough to have the program register them as completely different.

Edit: I will remedy my side of the problem by roughly approximating the position of the corners, since there is no need to be perfect in position, but to keep these things from happening in the future, I suggest looking into this bug.

 

Hey guys,

A bit of a necro, but I'm facing a peculiar issue with the library, when sites.count is 2 or 3.

When I create diagram for small number of cells, like 2 or 3, the cells tend to overlapp.
The site coords is fine (both sites are in their respective - separated positions - visible on the screenshot as numbers), but the second site has the same vertices / edges as the first one.

I spend 2 days trying to debug it, and honestly have no clue how to deal with it.
Could you please point me in the right direction?



On the second screenshot you can see both sites manualy separated, to better visualise the issue:



If you could help that would mean a world to me, thanks!

 

Apologies another necro of this thread.... just been experimenting with this library and I'm trying to understand if this is a bug.... here is a test with 9 points to show the issue....



The Voronoi digram looks fine, but my understanding is that the far right edge from the Delaunay edges should not be there... it is unnessary as all points are successfully included in the triangulation without that edge.

Can anyone who knows Delaunay better than me confirm if I am correct that this edge should not be there?

Thanks.

 

> Can anyone who knows Delaunay better than me confirm if I am correct that this edge should not be there?

OK did a bit more research and I think I can mostly answer my own question.. appears that this edge is added because Delaunay triangulaton creates a convex hull. According to wikipedia:

The problem of finding the Delaunay triangulation of a set of points in d-dimensional Euclidean space can be converted to the problem of finding the convex hull of a set of points in (d + 1)-dimensional space.

So that edge exists to make the resulting triangulation boundaries convex, hence is not a bug.

FWIW, in case some newbie like me reads this, my assumption was that the Delaunay edges would represent a list of site "neighbors". This does appear true... the above image is confusing because although the top left and bottom right sites dont' appear to be neightbours if the lines where extending beyond the arbitrary yellow border they would be. It's related to ubounded vs bounded sites and is explained reasonably well in this video:

Here is a dodge image of what I am talking about....

 

Hello everyone,

I'm quite new to unity and tried cloning this library in my unity project, I cloned it, placed it in my assets and ran the commands as said in the readme file but when I open the project, I get a number of warnings/ compilation errors. What is the correct way to import this in unity?