This project is read-only.

How do I create a voronoi polygon?

May 29, 2013 at 10:14 PM
Hey :).

I try to generate all voronoi polygons. But i cant figure out how to retrieve the vertices and their triangle indices.

I need this in Unity to create a mesh.

The delaunay triangulation provides already the triangle indices and vertices (RenderData).
Is there a similiar way to get this done?

I previously tried to loop over the Voronoi.Regions and their vertices. I connected the corners and the generator with some Debug.DrawLine to see how they are generated.

But I don't get it.

Thanks in advance!
May 29, 2013 at 11:40 PM
Not exactly sure what you're trying to do:

> I try to generate all voronoi polygons. But i cant figure out how to retrieve the vertices and their triangle indices.

So you got the Voronoi diagram of a point set (or polygon?), i.e. the region information and the points. And you want to know the triangle a Voronoi vertex lies in?

> I previously tried to loop over the Voronoi.Regions and their vertices. I connected the corners and the generator with some Debug.DrawLine to see how they are generated.

If you are trying get the original triangulation back from the Voronoi diagram, this is not the right way. The Voronoi vertices are not part of the Delaunay triangulation.
May 30, 2013 at 7:50 PM
Edited May 30, 2013 at 7:57 PM
I'm sorry for my bad explanation. Second try ;)

To start with your library I created a plane mesh with the points from the delaunay diagram. It was easy to understand and it was straight forward:
        private TriangleNet.Mesh _mesh;
        private TriangleNet.Render.RenderData _renderData

        var points = 5;
        var width= 100;
        var height= 100;

        TriangleNet.Geometry.InputGeometry geometry = new TriangleNet.Geometry.InputGeometry(points);

        for (int i = 0; i < points; i++)
            {
            geometry.AddPoint(rnd.NextDouble() * width, rnd.NextDouble() * height);
        }

        _mesh = new TriangleNet.Mesh();
        _mesh.SetOption(Options.ConformingDelaunay, true);
        _mesh.Triangulate(geometry);

        _renderData.SetInputGeometry(geometry);
        _renderData.SetMesh(_mesh);

        //Unity BuildIn Mesh-Class
        UnityEngine.Mesh uMesh = new UnityEngine.Mesh();

        uMesh.vertices = _mesh.Vertices; //add the delaunay vertices to the unity mesh

        //Unity needs triangle indices to create the triangles out of the mesh vertices
        //example: [0, 1, 2,   2, 3, 1]
        //_renderData.Triangles supports already counter clockwise indices (ID) / Vertex.P0 -> this.vertices[0].id
        uMesh.triangles =  _renderData.Triangles;
With the code above I was able to create this mesh:

Image

Now I want to create a plane mesh with voronoi data. Initially I start to "debug" the diagram by connecting the the points from a region with lines. If I'm right, every center from a voronoi region (Vertex.Generator) is a point in a delaunay triangle.

My "debug" code:
        private TriangleNet.Mesh _mesh;
        private TriangleNet.Tools.Voronoi _voronoi;
        private TriangleNet.Render.RenderData _renderData

        var points = 5;
        var width= 100;
        var height= 100;

        TriangleNet.Geometry.InputGeometry geometry = new TriangleNet.Geometry.InputGeometry(points);

        for (int i = 0; i < points; i++)
            {
            geometry.AddPoint(rnd.NextDouble() * width, rnd.NextDouble() * height);
        }

        _mesh = new TriangleNet.Mesh();
        _mesh.SetOption(Options.ConformingDelaunay, true);
        _mesh.Triangulate(geometry);
        _voronoi = new TriangleNet.Tools.Voronoi(_mesh)

        _renderData.SetInputGeometry(geometry);
        _renderData.SetMesh(_mesh);
        _renderData.SetVoronoi(_voronoi);

    foreach (var region in _voronoi.Regions) {
        
        //Try to get a "whole" polygon
        if (!region.Bounded) {
            continue;
        }
        
        //Draw the probably center of the polygon
        Debug.DrawLine(new Vector3((float)region.Generator.X, 0f, (float)region.Generator.Y),
                new  Vector3((float)region.Generator.X, 0.5f, (float)region.Generator.Y),
                Color.red);
        
        //Connect every edge? with the polygon center
        //The code works like the Triangle.NET GDI+ VoronoiRendere
        for (int i = 0; i < region.Vertices.Count; i++) {
                
            var ci0 = i;
            var ci1 = i + 1;
                
            if (ci1 == region.Vertices.Count) {
                ci1 = 0;
            }

            var center = item.Generator;    
            var corner0 = item.Vertices[ci0];
            var corner1 = item.Vertices[ci1];
                
            Debug.DrawLine(new Vector3((float)corner0.X, 0.0f, (float)corner0.Y),
                    new  Vector3((float)corner1.X, 0.0f, (float)corner1.Y),
                    Color.magenta);

            Debug.DrawLine(new Vector3((float)corner0.X, 0.0f, (float)corner0.Y),
                    new  Vector3((float)center.X, 0.0f, (float)center.Y),
                    Color.magenta);

            Debug.DrawLine(new Vector3((float)corner1.X, 0.0f, (float)corner1.Y),
                    new  Vector3((float)center.X, 0.0f, (float)center.Y),
                    Color.magenta);
        }
    }
This is what I got:

Image

Each blue circle in the picture above represents a vertex in the Voronoi.Regions[0].Vertices. The green circle (small red line) is the center / the Voronoi.Region.Generator.

Now I need the (ordered?) vertices and a related and correct sorted triangle indices array like the _renderData.Triangles from the delaunay diagram to create the mesh in unity.

And I don't know how to do this.

I hope this illustration is better than the one before :).

Thank you for helping me out!

PS: Some background, I want to create a terrain with the voronoi polygons :D.
May 30, 2013 at 11:09 PM
Edited May 30, 2013 at 11:12 PM
I'm not familiar with Unity, so I can't give you any advice on that one.

If I understand right, you have the Voronoi data and want to convert it to the usual 3D mesh datastructure, i.e. vertex array and triangle indices array, with triangle indices sorted consistently!?

The VoronoiRegion.Vertices should already be sorted counterclockwise and have unique ids. So if you want to build triangles by connecting the two vertices of a Voronoi edge with the cells generator, the resulting triangle will also be oriented counterclockwise (regardless of positioning the generator before or after the two edge vertices). The only thing you have to worry about, is assigning an unused id to the generator vertex. The easiest way would probably be finding the largest Voronoi vertex id (actually I think, as the mesh triangles are numbered from 0 to N, the highest id will also be N) and then using values higher than that id for the generators.

This shouldn't be too hard to code, I'm sure you can work that out. Anyway, feel free to come back if you get stuck...
Jun 4, 2013 at 10:39 PM
Edited Jun 4, 2013 at 10:51 PM
You have no idea how stupid I felt! It took me more than a few hours to realize my mistakes.

I tried to get the vertices by looping over the regions and add the vertices to a new list. My first mistake was to add these to the list without checking for duplicated vertices. The second mistake was to try it with unsorted vertices. To create the triangles I have to sort the vertices by their id. The clue is to use the Voronoi.Points. They are already sorted in the correct way.

After that I saved the current vertices count as "offset-index" and then I added the generator vertices at the end of my new list.

To create the triangle indices I went over the regions and the associated vertices, grabbed the id and finally added the generator id (id + the "offset-index") to the end.

In fact that was the whole magic.

Thanks for your support! Your post helped me!

Here is an example of the generated mesh:

Image

For the sake of completeness I leave some code to provide a sample if someone will do the same.
I know it's not the best piece of code and of course it also needs some improvements. I think in the near future I'll port this to a gp-gpu shader in unity to speed up the generation.

    void Start () {
        
        var points = 50;
        var width= 100;
        var height= 100;
        
        System.Random rnd = new System.Random(System.DateTime.Now.Millisecond);
        TriangleNet.Geometry.InputGeometry geometry = new TriangleNet.Geometry.InputGeometry(points);
        
        for (int i = 0; i < points; i++)
            {
                    geometry.AddPoint(rnd.NextDouble() * width,
                            rnd.NextDouble() * height);
            }
        
        _mesh = new TriangleNet.Mesh();
        _mesh.SetOption(Options.ConformingDelaunay, true);
        
        _mesh.Triangulate(geometry);
        _voronoi = new TriangleNet.Tools.Voronoi(_mesh);
        
        _renderData = new TriangleNet.Render.RenderData();      
        
        _renderData.SetInputGeometry(geometry);
        _renderData.SetMesh(_mesh);
        _renderData.SetVoronoi(_voronoi);

        var voronoiVertices = new List<Vector3>();
        var triangles = new List<int>();
            
        foreach (var point in _voronoi.Points) {
            voronoiVertices.Add(new Vector3((float)point.X, 0f, (float)point.Y));
        }

        
        int verticesCount = voronoiVertices.Count;

        foreach (var item in _voronoi.Regions) {
            voronoiVertices.Add(new Vector3((float)item.Generator.X, 0f, (float)item.Generator.Y));

        }

        foreach (var item in _voronoi.Regions) {
            if (!item.Bounded) {
                continue;
            }
            
            for (int i = 0; i < item.Vertices.Count; i++) {
                
                var ci0 = i;
                var ci1 = i + 1;
                
                if (ci1 == item.Vertices.Count) {
                    ci1 = 0;
                }
                
                var corner0 = item.Vertices[ci0].ID;
                var corner1 = item.Vertices[ci1].ID;
                var center = item.Generator.ID;
                
                triangles.Add(corner0);
                triangles.Add(corner1);
                triangles.Add(center + verticesCount);
                
            }
        }

        UnityEngine.Mesh uMesh = new UnityEngine.Mesh();
        
            GameObject HexiSphereSegment = new GameObject();

            HexiSphereSegment.transform.parent = base.transform;
            HexiSphereSegment.transform.localPosition = Vector3.zero;
            HexiSphereSegment.transform.rotation = base.transform.rotation;
        
            HexiSphereSegment.AddComponent<MeshRenderer>();
            MeshFilter filter = HexiSphereSegment.AddComponent<MeshFilter>();
            HexiSphereSegment.renderer.material= base.renderer.material;
        

            HexiSphereSegment.name = "Forward";
        Vector2[] _uv2D = new Vector2[voronoiVertices.Count];
        
        for(int x = 0; x < voronoiVertices.Count; x++){
            _uv2D[x] = new Vector2(voronoiVertices[x].x, voronoiVertices[x].y);
        }

        uMesh.hideFlags = HideFlags.DontSave;
        uMesh.vertices = voronoiVertices.ToArray();
            uMesh.uv = _uv2D;
            uMesh.triangles =  triangles.ToArray();
        uMesh.RecalculateNormals();
            uMesh.RecalculateBounds();
            filter.mesh = uMesh;
    }
PS: the mesh in unity is by default upside down. Change Y and Z rotation to 180 degrees! :)
Dec 9, 2013 at 1:03 PM
Thanks for quick replay

Its works
Apr 22, 2014 at 9:35 AM
Edited Apr 22, 2014 at 9:41 AM
We implemented Triangle voronoi in MatterMachine. It was all a little easier because of this thread and others. So we thought we'd share our implementation. It's somewhat tied to how we evaluate our 'operators', and how we represent our meshes (PolyMesh), but there's plenty to get here if you can ignore that.

Essentially, the input is one or more curves (order 2 NurbsCurves, so essentially polylines). The second etc curve can be treated like holes. In that case we use a trick to find a point inside the (potentially) convex hole.

Here's what it looks like.

  using UnityEngine;
  using System;
  using System.Collections;
  using System.Collections.Generic;
  using MM.Primitives;
  using MM.Types;
  using MM.Util;
  using Ayam.Nurbs;
  using TriangleNet.Geometry;
  using TriangleNet.Tools;


  namespace MM.Operators
  {
    public class Voronoi: Operator, IOperator
    {
        public int mode;  // 0 = holes, 1 = every curve a poly
        public int voronoi;  // 0 = meshes, 1 = curves, 2 = centers
        public bool asOneMesh;
        public bool bounded;
        public bool convexHull;
        public bool preFlatten;
        
        public int algorithm;  // 0 = sweepline, 1 = Dwyer, 2 = incremental

        public bool refine;
        public bool conformingDelauney = true;  // seems to fail most of the time if false
        public double maxArea;
        public double minAngle;
        public double maxAngle;
        
        public int smoothing;
        
        public double maxRunTime;
        
        // internal points are added to create vertices inside the triangulated polygon
        public List<mmVector3> internalPoints;
        
        public Voronoi()
        {
            internalPoints = new List<mmVector3>();
        }
        
        
        public bool Cook()
        {
            if ( !IsBound ( "internalPoints" ) )
                internalPoints = new List<mmVector3>();

            //  FIXME getting error when refine == false && internalPoints.Count > 0
            // to do with using BoundedVoronoi instead of Voronoi
  //            Triangle.cs error: System.IndexOutOfRangeException: Array index is out of range.
  //                    at TriangleNet.Tools.BoundedVoronoi.ConstructBvdCell
                    
            if ( refine == false && internalPoints.Count > 0 ) {
                errorMessage = "please switch on refinement when providing inner points";
                return false;
            }

            bool foundCurve = false;
            bool foundOrderTwoCurve = false;
            var curves = new List<NurbsCurve>();
            
            foreach ( Primitive primitive in inputGeometry ) {
                if ( primitive is NurbsCurve ) {
                    foundCurve = true;
                    var curve = primitive as NurbsCurve;
                    
                    if ( curve.order == 2 ) {
                        foundOrderTwoCurve = true;
                        
                        if ( preFlatten ) {
                            foreach ( mmVector3 point in curve.points )
                                point.y = 0;
                        }
                        else {
                            foreach ( mmVector3 point in curve.points ) {
                                if ( point.y > Double.Epsilon ) {
                                    errorMessage = "contours curve must lie in XZ (Y=0) plane";
                                    return false;
                                }
                            }
                        }
                        
                        // avoid overlapping end points
                        if ( ( curve.points[ 0 ].x - curve.points[ curve.points.Count - 1 ].x <= Double.Epsilon ) && ( curve.points[ 0 ].z - curve.points[ curve.points.Count - 1 ].z <= Double.Epsilon ) ) {
  //                            Logging.Error( "removing endpoint" );
                            curve.points.RemoveAt ( 0 );
                        }
                        
                        curves.Add ( curve );
                    }
                }
                else outputGeometry.Add ( primitive );
            }
            
            
            if ( foundCurve && !foundOrderTwoCurve ) {
                errorMessage = "triangulation only works on order 2 curves";
                return false;
            }

            try {
                if ( curves.Count > 0 ) {
                    if ( mode == 0 ) {  // 1st curve is outer boundary, other curves are holes
                        Triangle ( curves );
                    } else {  // each curve represents a separate polygon
                        foreach ( var curve in curves )
                            Triangle ( new List<NurbsCurve>() { curve } );
                    }
                }
            }
            catch ( Exception e ) {
                Logging.Error ( "Triangle.cs error: " + e );
                errorMessage = "triangulation failed - try other settings";
                return false;
            }

            return true;
        }



        
        // https://triangle.codeplex.com/
        private void Triangle ( List<NurbsCurve> curves )
        {
            var curve = curves[ 0 ];
            var inputGeo = new InputGeometry ( curve.points.Count );
            
            for ( int i = 0; i < curve.points.Count; i++ ) {
                inputGeo.AddPoint ( curve.points[i].x, curve.points[i].z, 1 );
                inputGeo.AddSegment ( i, ( i + 1 ) % curve.points.Count, 1 );
            }
            
            var mesh = new TriangleNet.Mesh();
            
            var numPoints = inputGeo.Count;
            
            for ( int j = 1; j < curves.Count; j++ ) {
                curve = curves[ j ];
                
                for ( int i = 0; i < curve.points.Count; i++ )
                    inputGeo.AddPoint ( curve.points[i].x, curve.points[i].z, j + 1 );
                
                for ( int i = numPoints; i < inputGeo.Count - 1; i++ )
                    inputGeo.AddSegment ( i, i + 1, j + 1 );
                inputGeo.AddSegment ( inputGeo.Count - 1, numPoints, j + 1 );
                
                // find a point that lies in the hole (Triangle quirkiness)
                // somewhat naive: construct a series of candidate points (two per vertex) and test until positive
                mmVector3 delta = .01f * MiscUtil.GetBounds( curve.points ).size;
                if ( curve.points.Count > 2 ) {
                    for ( int i = 0; i < curve.points.Count - 1; i++ ) {
                        if ( IsPointInPolygon( curve.points[i] + delta, curve.points ) ) {
                            inputGeo.AddHole( curve.points[i].x + delta.x, curve.points[i].z + delta.z );
                            break;
                        }
                        if ( IsPointInPolygon( curve.points[i] - delta, curve.points ) ) {
                            inputGeo.AddHole( curve.points[i].x - delta.x, curve.points[i].z - delta.z );
                            break;
                        }
                    }
                }
                
                numPoints += curve.points.Count;
            }
            
            
            // add inner points
            foreach ( mmVector3 innerPoint in internalPoints )
                inputGeo.AddPoint ( innerPoint.x, innerPoint.z, 0 );
            
            
            if ( convexHull )
                mesh.Behavior.Convex = true;
            
            if ( algorithm == 0 )
                mesh.Behavior.Algorithm = TriangleNet.TriangulationAlgorithm.SweepLine;  // seems most stable
            else if ( algorithm == 1 )
                mesh.Behavior.Algorithm = TriangleNet.TriangulationAlgorithm.Dwyer;
            else
                mesh.Behavior.Algorithm = TriangleNet.TriangulationAlgorithm.Incremental;
            
            mesh.Triangulate ( inputGeo );
            
            if ( refine ) {
                mesh.Behavior.ConformingDelaunay = conformingDelauney;
                mesh.Behavior.MinAngle = minAngle;
                mesh.Behavior.MaxAngle = maxAngle;
                mesh.Behavior.MaxArea = maxArea;
                mesh.Refine();
            }
            
            for ( int i = 0; i < smoothing; i++ )
                mesh.Smooth();

            var voronoiData = new BoundedVoronoi ( mesh, bounded );
            if ( voronoi == 0 ) {
                if ( asOneMesh ) {
                    outputGeometry.Add ( new PolyMesh ( voronoiData ) );
                } else {
                    foreach ( var region in voronoiData.Regions )
                        outputGeometry.Add ( new PolyMesh ( region ) );
                }
            }
            else if ( voronoi == 1 )  // outputs a Polyline for every region
            {
                foreach ( var region in voronoiData.Regions )
                {
                    if (!region.Bounded) continue;
                    
                    var regionBoundary = new NurbsCurve ();
                    regionBoundary.order = 2;
                    
                    foreach ( var vertex in region.Vertices )
                        regionBoundary.points.Add ( new mmVector3 ( vertex.X, 0f, vertex.Y ) );
                    regionBoundary.points.Add ( new mmVector3 ( region.Vertices[ 0 ].X, 0f, region.Vertices[ 0 ].Y ) );
                    
                    regionBoundary.knotVector = NurbsLibCore.GenerateKnotVector ( 2, regionBoundary.points.Count );
                    outputGeometry.Add ( regionBoundary );
                }
            } else {   // centers
                var markers = new PositionsPrimitive ();
                foreach ( var region in voronoiData.Regions )
                    markers.points.Add ( new mmVector3 ( region.Generator.X, 0f, region.Generator.Y ) );
                outputGeometry.Add ( markers );
            }
        }
        
        // http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test
        private bool IsPointInPolygon( mmVector3 p, List<mmVector3> polygon )
        {
            double minX = polygon[ 0 ].x;
            double maxX = polygon[ 0 ].x;
            double minY = polygon[ 0 ].z;
            double maxY = polygon[ 0 ].z;
            for ( int i = 1 ; i < polygon.Count ; i++ )
            {
                var q = polygon[ i ];
                minX = Math.Min( q.x, minX );
                maxX = Math.Max( q.x, maxX );
                minY = Math.Min( q.z, minY );
                maxY = Math.Max( q.z, maxY );
            }
            
            if ( p.x < minX || p.x > maxX || p.z < minY || p.z > maxY )
            {
                return false;
            }
            
            // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
            bool inside = false;
            for ( int i = 0, j = polygon.Count - 1 ; i < polygon.Count ; j = i++ )
            {
                if ( ( polygon[ i ].z > p.z ) != ( polygon[ j ].z > p.z ) &&
                    p.x < ( polygon[ j ].x - polygon[ i ].x ) * ( p.z - polygon[ i ].z ) / ( polygon[ j ].z - polygon[ i ].z ) + polygon[ i ].x )
                {
                    inside = !inside;
                }
            }
            
            return inside;
        }
        
    }
  }
Apr 22, 2014 at 9:38 AM
And this is how we convert back to our PolyMesh format, using BoundedVoronoi:

        // convert from TriangleNet.Tools.BoundedVoronoi
        public PolyMesh ( TriangleNet.Tools.BoundedVoronoi voronoi )
        {
            var voronoiRegions = voronoi.Regions;

            int vertexCount = 0;
            
            foreach (var region in voronoiRegions)
            {
                if (!region.Bounded) continue;
                
                points.Add ( new mmVector3 ( region.Vertices[0].X, 0f, region.Vertices[0].Y ) );
                
                for (int i = 1; i < region.Vertices.Count - 1; i++)
                {
                    points.Add ( new mmVector3 ( region.Vertices[i].X, 0f, region.Vertices[i].Y ) );
                    triangles.Add ( new Triangle ( vertexCount, vertexCount + i, vertexCount + i + 1, this ) );
                }
                
                points.Add ( new mmVector3 ( region.Vertices[ region.Vertices.Count - 1 ].X, 0f, region.Vertices[ region.Vertices.Count - 1 ].Y ) );

                vertexCount += region.Vertices.Count;
            }
        }

        public PolyMesh ( TriangleNet.Tools.VoronoiRegion region )
        {
            points.Add ( new mmVector3 ( region.Vertices[0].X, 0f, region.Vertices[0].Y ) );
            
            for (int i = 1; i < region.Vertices.Count - 1; i++)
            {
                points.Add ( new mmVector3 ( region.Vertices[i].X, 0f, region.Vertices[i].Y ) );
                triangles.Add ( new Triangle ( 0, i, i + 1, this ) );
            }
            
            points.Add ( new mmVector3 ( region.Vertices[ region.Vertices.Count - 1 ].X, 0f, region.Vertices[ region.Vertices.Count - 1 ].Y ) );
        }