Question Generating a hexgrid over an icospheres help

axxessdenied · Feb 3, 2021

I decided to take a crack at procedurally generating a sphere from an icosahedron and trying to create a hexgrid pattern over it.

I've made decent progress since last night. But, I'm still figuring out how to work with meshes.
For some reason some of the meshes for the hexgrids I create have the normals flipped around and don't get drawn properly since the camera thinks they are facing the wrong way.

I've used these two pages as a starting point for the project :
// http://blog.andreaskahler.com/2009/06/creating-icosphere-mesh-in-code.html
// https://github.com/joeld42/hexplanet/

I've attached the code and picture of what's going on.

Any guidance in the right direction would be highly appreciated! CreatePolygon() is at the bottom which creates the mesh for each hexgrid.

HexTile.cs

Code (csharp):

using System.Collections.Generic;

using UnityEngine;

//credit goes to Joel Davis https://github.com/joeld42/hexplanet/

//triangles that make up our pentagons and hexagons

public class HexTri

{

public HexTri(int A, int B, int C)

{

_hexA = A;

_hexB = B;

_hexC = C;

_neighbourAB = null;

_neighbourBC = null;

_neighbourCA = null;

}

private readonly int _hexA;

private readonly int _hexB;

private readonly int _hexC;

private float _angle;

private int _newVert;

//connectivity, links to neighbours

//separated by edges

private HexTri _neighbourAB, _neighbourBC, _neighbourCA;

public Vector3 GetCentre(List<HexTile> Tiles)

{

var centrePoint = Tiles[_hexA].Position;

centrePoint += Tiles[_hexB].Position;

centrePoint += Tiles[_hexC].Position;

centrePoint /= 3.0f;

return centrePoint;

}

public int HexA => _hexA;

public int HexB

{

get => _hexB;

set => throw new System.NotImplementedException();

}

public int HexC

{

get => _hexC;

set => throw new System.NotImplementedException();

}

public HexTri NeighbourAB

{

get => _neighbourAB;

set => _neighbourAB = value;

}

public HexTri NeighbourBC

{

get => _neighbourBC;

set => _neighbourBC = value;

}

public HexTri NeighbourCA

{

get => _neighbourCA;

set => _neighbourCA = value;

}

}

//hexTile, stores a list of HexTri it contains

public class HexTile

{

public HexTile(Vector3 p)

{

_position = p;

_terrain = Type.DESERT;

_normal = p.normalized;

_triangles = new List<HexTri>();

}

public enum Type

{

WATER = 0,

DESERT = 1,

GRASSLAND= 2,

FOREST= 3,

MOUNTAIN = 4

}

private Type _terrain;

private Vector3 _position;

private Vector3 _normal;

private readonly List<HexTri> _triangles;

public Vector3 Position

{

get => _position;

set => _position = value;

}

public Vector3 Normal

{

get => _normal;

set => _normal = value;

}

public List<HexTri> HexTris => _triangles;

public Type Terrain

{

get => _terrain;

set => _terrain = value;

}

}

Planet.cs

Code (csharp):

using System;

using System.Collections.Generic;

using System.Diagnostics;

using UnityEngine;

using Debug = UnityEngine.Debug;

using Random = UnityEngine.Random;

using Vector3 = UnityEngine.Vector3;

//based off work by Andreas Kahler and Joel Davis

// http://blog.andreaskahler.com/2009/06/creating-icosphere-mesh-in-code.html

// https://github.com/joeld42/hexplanet/

//other references

// https://en.wikipedia.org/wiki/Icosahedron

// https://en.wikipedia.org/wiki/Truncated_icosahedron

// https://samos.univ-paris1.fr/archives/WSOM05/papers/WSOM2005-11.pdf

// https://experilous.com/1/blog/post/procedural-planet-generation

public class Planet : MonoBehaviour

{

public Material material;

public float radius = 20.0f;

public int resolution = 3;

public Material tileMaterial;

private GameObject _planetMesh;

private int _subdivisionLevel;

private readonly List<HexTile> _tileList = new List<HexTile>();

private List<HexTri> _triangleList = new List<HexTri>();

private void Start()

{

var stopwatch = new Stopwatch();

stopwatch.Start();

InitializeIcosahedron();

while (_subdivisionLevel < resolution)

Subdivide();

GeneratePlanetMesh();

GenerateHexGridMesh();

stopwatch.Stop();

Debug.Log($"Start process took {stopwatch.Elapsed} seconds.");

}

private void InitializeIcosahedron()

{

var t = (1.0f + Mathf.Sqrt (5.0f)) * 0.5f;//golden mean

_tileList.Add(new HexTile(new Vector3(-1, t, 0)));

_tileList.Add(new HexTile(new Vector3(1, t, 0)));

_tileList.Add(new HexTile(new Vector3(-1, -t,0)));

_tileList.Add(new HexTile(new Vector3(1, -t, 0)));

_tileList.Add(new HexTile(new Vector3(0, -1, t)));

_tileList.Add(new HexTile(new Vector3(0, 1, t)));

_tileList.Add(new HexTile(new Vector3(0, -1, -t)));

_tileList.Add(new HexTile(new Vector3(0, 1, -t)));

_tileList.Add(new HexTile(new Vector3(t, 0, -1)));

_tileList.Add(new HexTile(new Vector3(t, 0, 1)));

_tileList.Add(new HexTile(new Vector3(-t, 0, -1)));

_tileList.Add(new HexTile(new Vector3(-t, 0, 1)));

_triangleList.Add(new HexTri(0, 11, 5));

_triangleList.Add(new HexTri(0, 5, 1));

_triangleList.Add(new HexTri(0, 1, 7));

_triangleList.Add(new HexTri(0, 7, 10));

_triangleList.Add(new HexTri(0, 10, 11));

_triangleList.Add(new HexTri(1, 5, 9));

_triangleList.Add(new HexTri(5, 11, 4));

_triangleList.Add(new HexTri(11, 10, 2));

_triangleList.Add(new HexTri(10, 7, 6));

_triangleList.Add(new HexTri(7, 1, 8));

_triangleList.Add (new HexTri(3, 9, 4));

_triangleList.Add (new HexTri(3, 4, 2));

_triangleList.Add (new HexTri(3, 2, 6));

_triangleList.Add (new HexTri(3, 6, 8));

_triangleList.Add (new HexTri(3, 8, 9));

_triangleList.Add (new HexTri(4, 9, 5));

_triangleList.Add (new HexTri(2, 4, 11));

_triangleList.Add (new HexTri(6, 2, 10));

_triangleList.Add (new HexTri(8, 6, 7));

_triangleList.Add (new HexTri(9, 8, 1));

Debug.Log($"Triangle Count is {_triangleList.Count}");

Debug.Log($"Tile Count is {_tileList.Count}");

//assign neighbours

FindNeighbours();

}

private int GetMidPointIndex(IDictionary<int, int> Cache, int A, int B)

{

//create a key from the original indices

//store the smaller index in the upper two bytes of an integer

//this makes sure the function returns the same result

//at all times since we sort by the smaller index first

var smallerIndex = Mathf.Min(A, B);

var largerIndex = Mathf.Max(A, B);

var key = (smallerIndex << 16) + largerIndex;

//check if the point exists

if (Cache.TryGetValue(key, out var ret))

return ret;

//create new midpoint

var p1 = _tileList[A].Position;

var p2 = _tileList[B].Position;

var middle = Vector3.Slerp(p1, p2, 0.5f).normalized * radius;

ret = _tileList.Count;

_tileList.Add(new HexTile(middle));

Cache.Add(key, ret);

return ret;

}

private void Subdivide()

{

var midPointCache = new Dictionary<int, int>();

var newHexTris = new List<HexTri>();

foreach (var hexTri in _triangleList)

{

var a = hexTri.HexA;

var b = hexTri.HexB;

var c = hexTri.HexC;

//get or create midpoints between the original vertices

var ab = GetMidPointIndex(midPointCache, a, b);

var bc = GetMidPointIndex(midPointCache, b, c);

var ca = GetMidPointIndex(midPointCache, c, a);

//original HexTri gets subdivided into 4 smaller HexTri

newHexTris.Add(new HexTri(a, ab, ca));

newHexTris.Add(new HexTri(b, bc, ab));

newHexTris.Add(new HexTri(c, ca, bc));

newHexTris.Add(new HexTri(ab, bc, ca));

}

_triangleList = newHexTris;

FindNeighbours();

ProjectToSphere();

_subdivisionLevel++;

Debug.Log($"Current triangles : {_triangleList.Count}");

Debug.Log($"Current number of tiles is : {_tileList.Count}");

}

private void GeneratePlanetMesh()

{

//destroy existing object if it exists

if (_planetMesh)

Destroy(_planetMesh);

_planetMesh = new GameObject("Planet Mesh");

var surfaceRenderer = _planetMesh.AddComponent<MeshRenderer>();

surfaceRenderer.material = material;

var terrainMesh = new Mesh();

var triangleCount = _triangleList.Count;

var vertexCount = triangleCount * 3;

var indices = new int[vertexCount];

var vertices = new Vector3[vertexCount];

var normals = new Vector3[vertexCount];

for (var i = 0; i < triangleCount; i++)

{

var hexTri = _triangleList[i];

indices[i * 3] = i * 3;

indices[i * 3 + 1] = i * 3 + 1;

indices[i * 3 + 2] = i * 3 + 2;

vertices[i * 3] = _tileList[hexTri.HexA].Position;

vertices[i * 3 + 1] = _tileList[hexTri.HexB].Position;

vertices[i * 3 + 2] = _tileList[hexTri.HexC].Position;

normals[i * 3] = _tileList[hexTri.HexA].Normal;

normals[i * 3 + 1] = _tileList[hexTri.HexB].Normal;

normals[i * 3 + 2] = _tileList[hexTri.HexC].Normal;

}

terrainMesh.vertices = vertices;

terrainMesh.normals = normals;

terrainMesh.SetTriangles(indices, 0);

var terrainFilter = _planetMesh.AddComponent<MeshFilter>();

terrainFilter.mesh = terrainMesh;

}

private static bool EdgeMatch(int A, int B, int OtherA, int OtherB, int OtherC)

{

return A==OtherA && B==OtherB ||

A==OtherB && B==OtherC ||

A==OtherC && B==OtherA ||

B==OtherA && A==OtherB ||

B==OtherB && A==OtherC ||

B==OtherC && A==OtherA;

}

private void FindNeighbours()

{

foreach (var hexTile in _tileList)

{

hexTile.HexTris.Clear();

}

foreach (var hexTri in _triangleList)

{

foreach (var hexTri2 in _triangleList)

{

if (hexTri == hexTri2) continue;

//neighbour A<->B edge

if (EdgeMatch(hexTri.HexA, hexTri.HexB, hexTri2.HexA, hexTri2.HexB, hexTri2.HexC))

hexTri.NeighbourAB = hexTri2;

//neighbour B<->C edge

if (EdgeMatch(hexTri.HexB, hexTri.HexC, hexTri2.HexA, hexTri2.HexB, hexTri2.HexC))

hexTri.NeighbourBC = hexTri2;

//neighbour C<->A edge

if (EdgeMatch(hexTri.HexC, hexTri.HexA, hexTri2.HexA, hexTri2.HexB, hexTri2.HexC))

hexTri.NeighbourCA = hexTri2;

}

_tileList[hexTri.HexA].HexTris.Add(hexTri);

_tileList[hexTri.HexB].HexTris.Add(hexTri);

_tileList[hexTri.HexC].HexTris.Add(hexTri);

}

}

private HexTile.Type GetRandomTerrain(float TWater)

{

if (Random.value <= TWater) return HexTile.Type.WATER;

// return a land hex

var values = (HexTile.Type[])Enum.GetValues(typeof(HexTile.Type));

var t = (int)Random.value * values.Length + 1;

t = t > values.Length ? values.Length : t;

return values[t];

}

private void ProjectToSphere()

{

foreach (var hexTile in _tileList)

{

var p = hexTile.Position;

p = p.normalized * radius;

hexTile.Position = p;

}

}

//returns polygon representation

private List<Vector3> GetPolygon (HexTile Tile, float Offset = 0.0f)

{

//clear list

var poly = new List<Vector3>();

foreach (var hexTri in Tile.HexTris)

{

var p = hexTri.GetCentre(_tileList).normalized;

p *= radius + Offset;

poly.Add(p);

}

//sort the polygons so they are arranged in an orderly fashion

var edges = poly.Count;

//angles won't be exact

//set an acceptable range to compensate for distortions

var maxAngle = 360.0f / edges + 5f;

var minAngle = 360.0f / edges - 5f;

var sortedPoly = new List<Vector3> {poly[0]};

poly.RemoveAt(0);

for (var i = 0; i < edges; i++)

{

var found = false;

var pop = new Vector3();

var smallestPoint = new Vector3();

var smallestAngle = 180.0f;

//arrange points by angle

foreach (var p in poly)

{

if (found) continue;

//sometimes distortions will lead to angles not being found right away

//lets store the smallest angle we find in case all angles don't fall within our set range

//seems to work after filtering the angles closest to the acceptable range

//TODO might be a better solution to this

var angle = Vector3.Angle(Tile.Position - sortedPoly[i], Tile.Position - p);

if (angle < smallestAngle)

{

smallestAngle = angle;

smallestPoint = p;

}

if (!(angle <= maxAngle) || !(angle >= minAngle)) continue;

sortedPoly.Add(p);

found = true;

pop = p;

}

if (!found && sortedPoly.Count < edges)

{

pop = smallestPoint;

sortedPoly.Add(pop);

}

poly.Remove(pop);

}

sortedPoly.Reverse();

return sortedPoly;

}

//creates a representation of each tile

private void GenerateHexGridMesh()

{

for (var i = 0; i < _tileList.Count; i++)

CreatePolygon(i);

}

//creates an individual tile

//some of the tiles have their normals flipped

//TODO need to fix this

private void CreatePolygon(int Tile)

{

var poly = GetPolygon(_tileList[Tile], 0.25f);

var edges = poly.Count;

//find centre point:

var centre = new Vector3();

switch (edges)

{

//if 5 edges

//find the midpoint between point 2 and 3 (by index)

//find midpoint between point 0 and new point

//0<-.->midpoint

case 5:

var midpoint = (poly[2] + poly[3]) / 2;

centre = (poly[0] + midpoint) / 2;

break;

//if 6 edges

//find midpoint between opposing corners

//0<-.->3 1<-.->4 2<-.->5

case 6:

centre = (poly[0] + poly[3]) / 2;

break;

}

var obj = new GameObject($"Polygon Tile {Tile}");

var surfaceRenderer = obj.AddComponent<MeshRenderer>();

surfaceRenderer.material = tileMaterial;

var terrainMesh = new Mesh();

var vertexCount = edges * 3;

var indices = new int[vertexCount];

var vertices = new Vector3[vertexCount];

var normals = new Vector3[vertexCount];

for (var i = 0; i < edges; i++)

{

var a = centre;

var b = poly[i];

var c = i != edges-1 ? poly[i + 1] : poly[0];

var nA = a.normalized;

var nB = b.normalized;

var nC = c.normalized;

indices[i * 3] = i * 3;

indices[i * 3 + 1] = i * 3 + 1;

indices[i * 3 + 2] = i * 3 + 2;

vertices[i * 3] = a;

vertices[i * 3 + 1] = b;

vertices[i * 3 + 2] = c;

normals[i * 3] = nA;

normals[i * 3 + 1] = nB;

normals[i * 3 + 2] = nC;

}

terrainMesh.vertices = vertices;

terrainMesh.normals = normals;

terrainMesh.SetTriangles(indices, 0);

var terrainFilter = obj.AddComponent<MeshFilter>();

terrainFilter.mesh = terrainMesh;

}

}

Bunny83 · Feb 3, 2021

So do I get you right, the missing tiles are not on purpose and you actually created a full sphere? If that's the case the code you use probably does not care about the winding order. This is a bit problematic ^^. Of course you could try to incoperate the right winding order in your triangle generation, however a simple fix would be to run a correction pass after you generated your triangles.

As you may know the direction a triangle faces is determined by the winding order or the triangle. While in OpenGL the front face is usually determined by a counter clockwise winding, Unity (which uses a left handed coordinate system) defines the front face by a clockwise winding order.

So it matters in which order the 3 indices of a triangle are stored in the triangle array. If you trace the vertices as seen from the camera in the order they are referenced by the triangle indices describe a clockwise winding, it means that triangle would be visible.

The great thing about a sphere is that all tiles / faces are perpendicular to the normal vector that connects each vertex with the sphere center. So you can determine the winding order with a bit of vector math. So imagine you take a look at a single triangle with the corners A, B and C. Lets call the sphere center "O". To check the winding order of that triangle you just need to construct two edges of that triangle. For example AB and BC (the third edge would be CA). Now calculating the cross product between the two edges give you a vector that is perpendicular to the plane the triangle lies in. However the direction depends on the order of the two vectors. As mentioned Unity uses a left handed system, so the left-hand-rule applies. If you do
var p = Vector3.Cross(AB, BC)
the resulting vector would point outwards from the triangle if the winding order is correct.

Now we can simply calculate the dot product between that vector and any of the vectors that go from the sphere center to any of the 3 vertices. Technically the correct vector would be the vector from the center of the sphere to the center of the triangle, but that's not really necessary as you just want to know if the triangle points in the right or wrong direction. So doing
float d = Vector3.Dot(p, OA);
gives us a number that will be positive if the triangle id oriented the right way and negative if it's oriented the wrong way. Once you identified a triangle that need to be flipped, all you have to do is swap two of the 3 indices of that triangle. Which pair you switch is irrelevant. So assuming a triangle has the indices 12, 3, 8 you can swap any two pairs. So valid solutions would be (3,12,8) or (12,8,3) or (8,3,12). So just swap the first two indices of that triangle and it will be oriented the right way.

axxessdenied · Feb 3, 2021

Yeah, I haven't figured out how to handle the winding order yet. That's definitely something I should implement. Your simple fix is along the lines of what I was thinking of trying in the mean time. Thanks for the detailed response

axxessdenied · Feb 3, 2021

https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html
A winged-edge data structure might be what I need to implement to keep track of the vertices.

Bunny83 · Feb 3, 2021

axxessdenied said: ↑

A winged-edge data structure might be what I need to implement to keep track of the vertices.
Click to expand...

I don't really think that this would be necessary. I guess you just have an error / the wrong order of the indices either in your subdivision routine or your original hex tri generation method. If the base structure is right and the subdivision is done correctly there should be no issues with the winding order.

I've posted a subdivision implementation over here with some explanation in the comments below. It generally helps to draw an image of your structure so you don't get lost between your indices.

axxessdenied · Feb 5, 2021

Thanks a lot for the help @Bunny83
I've restarted the project using the ecs approach with dots and i've got a working mesh being created already and its running noticeably quicker too

Touhma_Slater · Feb 8, 2022

I would love to see the code for that if possible !

Search Unity

Question Generating a hexgrid over an icospheres help

axxessdenied

Attached Files:

hexagrid.png

Bunny83

axxessdenied

axxessdenied

Bunny83

axxessdenied

Touhma_Slater

Search Unity

Unity ID

Useful Searches

Question Generating a hexgrid over an icospheres help

Attached Files: