Voronoi region neighbours

May 12, 2014 at 8:15 AM
Hello,

Is there an easy way to find a voronoi regions neighbouring regions? I'm going to need this data later on for A* pathing.

The way I'm currently doing it is incredibly hacky (2x for loops of all regions checking for shared verts)... there must be an easier way.

Any help greatly appreciated

Rob
Coordinator
May 12, 2014 at 8:59 AM
Edited May 12, 2014 at 9:07 AM
At the moment, there's no easy way to do this. You should probably convert the whole diagram to a more standard data structure, like a DCEL (this is actually on my todo list).

Feel free to post some code, and I will have a look at it.

And be aware that there's an open issue regarding the Bounded Voronoi diagram.
May 12, 2014 at 9:13 AM
I imagine DCEL would give the performance boost I need - looks pretty complex though ! :S

Doesn't the Voronoi calculation have to take into account neighbouring points in order to form its regions? If so, wouldn't there be a way of snagging the points at that level?

This is being done in Unity (each region is a tile for the game). I'm currently converting the region points into a convex Polygon then, for each region, checking for overlap with other polygons. The Math lib I'm using is pretty quick ... but the whole thing is still a hack - works though !
IEnumerator GetConnections()
{
    int counter = 0;
    for (int a = 0; a < tiles.Count; a++)

    {
        // Hack to ease the load... 
        counter++;
        if (counter % 500 == 0 )
        {
            yield return null;
        }
        for (int b = 0; b < tiles.Count; b ++)
        {
            bool join = Intersection.TestConvexPolygon2ConvexPolygon2(tiles[a].poly, tiles[b].poly);
            if (join == true)
            {
                tiles[a].AddNeighbour(tiles[b]);
            }
        }
    }
}
Coordinator
May 12, 2014 at 10:32 AM
Edited May 12, 2014 at 10:33 AM
Doesn't the Voronoi calculation have to take into account neighbouring points in order to form its regions? If so, wouldn't there be a way of snagging the points at that level?
Sure. Just have a look at Voronoi.cs, Line 162:
// Go counterclockwise until we reach the border or the initial triangle.
while (f_next.triangle != Mesh.dummytri)
{
    // Add circumcenter of current triangle
    vpoints.Add(points[f.triangle.id]);

    // [...]

    f_next.Copy(ref f);
    f_next.OnextSelf();
}
The ID of vertex f.Apex() is actually the ID of the neighbouring Voronoi cell (across the edge points[f.triangle.id] -> points[f_next.triangle.id]). This information could easily be stored in a Dictionary<int, VoronoiRegion> (the bounded Voronoi case could be quite a bit more complex, though).
Coordinator
May 12, 2014 at 10:38 AM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
May 12, 2014 at 12:17 PM
That seems straight forward enough - I'll give it a whirl :)

Regarding the open issue with the Bounded Voronoi diagram, could that be the reason why some generated region verts (usually in the .Y axis) are way off?

This is an extreme example where I'm subdividing voronoi regions into smaller regions. A bit of a mess...

Image
May 12, 2014 at 1:14 PM
You suggestion worked perfectly. I did a final check to see if the region had been previously culled (I got rid of regions that were too big, usually on the outder edges of the land generation. Looks a bit like this

Image


Thank you for all your help :)
Coordinator
May 12, 2014 at 5:37 PM
I have added the neighbor information to the (standard) Voronoi diagram, so you can now do something like
foreach (var region in voronoi.Regions)
{
    foreach (var vertex in region.Vertices)
    {
        // The regions vertices are ordered counter-clockwise, so for
        // each vertex, there's a well-defined edge starting at that vertex.
        // The GetNeighbor method will return the region across the edge.
        var neighbor = region.GetNeighbor(vertex);

        // Be aware, that for an unbounded Voronoi region, the last vertex
        // has no adjacent edge, so GetNeighbor will return null.
    }
}
For the above images you used the BoundedVoronoi code? I actually never got infinite edges. The issues I have are duplicate vertices and vertices at wrong locations (but still inside the polygon).
May 12, 2014 at 7:26 PM
Each region has the 'bounded' bool as true, if that's what you mean?

I tried building the Voronoi with :
_voronoi = new TriangleNet.Tools.BoundedVoronoi (_mesh);

but it threw up an error, so I'm just using:

_voronoi = new TriangleNet.Tools.Voronoi (_mesh);

To get rid of the massive regions I just check the distance between the verts bounds. Seemed the quickest way of getting results until I can make a contained region. These tiles are then excluded when hunting for neighbours.
// Hack to cull enormous regions 

            bool freakLength = false;
            for (int i = 0; i < vertsV3.Count; i++)
            {
                if (i != vertsV3.Count - 1)
                {
                    float distance = Vector3.Distance (vertsV3 [i], vertsV3 [i + 1]);
                    if (distance > 2000)
                    {
                        freakLength = true;
                    }
                }
                else
                {
                    float distance = Vector3.Distance (vertsV3 [i], vertsV3 [0]);
                    if (distance > 2000)
                    {
                        freakLength = true;
                    }
                }

                vertsV2 [i] = new Vector2 ((float)vertsV3 [i].x, (float)vertsV3[i].z);
            }



            //   float area = poly.CalcArea ();

            if (freakLength == false)
            {
                Polygon2 poly = new Polygon2 (vertsV2);
                VoronoiTile tile = new VoronoiTile(poly, region, this);
                tiles.Add (tile);
                regionToTileDictionary.Add(region, tile);

            }
This is all fine when I'm making the tiles individually (from region vert list) however if I make one giant mesh using this : https://triangle.codeplex.com/discussions/445376 method I get infinite sides.

Image


If you can think of a quicker method for culling them I'd love to hear it :)
Coordinator
May 12, 2014 at 10:09 PM
Edited May 12, 2014 at 10:17 PM
  1. Are you using the latest source code?
  2. What kind of error did you get with the BoundedVoronoi code?
  3. Did you use mesh.Behavior.ConformingDelaunay = true?
I don't know if I'll add the neighbouring information to the BoundedVoronoi code anytime soon, but the normal Voronoi diagram is quite a bad choice for polygon meshes. As you already said: it get's hacky.
May 13, 2014 at 1:17 PM
1) yup
2) After using :
int totalPoints = tilesPerAxis * tilesPerAxis;
        geometry = new TriangleNet.Geometry.InputGeometry (totalPoints);
// Place noise
        for (int x = 0; x < tilesPerAxis; x ++)
        {
            for (int z = 0; z < tilesPerAxis; z++)
            {
                float valueX = filterX.GetValue (x, z, seedX);
                valueX = (valueX + 1.0f) * .5f;
                float valueZ = filterZ.GetValue (z, seedZ, x);
                valueZ = (valueZ + 1.0f) * .5f;

                float xPos = valueX * chunkWidth;
                float zPos = valueZ * chunkHeight;

                geometry.AddPoint (xPos, zPos);

                //Vector3 worldPos = chunkStartPoint + new Vector3 (xPos, 0, zPos);
                //Draw.XHere(worldPos, 5f,Color.red,false);
            }
        }

        TriangleNet.Mesh _mesh2 = new TriangleNet.Mesh ();
        _mesh2.Behavior.ConformingDelaunay = true;
        _mesh2.Triangulate (geometry);
        TriangleNet.Tools.BoundedVoronoi _voronoi2 = new TriangleNet.Tools.BoundedVoronoi (_mesh2);
I get:
IndexOutOfRangeException: Array index is out of range.
(wrapper stelemref) object:stelemref (object,intptr,object)
TriangleNet.Tools.BoundedVoronoi.ConstructBoundaryBvdCell (TriangleNet.Data.Vertex vertex) (at Assets/Libs/Triangle/Tools/BoundedVoronoi.cs:458)
TriangleNet.Tools.BoundedVoronoi.Generate () (at Assets/Libs/Triangle/Tools/BoundedVoronoi.cs:98)
TriangleNet.Tools.BoundedVoronoi..ctor (TriangleNet.Mesh mesh, Boolean includeBoundary) (at Assets/Libs/Triangle/Tools/BoundedVoronoi.cs:54)
TriangleNet.Tools.BoundedVoronoi..ctor (TriangleNet.Mesh mesh)
VoronoiWorld+<Build>c__Iterator51.MoveNext () (at Assets/Voronoi/VoronoiWorld.cs:102)
UnityEngine.MonoBehaviour:StartCoroutine(String)
VoronoiWorld:Start() (at Assets/Voronoi/VoronoiWorld.cs:61)
Should I be defining the segments manually?
Coordinator
May 13, 2014 at 2:26 PM
Edited May 13, 2014 at 2:38 PM
Are you using the release from the Downloads section (dated Jun 18, 2013) or from the Source Code section (latest changeset May 12, 2014)?
Should I be defining the segments manually?
Yes, segments have to be added manually.
May 13, 2014 at 3:40 PM
Sorry, from the Downloads section - should I use latest source?
Yes, segments have to be added manually.
Well, I think that's my problem :) Is there a simple method to cycle through points and generate segments?
Coordinator
May 13, 2014 at 4:26 PM
Sorry, from the Downloads section - should I use latest source?
Yes.
Well, I think that's my problem :) Is there a simple method to cycle through points and generate segments?
I don't know how your geometry is defined, but take a look at the InputGeometry documentation. It should be pretty simple to add the segments.