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!
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 and a List, you simply create a new mesh like this:
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.
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 :
private void Iterate()
{
if (m_voronoi != null)
{
for (int i = 0; i < m_points.Count; ++i)
{
List<LineSegment> lineSegments = m_voronoi.VoronoiBoundaryForSite(m_points[i]);
Vector2 center = Vector2.zero;
for (int j = 0; j < lineSegments.Count; ++j)
{
center += ((Vector2)lineSegments[j].p0 + (Vector2)lineSegments[j].p1) * 0.5f;
}
center /= (lineSegments.Count);
m_points[i] = center;
}
m_voronoi.Dispose();
}
m_voronoi = new Delaunay.Voronoi(m_points, null, new Rect(0, 0, m_mapWidth, m_mapHeight));
m_edges = m_voronoi.VoronoiDiagram();
}
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 ?
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 lineSegments in class
declare this in class Vector2 center = Vector2.zero;
instead of new Rect(), reuse one declared in class level
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.
Hello. I have a simple question. How to know if a point in inside a site ?
Something like
List<Site> sites = voronoi.SitesIndexedByLocation;
Vector2f myPoint = new Vector2f(124,35);
foreach(Site s in sites)
{
if(s.Contains(myPoint)
Debug.Log($"your point in inside site {s.siteIndex}");
}
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.
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?
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?
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:
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?
I was reading this very interesting article by Red Blob Games about using the triangle centroids instead of the circumcenters to determine the position of the edge vertices of the voronoi cells. That way the edge vertices are more evenly spaced (in contrast to the original points being more evenly spaced by the lloyd relaxation).
Here is the blog article:
We have been using this thread’s amazing delauney library in our game for the entire duration of prototyping, but now I would love to get rid of the “short” cell edges that it (and all circumcenter based voronoi algorithms) produce.
When I dug through the code, I noticed that the triangles can be stored in the Fortunes Algorithm, but I’m not sure at what point in the algorithm I could insert the bit that lets me use the centroids instead of the circumcenters. I did not see any literal mentions of circumcenters. If anyone has a pointer or solution I would be super glad, and I’m sure it would be helpful for others too.
