- Home /

**Question**by FairGamesProductions · Aug 01, 2017 at 05:50 PM · proceduralprocedural meshprocedural generationprocedural-generation

# Procedural Mesh From Random List Of Veritces

I am very new to procedural mesh generation, but I need to find a solution on how to generate a mesh based on a list of random vertices. The only thing I know about the list of vertices is that they are ordered clockwise but that's it. I don't know how many vertices it will have or in what shape and I have no idea how to generate the triangles of the mesh. This is an image of a possible layout of vertices: Any direction, tutorial link or code snippet would be greatly appreciated.

Just to be clear, I know the code to generate the mesh itself, what I don't know is what order to connect the vertexes in when I don't know beforehand the final shape of the mesh (convex, concave, or a combination of the two).

**Answer** by look001
·
Aug 01, 2017 at 07:48 PM

Take a look at the unity triangulator and the delauny algorithm. Very interesting topic :)

"Sorry! This site is experiencing technical difficulties." :|

This site doesn't seem to load at all for me.

The wiki has some trouble lately. However there's the wayback machine:

**Answer** by adrienPlayerium
·
Aug 01, 2017 at 11:54 PM

@FairGamesProductions if you are still looking, The unity triangulator, as the server looks down~

```
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Triangulator
{
private List<Vector2> m_points = new List<Vector2>();
public Triangulator(Vector2[] points)
{
m_points = new List<Vector2>(points);
}
public int[] Triangulate()
{
List<int> indices = new List<int>();
int n = m_points.Count;
if (n < 3)
return indices.ToArray();
int[] V = new int[n];
if (Area() > 0)
{
for (int v = 0; v < n; v++)
V[v] = v;
}
else
{
for (int v = 0; v < n; v++)
V[v] = (n - 1) - v;
}
int nv = n;
int count = 2 * nv;
for (int m = 0, v = nv - 1; nv > 2;)
{
if ((count--) <= 0)
return indices.ToArray();
int u = v;
if (nv <= u)
u = 0;
v = u + 1;
if (nv <= v)
v = 0;
int w = v + 1;
if (nv <= w)
w = 0;
if (Snip(u, v, w, nv, V))
{
int a, b, c, s, t;
a = V[u];
b = V[v];
c = V[w];
indices.Add(a);
indices.Add(b);
indices.Add(c);
m++;
for (s = v, t = v + 1; t < nv; s++, t++)
V[s] = V[t];
nv--;
count = 2 * nv;
}
}
indices.Reverse();
return indices.ToArray();
}
private float Area()
{
int n = m_points.Count;
float A = 0.0f;
for (int p = n - 1, q = 0; q < n; p = q++)
{
Vector2 pval = m_points[p];
Vector2 qval = m_points[q];
A += pval.x * qval.y - qval.x * pval.y;
}
return (A * 0.5f);
}
private bool Snip(int u, int v, int w, int n, int[] V)
{
int p;
Vector2 A = m_points[V[u]];
Vector2 B = m_points[V[v]];
Vector2 C = m_points[V[w]];
if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
return false;
for (p = 0; p < n; p++)
{
if ((p == u) || (p == v) || (p == w))
continue;
Vector2 P = m_points[V[p]];
if (InsideTriangle(A, B, C, P))
return false;
}
return true;
}
private bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
float cCROSSap, bCROSScp, aCROSSbp;
ax = C.x - B.x; ay = C.y - B.y;
bx = A.x - C.x; by = A.y - C.y;
cx = B.x - A.x; cy = B.y - A.y;
apx = P.x - A.x; apy = P.y - A.y;
bpx = P.x - B.x; bpy = P.y - B.y;
cpx = P.x - C.x; cpy = P.y - C.y;
aCROSSbp = ax * bpy - ay * bpx;
cCROSSap = cx * apy - cy * apx;
bCROSScp = bx * cpy - by * cpx;
return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}
}
```

And a short test class to show you how to use it, using UnityEngine;

```
public class PolygonTester : MonoBehaviour
{
void Start()
{
// Create Vector2 vertices
Vector2[] vertices2D = new Vector2[] {
new Vector2(0,0),
new Vector2(0,50),
new Vector2(50,50),
new Vector2(50,100),
new Vector2(0,100),
new Vector2(0,150),
new Vector2(150,150),
new Vector2(150,100),
new Vector2(100,100),
new Vector2(100,50),
new Vector2(150,50),
new Vector2(150,0),
};
// Use the triangulator to get indices for creating triangles
Triangulator tr = new Triangulator(vertices2D);
int[] indices = tr.Triangulate();
// Create the Vector3 vertices
Vector3[] vertices = new Vector3[vertices2D.Length];
for (int i = 0; i < vertices.Length; i++)
{
vertices[i] = new Vector3(vertices2D[i].x, vertices2D[i].y, 0);
}
// Create the mesh
Mesh msh = new Mesh();
msh.vertices = vertices;
msh.triangles = indices;
msh.RecalculateNormals();
msh.RecalculateBounds();
// Set up game object with mesh;
gameObject.AddComponent(typeof(MeshRenderer));
MeshFilter filter = gameObject.AddComponent(typeof(MeshFilter)) as MeshFilter;
filter.mesh = msh;
}
}
```

### Your answer

### Welcome to Unity Answers

The best place to ask and answer questions about development with Unity.

To help users navigate the site we have posted a site navigation guide.

If you are a new user to Unity Answers, check out our FAQ for more information.

Make sure to check out our Knowledge Base for commonly asked Unity questions.

If you are a moderator, see our Moderator Guidelines page.

We are making improvements to UA, see the list of changes.