Need some insight on mesh triangulation and geodesic spheres

Question

I am making a game that's going to use a Class 1 (This is (n,0)) Goldberg Polyhedron as the map, that is I'm planning on using the hexagons and 12 pentagons as tiles for a tile-based game.

When it came to generate this shapes, I researched online and came to the conclusion that the best way to get there is to do an icosphere appropiately divided and then find it's dual shape so I got to work onto that and I came up with a code that will generate the vertices of an icosahedron divided just like I wanted and with zero duplicates.

Now my problem is, I'm having a lot of trouble finding a nice way to triangulate all this faces, because as some edges are shared the vertex index vary a lot. I'm gonna post some of my code and see if someone can help me out here cause i've been thinking about this for hours and I'm sure I'm just missing something.

void Subdivide(int frequency, List<Vector3> vertList, List<TriangleIndices> faces){

    List<Vector3> workingList = new List<Vector3> ();
    for (int i = 0; i < faces.Count; i++){
        float div = frequency + 1;
        Vector3 v1 = vertList [faces[i].v1];
        Vector3 v2 = vertList [faces [i].v2];
        Vector3 v3 = vertList [faces [i].v3];

        for (float k =0; k <= (frequency + 1); k++) {

            for (float j = 0; j <= div; j++){
                if (div == 0) {

                    for (int c = 0; c < workingList.Count; c++) {
                        if (workingList [c] == ((v1 + (k / (frequency + 1f)) * (v3 - v1)) + 1f * ((v2 + (k / (frequency + 1f)) * (v3 - v2)) - (v1 + (k / (frequency + 1f)) * (v3 - v1)))).normalized) {
                            isDupe = true;
                        }
                    }

                    if (isDupe == false) {
                        workingList.Add (((v1 + (k / (frequency + 1f)) * (v3 - v1)) + 1f * ((v2 + (k / (frequency + 1f)) * (v3 - v2)) - (v1 + (k / (frequency + 1f)) * (v3 - v1)))).normalized);
                    } else {
                        isDupe = false;
                    }


                } else {
                    for (int c = 0; c < workingList.Count; c++) {
                        if (workingList [c] == ((v1 + (k / (frequency + 1f)) * (v3 - v1)) + (j / div) * ((v2 + (k / (frequency + 1f)) * (v3 - v2)) - (v1 + (k / (frequency + 1f)) * (v3 - v1)))).normalized) {
                            isDupe = true;
                        } 
                    }
                    if (isDupe == false) {
                        workingList.Add (((v1 + (k / (frequency + 1f)) * (v3 - v1)) + (j / div) * ((v2 + (k / (frequency + 1f)) * (v3 - v2)) - (v1 + (k / (frequency + 1f)) * (v3 - v1)))).normalized);
                    } else { 
                        isDupe = false;
                    }
                }

            }
            div --;
    }

    Triangulate (frequency, workingList);
}

This is a function that given the frequency, this is the number of vertices that are placed between two vertexes on the original triangle, a list of vertices, and a list of faces it will, without duplicates, subdivide the faces accordingly. Then it calls the triangulate function that is supposed to group this into actual faces.

This for a frequency 'f' means that now every edge will have 2+f vertices instead of 2. I use this definition of frequency because it's what it's used when talking about Goldberg polyhedra.

void Triangulate(int frequency, List<Vector3> vertList){
    List<TriangleIndices> faces = new List<TriangleIndices> ();
    int div = frequency + 1;
    int divRecursive = 0;

    for (int k = 0; k < frequency + 1; k++) {

        for (int i = 0; i < div ; i++) {
            faces.Add (new TriangleIndices (i + divRecursive, i + 1 + divRecursive, i + div + 1 + divRecursive));
        } 
        for (int i = 0; i < div - 1; i++) {
            faces.Add (new TriangleIndices (i + 1 + divRecursive, i + div + 2 + divRecursive, i + div + 1 + divRecursive));
        }
        divRecursive += div + 1;
        div--;
    }

    List< int > triList = new List<int> ();
    for (int i = 0; i < faces.Count; i++) {
        triList.Add (faces [i].v1);
        triList.Add (faces [i].v2);
        triList.Add (faces [i].v3);
    }

    Debug.Log("There are " + faces.Count +" faces and " + vertList.Count + " vertices");
    mesh.vertices = vertList.ToArray ();
    mesh.triangles = triList.ToArray();
    mesh.RecalculateNormals();
    mesh.RecalculateBounds ();
}

This is my triangulate function, and at the moment, it only does the first face because i'm not sure how to do the other faces. Worth noting some stuff about it, divRecursive is a variable used to store the first vertex of the next line, div stands for divisions and is the number of divisions on each edge.

Now I need them to be grouped in faces to be able to then find the center of each face and apply a duality transformation to get the shape I actually want so if you have any tips for that too I'd be more than happy to hear them.

EDIT: This is a small video showing how it works

Answer 1

My preferred approach is to split the geosphere into flat charts, bent a little to fit a simple square grid so they're easier to reason about:

Let's say we split the underlying icosahedron into 5 of these charts as shown above. To avoid duplicating work, we can apply a rule that vertices along the top & right edges of each chart "belong" to a different chart (including a bonus 6th chart for the North & South Pole vertices). This lets us construct a well-defined regular ordering of the vertices and triangles in terms of their grid coordinates:

We can iterate over each rectangle of solid dots in this image to produce the vertices in this order, without ever visiting a vertex twice and needing to check for a duplicate.

Once we have the vertices in order, it's super fast to identify the vertices bounding a given triangle. And for Class-I geodesics we have the extra-nice property that each triangle "belongs" unambiguously to exactly one chart, so we can simply number them across each row like so:

(Of course all the numbering rules I've used here are arbitrary, and you can choose a different way to exploit the grid structure to still get the same predictability with whatever numbering scheme you prefer)

Here's an example of how we could build a triangle list (3 vertex indices per triangle) using the structure developed thus far:

(Disclaimer: this was all just written for this answer - I haven't compiled this code, so it's very likely there are typos or off-by-one errors I didn't spot, but it should at least show the flavour of this approach)

// Set up some reference values based on the size of our geosphere.
int rowSize = 2 * frequency;
int chartSize = rowSize * frequency;

int northPoleIndex = chartSize * 5;
int southPoleIndex = northPoleIndex + 1;

// (Our vertices array has northPoleIndex + 2 entries in total)

int t; // Tracks which triangle index we're writing to next.

for(int chart = 0; chart < 5; chart++) {

   // First, construct all the triangles wholly surrounded by black dots.
   // (ie. 0-13, 16-29, 32-45...)
   for(int row = 0; row < frequency; row++) {
      for(int col = 0; col < rowLength; col++) {

          // index of the vertex at the bottom-left of the cell.
          int baseVertex = chartSize * chart + rowSize * row + column);

          // 2 triangles per cell, 3 indices per triangle.
          t = 2 * 3 * baseVertex;

          // Top-left triangle in the cell.
          indices[t++] = baseVertex;
          indices[t++] = baseVertex + rowSize + 1;
          indices[t++] = baseVertex + rowSize;

          // Bottom-right triangle in the cell.
          indices[t++] = baseVertex;
          indices[t++] = baseVertex + 1;
          indices[t++] = baseVertex + rowSize + 1;
      }
    }

    // Now we handle triangles that border on the next chart & the poles.
    int nextChart = (chart + 1) % 5;

    // North pole cell.
    int topLeft = chart * chartSize + chartSize - rowSize;
    int nextTopLeft = nextChart * chartSize + chartSize - rowSize; 
    t = 2 * 3 * topLeft;

    indices[t++] = topLeft;
    indices[t++] = nextTopLeft;
    indices[t++] = northPoleIndex;

    indices[t++] = topLeft;
    indices[t++] = topLeft + 1;
    indices[t++] = nextTopLeft;

    // Continue rightward along the top edge of the chart, to its midpoint:
    for(int edge = 1; edge < frequency; edge++) {
        int baseVertex = topLeft + edge;
        int nextChartBase = nextTopLeft - rowSize * edge;

        indices[t++] = baseVertex;
        indices[t++] = nextChartBase;
        indices[t++] = nextChartBase + rowSize;

        indices[t++] = baseVertex;
        indices[t++] = baseVertex + 1;
        indices[t++] = nextChartBase;
    }

    // Next, continue from the midpoint of the top edge toward the right corner.
    ...

    // Then the top-right corner cell
    ...

    // Then down the right edge to the bottom
    ...

    // And lastly the bottom-right cell, bordering on the South pole
    ...

It's a little annoying to break out each segment of the rectangle into its own little loop, so an alternative method you can consider would be to lay all the charts out on a single x-y grid, and provide a function that takes an x,y coordinate and returns the corresponding vertex index.

int VertexIndex(int x, int y, int frequency) {
    // (Assuming integer division rounding toward zero)
    int chart = y / frequency; 

    int col = x - frequency * chart;

    // Catch references off the top of the left zig-zag edge:
    if( col < 0 ) {

        // North pole.
        if(col = -frequency)
           return frequency * frequency * 10;

        // Bend references up to vertical edge.
        y -= x;
        x = 0;
    }
    // Catch references off the right of the other zig-zag edge:
    else if ( col >= 2 * frequency ) {

        // South pole.
        if(y - chart * frequency == 0)
            return frequency * frequency * 10 + 1;

        // Bend references up to next horizontal edge.
        int nextY = (chart + 1) * frequency;
        x = frequency + nextY - y;
        y = nextY;
    }

    // Wrap references off the top of the chart back around to the bottom.
    y %= frequency * 5;

    // Return the computed index.
    return y * 2 * frequency + col;
}

Now we can have a much simpler-looking loop (though it does more conditional logic at each step):

int t = 0;
for(int chart = 0; chart < 5; chart++) {
   for(int row = 0; row < frequency; row++) {
      for(int col = 0; col < 2 * frequency; col++) {
          int x = chart * frequency + col;
          int y = chart * frequency + row;

          int a = VertexIndex(x, y, frequency);
          int b = VertexIndex(x + 1, y, frequency);
          int c = VertexIndex(x + 1, y + 1, frequency);
          int d = VertexIndex(x, y + 1, frequency);

          indices[t++] = a;
          indices[t++] = c;
          indices[t++] = d;

          indices[t++] = a;
          indices[t++] = b;
          indices[t++] = c;
      }
   }
}

I hope that gives you some useful leads!