Search Unity

Delaunay - Voronoi Diagram library for Unity

Discussion in 'Assets and Asset Store' started by PouletFrit, May 30, 2014.

  1. PouletFrit

    PouletFrit

    Joined:
    May 26, 2014
    Posts:
    14
    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.  
    $noRelaxtion.jpg
    $5lloydIterations.jpg

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

    and another time the library download link: csDelaunay Library
     
    Last edited: Sep 23, 2015
  2. Keshire

    Keshire

    Joined:
    Dec 10, 2012
    Posts:
    16
    Fangh likes this.
  3. hatuf

    hatuf

    Joined:
    Jan 6, 2013
    Posts:
    8
    Very cool! Does this work with iOS too (AOT compiling)?
     
  4. Keshire

    Keshire

    Joined:
    Dec 10, 2012
    Posts:
    16
    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.
     
  5. PouletFrit

    PouletFrit

    Joined:
    May 26, 2014
    Posts:
    14
    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.
     
  6. sukAta

    sukAta

    Joined:
    Jan 24, 2013
    Posts:
    1
    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!
     
  7. lordnorth

    lordnorth

    Joined:
    May 17, 2014
    Posts:
    1
    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?
     
  8. Deleted User

    Deleted User

    Guest

    Lohoris2 likes this.
  9. UniDro

    UniDro

    Joined:
    Nov 21, 2014
    Posts:
    25
    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?
     
    Last edited: Feb 19, 2015
  10. PouletFrit

    PouletFrit

    Joined:
    May 26, 2014
    Posts:
    14
    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.
     
    RedEarth, jhocking and Lohoris2 like this.
  11. dhostin

    dhostin

    Joined:
    Aug 10, 2015
    Posts:
    3
    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.
     
  12. dhostin

    dhostin

    Joined:
    Aug 10, 2015
    Posts:
    3
    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 !! :D
    Fortunes algorithm makes me fear !
     
  13. dhostin

    dhostin

    Joined:
    Aug 10, 2015
    Posts:
    3
    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 !!
     
    Last edited: Oct 23, 2015
    Alekxss likes this.
  14. astinog

    astinog

    Joined:
    Jan 10, 2014
    Posts:
    2
    Is there a way to create a mesh from each tile generated by this algorithm?
     
    Lohoris2 likes this.
  15. Edgargaza

    Edgargaza

    Joined:
    Nov 11, 2012
    Posts:
    3
    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?
     
  16. Fearen

    Fearen

    Joined:
    Jul 5, 2016
    Posts:
    1
    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.
    csDelaunay_bug1.jpg
    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.
    csDelaunay_bug2.jpg
     
  17. Tigro

    Tigro

    Joined:
    Apr 25, 2014
    Posts:
    58
    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.
     
  18. jason-fisher

    jason-fisher

    Joined:
    Mar 19, 2014
    Posts:
    133
    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.
     
  19. Fattie

    Fattie

    Joined:
    Jul 5, 2012
    Posts:
    469
    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?
     
  20. Yandalf

    Yandalf

    Joined:
    Feb 11, 2014
    Posts:
    468
    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.
     
  21. Fattie

    Fattie

    Joined:
    Jul 5, 2012
    Posts:
    469
    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.
     
    Yandalf likes this.
  22. Yandalf

    Yandalf

    Joined:
    Feb 11, 2014
    Posts:
    468
    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!
     
    Last edited: Jan 31, 2018
  23. Phoera

    Phoera

    Joined:
    Mar 10, 2015
    Posts:
    9
    You should've shared this stuff =)
     
  24. Yandalf

    Yandalf

    Joined:
    Feb 11, 2014
    Posts:
    468
    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.
     
    Phoera likes this.
  25. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    3,311
    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.
     
  26. Rekyem

    Rekyem

    Joined:
    Jun 23, 2014
    Posts:
    13
    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.
     
  27. mgear

    mgear

    Joined:
    Aug 3, 2010
    Posts:
    7,113
    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
     
  28. Rekyem

    Rekyem

    Joined:
    Jun 23, 2014
    Posts:
    13
    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 !
     
  29. Fangh

    Fangh

    Joined:
    Apr 19, 2013
    Posts:
    122
    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. }
     
  30. crazy4bricks

    crazy4bricks

    Joined:
    Mar 31, 2020
    Posts:
    1
    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.
     
  31. omx-jonson

    omx-jonson

    Joined:
    Mar 23, 2014
    Posts:
    10
    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!
     

    Attached Files:

unityunity