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.
Respuestas:
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.
fuente
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:
(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):
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.
fuente
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
fuente
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.
fuente