Universidad de la República
Oriental del Uruguay
Facultad de Ingeniería
Instituto de Computación
Junio, 2001
CONSTRUCCIÓN DE UN MODELO
TRIDIMENSIONAL A PARTIR DE CORTES SERIADOS
Descripción de algoritmos de
visualización 3D
Álvaro Martín
C.I. 1.884.198-9
Javier Preciozzi
C.I 1.893.683-1
Martín de los
Heros
C.I 3.109.468-8
1 Algoritmos Utilizados en VTK
|
E |
l siguiente documento es un resumen de las clases y transformaciones que brinda VTK para la creación y visualización en 3D, y está basado en el libro "The Visualization Toolkit". Si bien el libro fue una fuente importante de aprendizaje e introducción a VTK, al ser esta una biblioteca en continuo desarrollo, el mismo no contenía los últimos trabajos realizados[1]. Es por esto, que además del libro, se consultaron otras fuentes de información como son la ayuda en línea que brinda el sitio web de la biblioteca, así como también el foro de discusión del mismo sitio.
1.1 Elección de la técnica de visualización.
Las técnicas de visualización en 3D pueden ser clasificadas en dos grupos, de acuerdo a la forma en que se efectúa el rendering. Por un lado, ordenado de imagen (image-order) y ordenado por objeto (object-order).
Las técnicas de rendering que usan image-order, funcionan fijándose la incidencia de cada rayo de luz en los actores del modelo 3D, y recorriendo la escena a visualizar. Por cada rayo determina que es lo que hay que dibujar.
En object-order, por otro lado, funciona dibujando cada objeto por separado.
A su vez los modelos de Rendering pueden ser clasificados en dos tipos que son: rendering de superficie (surface rendering) y rendering de volumen (volume rendering).
La diferencia entre un modelo y otro es que en el caso del rendering de superficie se describe la superficie de los objetos y no el interior, o sea que el objeto queda representado solo por su superficie; mientras que para el rendering de volumen se describe todo el objeto incluyendo los puntos interiores.
La ventaja principal de usar una técnica de tipo surface rendering es la rapidez para generar y para interactuar con el objeto creado ya que solamente se necesitan crear los puntos en la superficie, mientras que en el volume rendering se deben dibujar todos los puntos del objeto.
La ventaja del volume rendering es que
tiene una mejor definición que el surface rendering, además que permite
representar el interior de los objetos.
Una de las funcionalidades principales del sistema construido es la posibilidad de que el usuario pueda interactuar con el objeto generado (rotarlo, trasladarlo, acercarlo o alejarlo, etc.). Por este motivo es que se optó por utilizar alguna técnica de surface rendering como forma de visualización principal, brindando la alternativa de utilizar volume rendering si el usuario lo cree pertinente.
1.1.1 Surface rendering
Existen varios algoritmos para generar
objetos 3D usando esta técnica, los cuales difieren básicamente en la forma en
que ellos establecen los límites del objeto. Para generar estos límites todos
ellos usan alguna forma de interpolación, siendo la más común la interpolación
lineal. El sistema construido cuenta con dos tipos de algoritmo: el Marching Cubes y
el Dividing Cubes.
1.1.2 Pipeline de creación del objeto 3D
VTK tiene una arquitectura de tipo pipeline, donde cada filtro, acción, o fuente de dato se concatena con el siguiente. De esta forma se define el "pipeline" para la creación de un objeto y en la última transformación se ejecuta todo el pipeline.
La definición del pipeline para la generación de los objetos 3D que fue seleccionado es el mostrado en la Figura 1.
La explicación de cada uno de estos filtros y su relación en el proyecto está debidamente documentada en el informe ejecutivo.
Aquí se dará una descripción más detallada del funcionamiento de los distintos algoritmos involucrados.
1.1.3 Análisis de los algoritmos utilizados
Dado un volumen representado por una matriz de vóxeles, para poder determinar el límite de un objeto a partir de cierto valor, se necesita recorrer todo el volumen, y comparar dicho valor con los valores numéricos que componen el mismo. Aquellos valores que sean menores al valor especificado, serán parte del objeto, mientras que los otros no.
A este valor se le denomina de Contour. Cabe destacar, que dado que los valores del volumen son escalares, y el valor del Contour no tiene porque serlo, es necesario realizar una interpolación para determinar que puntos pertenecen y cuales no. Esto requiere un procesamiento muy grande, por lo cual se diseñaron otros algoritmos para obtener las superficies.
1.1.1.1 Marching Cubes
Este algoritmo funciona tomando las distintas celdas que componen el objeto en forma independiente. Dado una celda de 3 dimensiones, que es el componente básico de los objetos 3D de VTK, y dado un valor de Contour, los vértices de dicha celda tienen un valor, que se compara contra el del Contour. Entonces, existe una combinación finita de vértices con valores menores al del Contour.
Para ver mas fácilmente el funcionamiento de esta clasificación, veamos el caso de dos dimensiones. Para este caso, se tendrían dieciséis posibles resultados, como se ilustra en la Figura 2:
Los puntos negros marcan los valores menores que el valor de Contour. Se ve entonces, que dado un valor de Contour, y una celda cualquiera, se puede determinar en cual de estos 16 casos se encuentra. Luego que se clasifica la celda en uno de los casos anteriores, se calcula la intersección real del valor del Contour con la misma, utilizando un interpolador.
El caso de tres dimensiones es análogo. La diferencia radica principalmente en que en vez de tener 16 posibilidades a la hora de clasificar una celda, se tienen 256. Se ha demostrado, que este conjunto puede reducirse a 15 casos. Para una explicación mas detallada ver [5].
El algoritmo de clasificación entonces comienza por crear la tabla de casos posibles, para clasificar cada una de las celdas. Luego, el algoritmo sigue de la siguiente manera:
1 - Se selecciona una celda.
2 - Se Calcula el estado de cada vértice de la celda ( es decir sí está dentro o fuera del valor del Contour)
3 - Se busca en la tabla de casos posibles, cual es el de esta celda.
5 - Calcula la intersección del lado de la celda con la línea de Contour mediante interpolación.
6 - Toma la siguiente celda.
Debido a que el algoritmo se aplica a cada celda, puede pasar que para los casos de borde, se generen vértices y lados duplicados. Estos se pueden eliminar luego, mediante la aplicación de algún filtro (Decimate, por ejemplo).
La clase que implementa este algoritmo es vtkMarchingCubes, que es una generalización de vtkContourFilter. VtkContourFilter implementa el algoritmo de Marching Cubes general, es decir, va creando la tabla de casos a medida que identifica de que tipo de objetos se trata. El caso de vtkMarchingCubes, está optimizado para usar Structured Points.
1.1.1.2 Dividing Cubes
A diferencia de Marching Cubes, que genera triángulos como primitivas, Dividing Cubes genera puntos (nube de puntos), lo cual lo hace más eficiente a la hora de hacer el rendering, ya que hacer render de puntos es mucho más eficiente que render de polígonos. Además existen otras operaciones que son más eficientes en puntos como por ejemplo, clipping o merging.
Una desventaja importante es que como la superficie es una nube de puntos sin conexión, hacer zoom revela “agujeros” dentro del objeto. Una solución es construir el conjunto conociendo el valor máximo del Zoom, de forma tal de generar puntos lo suficientemente cerca como para que no se noten los agujeros por más que realice el mismo.
El algoritmo funciona como sigue:
1 – Dado un valor de Contour, se selecciona una celda (Voxel) donde la superficie del Contour pase. Esto se determina si dentro del voxel hay puntos por encima y por debajo de la superficie.
2 - Una vez seleccionada el voxel, se subdivide en una grilla regular n1Xn2Xn3, donde los ni se determinan mediante la división entre el ancho del voxel original sobre la resolución de la pantalla.
3 - Se calculan los valores para los nuevos puntos con interpolación.
4 - Se chequea si el Contour pasa por cada subVoxel. Si pasa, se crea un punto en el medio del SubVoxel, y se computa la normal usando interpolación estándar. Estos puntos son los que van a formar parte de la nube de puntos que compondrán al objeto.
Este algoritmo se puede implementar dejando fijo la subdivisión de cada Voxel, o haciéndolo recursivo hasta que llegue a que el tamaño es menor a la resolución de la pantalla. La clase para trabajar con Dividing Cubes en VTK es vtkDividingCubes. Está especializada para trabajar con Structured Points.
1.1.1.3 Decimate
El objetivo principal de este algoritmo es reducir la cantidad de triángulos que forman un objeto, sin modificar la topología del mismo, e intentando realizar una buena aproximación de la geometría.
El algoritmo funciona recorriendo todos los puntos que componen la malla poligonal del objeto. Para cada punto, se realizan 3 operaciones sobre el mismo. Dichas operaciones son las siguientes:
1 – Clasificación del Punto
Existen 5 posibles clasificaciones para un punto, de acuerdo al entorno:
Punto Simple: es un punto que está rodeado de un ciclo completo de triángulos, y cada lado que usa dicho punto, pertenece exactamente a dos triángulos. A su vez un punto simple puede ser clasificado de la siguiente manera:
Punto de lado interno: si el ángulo entre las normales de dos triángulos adyacentes es mayor que un ángulo dado, existe entre ellos un "lado posible". El punto es de lado interno si dos lados posibles lo comparten. Si lo comparten uno tres o más lados posibles, decimos que el punto es:
Punto de Esquina.
Punto complejo: Es un punto que está rodeado de un ciclo completo de triángulos pero o bien existe un lado que no es usado por dos triángulos, o bien el punto es usado por un triangulo que no pertenece al ciclo de triángulos que lo rodea.
Punto límite: es aquel que está al borde del objeto, es decir, rodeado por un semicírculo de triángulos.
La Figura 3 ilustra cada una de las posibles clasificaciones.
Los puntos clasificados como Punto complejo y Punto de esquina, no se borran; todos los demás son candidatos posibles de ser borrados.
2 – Criterio de Decimate
Dado un punto posible de ser borrado, se estima el error resultante de borrar dicho punto y todos los triángulos asociados a él, y remplazarlos por una nueva triangulación.
Hay varias formas de calcular este error. Las más simples son distancias coplanares o colineares.
Para puntos simples, como no hay lados posibles, podemos suponer que los triángulos están muy cerca de ser un plano, y en este caso se utiliza un calculo del error basado en la distancia a dicho plano, se ilustra el concepto en la Figura 4.
Para los puntos límite o de lado interno, se calcula la distancia entre el punto candidato, y el nuevo lado formado tras el proceso de triangulación.
Un punto satisface el criterio de Decimate si la medida de distancia es menor o igual dicho criterio. Si esto sucede, el punto puede ser borrado, junto con todos los triángulos que lo usaban, dejando un hueco que es llenado con triangulación local.
3 – Triangulación
El hueco resultante de quitar el punto junto con los triángulos que conforma, es llenado triangulizando la región. Para obtener una mejor aproximación, se utiliza triangulación en tres dimensiones.