PDF de programación - Implementación de un algoritmo de refinamiento/desrefinamiento para mallas de tetraedros

Universidad de Las Palmas de Gran Canaria

Instituto Universitario de Sistemas Inteligentes y

Aplicaciones Num´ericas en Ingenier´ıa

Tesis Doctoral

Implementaci´on de un algoritmo de
refinamiento/desrefinamiento para

mallas de tetraedros

Jos´e Mar´ıa Gonz´alez Yuste

Las Palmas de Gran Canaria, mayo de 2007

Universidad de Las Palmas de Gran Canaria

Programa de Doctorado en Sistemas Inteligentes y Aplicaciones

Num´ericas en Ingenier´ıa

Instituto Universitario de Sistemas Inteligentes y

Aplicaciones Num´ericas en Ingenier´ıa

Tesis Doctoral

Implementaci´on de un algoritmo de
refinamiento/desrefinamiento para

mallas de tetraedros

Autor

Director

Director

Jos´e Ma Gonz´alez Yuste Rafael Montenegro Armas

Jos´e Ma Escobar S´anchez

Las Palmas de Gran Canaria, mayo de 2007

A Mila y Javier

Agradecimientos

Hay muchas personas que me han apoyado y han contribuido para que este

trabajo llegara a buen t´ermino.

En primer lugar, quiero mencionar a mi director Rafael Montenegro. Han
sido innumerables las tardes que hemos pasado comentando infinidad de temas
(y no s´olo de investigaci´on). Su paciencia conmigo y sus actos de fe cuando yo
le propon´ıa alguna locura no tienen precio.

Tambi´en quiero agradecer el entusianmo de Jos´e Ma Escobar, mi otro direc-
tor, y de Gustavo Montero, director de la divisi´on GANA del IUSIANI. Jos´e
Ma siempre anda buscando algo nuevo, siempre proponiendo alguna aplica-
ci´on. . . deber´ıa descansar un poco. Gustavo siempre aportaba alguna soluci´on
cuando nos atasc´abamos en un problema y nos daba una salida f´acil y elegante.
A mi compa˜nero (ya doctor) Eduardo Rodr´ıguez Barrera, le debo m´as de lo
que puedo agradecerle en estas l´ıneas. Me ha facilitado much´ısimo las cosas y
siempre ha estado a mi disposici´on cuando lo he necesitado.

A mi mujer, Mila. . . por fin! Siempre ha estado anim´andome, empuj´andome
y hasta persigui´endome para que continuara con la labor investigadora. Si mi
ocupaci´on laboral y familiar me llevaban el 110 % del tiempo, has conseguido
aligerarme much´ısimo la carga para que siguiera adelante. Gracias por tu pa-
ciencia y tu comprensi´on en todas esa jornadas at´ıpicas en las que el dormir era
un sue˜no. Y por encargarte de nuestro hijo, Javier, que antes de cumplir los dos
a˜nos ya distingu´ıa perfectamente lo que era un tri´angulo. Afortunadamente a´un
no sabe lo que es un tetraedro.

Tambi´en quiero mencionar a mis padres, hermanos, familiares y amigos que
han estado siempre interes´andose y anim´andome para que concluyera este tra-
bajo. Gracias a todos.

vi

Esta tesis ha sido desarrollada en el marco de los proyecto subvencionados
por el Ministerio de Ciencia y Tecnolog´ıa y FEDER, REN2001-0925-C03-02/CLI
titulado Modelizaci´on num´erica de transporte de contaminantes en la atm´osfera,
y CGL2004-06171-C03-02/CLI titulado Modelizaci´on y simulaci´on num´erica de
campos de viento orientados a procesos atmosf´ericos.

´Indice general

1. Introducci´on

1.1. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Justificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Objetivos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4. Metodolog´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Desarrollo

2.1. Programaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1. Tipos de datos y clases . . . . . . . . . . . . . . . . . . .

2.1.2. Plantillas

. . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.3. Punteros . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. La Standard Template Library . . . . . . . . . . . . . . . . . . .

2.3. POSIX threads

. . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1. Threads

. . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2. Mutex y Secciones cr´ıticas . . . . . . . . . . . . . . . . .

2.3.3. Variables de condici´on . . . . . . . . . . . . . . . . . . .

2.4. Modelo de objetos

. . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1. Objetos de la malla . . . . . . . . . . . . . . . . . . . . .

2.4.2. Clases para la resoluci´on de problemas . . . . . . . . . .

2.4.3. Clases que dan soporte a estructuras de datos . . . . . .

2.4.3.1.

Iterador . . . . . . . . . . . . . . . . . . . . . .

2.4.3.2. Threads y secciones cr´ıticas . . . . . . . . . . .

2.4.3.3. Acceso a ficheros . . . . . . . . . . . . . . . . .

2.4.4. Agregaci´on y uso . . . . . . . . . . . . . . . . . . . . . .

2.5. Estructuras de datos . . . . . . . . . . . . . . . . . . . . . . . .

2.5.1. Carga inicial de una malla . . . . . . . . . . . . . . . . .

2.5.2. Relaci´on entre elementos . . . . . . . . . . . . . . . . . .

1

2

5

5

6

9

9

10

10

11

11

15

15

16

17

19

20

22

22

23

23

23

24

25

25

26

viii

´Indice general

2.5.3. Operadores de conjuntos . . . . . . . . . . . . . . . . . .

2.5.4. Generaci´on/Eliminaci´on de elementos . . . . . . . . . . .

2.5.5.

Iteraciones sobre elementos . . . . . . . . . . . . . . . . .

3. Algoritmo de Refinamiento

3.1. Presentaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1. Divisi´on en 8 tetraedros

. . . . . . . . . . . . . . . . . .

3.1.2. Propagaci´on del algoritmo . . . . . . . . . . . . . . . . .

3.2.

Implementaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3. Proceso de Marcado . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1. Clasificaci´on de tetraedros . . . . . . . . . . . . . . . . .

3.3.2. Estudio de transitorios . . . . . . . . . . . . . . . . . . .

3.3.3. Eliminaci´on de transitorios . . . . . . . . . . . . . . . . .

3.4. Proceso de divisi´on . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1. Paralelizaci´on del proceso de divisi´on . . . . . . . . . . .

3.4.2. Lanzamiento de procesos . . . . . . . . . . . . . . . . . .

3.4.3. M´odulo principal de divisi´on . . . . . . . . . . . . . . . .

3.4.4. Procesos paralelos . . . . . . . . . . . . . . . . . . . . . .

3.4.5. Finalizaci´on de procesos

. . . . . . . . . . . . . . . . . .

3.4.6. Etiquetado de elementos . . . . . . . . . . . . . . . . . .

3.4.6.1. Notaci´on . . . . . . . . . . . . . . . . . . . . .

3.4.7. Divisi´on de aristas

. . . . . . . . . . . . . . . . . . . . .

3.4.8. Divisi´on de caras . . . . . . . . . . . . . . . . . . . . . .

3.4.8.1. Cara con una arista marcada . . . . . . . . . .

3.4.8.2. Cara con dos aristas marcadas

. . . . . . . . .

3.4.8.3. Cara con tres aristas marcadas

. . . . . . . . .

3.4.9. Divisi´on de tetraedros

. . . . . . . . . . . . . . . . . . .

3.4.9.1. Tetraedro con una arista marcada . . . . . . . .

3.4.9.2. Tetraedro con dos aristas marcadas en la misma
cara . . . . . . . . . . . . . . . . . . . . . . . .

3.4.9.3. Tetraedro con dos aristas marcadas en distinta
cara . . . . . . . . . . . . . . . . . . . . . . . .

3.4.9.4. Tetraedro con tres aristas marcadas en la misma
cara . . . . . . . . . . . . . . . . . . . . . . . .

3.4.9.5. Tetraedro con las seis aristas marcadas . . . . .

3.5. Proceso de Compactaci´on . . . . . . . . . . . . . . . . . . . . .

27

28

29

31

31

35

36

37

38

38

39

41

42

43

43

44

46

46

47

47

48

49

49

50

50

52

52

53

54

55

57

60

´Indice general

3.5.1. Borrado de elementos . . . . . . . . . . . . . . . . . . . .

3.5.2. Generaci´on de estructuras . . . . . . . . . . . . . . . . .

3.6. An´alisis computacional . . . . . . . . . . . . . . . . . . . . . . .

3.6.1. Proceso de marcado

. . . . . . . . . . . . . . . . . . . .

3.6.2. Proceso de divisi´on . . . . . . . . . . . . . . . . . . . . .

3.6.3. Proceso de compactaci´on . . . . . . . . . . . . . . . . . .

3.6.4. Proceso global . . . . . . . . . . . . . . . . . . . . . . . .

4. Algoritmo de Desrefinamiento

4.1. Presentaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.

Implementaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1. Aplicaci´on a otros elementos . . . . . . . . . . . . . . . .

4.3. Proceso de marcado . . . . . . . . . . . . . . . . . . . . . . . . .

4.4. Proceso de revisi´on . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.1. Generaci´on de listas por niveles . . . . . . . . . . . . . .

4.4.2. Procesamiento de listas de un nivel

. . . . . . . . . . . .

4.4.3. Eliminar elementos de un nivel

. . . . . . . . . . . . . .

4.5. Conformado . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6. An´alisis computacional . . . . . . . . . . . . . . . . . . . . . . .

5. Aplicaciones

5.1. Mallas de tri´angulos en 3D . . . . . . . . . . . . . . . . . . . . .

5.1.1.

Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.2. Adaptaci´on del algoritmo de refinamiento . . . . . . . . .

5.1.2.1. Lectura de ficheros . . . . . . . . . . . . . . . .

5.1.2.2. Refinamiento . . . . . . . . . . . . . . . . . . .

5.1.3. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . .

5.2. Suavizado de mallas en 3D . . . . . . . . . . . . . . . . . . . . .

5.2.1.

Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.2. Optimizaci´on de mallas con funciones objetivo mejoradas

5.2.2.1. Funciones objetivo . . . . . . . . . . . . . . . .

5.2.2.2. Funciones objetivo modificada . . . . . . . . . .

5.2.3. Experimentos num´ericos . . . . . . . . . . . . . . . . . .

5.2.4. Conclusiones

. . . . . . . . . . . . . . . . . . . . . . . .

5.3. Modelizaci´on de campos de viento . . . . . . . . . . . . . . . . .

5.3.1. Modelo de masa consistente . . . . . . . . . . . . . . . .

ix

60

62

64

64

65

65

66

67

67

68

69

69

71

72

73

75

76

77

79

79

79

80

80

80

84

84

84

86

87

89

91

95

95

96

x

´Indice general

97
5.3.2. Viento interpolado . . . . . . . . . . . . . . . . . . . . .
5.3.3. Refinamiento adaptativo . . . . . . . . . . . . . . . . . .
99
5.3.4. Estimaci´on de par´ametros . . . . . . . . . . . . . . . . . 100
5.3.5. Algoritmos gen´eticos . . . . . . . . . . . . . . . . . . . . 102
5