How to Generate Procedural Mesh Using Points

Unity Engine
1

I have a script that is designed so each outer edge point is supposed to create a triangle with the next point and the center of the mesh. The problem is, the mesh that is created is either flipped or there are missing triangles.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class MeshGenerator : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
       
    }

    // Update is called once per frame
    void Update()
    {
       
    }

    public static Mesh GenerateMesh(Vector3[] points)
    {
        Vector3[] vertices = new Vector3[points.Length + 1];
        Vector3 avg = Vector3.zero;
        Vector3 min = Vector3.one * 1000000;
        Vector3 max = Vector3.one * -1000000;
        for (int i = 0; i < points.Length; i++)
        {
            vertices[i] = points[i];
            avg += points[i];
            min = Vector3.Min(min, points[i]);
            max = Vector3.Max(max, points[i]);
        }
        avg /= points.Length;
        vertices[vertices.Length - 1] = avg;
        int[] tris = new int[points.Length * 3];
        Vector2[] uv = new Vector2[vertices.Length];
        for (int i = 0; i < points.Length; i++)
        {
            tris[i + 2] = vertices.Length - 1;
            tris[i] = (i < points.Length - 1) ? i + 1 : 0;
            tris[i + 1] = i;
           
           
            Debug.Log(vertices[vertices.Length - 1] + " " + vertices[(i < points.Length - 1) ? i + 1 : 0] + " " + vertices[i]);
           
        }
        for (int i = 0; i < vertices.Length; i++)
        {
           
            uv[i] = new Vector2(Mathf.InverseLerp(min.x, max.x, vertices[i].x), Mathf.InverseLerp(min.z, max.z, vertices[i].z));
        }
        Mesh mesh = new Mesh();
        mesh.vertices = vertices;
        mesh.triangles = tris;
        mesh.uv = uv;
        mesh.RecalculateNormals();
        return mesh;
    }
}

If there is a better way of doing this, please tell me.

2

Winding order matters. Unity uses left hand winding. Hie thee to google for more info.

You need to make 100% of the triangles you want to see.

The best way to do something is the first way that works.

If you want to see some other examples of procedural generation, you’re welcome to sniff around my MakeGeo project.

MakeGeo is presently hosted at these locations:

https://bitbucket.org/kurtdekker/makegeo

1 Like
3

The way the function works is by looping through all the points and creating a triangle with the center point and the point after it. I also make sure that if the point it is on is at the end of the array, it will connect it to the beginning point. I have also messed around with the order of the points and sometimes less triangles would appear. Also, I am not trying to make a 3d mesh. I am trying to procedurally generate a 2d convex mesh.

4

could try first sorting the points by angle, then connecting should be easier.

can also use pseudoangle, maybe faster than full angle check/sort
https://stackoverflow.com/questions/16542042/fastest-way-to-sort-vectors-by-angle-without-actually-computing-that-angle

5

If this helps I made the code for a basic cube generator using procedural mesh generator

Vector3[] verts = new Vector3[]
{
    new Vector3(0, 0, 0), // 0
    new Vector3(1, 0, 0), // 1
    new Vector3(0, 1, 0), // 2
    new Vector3(0, 0, 1), // 3
    new Vector3(1, 1, 0), // 4
    new Vector3(1, 0, 1), // 5
    new Vector3(0, 1, 1), // 6
    new Vector3(1, 1, 1), // 7
};

int[] tris = new int[]
{
     0, 4, 1, 0, 2, 4, // front
     5, 6, 3, 5, 7, 6, // back
     1, 7, 5, 1, 4, 7, // right
     3, 2, 0, 3, 6, 2, // left
     2, 7, 4, 2, 6, 7, // top
     0, 1, 5, 0, 5, 3, // bottom

};

void Start()
{
    MeshGenerator();
}

// Update is called once per frame
void Update()
{
   
}

void MeshGenerator()
{
    Mesh mesh = new Mesh();
    mesh.vertices = verts;
    mesh.triangles = tris;
    mesh.RecalculateNormals();
    GetComponent<MeshFilter>().mesh = mesh;
}
1 Like
6

did you figure out a solution?

7

As a patch:
You can analyze surface normals on the fly, compare them with intended direction (via dot) and then flip the triangle ad hoc.

triangle surface normal (turn two edges to vectors, then take a cross)

static public Vector3 GetTriangleNormal(Vector3 a, Vector3 b, Vector3 c)
  => Vector3.Cross(b - a, c - a).normalized;

if your object is generally convex, then you know the general inward direction is toward its center of mass (ideally origin).

var tri = GetTriangle(index);
var outward = (tri.GetCentroid() - center).normalized;
var normal = tri.GetNormal();
if(Vector3.Dot(outward, normal) < 0f) tri.Flip(); // *

to find a triangle centroid get arithmetic mean of its vertices.
to flip a triangle, swap any two of its consecutive vertex indices.

for these kinds of manipulations, I usually build my own Triangle type as an intermediate result which lets you inspect and modify both the topology and the geometry of the mesh. (i.e. a struct that only holds onto the indices, but can reach out to the actual points to perform math on them.)

Edit:
fixed inward to outward