Calculating the triangles of an extruded polygon

I made procedural flat polygon and I would like to extrude the polygon to give it a thickness. Im having trouble trying to create the resulting mesh procedurally.

By looping through the vertices, I can add the extruded verts upward by the extrusion height. I next need to create the triangles of the sides of the extrusion. Im having trouble figuring out how to generate this part of the algorithm. Any ideas?

Edit:
So calculating the top triangles ended up being easy, I just copied the original indices to the new verts and added the count of the original to them. Then you just have to flip the normals.

The triangles indices for the side is slightly harder, I found the formula for the sum of the first n integers to be:

Let count = Num Verts / 2 (the num of original verts before the extrusion)

foreach original vert (N)

  1st triangle: N, N + count, N + 1
  2nd triangle: N + 1, N + count, N + Count + 1

Of course you have to be careful when the indices reach the end and wrap around to the beginning of the sequence.

Heres the resulting code:

Mesh CalculateSideExtrusion(Mesh mesh) {
		List<int> indices = new List<int>( mesh.triangles );
		int count = (mesh.vertices.Count() / 2);
		for( int n = 0; n < count; n++) {

			int n1 = n;
			int n2 = n + count;
			int n3 = n + count + 1;
			int n4 = n + 1;				

			indices.Add((n == count - 1) ? 0 : n4);
			indices.Add((n2 > (count * 2) - 1) ? n2 - count * 2 : n2);
			indices.Add(n1);

			indices.Add((n2 > (count * 2) - 1) ? n2 - count * 2 : n2);
			indices.Add((n == count - 1) ? 0 : n4);
			indices.Add((n3 > (count * 2) - 1) ? n3 - count * 2 : n3);			
		}
		mesh.triangles = indices.ToArray();
		return mesh;
	}

It almost works except for the last triangle, Ive been trying to figure out that last triangle for a day. Any ideas?

[22132-screenshot+2014-02-13+13.27.55.png|22132]

Michael, never mind, I finally did it.

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

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;

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 = 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];
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));
}
~~ ~~
public static Mesh CreateMesh(Vector2[] poly , float extrusion)
{
~~ ~~
// convert polygon to triangles
~~ ~~
Triangulator triangulator = new Triangulator(poly);
~~ ~~
int[] tris = triangulator.Triangulate();
~~ ~~
Mesh m = new Mesh();
~~ ~~
Vector3[] vertices = new Vector3[poly.Length * 2];
~~ ~~
~~ ~~
~~ ~~
for (int i = 0; i < poly.Length; i++)
{
~~ ~~
vertices_.x = poly*.x;*_
~~ ~~
vertices_.y = poly*.y;*_
~~ ~~
vertices*.z = -extrusion; // front vertex*
~~ ~~
vertices[i + poly.Length].x = poly*.x;*
~~ ~~
vertices[i + poly.Length].y = poly*.y;*
~~ ~~
vertices[i + poly.Length].z = extrusion; // back vertex
~~ ~~
}
~~ ~~
int[] triangles = new int[tris.Length * 2 + poly.Length * 6];
~~ ~~
int count_tris = 0;
~~ ~~
for (int i = 0; i < tris.Length; i += 3)
{
~~ ~~
triangles = tris*;*
~~ ~~
triangles[i + 1] = tris[i +1];
~~ ~~
triangles[i + 2] = tris[i +2];
~~ ~~
} // front vertices
~~ ~~
count_tris += tris.Length;
~~ ~~
for (int i = 0; i < tris.Length; i += 3)
{
~~ ~~
triangles[count_tris + i] = tris[i + 2] + poly.Length;
~~ ~~
triangles[count_tris + i + 1] = tris[i + 1] + poly.Length;
~~ ~~
triangles[count_tris + i + 2] = tris + poly.Length;
~~ ~~
}
~~ ~~
//texture coordinate
Vector2[] uvs = new Vector2[vertices.Length];
~~ ~~
for (int i = 0; i < uvs.Length ; i++)
{
uvs = new Vector2(vertices_.x, vertices*.z);*_
~~ ~~
}
~~ ~~
~~ ~~
~~ ~~
m.vertices = vertices;
~~ ~~
m.triangles = triangles;
~~ ~~
m.uv = uvs;
~~ ~~
m = Triangulator.SideExtrusion(m);
~~ ~~
m.RecalculateNormals();
~~ ~~
m.RecalculateBounds();
~~ ~~
~~ ~~
~~ ~~
m.Optimize();
~~ ~~
return m;
~~ ~~
}
~~ ~~
private static Mesh SideExtrusion(Mesh mesh)
{
List indices = new List(mesh.triangles);
int count = (mesh.vertices.Length / 2);
for (int i = 0; i < count; i++)
{
int i1 = i;
int i2 = (i1 + 1) % count;
int i3 = i1 + count;
int i4 = i2 + count;
~~ ~~
indices.Add(i4);
indices.Add(i3);
indices.Add(i1);
~~ ~~
indices.Add(i2);
indices.Add(i4);
indices.Add(i1);
}
mesh.triangles = indices.ToArray();
return mesh;
}
}
I’m using the Triangulator class from the wiki and also some code form a forum post modified with your code(the forum code was not generating the sides properly).
For anyone else, if you want to use it, just call Triangulator.CreateMesh() and pass the polygon (path of vector2’s) and the extrusion amount as arguments. I’m not sure what I’ve done here, this is some kind internet copy/paste Frankenstein, but it works. I would recommend not to use this in Update. Start or Awake are better places to call it.

Figured it Out! I was close in my above implementation but it needed to be altered slightly to better accommodate for the end of the vertex list.

	Mesh CalculateSideExtrusion(Mesh mesh) {
		List<int> indices = new List<int>( mesh.triangles );
		int count = (mesh.vertices.Count() / 2);
		for( int i = 0; i < count; i++) {
			int i1 = i;			
			int i2 = (i1 + 1) % count;			
			int i3 = i1 + count;			
			int i4 = i2 + count;		

			indices.Add(i4);
			indices.Add(i3);
			indices.Add(i1);		

			indices.Add(i2);
			indices.Add(i4);
			indices.Add(i1);								
		}
		mesh.triangles = indices.ToArray();
		return mesh;
	}

Hey @josessito , I realise you wrote that script ages ago (and it’s been an absolute life-saver), but I was wondering if you’d be able to give me a quick pointer into how I’d prevent this from creating interior faces?

Anything I comment out causes a bit of chaos, haha.