I have a programmatically generated icosahedron mesh with mesh face sub-division implemented. Each triangle of the mesh is a separate object in a list, and I need to make each triangle know it’s neighbours.
.
Mesh generation is accomplished by creating a 20-sided icosahedron (tri by tri in a set order) and then looping through the queue of triangles for X amount of subdivisions and creating 4 new triangles to replace the original one (and pushing the 3 new points away from the origin to match the spherical radius - note that this makes 3 of every 4 triangles isosceles where the other is equilateral).
.
My original thought for working out the neighbours (and keeping it modular so I can change the sub-division level in the future) was to take the vector between the centres of the first couple of triangles (after the last subD level) and store it’s magnitude projected along a couple of constant axes ([1]the triangle’s normal and [2]the shared side’s midpoint minus the triangle’s centre). This is where I discovered that the triangles aren’t all equilateral so I had to shift the “shared side’s midpoint” for the 2nd axis (I’ll spare the details here but to be brief; I calculated the closest point between 2 lines and stored the difference). A lot of fluffing around, but this worked for 1 subD level (80 triangles total). The issue being that it doesn’t seem to work if I sub-divide it any more…
.
So I was wondering if anyone had any ideas of a way I could keep track of which triangles are neighboured to which from the beginning? Or maybe another idea for calculating them afterwards? I’m open to any and all thoughts right now…
You could try this script. I wrote this in a console project and not unity, so you’ll have to replace the Console.WriteLines with Debug.Logs, and the Random’s too. The max number of iterations over the list, to find all neighboring triangles, is the number of distinct vertices you have. So the size of your vertex array. I ran this over 1000 elements with a vertex array size of 20, and it took a while to print, but it populated the list very quickly:
class Program
{
static void Main()
{
#region Create random triangle array
List<int[]> tris = new List<int[]>();
Random rand = new Random();
for (int i = 0; i < 1000; i++)
{
int[] rndmTri = new int[3]
{
rand.Next(0, 20),
rand.Next(0, 20),
rand.Next(0, 20)
};
tris.Add(rndmTri);
}
#endregion
Find_Neighboring_Triangles triangles = new Find_Neighboring_Triangles
(
tris.ToArray()
);
#region Print results
foreach (NeighboringTriangle tri in triangles.neighboringTriangles)
{
Console.WriteLine("Shared Vertex: " + tri.SharedVertex);
foreach (int[] triangle in tri.Triangles)
{
Console.WriteLine
(
triangle[0] + ", " +
triangle[1] + ", " +
triangle[2]
);
}
Console.WriteLine();
}
#endregion
}
}
class Find_Neighboring_Triangles
{
public List<NeighboringTriangle> neighboringTriangles;
readonly int[][] triangles;
public Find_Neighboring_Triangles(int[][] TriangleIndicis)
{
neighboringTriangles = new List<NeighboringTriangle>();
triangles = TriangleIndicis;
GetNeighboringTriangles();
}
int[] GetDistinctIndicis()
{
List<int> DistinctIndicies = new List<int>();
foreach (int[] triangle in triangles)
{
foreach (int indicie in triangle)
{
if (!DistinctIndicies.Contains(indicie))
DistinctIndicies.Add(indicie);
}
}
return DistinctIndicies.ToArray();
}
void GetNeighboringTriangles()
{
foreach (int DistinctIndicie in GetDistinctIndicis())
{
NeighboringTriangle neighboringTriangle = new NeighboringTriangle
{
SharedVertex = DistinctIndicie
};
foreach (int[] triangle in triangles)
{
foreach (int indicie in triangle)
{
// Checks if triangles share a common vertex
if (indicie == DistinctIndicie)
{
neighboringTriangle.Triangles.Add(triangle);
break;
}
}
}
if (neighboringTriangle.Triangles.Count > 1)
neighboringTriangles.Add(neighboringTriangle);
}
}
}
class NeighboringTriangle
{
public List<int[]> Triangles = new List<int[]>();
public int SharedVertex;
}