Meu último jogo ocorrerá em um pequeno planetoide. Estou procurando uma boa estrutura de dados para representar células na superfície de uma esfera. Triângulos, quadrados, pentágonos, hexágonos? Qual minimiza o alongamento e cria a melhor telha?
O mapeamento esférico é o mais fácil, mas o alongamento nos polos é inaceitável. O mapeamento de cubo também é bastante fácil, mas ainda haveria um alongamento considerável próximo aos cantos do cubo. Subdividir um icosaedro parece o melhor em termos de extensão, mas há o problema de indexar muitas matrizes triangulares e encontrar células vizinhas nos limites seria difícil.
Eu acho que eu poderia usar uma única matriz linear de pontos representando N-gons, cada um com uma matriz de índices N vizinhos, mas isso parece um enorme desperdício de espaço.
O jogo tem elementos RTS, então eu vou armazenar coisas como mapas de influência e executar a busca e a convolução A *, para que a representação tenha que ser eficiente.
Respostas:
Ok, para qualquer pessoa interessada neste tópico, detalharei agora a solução que escolhi. Obrigado a todos que responderam e me deram idéias.
Primeiro, para o 'melhor' mosaico, escolherei o icosaedro truncado como ponto de partida. A subdivisão leva a um mosaico muito agradável de hexágonos, com 12 pentágonos fornecendo a curvatura. Além disso, a continuação da subdivisão na sua dupla me proporcionará uma malha triangular muito boa para renderização com boas propriedades. Com relação às 12 células pentagonais: eu posso ignorá-las, torná-las especiais (como os únicos lugares em que as bases podem ser construídas) ou posso escondê-las sob o cenário.
As células hexagonais e pentagonais serão armazenadas em uma estrutura de dados de meia borda para facilitar o acesso aos vizinhos e atravessar rapidamente. A única parte complicada é descobrir em qual célula está um determinado ponto do mundo, mas isso pode ser feito começando em uma célula aleatória e caminhando em direção ao ponto através dos vizinhos.
Espero que alguém ache esta informação útil. Aprendi muito e estou ansioso para obter alguns resultados.
Editar:
Aqui está uma imagem mostrando o resultado da minha subdivisão de icosaedro e comutação de malha dupla usando estrutura de dados de meia borda.
Eu posso fazer algumas iterações de relaxamento para tornar as áreas celulares ainda mais uniformes.
fonte
Existe uma maneira de fazer isso de maneira bastante elegante, com base na subdivisão de um icosaedro, como você sugeriu na sua pergunta. Um icosaedro é composto por 20 triângulos equilaterais, e esses triângulos podem ser agrupados em 5 conjuntos, onde os 4 triângulos em um conjunto formam uma forma de paralelogramo:
(Os grupos de quatro triângulos com um rabisco desenhado através deles são os paralelogramos de que estou falando. As setas dizem quais bordas seriam coladas para dobrar isso em um icosaedro.)
Se esses triângulos são subdivididos em triângulos menores, todo o paralelogramo pode ser indexado como uma matriz retangular n por 4n (n = 4 no exemplo):
Os números em cada célula são os números das colunas da matriz retangular. As regras para encontrar vizinhos na matriz são bastante simples: os vizinhos horizontais são apenas mais ou menos 1 coluna, enquanto o vizinho vertical é menos uma linha e mais uma coluna, ou mais uma linha e menos uma coluna, dependendo se o o número da coluna é par ou ímpar, respectivamente.
No entanto, você ainda precisa escrever um código de caso especial para encontrar vizinhos que cruzam o limite de um paralelogramo para o próximo. É um pouco complicado, já que em alguns lugares, a parte superior ou inferior de um paralelogramo será conectada ao lado de outro, ou a parte superior e a parte inferior serão conectadas com um deslocamento horizontal entre elas, etc. para os paralelogramos seria útil aqui. No entanto, pelo menos os relacionamentos são simétricos entre todos os 5 paralelogramos: todos seguem o mesmo padrão em que lado está conectado ao outro lado de seus vizinhos.
fonte
Hmmm - os comentários sobre o alongamento indicam que você está se movendo entre o mapeamento esférico e o plano, é isso que leva às distorções nos pólos
Se você deseja que os ladrilhos sejam planos e uniformes, você está certo de que um icosaedro, especificamente um icosaedro truncado, é bastante comum
Você pode encontrar todos os diferentes mapeamentos aqui - Poliedros Esféricos na wikipedia
Na medida em que a manutenção das relações entre os rostos, isso é um problema topologia - que você pode encontrar uma ou outra borda alada ou edge quad útil (e você terá a oportunidade maravilhosa de conhecer uma nova forma de álgebra) Winged Borda
fonte
Acho que estou chegando um pouco tarde para a festa, mas aqui está uma solução possível que pode ser usada para manter um mundo esférico de tamanho arbitrário e aparência uniforme.
A principal coisa a entender aqui é que o mundo não é plano e, portanto, uma telha 100% uniforme seria impossível (isso se segue do chamado Teorema da Bola Peluda ). Algumas irregularidades precisam ser permitidas, e o melhor que podemos esperar é espalhá-las uniformemente pela superfície, tornando cada uma delas a menor possível.
Na verdade, é muito fácil de fazer de maneira não determinística. Primeiro, escolha N pontos aleatórios uniformemente ao redor da superfície. Verifique se esses pontos são realmente uniformes (consulte Seleção de pontos da esfera , fórmulas 9 a 11). No segundo passo, tornamos esses pontos menos aleatórios e mais uniformes: suponha que todos esses pontos tenham carga elétrica negativa para que se repelam. Simule o movimento dos pontos por várias etapas, até convergirem para um estado de equilíbrio. Essa configuração final dos pontos fornecerá uma malha quase uniformemente distribuída em torno da superfície da esfera.
fonte