Representación esférica del mapa

19

Mi último juego tendrá lugar en un pequeño planetoide. Estoy buscando una buena estructura de datos para representar celdas en la superficie de una esfera. Triángulos, cuadrados, pentágonos, hexágonos? ¿Cuál minimiza más el estiramiento y crea el mejor mosaico?

El mapeo esférico es el más fácil, pero el estiramiento en los polos es inaceptable. El mapeo de cubos también es bastante fácil, pero aún habría una considerable extensión cerca de las esquinas del cubo. Subdividir un icosaedro parece lo mejor en términos de estiramiento, pero existe el problema de indexar muchas matrices triangulares y encontrar células vecinas en los límites sería difícil.

Supongo que podría usar una única matriz lineal de puntos que representan N-gons, cada uno con una matriz de N índices vecinos, pero eso parece una gran pérdida de espacio.

El juego tiene elementos RTS, por lo que estaré almacenando cosas como mapas de influencia y realizando una búsqueda de curvas y convolución A *, por lo que la representación debe ser eficiente.

DaleyPaley
fuente
¿Cuán importante es la topología exacta del mapa, en lugar de simplemente dejar que los actores vayan en una dirección y finalmente terminen donde comenzaron? La representación más simple y eficiente sería un toro / donut.
congusbongus
1
Sí, mencioné el mapeo esférico y los problemas que tiene con los polos. Quiero almacenar valores alrededor de la superficie, por lo que necesito un mapeo desde el punto de superficie 3D al índice de matriz con el menor estiramiento posible.
DaleyPaley
Podrías intentar subdividir un tetraedro para crear una esfera. Consiste en triángulos de igual tamaño y distribuidos.
thalador
1
@thalador Gracias por la sugerencia. No estoy seguro, pero creo que los icosaedros son mejores que los tetraedros si sigo la ruta triangular. Pero de todos modos, la teselación no es el problema. Es la indexación de matriz eficiente lo que me está molestando.
DaleyPaley
Lectura
Kromster dice que apoya a Monica

Respuestas:

12

Bien, para cualquier persona interesada en este tema, ahora detallaré la solución que he elegido. Gracias a todos los que respondieron y me dieron ideas.

Primero, para la 'mejor' teselación, elegiré el icosaedro truncado como punto de partida. Subdividirlo conduce a una muy buena teselación de hexágonos con 12 pentágonos que proporcionan la curvatura. Además, continuar la subdivisión en su dual me dará una muy buena malla triangular para renderizar con buenas propiedades. Con respecto a las 12 celdas pentagonales: puedo ignorarlas, hacerlas especiales (como los únicos lugares donde se pueden construir bases), o puedo esconderlas debajo del escenario.

Las celdas hexagonales y pentagonales se almacenarán en una estructura de datos de medio borde para facilitar el acceso a los vecinos y un recorrido rápido. La única parte difícil es encontrar en qué celda se encuentra un punto mundial dado, pero eso se puede hacer comenzando en una celda aleatoria y caminando hacia el punto a través de vecinos.

Espero que alguien encuentre útil esta información. He aprendido mucho y espero obtener algunos resultados.

Editar:

Aquí hay una imagen que muestra el resultado de la subdivisión de mi icosaedro y el cambio de malla dual utilizando la estructura de datos de medio borde.

Puedo hacer algunas iteraciones de relajación para lograr que las áreas celulares sean aún más uniformes.

subdivisión de icosaedro

DaleyPaley
fuente
7

Hay una manera de hacer esto de manera elegante basada en la subdivisión de un icosaedro, como sugirió en su pregunta. Un icosaedro está formado por 20 triángulos equiláteros, y estos triángulos se pueden agrupar en 5 conjuntos, donde los 4 triángulos en un conjunto forman una forma de paralelogramo:

ingrese la descripción de la imagen aquí

(Los grupos de cuatro triángulos con un garabato dibujado a través de ellos son los paralelogramos de los que hablo. Las flechas dicen qué bordes se pegarían para doblar esto en un icosaedro).

Si estos triángulos se subdividen en triángulos más pequeños, todo el paralelogramo se puede indexar como una matriz rectangular de n por 4n (n = 4 en el ejemplo):

ingrese la descripción de la imagen aquí

Los números en cada celda son los números de columna de la matriz rectangular. Las reglas para encontrar vecinos dentro de la matriz son bastante simples: los vecinos horizontales son solo más o menos 1 columna, mientras que los vecinos verticales son menos una fila y más una columna, o más una fila y menos una columna, dependiendo de si El número de columna es par o impar, respectivamente.

Sin embargo, aún tiene que escribir un código de caso especial para encontrar vecinos que crucen el límite de un paralelogramo al siguiente. Es un poco complicado ya que en algunos lugares, la parte superior o inferior de un paralelogramo se conectará al lado de otro, o la parte superior e inferior se conectarán con un desplazamiento horizontal entre ellas, etc. Posiblemente una estructura de medio borde o similar para los paralelogramos sería útil aquí. Sin embargo, al menos las relaciones son simétricas entre los 5 paralelogramos: todos siguen el mismo patrón en qué lado está conectado a qué otro lado de sus vecinos.

Nathan Reed
fuente
De hecho, es una muy buena representación. Mi principal preocupación con los métodos triangulares era mantener matrices triangulares y todas las costuras. Todavía hay un poco de costura aquí, pero las matrices son rectangulares. Gracias, muy bueno saberlo
DaleyPaley
3

Hmmm: los comentarios sobre el estiramiento indican que te estás moviendo entre el mapeo esférico y el plano, eso es lo que conduce a las distorsiones en los polos

Si desea que los mosaicos sean planos y uniformes, tiene razón en que un icosaedro, específicamente un icosaedro truncado, es bastante común.

Puede encontrar todas las asignaciones diferentes aquí: Poliedros esféricos en wikipedia

Por lo que el mantenimiento de las relaciones entre las caras, que es un problema de topología - que puede encontrar cualquiera de los bordes de alas o borde quad útiles (y obtener la maravillosa oportunidad de conocer una forma completamente nueva de álgebra) con alas Edge

Mark Mullin
fuente
Ah, un icosaedro truncado. Sí, eso es exactamente lo que necesito. Gracias. Además, aunque nunca utilicé el borde alado, he usado mucho los medios bordes para la manipulación de mallas, así que estoy bien versado en esa área. Saludos, estoy cerca de una solución.
DaleyPaley
2

Supongo que llego un poco tarde a la fiesta, pero aquí hay una posible solución que puede usarse para mantener un mundo esférico de tamaño arbitrario y apariencia uniforme.

La clave para entender aquí es que el mundo no es plano y, por lo tanto, sería imposible un mosaico 100% uniforme (esto se desprende del llamado Teorema de la Pelota Peluda ). Deben permitirse algunas irregularidades, y lo mejor que podríamos esperar es extender esas irregularidades de manera uniforme por la superficie, haciendo que cada una sea lo más pequeña posible.

En realidad, es bastante fácil de hacer de manera no determinista. Primero, elija N puntos aleatorios uniformemente alrededor de la superficie. Asegúrese de que esos puntos sean realmente uniformes (consulte Selección de puntos de Esfera , fórmulas 9-11). En el segundo paso, hacemos que esos puntos sean menos aleatorios y más uniformes: suponga que todos esos puntos tienen carga eléctrica negativa para que se repelen entre sí. Simule el movimiento de los puntos durante varios pasos, hasta que converjan en un estado de equilibrio. Esta configuración final de los puntos le dará una malla que se distribuye casi uniformemente alrededor de la superficie de la esfera.

Bajá
fuente
1
Nunca había oído hablar de la teoría de la pelota peluda, es bastante interesante. Tengo que evitar hacer bromas pueril. He distribuido puntos en esferas antes de esa manera, pero el problema es que la poligonalización es mucho más lenta que la subdivisión de un politopo. Además, las formas y la valencia de las células serán demasiado poco uniformes para mi gusto. Pero gracias de todos modos.
DaleyPaley