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

Advertisements

4 thoughts on “Geodesic Grid – Part 3

  1. Pingback: Geodisc Grid, Part 3 « Sgt. Conker

  2. Hello;

    I want to start by thanking you for this series of tutorials as they have been absolutely invaluable. I too am interested in mapping out a spherical map for a strategy game, and I would certainly not have gotten as far as I have without these tutorials. So thank you very much.

    That said, I have found a bug! I’m not sure if this bug is actually inherent in your code as I haven’t been able to get Visual Studio to let me compile and run your sample directly, or if it was introduced when I tried to rewrite the code to work with OpenGL and also relocate some things, but I figured it can’t help to report my findings.

    Essentially, when using a Frequency Higher than 1, I get rectangular holes in the dual polyhedron, spanning from one pentagon to another. This doesn’t happen between all of the Pentagons, but it does consistently happen between the same Pentagons and is preserved between those Pentagons when increasing the frequency further. Please see the screenshot below.

    I have managed to isolate this to an apparent rounding error in the construction of the Icosohedron. Two Vertices that should be identical are instead just very very slightly apart. So slightly that when looking at the Icosohedron the human eye can’t see the gap, however when converting that Icosohedron into its Dual Polyhedron, it splits what should be a single hexagon into two triangles with a gap between them.

    For instance, two of the vertices this happens for in a frequency 1 Dual Polyhedron are the following;

    -0.5000001, -0.309017, 0.8090169
    -0.4999999, -0.309017, 0.8090170

    These points are extremely close together, and if I quickly modify the Pie Generator to allow some very slight distance between the two center points, it correctly completes the entire Dual-Polyhedron.

    Unfortunately I’m not seeing where in your code, I decided to try and build my own DualPolyhedronFactory until I got to the visible error and that is where I made my changes, that a similar change should be made. I would like to simply resolve the rounding error in the IcosohedronFactory because I would like to have a functional Icosohedron, as that may be useful.

    I’m still working on this, but I figured you probably know your code better than I do, and may have already found and resolved this issue, if it actually exists in your code and not as a side effect of something I did in mine or a limitation of OpenGL compared to XNA.

    Thanks Again;
    -JCVocke

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: