Embed Size (px)
Citation preview
Revista Cubana de Ciencias Informáticas
ISSN: 1994-1536
Universidad de las Ciencias Informáticas
Cuba
Quesada Rodríguez, Eddy Dangel; Suárez Morales, Dagoberto Antonio
TI-Octree: Índice espacial para estructuras geológicas.
Revista Cubana de Ciencias Informáticas, vol. 6, núm. 2, 2012, pp. 1-13
Universidad de las Ciencias Informáticas
Ciudad de la Habana, Cuba
Disponible en: http://www.redalyc.org/articulo.oa?id=378343676003
Cómo citar el artículo
Número completo
Más información del artículo
Página de la revista en redalyc.org
Sistema de Información Científica
Red de Revistas Científicas de América Latina, el Caribe, España y Portugal
Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
1
Tipo de artículo: artículo
Temática: Geoinformática
Recibido: 4/08/2012 | Aceptado : 12/09/2012
TI-Octree: Índice espacial para estructuras geológicas.
TI-Octree: Spatial index for geological structures.
Eddy Dangel Quesada Rodríguez1*
, Dagoberto Antonio Suárez Morales2
1Centro GEySED, Universidad de las Ciencias Informáticas, La Habana, Cuba. Email: [email protected]
2Centro GEySED, Universidad de las Ciencias Informáticas, La Habana, Cuba. Email: [email protected]
* Autor para correspondencia
Resumen: La modelación y visualización en tres dimensiones de estructuras geológicas es una de las actividades
fundamentales realizadas en la industria minera. Los mineros y geólogos deben mantener un control exhaustivo
del volumen de extracción de los minerales de un yacimiento, utilizando generalmente programas de cómputo
para procesar la información obtenida. En la minería un yacimiento mineral es habitualmente representado por
un modelo de bloques y este modelo debe respetar la morfología de las estructuras geológicas. Para modelar las
estructuras geológicas y los volúmenes de extracción de mineral se utilizan mallas de tetraedros. La malla de
tetraedros es una estructura espacial que, por sus características, permite modelar las estructuras geológicas en la
rama de la geología y la minería, facilitando el cálculo del volumen del sólido. Con el objetivo de mejorar el
rendimiento en la búsqueda de tetraedros dada una región determinada del espacio, el presente artículo propone
la implementación de una estructura de datos espaciales para indexar la malla de tetraedros, realizando pruebas
que permiten obtener como conclusión que el tiempo de búsqueda de la propuesta realizada disminuye en
comparación con el tiempo de búsqueda en una estructura lineal.
Palabras claves: Indexación, Octree, tetraedro.
Abstract: Modeling and visualization of three-dimensional geological structures is one of the main activities in
the mining industry. Miners and geologists most maintain an exhaustive control of the extracted volume of
mineral of a deposit, using computer programs for processing the obtained information. In the mining process, a
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
2
mineral deposit is commonly represented by a block model, which represents the morphology of the laying
geological structures. For modeling those geological structures and the volume of extracted mineral they use
tetrahedral networks. The tetrahedral network is an spatial structure that, given it characteristics, allows
modeling geological structures in the fields of mining and geology, making easier the volume calculus. Aiming to
improve the tetrahedral search process given an spatial region, this work presents a proposal of one spatial
data structure for indexing tetrahedral networks, demonstrating by some experiments that the searching time
over this proposal is less compared with the searching time over a linear structure.
Keywords: Indexing, Octree, tetrahedron.
1. Introducción
Las estructuras geológicas o zonas geológicas son la representación geométrica de cuerpos sólidos formados por
zonas mineralizadas o capas litológicas localizadas en el subsuelo de la corteza terrestre (Luthi, 1992). Estas
estructuras son el resultado de la interpretación geológica realizada a un depósito mineral (Hanna, 2000) y son
utilizados posteriormente para delimitar zonas mineralizadas (ver Figura 1) en modelos de bloques geológicos.
En la industria minera es necesario llevar un control exhaustivo del volumen de extracción de los minerales de
un yacimiento, por lo cual se emplean, generalmente, mallas poligonales para modelar los volúmenes de
extracción de mineral (Zhao y Wen, 2010).
Figura 1 Estructura Geológica
Las mallas poligonales más utilizadas en la representación de objetos sólidos son las compuestas por triángulos o
tetraedros. La representación de un cuerpo sólido utilizando mallas de triángulos permite un mayor ahorro de
memoria en comparación con la representación de cuerpos sólidos con mallas de tetraedros. Aunque las mallas
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
3
de triángulos son más ligeras para este tipo de representación, debido a que solamente modelan las superficies
exteriores de los objetos sólidos, pueden acarrear problemas que influyen en el cálculo de volumen del sólido.
Estos problemas son originados cuando la malla de triángulos en su totalidad no representa una superficie
cerrada y no cumpla con el teorema de Jordan (Berg et al. 1975; Hales, 2007). También se debe tener en cuenta
que el vector normal de cada triángulo de la malla debe estar orientado hacia el exterior de la superficie. Para
evitar estos problemas, es necesario realizar un conjunto de pruebas a la malla para comprobar su integridad.
Estas pruebas traen como consecuencia un aumento del tiempo de cómputo en las operaciones de cálculo. Las
herramientas informáticas que trabajan con objetos sólidos y realizan análisis de elementos finitos (Hutton,
2004) generalmente utilizan mallas de tetraedros por las facilidades que brinda este tipo de malla en los cálculos
de volumen.
Una malla de tetraedros (ver Figura 2), también conocida como Tetrahedral Network (TEN) (PiloukI, 2008;
Sherif, 2011), es una estructura espacial que, por sus características, permite modelar las estructuras geológicas
en la rama de la geología y la minería, facilitando el cálculo del volumen del sólido y eliminando errores de
inconsistencias que habitualmente tienen las mallas de triángulos para el cálculo de volumen. Estas mallas
generan más objetos geométricos que una malla de triángulos, por tanto, se pueden utilizar diversos algoritmos
que permitan disminuir la cantidad de elementos en la malla.
Figura 2. Objeto geométrico modelado por una malla de tetraedros.
En diversas áreas de la geometría computacional y las geociencias es común realizar búsquedas espaciales sobre
un conjunto de objetos geométricos distribuidos en una región del espacio. Los costos computacionales de estas
consultas pueden ser realmente altos en dependencia de la cantidad de objetos geométricos que se procesan y de
la utilización de matrices tridimensionales para el almacenamiento de la información. Para disminuir los costos
computacionales en operaciones de búsquedas y procesamiento de los datos espaciales se utilizan estructuras de
datos espaciales jerárquicas (Keim, 1999). Según (Zachmann, 2006), existe un conjunto de estructuras de datos
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
4
espaciales que permiten mejorar los procesos de búsqueda sobre las estructuras geológicas, tales como: R-Tree,
Quadtree, Octree, Kd-Tree, entre otras. Como expusiera (Samet, 1990b), en problemas de modelado de sólidos
la principal estructura de datos espaciales (EDE) a seleccionar es el Octree. El presente artículo aborda la
implementación de una variante de Octree (Tetrahedral Indexed Octree) que permite disminuir el tiempo de una
búsqueda espacial en estructuras geológicas modelas por mallas de tetraedros.
Trabajos relacionados
Existen estructuras de datos espaciales que se han utilizado para la representación de cuerpos geométricos, en
muchos casos para la representación de cuerpos sólidos, característica que comparten los cuerpos de mineral. A
continuación se describen algunas de las principales estructuras de datos utilizadas en la representación de
objetos geométricos tridimensionales. Un Octree (Metha y Sahni, 2005; SAMET 1990b; Zachmann, 2006) es
una estructura de datos espaciales jerárquica utilizada para modelar datos volumétricos. Esta estructura de datos
se almacena en un árbol y se basa en la subdivisión recursiva de cada nodo del árbol en octantes, dando como
resultado que cada nodo tenga solo 8 hijos, como se muestra en la Figura 3. Existen variantes de implementación
del Octree tradicional, algunas de ellas utilizan apuntadores y otras no. La variante donde no se hace uso de
apuntadores se conoce como Linear Octree (Brunet, 1999) y es de gran utilidad por su capacidad de comprimir
el Octree, pues solo almacena los nodos hoja del árbol. En la presente investigación se utilizó la variante clásica
de un Pointer Octree (Brunet, 1999).
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
5
Figura 3. Representación de jerarquía de nodos de un Octree.
Un Octree se puede clasificar según el método de subdivisión espacial que utiliza y según el tipo de datos que
almacenan en sus hojas. En (Mehta y Sahni, 2005; Samet, 1990a) se define un conjunto de estructuras de datos
como el PR-Octree, el PM-Octree y el PMR- Octree, las cuales son variantes del Octree diferenciadas
fundamentalmente por la técnica de subdivisión espacial que utiliza cada una de ellas. Sus características son
explicadas basándose en las estructuras de datos Quadtree (PR-Quadtree, el PM-Quadtree y el PMR- Quadtree),
estructuras de datos espaciales que se utilizan en problemas bidimensionales y son análogas a las estructuras
Octree mencionadas anteriormente. El PR-Octree tiene como idea fundamental la descomposición recursiva del
espacio en 8 bloques hasta que cada bloque contenga un número muy pequeño de puntos definidos por un
umbral. El PM-Octree y el PMR-Octree son utilizados para indexar espacialmente una colección de vértices y
aristas que no necesariamente tienen que formar un cuerpo geométrico. Las estructuras de datos utilizadas para
indexar mallas de tetraedros son conocidas como Tetrahedral Trees (Floriani et al., 2010) y se basan en los PR-
Octree, PM-Octree y PMR-Octree. En (Floriani et al., 2010) se describen 4 tipos de Tetrahedral Trees: el PR-
Tetrahedral Tree, Centroide Tetrahedral Tree, PMR-Tetrahedral Tree y PM-Tetrahedral Tree.
Tetrahedral Indexed Octree
En el presente trabajo se propone el Tetrahedral Indexed Octree (TI-Octree) como una nueva estructura de datos
espaciales basada en la variante PM-Tetrahedral Tree para el almacenamiento de estructuras geológicas. El
objetivo principal del TI-Octree consiste en construir un árbol que contenga una lista con todos los tetraedros de
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
6
la malla y que cada hoja del árbol guarde una lista de los índices de los tetraedros que estén contenidos parcial o
totalmente dentro de los límites geométricos de la hoja. En la Figura 4 se muestra un caso análogo para un
espacio bidimensional, este caso sería un TI-Quadtree.
Figura 4: TI-Quadtree
En el proceso de creación del TI-Octree se toma como datos de entrada una lista de tetraedros y se emplea la
misma técnica de subdivisión recursiva del espacio que utiliza el PM-Tetrahedral Tree como se muestra en la
(Figura 5). El ortoedro que contiene la malla de tetraedros se subdivide recursivamente en octantes más
pequeños mientras no se cumplan las siguientes condiciones:
El octante solo puede contener una cantidad de vértices menor o igual que el umbral definido.
El octante no tiene vértices contenidos pero es interceptado por alguna arista de cualquiera de los
tetraedros de la malla.
El octante no tiene vértices contenidos y no es interceptado por alguna arista pero es interceptado por
una cara de los tetraedros de la malla.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
7
Figura 5. Subdivisión recursiva de la malla de tetraedro.
Las variantes de Octree estudiadas para el presente trabajo difieren en el método de subdivisión espacial
utilizado para crear el árbol, mientras que esta propuesta modifica la forma de almacenamiento de los tetraedros
en las hojas del árbol. Las variantes ya existentes guardan los tetraedros, como un todo, en las hojas del árbol,
repitiéndose el tetraedro en la estructura cuando se encuentra en dos o más hojas de la misma. En la propuesta
realizada los tetraedros se encuentran almacenados en un arreglo y cada hoja de la estructura espacial creada
posee una lista con las posiciones que ocupan en dicho arreglo los tetraedros que contiene. Esta implementación
permite una optimización del almacenamiento ya que el tamaño en bits de la posición en el arreglo siempre será
menor que el tamaño de la estructura u objeto almacenado.
2. Discusión de los resultados obtenidos
En el presente epígrafe se destacan los resultados referentes a la creación y utilización del TI-Octree para indexar
mallas de tetraedros. Para probar el funcionamiento del TI-Octree se utilizaron redes de tetraedros
correspondientes a dos zonas geológicas mineralizadas y un objeto geométrico complejo. El TI-Octree se
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
8
implementó utilizando el lenguaje de programación C/C++ y una estación de trabajo con el sistema operativo
Ubuntu 11.10, con 1 GB de memoria RAM y un procesador Pentium D a 3.00 GHz de velocidad. A
continuación se muestra una tabla con las características de las mallas de tetraedros utilizadas, tiempo de
creación del Octree y el tiempo de búsqueda de tetraedros en una región determinada de la malla. Todos los
tiempos están expresados en milisegundos.
Tabla 1: Características de las mallas, tiempos de creación y búsquedas.
Objetos Geométricos Cantidad de
tetraedros de
la malla
Cantidad de
hojas en el TI-
Octree
Cantidad de
Nodos en el
TI-Octree
Tiempo de
creación del
TI-Octree
Tiempo de
Búsqueda
lineal
Tiempo de
búsqueda en
TI-Octree
Cuerpo Mineral 1 993 1017 1208 647 8 3
Cuerpo Mineral 2 724 619 738 500 6 1
Escultura 3872 2670 3193 2743 32 9
A partir de los resultados expresados en la Tabla 1 se demuestra que los tiempos de búsqueda en el TI-Octree
disminuyen sustancialmente comparados con los tiempos resultantes de una búsqueda lineal, mostrando mayor
connotación a medida que aumenta la cantidad de tetraedros de la malla. El mayor costo temporal de la
estructura es su creación, sin embargo, una vez construida, las operaciones en la misma son relativamente bajas.
En la Figura 6 se muestran las regiones donde se realizaron las búsquedas de tetraedros cuyos tiempo de
procesamiento se pueden apreciar en la tabla 1.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
9
Figura 6. Regiones donde se realizaron las búsquedas espaciales.
Para una mejor comprensión se muestra en la Figura 7, Figura 8 y Figura 9, una representación de cuerpos de
mineral mediante el TI-Octree, cada figura tiene 3 partes: a) el objeto geométrico original, b) los nodos hojas
creados en el Octree visualizados con un estilo de alambrado y c) los nodos hojas creados en el Octree
visualizados con un estilo sólido.
Figura 7. Cuerpo Mineral 1.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
10
Figura 8. Cuerpo Mineral 2.
Figura 9. Escultura.
El TI-Octree se puede utilizar también para realizar operaciones de simplificación de mallas de tetraedros. Es
necesario tener en cuenta las características de la malla, si en la malla existen aristas muy pequeñas con relación
a las demás, el nivel del árbol será mayor. En casos como estos es necesario utilizar un algoritmo de
simplificación de mallas o redefinir el umbral del método de subdivisión. En (Mehta y Sahni, 2005) se definen
una serie de estrategias para redefinir el umbral de subdivisión en un PM-Quadtree que también pueden ser
utilizadas en un PM-Octree. Estas estrategias toman en cuenta la cantidad de vértices, aristas y caras dentro del
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
11
octante que se quiere subdividir. Al redefinir el umbral del método de subdivisión de un PM-Octree se minimiza
el número de nodos del árbol y disminuye la cantidad de niveles del árbol.
El TI-Octree que propuesto se utilizó en la voxelización de estructuras geológicas. En el proceso de voxelización
(RUEDA et al. 2004) de estructuras geológicas se necesita recorrer el arreglo tridimensional de celdas y evaluar
si una celda está contenida totalmente o parcialmente en la estructura geológica. Si la celda está contenida
parcialmente se subdivide recursivamente en 8 subceldas hasta que se cumpla la condición de parada. Estas
estructuras geológicas son modeladas mediante mallas de tetraedros.
Como los tetraedros de la malla están indexados espacialmente, no es necesario consultar todos los elementos de
la malla para determinar si una celda está contenida parcial o totalmente en la estructura geológica. Para
determinar el estado de una celda con respecto a la estructura geológica se realiza una consulta espacial al TI-
Octree para obtener los índices de los tetraedros que están cercanos a la región de la misma. La utilización del
TI-Octree en la operación de voxelización de estructuras geológicas permitió disminuir considerablemente el
tiempo de procesamiento de esta operación.
3. Conclusiones
En el presente artículo se presentaron los resultados de la utilización del TI-Octree para indexar mallas de
tetraedros, lo que permitió identificar que:
La selección de la estructura de datos depende de la solución que se quiera dar a un problema
determinado.
La cantidad de niveles del árbol está relacionada con la distancia mínima existente entre dos vértices de
la malla de tetraedros. En algunas ocasiones es necesario aumentar la cantidad de vértices, aristas y caras
dentro del nodo hoja del árbol.
Los Tetrahedral Tree permiten disminuir el tiempo de procesamiento de una consulta espacial en una
malla de tetraedros, utilizándose en la implementación de algoritmos de simplificación de mallas y en
algoritmos de voxelización.
La estructura propuesta disminuye la cantidad de bits almacenados en la estructura en comparación con
las variantes existentes.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
12
En el futuro se prevé implementar la estructura propuesta utilizando un Linear Octree para almacenar solo los
nodos hojas del árbol, permitiendo una mayor compresión del Octree.
Referencias
BERG, G.; W. JULIAN, et al. THE CONSTRUCTIVE JORDAN CURVE THEOREM JOURNAL OF
MATHEMATICS, 1975, 5(2).
FLORIANI, L. D.; R. FELLEGARA, et al. Design, Analysis and Comparison of Spatial Indexes for Tetrahedral
Meshes, Universidad de Genova, 2010.
HALES, T. C. The Jordan Curve Theorem,Formally and Informally THE MATHEMATICAL ASSOCIATION OF
AMERICA, 2007.
HANNA, J. D. A. P. Geological Interpretation for Resource Estimation The Resource Database Towards 2000,
2000.
HUTTON, D. V. Fundamentals of Finite Elements Analysis. 2004. p.
KEIM, D. A. Efficient Geometry-based Similarity Search of 3D Spatial Databases, 1999.
LUTHI, S. M. Solid computational models of geological structures in borehole Lecture Notes in Earth Sciences,
1992, 41.
MEHTA, D. P. and S. SAHNI, Eds. Handbook of data structures and applications, 2005. 1-58488-435-5
P. BRUNET, F. J. S., A. VILANOVA, L. CHIARABINI, G.A.PATOW, E. STAFFETI, J. SURINYAC.
Estructuras Geométricas Jerárquicas para Modelización de Escenas 3D. 1999. p.
PILOUK, A. A.-R. A. M. Spatial Data Modelling for GIS 3D. Berlin, Springer, 2008. p.
RUEDA, A. J.; R. J. SEGURA, et al. Voxelization of solids using simplicial coverings. WSCG SHORT
Communication, Czech Republic, 2004. p.
SAMET, H. Applications of Spatial Data Structure: Computer Graphics,Image Processing and GIS
Addison-Wesley, 1990a. p. 0-201-50300-X
SAMET, H. The design and analysis of spatial data structures. Reading, Massachusetts, Addison-Wesley,
1990b. p. 0-201-50255-0
SHERIF, M. A. A.-K., HATEM Novel Robust Multilevel 3D Visualization Technique for Web Based GIS The
International Arab Journal of Information Technology, 2011, 8(1).
ZACHMANN, E. L. A. G. Geometric Data Structures for Computer Graphics. 2006. p.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 2, abril-junio, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial “Ediciones Futuro”
Universidad de las Ciencias Informáticas. La Habana, Cuba
13
ZHAO, N. and S. WEN. Based on the profile of complex three dimensional stratum modeling. Proceedings of
the Third International Symposium on Electronic Commerce and Security Workshops, Guangzhou, P. R.
China, 2010. p. 978-952-5726-11-4
