The triangular mesh is still a quadtree, just like the cube mesh: each cell has four finer-level cells. The basic cell expansion is:
There is an added complexity in this expansion that we didn't have with the square mesh: the cells each have a facing. I will arbitrarily say that point-up cells are facing 0 and point-down cells are facing 1. It turns out that many of the algorithms I use need to know cell facing, so I add this to my cell data structure.
I have cells that are equilateral triangles, so I need an underlying polyhedron with sides that are equilateral triangles. The choices are tetrahedron, octahedron, and icosahedron (if I stick to regular ones.) An icosahedron will minimize corner defects and the only reason not to use it is that it forces a minimum of 20 polygons in a planet at any distance (actually, because of the way I divide up the sides, the effective minimum turns out to be 20 * 16 = 320, but the ones facing away from the viewer can be suppressed so effectively about 160.) So, I choose an icosahedron.