Représentation de carte sphérique

Mon dernier jeu se déroulera sur un petit planétoïde. Je recherche une bonne structure de données pour représenter les cellules à la surface d'une sphère. Triangles, carrés, pentagones, hexagones? Lequel minimise le plus l'étirement et crée le meilleur carrelage?

La cartographie sphérique est la plus simple mais l'étirement aux pôles est inacceptable. La cartographie cubique est également assez facile mais il y aurait encore un étirement considérable près des coins du cube. La subdivision d'un icosaèdre semble la meilleure en termes d'étirement, mais il y a le problème d'indexer de nombreux tableaux triangulaires et de trouver des cellules voisines aux limites serait difficile.

Je suppose que je pourrais utiliser un seul tableau linéaire de points représentant N-gons, chacun avec un tableau de N indices voisins, mais cela semble être une énorme perte d'espace.

Le jeu a des éléments RTS, donc je vais stocker des choses comme les cartes d'influence et effectuer un A * pathfinding et convolution, donc la représentation doit être efficace.

D'accord, pour toute personne intéressée par ce sujet, je vais maintenant détailler la solution que j'ai choisie. Merci à tous ceux qui ont répondu et m'ont donné des idées.

Premièrement, pour la «meilleure» tesselation, je choisirai l' icosaèdre tronqué comme point de départ. La subdiviser conduit à une très belle tesselation d'hexagones avec 12 pentagones assurant la courbure. De plus, continuer la subdivision sur son dual me donnera un très bon maillage triangulaire pour un rendu avec de belles propriétés. Concernant les 12 cellules pentagonales: je peux les ignorer, les rendre spéciales (comme les seuls endroits où des bases peuvent être construites), ou je peux les cacher sous un décor.

Les cellules hexagonales et pentagonales seront stockées dans une structure de données demi-bord pour un accès facile aux voisins et une traversée rapide. La seule partie délicate consiste à trouver dans quelle cellule se trouve un point mondial donné, mais cela peut être fait en commençant par une cellule aléatoire et en marchant vers le point à travers les voisins.

J'espère que quelqu'un trouve ces informations utiles. J'ai beaucoup appris et j'ai hâte d'obtenir des résultats.

Éditer:

Voici une image montrant le résultat de la subdivision de mon icosaèdre et de la commutation double maillage à l'aide d'une structure de données à demi-bord.

Je peux faire quelques itérations de relaxation pour rendre les zones cellulaires encore plus uniformes.

Il existe un moyen de le faire de manière assez élégante en subdivisant un icosaèdre, comme vous l'avez suggéré dans votre question. Un icosaèdre est composé de 20 triangles équilatéraux, et ces triangles peuvent être regroupés en 5 ensembles, où les 4 triangles d'un ensemble forment une forme de parallélogramme:

(Les groupes de quatre triangles avec un gribouillis dessiné à travers eux sont les parallélogrammes dont je parle. Les flèches indiquent quels bords seraient collés ensemble pour plier cela en un icosaèdre.)

Si ces triangles sont subdivisés en triangles plus petits, l'ensemble du parallélogramme peut être indexé comme un tableau rectangulaire n par 4n (n = 4 dans l'exemple):

Les nombres dans chaque cellule sont les numéros de colonne du tableau rectangulaire. Les règles pour trouver des voisins dans le tableau sont assez simples: les voisins horizontaux sont juste plus ou moins 1 colonne, tandis que le voisin vertical est soit moins une ligne et plus une colonne, soit plus une ligne et moins une colonne, selon que le le numéro de colonne est pair ou impair, respectivement.

Cependant, vous devez toujours écrire un code de cas spécial pour trouver des voisins qui traversent la frontière d'un parallélogramme à l'autre. C'est un peu délicat car à certains endroits, le haut ou le bas d'un parallélogramme sera connecté sur le côté d'un autre, ou le haut et le bas seront connectés avec un décalage horizontal entre eux, etc. Peut-être une structure en demi-bord ou similaire car les parallélogrammes seraient utiles ici. Cependant, au moins les relations sont symétriques parmi les 5 parallélogrammes: elles suivent toutes le même modèle dans lequel côté est connecté à quel autre côté de leurs voisins.

Hmmm - les commentaires sur l'étirement indiquent que vous vous déplacez entre la cartographie sphérique et planaire, c'est ce qui conduit aux distorsions aux pôles

Si vous voulez que les carreaux soient plats et uniformes, vous avez raison de dire qu'un icosaèdre, en particulier un icosaèdre tronqué est assez courant

Vous pouvez trouver toutes les différentes cartographies ici - Polyèdres sphériques sur wikipedia

En ce qui concerne le maintien des relations entre les faces, c'est un problème de topologie - vous pouvez trouver le bord ailé ou le bord quadruple utile (et vous avez la merveilleuse occasion de rencontrer une toute nouvelle forme d'algèbre) Winged Edge

Je suppose que je viens un peu en retard à la fête, mais voici une solution possible qui peut être utilisée pour maintenir un monde sphérique de taille arbitraire et d'apparence uniforme.

L'essentiel à comprendre ici est que le monde n'est pas plat, et donc un carrelage 100% uniforme serait impossible (cela découle du soi-disant théorème de la boule velue ). Certaines irrégularités doivent être autorisées, et le mieux que nous puissions espérer est de répartir ces irrégularités uniformément autour de la surface, en les rendant aussi petites que possible.

C'est en fait assez facile à faire de manière non déterministe. Tout d'abord, choisissez N points aléatoires uniformément autour de la surface. Assurez-vous que ces points sont réellement uniformes (voir Sélection de points Sphère , formules 9-11). Dans la deuxième étape, nous rendons ces points moins aléatoires et plus uniformes: supposons que tous ces points ont une charge électrique négative afin qu'ils se repoussent. Simulez le mouvement des points pour plusieurs étapes, jusqu'à ce qu'ils convergent vers un état d'équilibre. Cette configuration finale des points vous donnera un maillage qui est réparti presque uniformément autour de la surface de la sphère.