Map representation : meshes

In this article I will discuss the representation of the hexagonal cells of my map.

There is several possibilities for the representation of a map. In this article i will concentrate on a "block" or "voxel" representation, where each cell is represented as an flat hexagon block. The following picture show the kind of representation I'm targeting with this method.

The bad

The first idea that come to mind when you want to display such a map is to generate a mesh for an  hex cell, and then duplicate (or share) this mesh for each cell, with a simple modification of the position. 

This is a bad idea, as there will be a lot of unused data. Such a hex mesh contains 13  points (6 vertex plus the center for the top, and 6 vertex for the bottom), and  18 triangles (6 for the top, and 2 for each side.  We do not generate  the bottom representation). 

When two of these mesh are put side by side, the face they share will be obscured  and never visible, for the two meshes. We have wasted 4 triangle (2 for one side, for two  meshes). As you may notice from the picture above, there is a lot of side by side hexes... You send a lot of data to the graphic card  that will never be visible, or even useful. The only case when you need to represent the side is when the cell is at a higher level than its neighbours (or if there is no  neighbour). Otherwise, this data will not be visible.

The good

The correct idea is not to consider the hex as a block, but as a set of faces, and to  create only the faces that are needed.  This is what is done with others voxel worlds (Minecraft, for example), where only faces that are in contact with empty (air) block are generated.

In our case, this mean generating the side only when the cell in this direction is lower, as stated above. In effect, you limit yourself to the potentially visible faces.

The ugly

Our first implementation  is based on this principle. However, for a given cell we use the top mesh (7 point, 6 triangles), and as many side mesh as needed (4 points, 2 triangles by side). The side are duplicated if there is more than one level difference between the two cells.

This method limit the number of unused data send to the card. In the following picture, the hex labelled as A is represented by 6 triangles (top mesh only), while the one labelled as B is represented by 6 triangles for the top, 10 triangles for the first level side meshes, indicated by the "1" (2 triangles / 5 sides) and 2 triangles for the second level side, indicated by the "2".

Batching

The first test of our implementation on a 100*100 map is not very successful. While the map is neatly displayed, the framerate is very low, about 12 fps. A quick look at the data show that there is more than 23000 objects present in the scene, and we know that those objects are small (between 4 and 6 triangles) leading to 113078 triangles.

A standard graphic card can push a hefty number of triangles on screen, far in excess of our number. However the API prefers a limited number of objects.

Our library contains an utility class than can merge meshes with the same material (same texture in our case)  in one mesh, a process known as batching. We do this for groups of 50*50 cells. The number of objects is down to 42. The result is far better, since we got 160 fps one the same scene.

Of course this solution has a trade off. Since we're merging the  meshes for 2500 cells into  one mesh, any ray cast or  selection we perform will return the whole mesh, and  not a specific cell. We have to  keep the  50*50 cell's  meshes in  a separate (non  displayed) hierarchy to get this information. Once we found which merged mesh is touched by a ray, we can them perform the same operation on the separate hierarchy, to find  which basic mesh is touched by the ray.