Calculating the triangles of an extruded polygon

Question

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?

alt text

Answer 1

Best Answer

Answer by MichaelTaylor3d · Feb 13, 2014 at 08:43 PM

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;
     }

Add comment · Show 1 · Share

josessito · Apr 30, 2014 at 06:19 PM 0

Share

Hi $$anonymous$$ichael, I don't know if I should do this from here, but I wanted to ask if by any chance you could post the full extrusion code. I've been trying to do this but I'm way over my head and my code is not working properly (some of the faces don't get rendered) So if you post the code It would be fantastic Thanks

Answer 2

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[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));
     }
 
     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[i].x = poly[i].x;
 
             vertices[i].y = poly[i].y;
 
             vertices[i].z = -extrusion; // front vertex
 
             vertices[i + poly.Length].x = poly[i].x;
 
             vertices[i + poly.Length].y = poly[i].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[i] = tris[i];
 
             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[i] + poly.Length;
 
         } 
        
         //texture coordinate
         Vector2[] uvs = new Vector2[vertices.Length];
         
         for (int i = 0; i < uvs.Length ; i++)
         {
             uvs[i] = new Vector2(vertices[i].x, vertices[i].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<int> indices = new List<int>(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.

Calculating the triangles of an extruded polygon

2 Replies

Your answer

Follow this Question

Related Questions