Representação de mapa esférico

19

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.

DaleyPaley
fonte
Quão importante é a topologia exata do mapa, em vez de apenas deixar os atores seguirem uma direção e, eventualmente, acabar onde começaram? A representação mais simples e mais eficiente seria um toro / rosquinha.
congusbongus
1
Sim, mencionei o mapeamento esférico e os problemas que ele tem com os pólos. Quero armazenar valores em torno da superfície, por isso preciso de um mapeamento do ponto de superfície 3D para o índice da matriz com o menor alongamento possível.
DaleyPaley 27/05
Você pode tentar subdividir um tetraedro para criar uma esfera. Consiste em triângulos de tamanho e distribuição iguais.
Thalador 27/05
1
@ thalador Obrigado pela sugestão. Não tenho certeza, mas acho que os icosaedros são melhores que os tetraedros se eu seguir a rota triangular. Mas, enfim, o mosaico não é o problema. É a eficiente indexação de array que está me incomodando.
DaleyPaley 27/05
Leitura adicional: gamedev.stackexchange.com/questions/10249/…
Kromster diz suporte Monica

Respostas:

12

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.

subdivisão icosaedro

DaleyPaley
fonte
7

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:

insira a descrição da imagem aqui

(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):

insira a descrição da imagem aqui

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.

Nathan Reed
fonte
Essa é realmente uma representação muito boa. Minha principal preocupação com os métodos triangulares era manter matrizes triangulares e toda a costura. Ainda há um pouco de costura aqui, mas as matrizes são retangulares. Obrigado, muito bom saber
#
3

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

Mark Mullin
fonte
Ah, um icosaedro truncado. Sim, é exatamente disso que eu preciso. Obrigado. Além disso, embora nunca tenha usado arestas com asas, usei muito arestas para manipulação de malhas, por isso sou versado nessa área. Saúde, estou perto de uma solução.
DaleyPaley
2

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.

Paxá
fonte
1
Eu nunca tinha ouvido falar da teoria da bola peluda, é bem interessante. Tenho que parar de fazer piadas pueris. Eu já distribuí pontos em esferas antes dessa maneira, mas o problema é que a poligonização é muito mais lenta do que a subdivisão de um politopo. Além disso, as formas e a valência das células serão muito não uniformes para o meu gosto. Mas obrigada mesmo assim.
DaleyPaley