Construyendo un Octree para la generación del terreno

9

Anteriormente he implementado cubos de marcha / tetraedros para representar un IsoSurface. Funcionó ( YouTube ), pero el rendimiento fue terrible ya que nunca pude implementar un Nivel de detalle variable basado en la distancia de visualización (o incluso eliminar fragmentos viejos y distantes).

Decidí probar otra vez y hacerlo bien esta vez. Comencé creando un OctreeNode que funciona de la siguiente manera cuando Build()se llama.

  • Si el fragmento es demasiado pequeño para construirlo, regrese de inmediato.
  • Averigüe si la superficie pasa a través del volumen de este fragmento.
  • Si es así, decida si queremos elevar el LOD (porque la cámara está cerca)
  • Si es así, genera 8 niños y llama al mismo proceso
  • Si no, construya la malla usando las dimensiones del nodo actual

Algunos pseudocódigo:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ Además de devolver la densidad en un punto, la fuente de densidad puede determinar el rango de densidad posible para un volumen dado.

² El proveedor de LoD toma un cuadro delimitador y devuelve el LoD máximo deseado en función de la posición / frustum de la cámara, la configuración del usuario, etc.

Entonces ... Todo esto funciona bastante bien. Usando una esfera simple como la fuente de densidad, y mostrando todos los nodos:

Octree completo

Y solo las hojas:

Octree mostrando solo hojas

Sin embargo, hay un par de problemas:

  • Tengo que definir el volumen delimitador inicial (y cuanto más grande sea, más procesamiento necesito hacer)
  • En la raíz del árbol, no tengo idea de qué tan profundas serán las hojas, por lo que mi numeración LoD comienza con la calidad más baja (raíz) y aumenta a medida que los trozos se hacen más pequeños. Debido a que LoD ahora es relativo al volumen inicial, no sirve de mucho cuando quiero hacer cosas en tamaños / calidades específicos.

He pensado en un par de opciones, pero ambas parecen defectuosas:

  • Mantenga una colección de octrees y agregue / elimine según la distancia. No puedo ver cómo encajaría bien, además, necesitaría una lista de nodos vacíos conocidos, especialmente si quiero superficies 3D arbitrarias (para evitar volver a calcular volúmenes vacíos repetidamente)
  • Agregue un nodo primario a la raíz actual, luego agregue siete hermanos para el nodo original. Esto funcionaría y sería a pedido, pero parece complejo reducirlo sensiblemente a medida que el jugador se mueve por el paisaje. También haría que los números de LoD fueran aún menos significativos.

¹ [En aclaración a Q a continuación] En la actualidad, si 2 nodos físicamente adyacentes en el árbol están en LOD diferentes, tengo algún código para forzar a los verts de modo que no haya costura cuando se generan las mallas. Puedo hacer esto conociendo la densidad para múltiples nodos circundantes. En un escenario en el que tengo 2 octreos independientes uno al lado del otro, no tendría una manera fácil de recuperar esta información, lo que daría lugar a costuras.

¿Cuál es una forma óptima de abordar esto?

Básico
fuente

Respuestas:

1

No estoy seguro de estar respondiendo la pregunta exacta, así que voy a responder en segmentos, y siéntase libre de responder en los comentarios si hay un malentendido sobre los detalles de una pregunta específica.

Tengo que definir el volumen delimitador inicial (y cuanto más grande sea, más procesamiento necesito hacer)

Esto no parece ser el caso. Dado que el octree aumenta exponencialmente la granularidad, agregar algunos niveles en la parte superior debería ser un aumento neto muy pequeño en el rendimiento.

En la raíz del árbol, no tengo idea de qué tan profundas serán las hojas, por lo que mi numeración LoD comienza con la calidad más baja (raíz) y aumenta a medida que los trozos se hacen más pequeños. Debido a que LoD ahora es relativo al volumen inicial, no sirve de mucho cuando quiero hacer cosas en tamaños / calidades específicos.

Si fija su octree raíz a un "valor suficientemente grande", entonces "LoD relativo al volumen inicial" no debería ser un problema. Y como se mencionó anteriormente, no creo que tener un nivel adicional en la parte superior afecte el rendimiento general.

Mantenga una colección de octrees y agregue / elimine según la distancia. No puedo ver cómo encajaría bien, además, necesitaría una lista de nodos vacíos conocidos, especialmente si quiero superficies 3D arbitrarias (para evitar volver a calcular volúmenes vacíos repetidamente)

Según tengo entendido, esta solución propuesta se trata de reducir LoD al alejarse de un área previamente detallada. Me imagino que debería ser muy similar a la ruta de código "creciente LoD":

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

Entonces, no pasará demasiado tiempo comprobando nodos distantes porque puede confiar en el hecho de que, mientras está lejos, no hay demasiados nodos "activos", ya que todos los nodos de mayor resolución se habrán eliminado.


Asumiendo que los nodos pequeños son de escala de roca, eso significaría potencialmente docenas si no cientos de niveles mientras viajo a través de un continente

Creo que la escala logarítmica del octree lo hace aún factible. Si su nivel superior es de 1,000,0000,000 m de ancho (esto sería 25 veces más ancho que la Tierra real, y con 625x el área de superficie) y sus bits de nivel más bajo tienen 10 cm de ancho, eso es 32 niveles en el octree, que probablemente sea lo suficientemente manejable Si quisieras un planeta 100 veces más ancho que la Tierra (y con 10000 veces más área de superficie), eso es solo de 3 a 4 niveles adicionales en tu octree. En este punto, le tomaría cientos de años a un jugador caminar por el mundo, y si usa matemática ingenua de coma flotante, el mundo acumulará errores de precisión.

Mantenga una colección de octrees y agregue / elimine según la distancia. No puedo ver cómo encajaría bien, además, necesitaría una lista de nodos vacíos conocidos, especialmente si quiero superficies 3D arbitrarias (para evitar volver a calcular volúmenes vacíos repetidamente)

¿No es esto fundamentalmente equivalente a tener el octree de mil millones de kilómetros de ancho, pero mantener una lista de punteros en cada bloque de, por ejemplo, 1 km? Luego, "combinar" simplemente dependería de los nodos de 2 km de tamaño. Mantener una referencia local a cada "bloque grande" de nivel medio también evita que tenga que recorrer los nodos de nivel superior, si le preocupan las "posiblemente docenas de niveles de octree adicionales".

Palanqueta
fuente
Gracias por responder. No puedo elegir un volumen inicial masivo ya que mi terreno es infinito (ese es mi objetivo). Mira el video para tener una idea. Como tal, mi árbol de nodos se volvería cada vez más alto. Asumiendo que los nodos pequeños son de escala de roca, eso significaría potencialmente docenas si no cientos de niveles mientras viajo a través de un continente. Re: Malla a través, déjenme agregar un poco más de detalle a la pregunta [Hecho]
Básico
en lo que respecta al jugador, "mil millones de millas" está bastante cerca de "infinito". Más argumentos para un volumen inicial fijo agregado a la respuesta.
Jimmy
Todavía no estoy convencido. ¿Por qué tener más de 30 capas de procesamiento inútil conocido? No es elegante, y mucho menos eficiente. Aprovecho su punto sobre el tiempo para cruzar, pero simplemente estamos hablando de la generación del terreno. Nada que diga que tengo que centrarme en el origen, ni que volar a alta velocidad es imposible (¡aunque no estaría mallando a esa velocidad!). FWIW Estoy usando dobles internamente para evitar ese problema de precisión.
Básico