Presentacion-terrenos

Contenido 

Refinamiento-desrefinamiento de mallas.



Esqueleto de una malla.



Algoritmos de refinamiento y desrefinamiento.



Niveles de Detalle del Terreno.



Aplicaciones.



Conclusiones.

Refinamiento/Desrefinamiento Generación de mallas Proceso de discretización de un dominio físico en subdominios más pequeños (elementos): Métodos Numéricos, Gráficos por Ordenador, CAD/CAM ...

Refinamiento/ Desrefinamiento de mallas Procesos aplicados a mallas que permiten insertar nuevos elementos (refinamiento) y eliminar elementos existentes (desrefinamiento) con el objetivo de obtener mallas adaptadas

Refinamiento de mallas en 2D Aproximación de superficies

Refinamiento/Desrefinamiento de mallas en 2D Problema de Convección-Difusión

∂u + v ⋅ ∇u − ∇ ⋅ ( k∇u ) = f ∂t

Refinamiento/Desrefinamiento de mallas en 2D (cont.)

Problema de Convección-Difusión

Refinamiento/Desrefinamiento de mallas en 3D

BOLA-3D

Esqueleto de una malla Definición

(n-1) - esqueleto (τ ) = {(n-1)-caras(τ ) }

Tetraedro

Caras

Aristas

Nodos

Refinamiento basado en el Esqueleto Refinamiento Basado en el Esqueleto (malla,n-símplice,partición) Para cada n-símplice a refinar hacer 1) División del 1-esqueleto 2) División del 2-esqueleto ... n) Reconstruir interior del n-símplice Fin Propiedades • Complejidad lineal de los algoritmos 2D-SBR y 3D-SBR • Aplicación a mallas con regiones de alta no convexidad • No requiere pre-procesamiento inicial de la malla • La no degeneración de elementos está probada empíricamente en 3D

Algoritmo de Refinamiento 2D-SBR

LEPP 1

t LEPP 3

LEPP 2

Algoritmo de Refinamiento 2D-SBR Algoritmo 2D-SBR(τ, t0) /* Entrada: τ malla, t0 triángulo /* Salida: τ malla 1.L=1-esqueleto(t0) LEPP 1 Para cada arista ei ∈ L hacer Subdivisión(ei) Fin LEPP 3 2.Para cada arista ei ∈ L hacer Si=LEPP(ei,G1(τ)) Para cada triángulo ti ∈ Si hacer Sea ei la arista mayor de ti Subdivisión(ei) Fin Fin 3.Para cada triángulo tj ∈ τ (G1(τ) ) a ser subdividido hacer Subdivisión(tj) Fin

LEPP 2

Algoritmo de Desrefinamiento 2D-SBD Algoritmo 2D-SBD(T,ε) /* Entrada: Secuencia T={τ1, τ2, τ3,…,τn}, ε=error /* Salida: Secuencia T’={τ1, τ’2, τ’3, …,τ’m} 1: Para j=n hasta 2 hacer Para cada nodo propio elegible ∈ τj hacer

Fin

•Se calcula el conjunto L ∈ 1-esqueleto con las aristas a refinar •Se examina la condición de desrefinamiento y ε •Se marcan los nodos a eliminar 1.1 Se comprueba la conformidad local 1.2 Si un nodo no se elimina, tampoco los de la arista entorno

Fin 2: Para j=2 hasta n hacer •Se redefine la malla τj

τj=2D-SBR(τ j-1 ,L) Fin

Desrefinamiento: 2D-SBD Criterio Desrefinamiento

Proceso de conformidad

Niveles de Detalle Incorporación de los algoritmos al lenguaje de realidad virtual VRML para generar niveles de detalle.

 L 0 si d < R 0  L(d) =  L i +1 si R i ≤ d < R i +1 para - 1 < i < n - 1 L  n-1 si d ≥ R n-1

Niveles de Detalle

(cont.)

Nivel de Detalle 2 10 % error Nivel de Detalle 1 0 % error

Nivel de Detalle 3 30 % error

Incorporación a VRML Modelo inicial

Desrefinamiento de mallas Representación VRML Malla 1 Malla 2

... Malla n

Generación LOD´s VRML

Pruebas Numéricas

Ejemplos de aplicación Modelos Digitales del Terreno (DEM)

Caldera de Bandama, Gran Canaria

La caldera de Bandama

Malla 2D desrefinada con ε=10 m.

Superficie del terreno con ε=10 m.

La caldera de Bandama

Malla 2D desrefinada con ε=18 m.

(cont.)

Superficie del terreno con ε=18 m.

Bandama.vrml

La caldera de Bandama

(cont.)

Curvas de Nivel: INDICADOR DE LA BONDAD DE LA APROXIMACIÓN DEL TERRENO

original

ε=18 m.

ε=10 m.

ε=25 m.

Niveles de Detalle: Ciudad de Gáldar, Gran Canaria

Desrefinamiento -Niveles de Detalle Aproximación con 10 metros de error, 19506 nodos, 38732 triángulos

Aproximación con 15 metros de error, 13661 nodos, 27073 triángulos

Aproximación con 90 metros de error, 1094 nodos, 2035 triángulos

Análisis de resultados Relación Señal-Ruido

∑ SNR = 10 log ∑

N

n =1 N

s 2 (n)

2 e (n) n =1

SNR=0 -> máx. error SNR=inf -> min. error Gráfica del SNR en decibelios frente al número de nodos

Tiempo de obtención de las mallas frente al nivel de error

Análisis del resultado

(cont)

Galdar.vrml

LOD Error (m.) triángulos N. puntos T. Render (s.) Tamaño (Kb.)

1 0 131072 66049 1.310 3653

2 20 10096 19962 0.220 406

3 40 3755 7333 0.110 156

Ejemplo del terreno de Gáldar, Gran Canaria

4 60 1975 3789 0.060 86

Conclusiones •

Los algoritmos de Refinamiento y Desrefinamiento son herramientas útiles para la generación de Niveles de Detalle del terreno (proceso adaptativo).

•

La complejidad de los algoritmos en términos de tiempo es lineal.

•

El desrefinamiento es eficiente (tiempo real) para errores no muy pequeños.

•

La complejidad en cuanto al almacenamiento es mínima debido a la estructura de datos (lista de nodos + lista de triángulos en función de nodos).

•

Los algoritmos son fácilmente portables a código VRML