Spring RTS Engine

I'm trying to figure out an algorithm for creating a spheres of various sizes out of triangular faces that I can then navigate from one face to any adjacent face. I was able to get it to work with icosaspheres of certain sizes... and I was thinking it would be trivial to just transect the triangles into groups of 4 so I have more triangles, and therefore a larger sphere... but it breaks my navigation algorithm, and I can't find an elegant way to scale up without breaking any new navigation system I create.

Anyone solved this problem before?

Thank you for your insight ivory.

Build little icosahedrons in paper (or buy a D20), split their faces in triangles with a pen, then follow with your fringer the pathes. Your mind will have an easier with the physical object in your hand, before your eyes, than with pure abstraction.

zwzsg wrote:Build little icosahedrons in paper (or buy a D20), split their faces in triangles with a pen, then follow with your fringer the pathes. Your mind will have an easier with the physical object in your hand, before your eyes, than with pure abstraction.

Ya, I did that. I was able to produce algorithms for icosahedrons of a fixed size that allow me to navigate from any one face to all it's adjacent faces... But the whole point of using icosahedrons is that you can scale them up, every different scale needs a different navigation algorithm, at least to the point that I can wrap my mind around them...

I think it is topologically impossible to place triangles on a sphere such that each vertex is next to 6 other vertexes along the edges of the triangles. This is regardless of the shape of the triangles.

So you've got to make your algorithm take into account the 12 vertexes with only 5 connected vertexes.

Google_Frog wrote:I think it is topologically impossible to place triangles on a sphere such that each vertex is next to 6 other vertexes along the edges of the triangles. This is regardless of the shape of the triangles.

So you've got to make your algorithm take into account the 12 vertexes with only 5 connected vertexes.

sort of. The larger the face count on the sphere gets, the higher the percentage of vertexes that have 6 adjacent vertexes. On the smallest possible icasahedron, all vertexes share 5 vertexes.

It's sort of irrelevant though, because I'm navigating over edges, not over vertexes. I suppose it would be kind of interesting to create a soccerball shape and navigate over the edges of that though. That model would be effectively trading edges for vertexes. I prefer sticking to triangles right now though, because it's hard enough to calculate navigation without having to worry about 6 degrees of navigable freedom, and have to do something special to deal with the 5 sided shapes.

sort of. The larger the face count on the sphere gets, the higher the percentage of vertexes that have 6 adjacent vertexes. On the smallest possible icasahedron, all vertexes share 5 vertexes.

That's implied from "12 vertexes with 5 links", large spheres still have 12 vertexes with 5 links.

Even if you're navigating along faces you have to deal with the situation where you have faces forming pentagons.

To make the grid spaces easily index-able I would suggest splitting the sphere into 3 parts; top, middle and bottom. The top and bottom each correspond to a cap of 5 triangles on an icosahedron. All triangles can then be subdivided. The middle is made of a band of triangles.

You now have lines of latitude that each triangle is placed upon in a band around the sphere. You can then index each from an arbitrary angle looking down on the sphere lining up top and bottom.

AFAIK there is a recursive algorithm available for this task and it doesn't need any special cases (like splitting in in 3 parts etc.).

edit:
NVM the one I meant just handles the special cases with N=20,80,320,... (splitting each triangle in 4 new ones).
On the other hand, are there any other icosahedrons possible with just triangles?