opengl - videojuego - ¿Cómo hacer la eliminación de la cara en un mundo de cubos unitarios a la Minecraft?

que puede ser argumentado en contra

Question

Nota importante: esta pregunta NO es acerca de la selección de geometría (selección frustrum, selección de la cara posterior, selección de oclusión o cualquiera de sus amigos). Esta pregunta es sobre la eliminación de la geometría en el momento de la configuración, mucho antes de que hagamos la selección y el procesamiento.

En un mundo renderizado de cubos unitarios ( a la MineCraft), estoy tratando de encontrar algoritmos sobre cómo eliminar de mi lista de caras geométricas que no se pueden ver desde ningún ángulo, sin importar dónde esté la cámara.

Por ejemplo, imagina 2 cuadrados:

+----+      +----+
|    |      |    |
|    |      |    |
+----+      +----+

claramente hay 8 lados visibles (4 en cada cuadrado). Ahora muevo los cuadrados juntos, en vista:

+----+----+
|         |
|         |
+----+----+

En lugar de tener 8 lados, ahora solo tengo 6! Los dos que se tocan en el medio no se pueden ver, sin importar dónde esté colocada la cámara, ni qué ángulo está mirando. (Los cuadrados tienen una textura diferente, por lo que no podemos llamarlos 4 lados).

(Lo mismo funciona en 3D con cubos, pero 12 caras (6 por cubo) se convierten en 10 cuando se eliminan los 2 toques).

Mi pregunta es: ¿cuáles son algunos algoritmos que me ayudan a reconocer estas caras ocultas? (Estoy feliz de hacer mi propia búsqueda en Google, ¡pero ni siquiera sé cómo se llama esto!) En particular, estoy buscando algo que maneje manchas huecas en el medio: lugares que PODRÍAN ser visibles si estuvieras allí, pero, debido a que están rodeados de geometría, no puedes verlos.

Por ejemplo:

+----+----+----+----+
|                   |
|                   |
+    +----+         +
|    |    |         |
|    | A  |         |
+    +----+         +
|                   |
|                   |
+----+----+----+----+

En este caso, se podría pensar que hay 18 lados "visibles" pero, como sabemos a ciencia cierta que la cámara está fuera de la geometría, los 4 lados en el cuadrado "A" no son visibles.

Para complicar aún más las cosas, espero encontrar un algoritmo que pueda hacer actualizaciones rápidas si se agrega o elimina un bloque (una vez más, como en MineCraft).

¡Gracias!

Answer 1

La primera parte de tu pregunta es realmente muy simple. Para cada cubo, si está directamente adyacente a otro cubo, quita la cara que comparte con ese cubo.

Esto no es algo que deba ser un problema de rendimiento (fuera del costo de modificar y cargar los datos de vértice modificados), ya que solo se volverá a calcular cuando se coloque o elimine un bloque. Los efectos de colocar y quitar un bloque son bastante locales; Solo afectará a los 6 cubos vecinos y a sí mismo, por lo que no debería ser un problema. Tampoco necesita estructuras de datos especializadas, aparte de las obvias que necesita para manejar un entorno basado en cubos.

El costo inicial de construir el terreno puede ser algo, pero ese es un costo único con el que puedes vivir. Factoriza en tu tiempo de carga. Si está realizando muchas colocaciones y eliminaciones en el espacio de un marco, podría ser un problema.

El problema más difícil es la eliminación de interiores sellados. Mi sugerencia: no vale la pena. Al tratar de eliminar los interiores sellados, la colocación o eliminación de un bloque se convierte en una operación no local. Probablemente obtendría más rendimiento si pasara tiempo optimizando el conteo de lotes (use atlas / matrices de texturas cuando sea posible) y sus datos de vértice.

Para eliminar los interiores sellados, debe poder detectar los interiores. Y, por lo tanto, deberá mantener un gráfico bidireccional de caras adyacentes. Para cada cara, tendrá cuatro caras adyacentes. Las caras que fueron eliminadas porque estaba entre dos cubos adyacentes (anteriormente referidas como "caras muertas") no deben formar parte de la gráfica.

Cuando se coloca un cubo, debe actualizar la información de adyacencia para el gráfico de caras. Las caras muertas necesitan ser eliminadas. La adyacencia para las caras vivas después de la colocación debe incorporar las nuevas caras que se agregaron debido al nuevo bloque que se colocó. El algoritmo para hacer esto debería ser bastante sencillo si te sientas y trazas las posibilidades. Por ejemplo, si tienes este cuadrado:

  A
+++++
+   +
+   + B
+   +
+++++

Las caras A y B son adyacentes. Si coloca un nuevo bloque, cambia la adyacencia:

     +++++
     +   +
   C +   +
     +   +
  A  +++++
+++++  D
+   +
+   + B
+   +
+++++

A ahora es adyacente a C y B adyacente a D.

Cuando se quita un cubo, debe actualizar nuevamente la información de adyacencia para el gráfico de caras. Esencialmente, hay que revertir la operación anterior.

El punto de este gráfico de adyacencia es este: si todas las caras no muertas están conectadas en el gráfico, entonces será visible exactamente un ciclo del gráfico; Todos los demás ciclos de gráficos no serán visibles. Un ciclo de la gráfica es un grupo de caras que están conectadas entre sí, ya sea directa o indirectamente.

La gran pregunta es esta: ¿cómo encuentras el ciclo visible? El siguiente algoritmo asume que los bloques son colocados / eliminados por una entidad. Esto significa que al menos una cara de cualquier bloque que se coloca es visible. También significa que las caras muertas que se vuelven vivas al eliminar un bloque son visibles.

Cuando coloca un bloque, puede crear uno o más ciclos nuevos de caras. Para detectar esto, primero encuentra todas las caras no muertas (las que no están directamente adyacentes a algo) que ha creado al colocar el bloque. Al menos uno de estos será visible; encuentra esa cara

Luego, para cada otra cara no muerta en el nuevo bloque, use una búsqueda en el gráfico A * (estrella A) para encontrar esa cara. A * es un algoritmo de búsqueda de gráficos basado en colas de prioridad. En este caso, la "distancia" para el algoritmo es la distancia entre el cuadrado en el que se encuentra la cara actual y el cuadrado en el que está la cara visible.

Si el A * no puede encontrar la cara, sabrá que cada cara que buscó (probablemente debería almacenarlas en un búfer mientras las prueba) forma parte de un ciclo no visible y, por lo tanto, puede eliminarse. Debe marcar estas caras como no visibles para referencias posteriores.

Eliminar un bloque es mucho más fácil. Cuando está eliminando un bloque, al menos una cara del bloque debe estar visible (consulte el supuesto anterior). Por lo tanto, si el bloque que se va a eliminar tiene algunas caras no visibles, todas las caras de un ciclo, incluidas las caras no visibles, deben ser visibles. Así que antes de eliminar el bloque, compruebe si hay caras no visibles. Si hay alguno, utilice una búsqueda en profundidad para encontrar todas las caras en ese ciclo y colóquelas en un búfer. Una vez que elimines el bloque, todas esas caras se harán visibles.

Ahora, si eres capaz de teletransportar bloques, las cosas se vuelven más complejas. Cuando coloca un bloque, existe la posibilidad de que ninguna de las caras de ese bloque sea visible. Entonces, lo que debe hacer es encontrar una cara en algún lugar del mundo que sea visible. Luego haz tu A * buscando esa cara como normal. Sería bueno si la cara visible estuviera en algún lugar cercano, por lo que la búsqueda no tuvo que ir demasiado lejos.

Con la eliminación, lo que tiene que hacer es encontrar todos los ciclos de caras no visibles adyacentes al bloque. Entonces necesitas encontrar esa cara visible como antes. Luego remueve el bloque y busca esos ciclos con A * para ver si pueden encontrar la cara visible. Esos ciclos que pueden ser visibles. Esos ciclos que no pueden no ser visibles.

Además, debe tener un caso especial para eliminar un bloque que no tenga caras activas (es decir, está totalmente integrado en otros bloques). Esto crea un ciclo de 6 caras que no es visible.

Tal vez ahora ves por qué no vale la pena el esfuerzo? Honestamente, a menos que tenga datos de perfiles reales en la mano que demuestren que necesita esto, le recomiendo encarecidamente que no lo haga. Es probable que esté haciendo más trabajo del necesario, y que posiblemente dedique mucho tiempo a algo irrelevante.

Ahora, escribí este post del manguito; Pensé en el algoritmo más simple que podría funcionar. No he investigado las posibles mejoras de este algoritmo, como la búsqueda preventiva de ubicaciones de bloques que podrían crear interiores, o la búsqueda de bloques que, de eliminarse, harían visible un interior. Así que admito libremente que este algoritmo es bastante fuerza bruta. Pero encontrar uno mejor requerirá un poco de esfuerzo, así que, una vez más, a menos que tenga datos de perfil que digan que debe hacer esto para lograr el rendimiento que desea, le aconsejo que no lo haga.