Geodesic Grid – Part 3

Dual Polyhedron

In order to make our Geodesic Grid, we need to get the dual polyhedron form of our subdivided icosahedron.  In theory, it’s a fairly simple process.  Each vertex of the icosahedron corresponds to a cell (the planar face).  The cell is defined by its corners which are the positions of the center of each face in the icosahedron that adjoins the icosahedron vertex.

When that simple process is applied to every vertex of the subdivided icosahedron, we end up with the cells we need for our geodesic.

Design Decisions

So we’ve got the basic idea of what a Cell is.  Before we go further though, I want to take some time to discuss the functionality I’m aiming for in the end.  I know that at the outset I said this would be all about the shape, and not about a game or anything else.  However, having just the vertices and indices of the geodesic grid is fairly useless in the end.  About all you could do with that information is draw the shape.

As a base level of functionality, I’d like to have each Cell have a reference to its neighbors.  What purpose would this serve?  Well, the most apparent use I can think of is for pathfinding.  Knowing which Cells border which other Cells can make a pathfinding algorithm like A* much simpler.  My pathfinding code is heavily influenced by Leniel Macaferi’s blog posts on the subject.

With that in mind, I’ll introduce a new interface called INode that our Cell class will implement.

public interface INode
{
    Guid Key { get; }
    AdjacencyList NeighborLinks { get; }
    List<INode> Neighbors { get; }
}

public class Cell : INode
{
    public int[] Indices;

    public Guid Key { get; private set; }

    public AdjacencyList NeighborLinks { get; private set; }

    public List<INode> Neighbors
    {
        get
        {
            List<INode> nodes = new List<INode>();

            foreach (LinkToNeighbor link in NeighborLinks)
            {
                nodes.Add(link.Neighbor);
            }

            return nodes;
        }
    }

Our Cell class knows what indices its vertices are at in the greater DualPolyhedron (listed below), though our DualPolyhedron class will hold the actual vertex data.

It also has an AdjacencyList which is essentially a collection of LinkToNeighbor.

public class LinkToNeighbor
{
    public virtual double Cost { get; private set; }
    public virtual INode Neighbor { get; private set; }
}

LinkToNeighbor holds data about which node it links to, and the “cost” to travel the link.

And here’s the previously mentioned DualPolyhedron class.

public class DualPolyhedron
{
    public byte Frequency;
    public NodeCollection<Cell> Cells;
    public Wireframe Wireframe;
    public VertexPositionNormal[] Vertices { get; set; }
    public int[] Indices { get; set; }
}

It’s nearly identical to the Icosahedron class. The only difference is the NodeCollection, which is a KeyedCollection of INodes keyed on their Guid keys for easy lookup.

In Part 4, I’ll go into detail about the actual code to generate the DualPolyhedron that is the Geodesic Grid. Until then, I’ve uploaded the working code. Grab it and take a gander, and all shall be explained shortly.

Solution Files

GeodesicExample_Part-3.zip

Advertisement