Note to others: HeroesGraveDev’s pictures are exactly what my previous post was attempting to say. Take your 20 sided dice (tris), perform how many subdivision steps you want (still tris) and the dual mesh is hexagons. So hexs only at the end and they are implicit. If ‘n’ is the number of subdivisions (and my quick math holds) you have:
tris: 20 3n
hex: 10 3n + 2
So zero to six subdivisions yields: tris: 20, 60, 180, 540, 1620, 4860, 14580 hex: 12, 32, 92, 272, 812, 2432, 7292
The dual mesh is hexagons + 12 pentagons.
Oh yeah…I guess I need some coffee.
Here you go:
http://pastebin.java-gaming.org/909ab45681c13
Duality was the key to what I needed. I was being confused by rendering territories (which requires me to render faces) when in fact I just needed neighbours (for which I only need vertices). The version you see here is after an hour or so of memory optimisation (with 10 subdivisions it requires gigs of RAM) so it’s a little unclean but at least it’s quite fast and fits in RAM now for the size that I need.
Cas 
*rubs his head , Ow
What’s the .c field in Edge about?
c = numVertices[0]++;
Seems to be the only modification of the .c variable , im a bit out of context.
Ah, it’s the index of the midpoint of index A and index B. So… why call it C? That seems a bit misleading
Seemed like a good idea at 2am
Just for kicks I might rearrange this code so that it does not actually construct instances of Edge or Tri and just packs the lot inside int[] arrays, which would further drastically reduce memory consumption (at 10 subdivisions it won’t fit in a 32-bit JVM right now)
Cas
Or use LibStruct!
… I’ll see myself out.
I’m gonna wait patiently for Java to get value types
Cas
You should be able to exploit symmetry.
Yes, in theory, but in practice, my brain can’t quite cope This algorithm does have an advantage in simplicity. Well, apart from the memory mangling.
Cas
Here’s the super-duper extra fast uses-barely-any-memory version.
http://pastebin.java-gaming.org/09ab5586c1318
Looks a bit like C code Runs like it, too (that is, fast)
Cas
On to my next problem. I now have a working topology for my world. However, it exists purely in the mathematical sense… there’s no “up”, there’s no way of knowing exactly what it really even looks like. Working backwards from where I need to be…
I have an atlas projection of the world. In fact I’ve got several different ones, some more suitable than others, but the key piece of data I have is a rectangular bitmap (for now let us assume it contains just 1 or 0 for “land or sea”). I need to wrap that atlas around my sphere, but each node in the sphere is only known by a simple integer index. We know several pieces of information:
However, how exactly the hexes are laid out in memory - that is, the order of their indicies - I have no actual idea. There is no deliberate relation between index and any notional physical coordinate.
This is arguably a much more interesting problem
Cas
My thinking on this one is to adapt the existing algorithm to actually calculate the 3D coordinates of the vertices, and then use some manner of “texture mapping” to sample the bitmap. (Note: still not actually concerned with rendering or OpenGL or anything here… this is purely nonvisual data)
Cas
Google Maps uses this conversion between coordinate systems:
Well considering the icosahedron is a relatively “low def” shape , maybe go the way of the periodic table at indexing , think of it like flattening out the shape into a 2d map , with north (0) at the centre at the top and the south at the bottom (final index) run through this left to right binding. This should be fairly easy to do. I dont really understand how you generate the icosahedron fully but when you are creating it surely you should be able to store the locations of it whilst generating.
Hope this helps.
Thanks.
Well obviously mine’s not working so well. I’m not really thinking about memory reduction or speeding up the generation process but using symmetry to be able to have a simple enumeration of all cells to allow fast “do-stuff”: calc index, neighbors, etc. and things built on top of these basic ops.
At zero subdivisions you have 20 tris and 12 cells and the 12 cells will all be pentagons. After ‘n’ subdivision steps we still have 12 pentagons which will remain in the same configuration as the unsubdivided version (the centers of pentagons are the 12 original vertices). So we can have a pentagon at each of the poles and place the north one so there’s a vertex straight in the ‘east’ direction.
Actually look at HeroesGraveDev’s posted link - http://kiwi.atmos.colostate.edu/BUGS/geodesic/text.html
It’s showing the 5 fold symmetry about the poles (one per color). And at each vertex of the colored spherical triangles is one of the pentagons. And each color is made up of four spherical triangles each of which can be folded. So all of the information is less than one of colored spherical tris. Less since it has exploitable symmetry as well. So the interesting thing would be to device a good ordering of symmetry manipulations which is cheap. (extra credit for someone that can come up with a cheap space filling curve ordering which minimizes the neighbor distance between all cells.)
Somebody check me. Is all of this correct?
In case anybody was looking… the pastebinned code above of mine produces a valid topology but one which is decidedly non-Euclidian When it came to actually visualising what I’d produced it was like something from the 9th dimension.
Some tweaks to the algorithm have sorted it.
The data structure I’ve settled on for rendering is subdivided faces down to a certain level; and then at the bottom, “buckets” of the smallest faces. The plan is to do a frustum cull based on the upper levels of subdivided faces, and thus end up with a number of potentially visible buckets of faces, which I’ll just render in their entirety. As an added bonus I can do a little trick with the top level faces by projecting a triangle out of it which is at a tangent to the midpoint of the face, and thus do a simple winding order normal test on a whole face and all its children in one go and eliminate them early.
Cas