Friday, November 6, 2009

Geodesic Map - 1 - Generating a geogrid.

So I wanted to tinker with a hex grid. I had a few ideas, but nothing really took hold until the thought of projecting the hex grid around a sphere occured. Was such a thing possible? Yes, sort of. How would the mesh be generated? With lots of work. Could it be done dynamically to allow for multiple map sizes? Yup.

The Process

Generate Icosahedron

A sphere made purely of hexagons isn't quite possible, or if it is, I couldn't find any confirming documentation. Using an icosahedron will yield 12 5-sided cells across the surface of the grid, each one being at the original icosahedron's vertices (also known as a dodecahedron).

All images curtesy of the wonderfully informative BUGS project.

  1. The base icosahedron
  2. Each face subdivided
  3. Project each new vertex out to the unit sphere
  4. This process can be repeated until you reach the total number of cells you wish

Generate Cells

Once you have reached your target cell count, it's time actually generate the cell mesh. The basic process runs as such:
  1. Foreach vertex in the subdivided icosahedron:
    1. Find all neighbor cells
    2. Foreach neighbor cell:
        Find the midpoint of neighbor cell and neighbor + 1 cell, this forms one section of the hexagon (or pentagon)

Example Subdivision Levels

Level 1 - 42 Cells Truncated Icosahedron aka, soccer ball, buckyball
Level 2 - 162 Cells
Level 3 - 642 Cells


Some of the hexagons will be warped slightly due to wrapping to a sphere and floating point errors.


Icosahedral Hexagonal Grids

No comments:

Post a Comment