Editar: Esto es solo por mi propia experiencia de aprendizaje, NO es por razones de rendimiento que hago esta pregunta.
Esto se refiere a un motor de terreno similar a Minecraft. Almaceno bloques en trozos (16x256x16 bloques en un trozo). Cuando genero un fragmento, utilizo múltiples técnicas de procedimiento para establecer el terreno y colocar objetos. Mientras genero, mantengo una matriz 1D para el fragmento completo (sólido o no) y una matriz 1D separada de bloques sólidos.
Después de la generación, recorro los bloques sólidos comprobando sus vecinos para que solo genere caras de bloque que no tengan vecinos sólidos. Almaceno qué caras generar en su propia lista (eso es 6 listas, una por cara posible / normal). Cuando renderizo un fragmento, renderizo todas las listas en el fragmento actual de la cámara y solo las listas que miran hacia la cámara en todos los demás fragmentos. Hago esto almacenando las 6 listas en un búfer, luego simplemente cambio los rangos que dibujo.
Usando un atlas 2D con este pequeño truco de sombreado que sugirió Andrew Russell, quiero fusionar caras similares por completo. Es decir, si están en la misma lista (la misma normal), son adyacentes entre sí, tienen el mismo nivel de luz, etc. Sé que todavía terminaré con rectángulos, pero debería reducir fácilmente mi conteo de vértices en un 50% o mejor si mis estimaciones son correctas.
Mi suposición sería ordenar cada una de las 6 listas por el eje en el que descansan, luego por los otros dos ejes (la lista para la parte superior de un bloque se ordenaría por su valor Y, luego X, luego Z).
Solo con esto, podría fusionar fácilmente tiras de caras, pero estoy buscando fusionar más que solo tiras juntas cuando sea posible. He leído sobre este codicioso algoritmo de mallado, pero tengo muchos problemas para entenderlo.
Entonces, mi pregunta: para realizar la fusión de caras como se describe (ignorando si es una mala idea para terreno / iluminación dinámica), ¿hay quizás un algoritmo que sea más simple de implementar? También con mucho gusto aceptaría una respuesta que me guíe a través del algoritmo codicioso de una manera mucho más simple (un enlace o explicación).
No me importa una ligera disminución del rendimiento si es más fácil de implementar o incluso si es solo un poco mejor que solo hacer tiras. Me preocupa que la mayoría de los algoritmos se centren en triángulos en lugar de cuádriceps, y usando un atlas 2D como soy, no sé si podría implementar algo de triángulo basado en mis habilidades actuales.
PD: ya estoy descartando por fragmento y como se describe, también elimino caras entre bloques sólidos. Todavía no ocluyo y quizás nunca.
* Editar: he implementado mi propia pequeña técnica, que probablemente tenga un nombre, pero simplemente reviso mis 6 listas que están ordenadas por los ejes en los que descansan, seguidos por el tipo de bloque y luego por el nivel de iluminación. I itero a través de ellos, creando nuevos rectángulos a medida que avanzo y los hago crecer simultáneamente (con un fuerte sesgo hacia cierto eje). Definitivamente no es óptimo, pero de hecho es bastante rápido y reduce mi conteo de vértices en casi un 50% en promedio. El comentario de Byte56 es el armario que creo que es una respuesta real, pero no puedo seleccionarlo para la respuesta / recompensa.
Aquí está mi forma rápida y simplista de manejar este problema DESPUÉS de generar todo el terreno inicial sin mucha optimización. Suponiendo que todos los cuadrados dados son la misma imagen, nivel de luz, normal, etc. cada color es un quad diferente que yo renderizaría. Con mis listas ordenadas como están, este es un enfoque muy fácil / rápido.
fuente
Respuestas:
Solo desea hacer tiras, o en el mejor de los casos, rectángulos. No hay otras formas que sean solucionables o útiles para usted.
También me gustaría señalar que al mantener 6 listas por fragmento, en cualquier momento utilizará 5 listas de los fragmentos en direcciones cardinales, y al menos 3 en cada una. Estás perdiendo el tiempo aquí, cuando la tarjeta de video no solo puede hacer esta optimización por ti, sino que incluso si lo hicieras tú mismo, sería mejor mantener todas las caras en un solo lugar y comparar lo normal con la dirección con cámara (producto DOT de investigación de vectores).
Los enlaces de CaptainRedMuff sobre mallas codiciosas que ya has visto son LA respuesta a tu problema. También debería ser evidente a partir de eso que terminarás con mallas "a rayas", pero son perfectamente efectivas, y venir con algo más óptimo será más complicado, y has expresado que la malla codiciosa ya es demasiado complicada.
Si tiene problemas de rendimiento con un solo fragmento, me hace pensar que algo más está muy mal.
Mi primera suposición sería que está llamando a una operación de sorteo con demasiada frecuencia. Solo puede decirle a la tarjeta gráfica que dibuje entre 50 y 400 ~ veces por segundo, dependiendo del hardware. ¿Cuántas llamadas a .setData o .draw ____ primitivas estás haciendo?
fuente
El artículo al que enlaza en realidad no proporciona un algoritmo para generar la malla; establece una forma de evaluar posibles soluciones.
En general, sin embargo, el artículo ofrece un buen resumen: 1) la solución ingenua es mala, 2) hay una solución óptima, pero requerirá mucho tiempo escribir y ejecutar, 3) una eliminación rápida da resultados mucho mejores ( y esto es todo lo que hace Minecraft), y finalmente 4) podría haber una solución más inteligente (el algoritmo codicioso).
La "solución" que implica en la imagen en su pregunta es el algoritmo codicioso. Parece que su pregunta es "¿implementé su solución correctamente?" a lo que debo responder "él no dio una solución; tú mismo resolviste esto".
¿Puede su solución ser mejor? Meh Por supuesto. Probablemente no valga la pena. Creo que la eliminación de oclusiones o LOD serían mejores pasos a seguir. Minecraft desperdicia una buena cantidad de ciclos dibujando la superficie incluso cuando estás bajo tierra, así como dibujando vastas redes de sistemas de cuevas y minas cuando estás en la superficie. Una vez que tenga un buen desglose de la malla, sí, deshacerse de las superficies oscuras puede ser algo bueno, pero (por ejemplo) en general es más rápido dejar que su tarjeta de video descarte la parte posterior que hacerlo en la CPU.
fuente