algorithm to sort out an icosphere's vertices, help needed

Unity Engine
1

Hi guys,
I’m making a grand strategy game in which the map is an icosphere (ie a sphere composed of hexagons and 12 pentagons).
Papers about hexaginal grids I found on the net mention flat maps only and do not apply to my case (unless I misunderstand the core concept), so I’m calling for your help :slight_smile:
I think you need details (I’m affraid this makes for a lengthy post) :

  • What am I intending to do exactely :
    As the player clicks, or the mouse hovers over the sphere, data corresponding to the selected cell is retrieved and served for the player’s masochistic pleasure.
    Obviously this system is the game’s backbone, and nothing can be done without it !

  • What am I doing precisely :
    I divided planet Earth into 20 game objects, each of them representing the icosphere face (bcs meshes can’t store more than 2^16 vertices and we do need plenty).
    Each face is subdivided 6 times (1 hexagon represents ~100km). Needless to say that there’ll be TONS of hexagons :slight_smile:
    Each vertex is the center of an hexagon (or pentagon). Actually it’s more complicated (I want to save your synapses =), you’ll see at the end of the post…
    The world cells data will be stored into an array[ ], in its own script : the data managing script.
    That script will access data by knowing the clicked/hovered face id and the closest vertex from the click.
    I want to acces a given cell like that :
    int index = faceId * faceLength + vertexId; // faceId, faceLength are passed by the face game object script. VertexId is retrieved by computing the shortest distance raycasthit.point ↔ raycasthit.triangleIndex (we’re making 3 checks)
    array[index].DoStuff ();
    In order this to work, array needs data be stored by face and vertex order (that’s tricky to explain, example incoming)
    That’s precisely my issue, the algorithm responsible for creating the geometry works that way ( SarvanZ: Sphere tessellation/triangulation using Icosahedron ) :
    Primary face vertices (* = vertex)

             *A
        


  C*                  *B

We get (beware pseudo code) mesh.vertices = { A,B,C }

1st subdivision

             *A

     1*           *2

  C*        *         *B
              3

mesh.vertices = { A,B,C,1,2,3 }

The 2nd subdivision will break a,b,c into 4 triangles, leading to sth like mesh.vertices = { A,B,C,1,2,3,do,re,mi } // Hear the programing melody ? :wink:
Rince and repeat 4 more times. I let you imagine the mess inside mesh.vertices (and triangles)

What I want to achieve is ordering vertices the same way as we, westerners, read text (upper row, left, to right, then next row, left right…) :
mesh.vertices = { A,1,2,C,3,B }

I can’t find a way to achieve this, especially knowing that in addition to vertices reordering, we must reassign triangles.
Oh, remember that I told you it gets dirtier ? every vertices are generated 3 times (the same texture is applied on every triangles, UVs will differ depending on terrain type)
T_T

I will greatly appreciate some help, really and I thank you a lot by advance
p.s. : I’ll take any simpler/better way to handle this visuals-data system

2

Some people visited this thread without replying. Maybe that’s because I didn’t show my work ?
I didn’t want to make the post even more longer but it’s ok to add it here.
I don’t want people to think that I’m waiting for a turnkey solution.

Here’s one side script, that is attached to one of the 20 game objects I mentioned earlier :

using UnityEngine;
using System.Collections.Generic;

[RequireComponent (typeof (MeshFilter), typeof (MeshRenderer), typeof (MeshCollider))]
public class F_00 : FaceScript
{
    MeshFilter filter;
    Mesh mesh;
    MeshCollider collider;
    Vector3[] vertices;
    /// <summary>
    /// True if the face is oriented upwards.
    /// Necessary to do the mapping correctly, not used yet
    /// </summary>
    bool isOrientedUpwards;
  
    void Awake () {
        filter = (MeshFilter) gameObject.GetComponent< MeshFilter >();
        mesh = filter.mesh;
        collider = (MeshCollider) gameObject.GetComponent<MeshCollider> ();
        vertices = mesh.vertices;
    }
  
    private struct TriangleIndices
    {
        public int v0;
        public int v1;
        public int v2;
      
        public TriangleIndices(int v00, int v11, int v22)
        {
            this.v0 = v00;
            this.v1 = v11;
            this.v2 = v22;
        }
    }
  
    // return index of point in the middle of p1 and p2
    private static int getMiddlePoint(int p1, int p2, ref List<Vector3> vertices, float radius)
    {
        // not in cache, calculate it
        Vector3 point1 = vertices[p1];
        Vector3 point2 = vertices[p2];
        Vector3 middle = new Vector3
            (
                (point1.x + point2.x) / 2f,
                (point1.y + point2.y) / 2f,
                (point1.z + point2.z) / 2f
                );
      
        // add vertex makes sure point is on unit sphere
        int i = vertices.Count;
        vertices.Add( middle.normalized * radius );
      
        return i;
    }
  
    public override void Create (float radius, int recursionLevel)
    {
        mesh.Clear();
      
        List<Vector3> vertList = new List<Vector3>();
      
        // create 12 vertices of a icosahedron
        float t = (1f + Mathf.Sqrt(5f)) / 2f;
        Debug.Log ("magic number = " +t);

        #region VERTICES & TRIANGLES

        // V 0 (TOP VERTEX)
        vertList.Add(new Vector3( 0f,  1f,  t).normalized * radius);
        // V 1
        vertList.Add(new Vector3( 1f,  t,  0f).normalized * radius);
        // V 2
        vertList.Add(new Vector3(-1f,  t,  0f).normalized * radius);
      
        // create face triangles
        List<TriangleIndices> faces = new List<TriangleIndices>();

        // NORTH 0 (Face (0))
        //      *0 (vertex 0)
        //   a+   +b
        //  2*  +  *1 (vertex 1)
        //      c
        faces.Add(new TriangleIndices(0, 1, 2)); // N0, 0, 1, 2
        #endregion

        // refine triangles
        for (int i = 0; i < recursionLevel; i++)
        {
            List<TriangleIndices> faces2 = new List<TriangleIndices>();
            foreach (var tri in faces)
            {
                // replace triangle by 4 triangles
                int a = getMiddlePoint(tri.v2, tri.v0, ref vertList, radius);
                int a2 = getMiddlePoint(tri.v2, tri.v0, ref vertList, radius);
                int a3 = getMiddlePoint(tri.v2, tri.v0, ref vertList, radius);

                int b = getMiddlePoint(tri.v0, tri.v1, ref vertList, radius);
                int b2 = getMiddlePoint(tri.v0, tri.v1, ref vertList, radius);
                int b3 = getMiddlePoint(tri.v0, tri.v1, ref vertList, radius);
              
                int c = getMiddlePoint(tri.v1, tri.v2, ref vertList, radius);
                int c2 = getMiddlePoint(tri.v1, tri.v2, ref vertList, radius);
                int c3 = getMiddlePoint(tri.v1, tri.v2, ref vertList, radius);

              
                faces2.Add(new TriangleIndices(tri.v0, b, a)); // Triangle UP
                faces2.Add(new TriangleIndices(a2, c2, tri.v2)); // Triangle LEFT
                faces2.Add(new TriangleIndices(a3, b3, c3)); // Triangle MIDDLE
                faces2.Add(new TriangleIndices(b2, tri.v1, c)); // Triangle RIGHT
            }
            faces = faces2;
        }
      
        mesh.vertices = vertList.ToArray();
      
        List< int > triList = new List<int>();
        for( int i = 0; i < faces.Count; i++ )
        {
            triList.Add( faces[i].v0 );
            triList.Add( faces[i].v1 );
            triList.Add( faces[i].v2 );
        }      
        mesh.triangles = triList.ToArray();
        Vector2[] UVs = ComputeUVs ();
        mesh.uv = UVs;
      
        Vector3[] normales = new Vector3[ vertList.Count];
        for( int i = 0; i < normales.Length; i++ )
            normales[i] = vertList[i].normalized;
      
      
        mesh.normals = normales;
      
        mesh.RecalculateBounds();
        mesh.Optimize();

        collider.sharedMesh = mesh;
    }
  
    Vector2[] ComputeUVs () {

        Vector2[] UVs = new Vector2[ mesh.vertices.Length ];
        int c = 0;
      
        for (int i = 0; i < mesh.triangles.Length; i++) {
            int vertexId = mesh.triangles[i];
          
            if (c == 0) {
                UVs[vertexId] = new Vector2 (.5f, .05859385f);
            }
            else if (c == 1) {
                UVs[vertexId] = new Vector2 (.890625f, .735375f);
            }
            else {
                UVs[vertexId] = new Vector2 (.109375f, .735375f);
                c = -1;
            }
            c++;
        }
      
        return UVs;
    }
}

You can see that the triangles should be sorted out, well with the current vertices construction.
All I need to know is how to sort the vertices and I’ll figure out the triangles (hopefully =)

Again, sorry for the massive post(s), but you’ll agree that the issue is quite complicated.

3

After spending a few days on it, I can tell that I’ve tackled the problem the wrong way.
Actually the problem is the mesh subdivision method.
Dividing edges by 2 recursively messes everything up, as shown in the 1st post above.

There’s a better way to do that, if you want to sort vertices.
In case some people are interested, here’s the principle :

  • You’ve got your initial triangle, with vertices A (top), B (left) and C (right)
  • Compute how many rows of hexagons u want to have between pentagons (say we want 5 hexas. Remember that Unity limits us to 65K vertices/mesh)
  • For eah row,
  • Compute row coeficient from vertex A to either B or C, it does not matter (row 1 coef = 1/ (5 hexas +2 pentas) = 1/7)
  • Compute the row’s leftmost vertex (x = 1/7 (A.x+B.x), same for y and z) (in my case, for my UV needs, I created 3 vertices @ the same location). Add a condition to avoid adding 3 times B !
  • Do the same with the rightmost vertex (x = 1/7 (A.x+C.x), same for y and z) (in my case, I created 3 vertices @ the same location)
  • Then, compute vertices inbetween (same principle than above, in its own loop) (here too, I created 3 verts per position)
  • Out of the 2nd loop, add in that order leftmost, then vertices in between, then rightmost vertices to your final vertex list
  • Out of both loops, remove the last two vertices in order to have only one C vertex
    The post’s getting long so I let you take care of the details

Here you have your verices. Normalize them and apply radius and you get 1/20th of a sphere.
Repeat the process with the icosahedron’s other 19 triangles to get an isosphere with up to 64 subdivisions !
64 subdiv’ => 1 hexagon represents about 100km on Earth.
Hoping all my explanations are clear :slight_smile:

Now, I’ve got difficulties to sort out triangles (this would’ve risen with the previous method by the way).
I’ll post the solution once I solved this last issue.

Thanks for reading :wink: