Voxel Face Crawling (simplificación de malla, posiblemente usando codicioso)

9

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.

Mitos
fuente
Después de todas sus optimizaciones, ¿todavía tiene problemas de rendimiento? ¿Has intentado perfilar el código para ver dónde están los problemas?
MichaelHouse
@ Byte56 Oh, definitivamente no es un problema de rendimiento en absoluto actualmente. Puede ser uno en el futuro cuando intento poner lo que estoy aprendiendo a usar para un juego real. Por ahora, sin embargo, simplemente quiero aprender. No dije nada de eso porque parece que obtengo menos ayuda si solo quiero aprender cosas simplemente para aprenderlas.
Míticos
Siento que también debería decir que si realmente logro intentar un juego adecuado con esto, querré que el mundo visible sea ENORME. No quisiera que el personaje tenga 2 bloques de alto y 1 bloque de ancho como Minecraft y muchos otros, pero más como 3 bloques de ancho / largo y 6-9 de alto. Probablemente terreno estático sin embargo.
Míticos
1
Ah, ok Tim. Gracias por la explicación. Investigué un poco sobre esto cuando estaba haciendo el motor de mi juego. Como mi panorama es dinámico, no pensé que valiera la pena el costo de rendimiento cada vez que se cambiara algo. Sin embargo, puede encontrar algún uso de este artículo sobre el problema del rectángulo máximo. Esencialmente, es el algoritmo del que habla para fusionar caras similares (tal vez no codiciosas, pero óptimas). ¡Buena suerte!
MichaelHouse
@ Byte56 Gracias, lo aprecio mucho. Eso ciertamente se parece más al tipo de algoritmo que estoy buscando, si no es que lo veo. Tendré que jugar un poco para ver si puedo obtener todos los rectángulos máximos con una sola ejecución. También puedo ofrecer una recompensa por esto en un momento, ya que creo que tanto la pregunta como una respuesta detallada podrían ayudar a muchos otros en el futuro.
Míticos

Respuestas:

4

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?

Phil
fuente
Los rectángulos son lo que quiero. Byte56 vinculó un algoritmo mucho más simple de seguir que codicioso, pero no puedo aceptar un comentario como respuesta. Asumí que comentó en su lugar porque solo se vinculaba a un algoritmo en lugar de explicarlo. No sé a qué te refieres con mis listas. Por lo general, tengo 1-2 llamadas de sorteo por trozo. Mis listas se almacenan en un búfer por fragmento. Cambio los rangos para dibujar por cuadro. Podría estar equivocado, pero enviar datos innecesarios a la GPU parece contraproducente. Un sorteo adicional o dos por porción parece mejor que enviar más datos al gpu y obligarlo a eliminarlo también.
Míticos
No tengo problemas de rendimiento. Simplemente disfruto aprendiendo estas cosas. Editaré mi pregunta para decir esto, pero como también le dije a Byte56, obtengo menos ayuda si lo que estoy tratando de hacer no está resolviendo un problema. Para responder a su pregunta, actualmente renderizo 200-260 fragmentos como máximo por cuadro. Esa es una bastante común 500ish DrawIndexedPrimitives por cuadro. Regularmente obtengo 100-130 FPS sin vsync, lo que hace 65,000 llamadas por segundo. No estoy tratando de ser grosero, pero lo poco que dijiste tiene sentido para mí. Puede que no entienda, así que por favor explique si no lo entendí. Tal vez tiene que ver con XNA?
Míticos
Ah, lo siento, quise decir por fotograma, no por segundo. Te estás acercando a un límite superior allí, y si solo estás en terreno, te has quedado prácticamente sin agua.
Phil
Hice +1 en su respuesta, ya que me hizo pensar en algunas mejoras que podría hacer, pero nada que ver con la pregunta. Además, pensé que debería compartir una respuesta de Nathan Reed sobre el posible enlace de
Míticos
Tendré que encontrar el artículo que leí que citaba 400-500 como límite. Un google rápido no me ayudó.
Phil
0

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.

AndrewS
fuente