Técnicas de Representación y Modelado de Sólidos en Informática Gráfica

Técnicas de Representación y Modelado de Sólidos

Algunos Ejemplos

http://www.dariolanza.com/pegasoz102.html

Reynaldo Acevedo

http://www.dariolanza.com/u2.html

Índice

Introducción:
1. Requisitos de las técnicas de representación
2. Adquisición de objetos
Técnicas de representación de objetos:
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
Comparación entre representaciones

1. Introducción

Modelo

Modelo Geométrico

Iluminación

En informática gráfica necesitamos modelar los objetos que componen la escena a visualizar. La simulación de la interacción de la luz con ellos nos permitirá luego generar imágenes realistas.

1. Introducción

Necesitamos poder describir de alguna manera la forma y propiedades de los objetos que queremos representar.

Modelo: Representación de una entidad que nos interesa estudiar o visualizar, cuyas características básicas pueden describirse a través de su geometría y las propiedades del material del que está hecho.

Disponer de modelos:

Nos ayuda a comprender el comportamiento y estructura de los objetos, a realizar experimentos y a predecir y visualizar los efectos de modificaciones.
Puede sustituir a las técnicas tradicionales de construcción de prototipos.

Más adelante se estudiarán modelos de iluminación y sombreado que servirán para dar mayor realismo y vistosidad a las imágenes.

Introducción

Objetivos perseguidos al crear un modelo:

Permitir que se visualice y comprenda el comportamiento de la realidad que estamos representando (aplicable tanto a modelos para visualización o simulación).
Proporcionar un medio adecuado para realizar experimentos y predecir los efectos de determinadas modificaciones.

Problemas:

La realidad que se modela es muy compleja, y tenemos que recurrir a simplificaciones de la estructura o del comportamiento de la entidad modelada.
Cuanto más se asemeje el modelo a la realidad, mejores serán los resultados que podamos obtener (compromiso coste computacional-realismo del modelo).

Introducción

Información contenida en un modelo geométrico en informática gráfica:

Distribución espacial y forma de los componentes: la geometría en función de puntos, líneas, polígonos o volúmenes más complejos.
La conectividad o relación entre los componentes (es decir la estructura o topología del objeto).
Propiedades y características específicas para cada aplicación, así como todos los datos relevantes de los objetos (tanto para visualizar como para simular su comportamiento).
Otros (tipo de material, propiedades de reflexión/transmisión de luz del material, textura, valor de la normal en su superficie, etc.)

En muchos casos no necesitamos más que una descripción aproximada que permita generar imágenes de una calidad aceptable.

Introducción

Para cada técnica de representación, hay dos aspectos fundamentales a considerar:

Cómo está representado el sólido. Qué primitivas usamos en la representación. Tipo de representación (continua frente a discreta, superficial o de volumen, etc.)
Cómo almacenamos la información del modelo. Qué información se almacena.

Hace falta buscar un compromiso para decidir qué información se almacena para cada modelo.

Almacenar información redundante aumenta el tamaño del modelo.
Disponer de información adicional puede acelerar el proceso de análisis o representación, porque puede evitar la realización de cálculos en tiempo de ejecución.

Introducción

La creación y manipulación de un modelo necesita varias etapas:

Edición (creación y modificación) del modelo.
Almacenamiento.
Utilización para visualización o simulación del objeto.

Hay fuertes diferencias en las necesidades de estas etapas según el área de aplicación en el que trabajamos (CAD, animación, etc.)

En consecuencia, no existe una única técnica de representación que sea óptima para todos los casos.

1.1 Requisitos de las Técnicas de Representación

La capacidad de un modelo para representar y codificar objetos que parecen sólidos no significa que las representaciones obtenidas pertenezcan siempre a sólidos válidos.

Propiedades o requisitos que debe cumplir un esquema o modelo de representación de sólidos, o características que nos permiten comparar diferentes técnicas de representación:

Precisión: Indica el error de aproximar el objeto por su modelo.
Dominio: Conjunto de objetos que se pueden representar con el modelo.
Ausencia de ambigüedad: Si no existen ambigüedades, una representación debe corresponder a un sólido y sólo a uno.
Unicidad: Un objeto sólo se codifica de una única forma.

Requisitos de las Técnicas de Representación (2)

Validez: debe hacer imposible la creación de una representación inválida, que no corresponda a un sólido.
Cierre: Todas las operaciones sobre objetos deben ser cerradas, es decir aplicando una operación a objetos válidos debe dar como resultado otro objeto válido.
Compacidad: Capacidad de reducir el espacio de almacenamiento.
Eficiencia: Disponibilidad de algoritmos eficientes para calcular las propiedades físicas de los objetos y crear las imágenes.

El diseño de una técnica de representación que reúna todas estas propiedades es muy difícil.

Muchas de estas propiedades son contrapuestas. En muchas ocasiones hay que llegar a un compromiso.

Analizaremos a continuación estas propiedades o requisitos.

Ausencia de Ambigüedades

Algunas técnicas de representación pueden ser interpretadas de más de una manera:

Podemos suponer el origen de coordenadas en la cara posterior, en la esquina inferior izquierda (eje Z apuntando hacia el frente).
Podemos suponerlo también en la cara anterior, en la esquina inferior izquierda (eje Z apuntando hacia atrás).

Existen ambigüedades inherentes a las representaciones 2D.

Validez: Ejemplos de Objetos Imposibles

Validez

Muchas de las técnicas de representación pueden generar representaciones no válidas.

Evitar esta posibilidad suele resultar en un mayor grado de complejidad.

1.2. Adquisición de Modelos

Existen dos maneras principalmente para generar un modelo geométrico para un objeto concreto:

Edición manual utilizando un programa de modelado.
Adquisición de datos 3D a partir de un modelo similar o de una maqueta. Podemos emplear diferentes tipos de dispositivos:
- Digitalizadores 3D manuales (por contacto).
- Digitalizadores ópticos, sin contacto (fundamentalmente láser).

(Realmente existen otras formas, como los métodos procedurales, en los que usamos algoritmos para crear formas).

Diseño Asistido por Ordenador

Digitalizador Manual

El operador muestrea puntos de la superficie del objeto desplazando el extremo del digitalizador por su superficie.

Digitalizador Láser

Se basan en la emisión de luz estructurada (haz láser) y la adquisición de imágenes desde un punto de vista diferente. Por triangulación o tiempo de vuelo, el sistema puede calcular las coordenadas tridimensionales de los puntos de la superficie del objeto.

Escáner Láser

The Digital Michelangelo Project

David: 2 billones de polígonos

Detalle de la Malla

Datos Volumétricos

CT Scan 256x256x256

Ver video

CT Scan 256x256x110

Ver video

Datos Volumétricos

El Proyecto Humano Visible

Ver video

Imágenes de Satélite

Aplicaciones de Modelado

Índice

Introducción:
Técnicas de representación de objetos:
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
Comparación entre representaciones

Modelos de Alambre

La información que se tiene sobre el objeto es un conjunto de líneas, que representan las aristas que forman dicho objeto, por lo que nos permite representar el esqueleto de la estructura del objeto.

Es uno de los métodos más antiguos.

Aproximación mediante malla de alambre.

Representación superficial sombreada del mismo objeto.

Modelos de Alambre

Precisa sólo información sobre los vértices y las aristas.

En principio, no recoge información sobre las caras.

Para un cubo centrado en el origen, con aristas de longitud unidad, tenemos la siguiente información:

Vértices

Nº de vértice	x	y	z
1	0,5	0,5	0,5
2	0,5	-0,5	0,5
3	-0,5	-0,5	0,5
4	-0,5	0,5	0,5
5	0,5	0,5	-0,5
6	0,5	-0,5	-0,5
7	-0,5	-0,5	-0,5
8	-0,5	0,5	-0,5

Aristas

Nº de arista	Vértice inicial	Vértice final
1	1	2
2	2	3
3	3	4
4	4	1
5	5	6
6	6	7
7	7	8
8	8	5
9	1	5
10	2	6
11	3	7
12	4	8

Modelos de Alambre

Ventaja: sencillez, puede generar imágenes muy rápidamente (útiles para previsualizar objetos o animaciones).

Problemas:

Ambigüedad en la representación en pantalla.
No permite realizar operaciones booleanas.
Incapacidad de representar perfiles curvados si se usan sólo rectas y planos.
Incapacidad de detectar interferencias entre componentes.
Dificultades en el cálculo de las propiedades físicas de los objetos.
Incapacidad para aplicar métodos de iluminación y sombreado.

Opciones:

Presentar líneas ocultas (afecta a la facilidad de interpretación y a la información que ofrecemos).
A veces se utilizan este tipo de representaciones para resaltar que vemos un modelo por ordenador.
Las aristas no tienen por qué ser rectas (como en este caso, aunque se complica la representación).

Índice

Introducción:
Técnicas de representación de objetos:
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
Comparación entre representaciones

2.2 Generación de Sólidos por Primitivas

En la generación de sólidos por primitivas el sistema de modelado define un conjunto de formas sólidas básicas 3D (primitivas) que son relevantes para el área de aplicación.

Estas primitivas pueden particularizarse en función de una serie de parámetros o propiedades (nº caras de una pirámide, radio de una esfera, etc.)

Generación de Sólidos por Primitivas

Una primitiva parametrizada se puede considerar como la definición de una familia cuyos miembros varían en unos cuantos parámetros.

Este tipo de representación es útil para la generación de objetos complejos, sobre todo en CAD.

Índice

Introducción:
Técnicas de representación de objetos:
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
Comparación entre representaciones

2.3 Representaciones de Desplazamiento

Al desplazar un objeto a lo largo de una trayectoria por el espacio se barre una región que define un objeto nuevo.

El tipo de desplazamiento más sencillo es el definido por un área bidimensional constante desplazada a lo largo de una trayectoria normal al plano del área, para crear un volumen.

Este proceso se conoce con el nombre de desplazamiento o barrido (translacional o de rotación), o extrusión.

Representaciones de Desplazamiento

Los desplazamientos rotacionales se definen mediante la rotación de un área con respecto a un eje.

Representaciones de Desplazamiento

Los desplazamientos donde el área o el volumen que generan el objeto cambia de tamaño, forma u orientación y/o que siguen una trayectoria curva arbitraria se denominan barridos generales.

Son muy difíciles de modelar de una forma eficiente desde el punto de vista computacional y no siempre generan sólidos válidos.

A pesar de todos los problemas, los desplazamientos son una forma natural e intuitiva de construir diversos objetos (facilidad de edición).

Muchos sistemas de modelado de sólidos permiten a los usuarios construir objetos mediante desplazamientos, pero los almacenan con alguna otra forma de representación que analizaremos más adelante.

Representaciones de Desplazamiento

Las representaciones de desplazamiento mediante barridos generales se denominan también cilindros generalizados.

Índice

Introducción:
Técnicas de representación de objetos:
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
Comparación entre representaciones

2.4 Representaciones de Fronteras (B-Rep)

Describen un objeto en función de sus fronteras superficiales, es decir, de las caras y superficies que delimitan su superficie. Permiten distinguir el interior del exterior de los objetos.

Podríamos considerarlas como una extensión de los modelos de alambre (añadiendo caras, que son trozos de algún tipo de superficie y la información asociada a ellas).

Pueden incorporar caras planas o curvas (limitarnos a poliedros supone una pérdida de precisión).

Necesitamos definir sus vértices, aristas (que pueden ser rectas o curvas) y caras (planas o no).

Operar con ellas puede generar representaciones no válidas (por ejemplo, eliminar una cara de un poliedro, o retorcer la base y tapa de un cubo, lo que precisa añadir nuevas caras).

Representación de Fronteras

Representaciones superficiales: frecuentemente, limitadas a fronteras poligonales planas por eficiencia (por ej., determinar qué parte del espacio corresponde a dentro o fuera de una cara curva puede ser complejo. También son más rápidas de sombrear).

Restricciones adicionales que solemos ver para acelerar la visualización:

Polígonos convexos.
Triángulos (tiras/abanicos de triángulos: mayor eficiencia).

Para distinguir fuera y dentro, usamos la dirección de la normal.

Por convención, la normal apunta hacia el exterior del objeto.

Los vértices de la cara se enumeran siguiendo la regla del sacacorchos (la normal avanza como un sacacorchos que se gira siguiendo el orden de los vértices, que es antihorario si se mira desde el exterior).

Representación de Fronteras: Objetos no Válidos

Existen restricciones para estas representaciones:

Sólo se pueden emplear para superficies orientables.
Suelen soportar sólo representaciones 2-variedad (2-manifold). En ellas, cualquier punto está rodeado por una vecindad topológicamente equivalente a un disco (región en R2).

Cinta de Moebius (ejemplo de superficie no orientable).

Topología

Mallas triangulares:

Arista compartida por 2 facetas.
Faceta con 3 vecinos de arista.

2D-manifold con frontera:

Aristas frontera pertenecen a 1 sólo triángulo.

Mallas no Manifold

Arista compartida por más de 2 facetas.
Vértice conectando dos regiones de otra forma no conexas.
T-vértice.

Representación de Fronteras: Objetos no Válidos

Ejemplos de objetos no válidos:

Cinta de Moebius y botella de Klein (superficies no orientables).
Objetos que no son 2-variedades.

Representación de Fronteras

Vecindad topológicamente equivalente a un disco: podríamos deformarla y obtener un disco.

Representaciones volumétricas: mallas de tetraedros.

Representan la generalización a 3D (no son representaciones de fronteras; son representaciones volumétricas).

Vecindades topológicamente equivalentes o no a un disco.

Ejemplos de mallas de tetraedros.

Representación de Fronteras

Facilitan determinadas operaciones (cálculo de la envoltura convexa, cajas límites/volúmenes contenedores, etc.)

Envoltura convexa de un objeto 3D.

Jerarquía de volúmenes contenedores (esferas).

Representaciones de Fronteras: Poliedros

Son sólidos acotados por polígonos.

Poliedro simple: podemos deformarlo para obtener una esfera (tienen género 0; género: nº de cortes sobre curvas simples que no descomponen el objeto en trozos).

Cada arista conecta dos vértices y está compartida por dos caras.
A cada vértice llegan al menos tres aristas.
Las caras no pueden interpenetrarse.
Satisfacen la fórmula de Euler (V+C = A+2).

Representación de Fronteras

Las caras curvas muchas veces se aproximan por polígonos con la consiguiente pérdida de precisión y aumento de las necesidades de memoria para almacenar las estructuras de datos (pero ganamos muchas veces en eficiencia al sombrear).

Representación de Fronteras

Es la forma de representación más extendida para gráficos en tiempo real.

Aproximan superficies curvas con precisión dependiente de la resolución. Problema: elegir la densidad de facetas en zonas curvas.
Son sencillas de crear, aunque son difíciles de editar directamente.
Pueden servir de código máquina de otras representaciones.
Existen algoritmos de iluminación muy rápidos con resultados visualmente muy atractivos.
Pueden utilizar polígonos o triángulos (o tiras y abanicos de ellos).

Representación de Fronteras

Estructuras de datos basadas en grafos dirigidos que describen la topología.

La representación más simple es una lista de caras poligonales, cada una representada por una lista de coordenadas de vértices.

Normal:

Almacenamiento explícito.
Almacenamiento implícito.

Representación de Fronteras

Para evitar la duplicación de coordenadas cada vértice se representa con un índice sobre una lista de coordenadas.

Las caras se representan implícitamente con conjuntos de vértices adyacentes en las listas de vértices.

Tiras y abanicos (strips/fans): cadenas de triángulos que comparten vértices. Más eficientes: reutilizamos datos de vértices entre caras adyacentes.

Representación de Fronteras

Representación Arista con Alas (Winged-Edge) para Poliedros

Propuesta por Baumgart en el 75 dentro del marco de visión artificial; es una de las primeras.

Almacena información redundante para facilitar tareas de procesamiento o análisis posteriores.

Para cada arista guarda sus vértices inicial y final, las caras que divide y las aristas anterior y posterior en las caras que divide.

Requiere tablas de aristas, vértices y caras.

Veremos la representación para poliedros sin agujeros (para contemplar agujeros se pueden añadir aristas ficticias que unan los agujeros a las aristas de la cara).

Existen otros métodos de representación de poliedros.

Tabla de Aristas

En cada cara, las aristas se ordenan en sentido horario (visto desde fuera).

Suponemos que recorremos de X a Y.

Necesitamos dos tablas más; una para vértices y otra para caras.

Facilita muchas operaciones (adyacencias a vértices, caras y aristas, etc.)

Arista	Vértice inicial	Vértice final	Cara izq.	Cara dcha.	Cara izq: arista ant.	Cara izq: arista post	Cara dch: arista ant	Cara dch: arista post
a	X	Y	1	2	b	d	e	c

Ejemplo

Para el tetraedro de la figura:

Tabla de aristas:

Arista	Vértice inicial	Vértice final	Cara izq.	Cara dcha.	Cara izq: arista ant.	Cara izq: arista post	Cara dch: arista ant	Cara dch: arista post
a	A	D	3	1	e	f	b	c
b	A	B	1	4	c	a	f	d
c	B	D	1	2	a	b	d	e
d	B	C	2	4	e	c	b	f
e	C	D	2	3	c	d	f	a
f	A	C	4	3	d	b	a	e

Otras Tablas:

Necesitamos dos tablas más; una para vértices y otra para caras.

Facilita muchas operaciones (adyacencias a vértices, caras y aristas, etc.)

Tabla de vértices

Vértice	Arista incidente
A	a
B	b
C	d
D	e

Tabla de facetas

Cara	Arista incidente
1	a
2	c
3	a
4	b

Mallas de Polígonos. Modelos Multirresolución

Distancia o Tamaño

Modelo View-Dependent

Mallas Progresivas

Representaciones de fronteras no
poliédricas (parches bicúbicos…)
Aproximación de
superficies
mediante mallas
Podemos utilizar
mallas como
representación
de máquina en
gráficos
Aproximación de
superficies
mediante mallas
Los algoritmos de
sombreado
recuperan la
apariencia curva de
las superficies
Índice
1. Introducción:
2. Técnicas de representación de objetos
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
3. Comparación entre representaciones
2.5 Representación de partición
espacial
Las representaciones de partición espacial forman una familia
de métodos que se caracterizan por dividir el espacio en un
conjunto de celdas frecuentemente cúbicas, y estudiar cuales
están ocupadas y cuales vacías. A estas celdas se las llama
voxel (elementos de volumen)
Cuando se quiere dibujar un objeto se recorren las celdas y se
comprueba si ese objeto ocupa la celda o no, y en caso de
ocuparla si lo hace total o parcialmente.
En función de este grado de ocupación, y del método con el que
estemos trabajando las acciones a realizar son distintas.
Representación de partición espacial
Los métodos de ocupación espacial se diferencian en dos
puntos fundamentales:
Cómo dividir el espacio
Qué hacer cuando se detecta una celda parcialmente ocupada
Si se divide el espacio en celdas poliédricas los únicos objetos
que se pueden representar con precisión son aquellos con
superficies poliédricas (incluso de caras paralelas a los ejes).
La única forma de aumentar la exactitud del modelo es
incrementando la resolución, es decir, dividir el espacio en
celdas más pequeñas, aumentando el número de elementos de
volumen o voxels necesarios para describir la escena.
Representación de partición espacial
Son representaciones puramente tridimensionales.
Describimos el interior de los objetos (por enumeración, por ej.)
y no su superficie
Pueden ser empleados para generar imágenes mediante traza de
rayos
Son muy frecuentes en medicina y en visualización científica,
ya que en estos casos interesan representaciones volumétricas
del interior (tejidos, órganos, objetos, etc.)
Existen algoritmos para pasar de representaciones volumétricas
a otras basadas en fronteras (cuando están claras las fronteras de
los objetos representados)
Representación de partición espacial:
Enumeración de ocupación espacial
Se basan en descomponer la
escena en un número
prefijado de celdas
idénticas, dispuestas
sobre una malla regular
fija.
El tipo de celda más
común es el cubo
Representación de partición espacial: Enumeración
de ocupación espacial
Ventajas de la enumeración de celdas o voxels:
Para representar el modelo sólo es necesario comprobar para cada celda
si está ocupada o no.
Sólo en caso de estar ocupada se dibuja con el color del objeto
Un objeto se puede codificar con una lista única y no ambigua de celdas
ocupadas.
Es sencillo determinar si una celda está dentro o fuera del sólido, y
también si dos objetos son adyacentes.
Representación de partición espacial: Enumeración
de ocupación espacial
Problemas:
No existe el concepto de ocupación parcial, por lo tanto, los
sólidos con superficies curvas sólo pueden aproximarse.
Sólo se pueden representar con exactitud los objetos cuyas caras
son paralelas a los lados del cubo y cuyos vértices corresponden a
la malla.
Requiere una gran cantidad de memoria: necesita N3 celdas
ocupadas para representar un objeto con una resolución de N
elementos de volumen en cada una de las tres dimensiones
espaciales (orden N3)
Representación de partición espacial: árboles
de cuadrantes y árboles octales
Árboles de cuadrantes (quadtree):
Variante jerárquica de la
enumeración de ocupación
espacial, diseñada para optimizar
los requisitos de almacenamiento
de este método.
Un árbol de cuadrantes se forma
dividiendo sucesivamente un
plano bidimensional en ambas
direcciones (X, Y) para formar
regiones cuadradas
Representación de partición espacial: árboles
de cuadrantes y árboles octales
Cada cuadrante puede estar lleno, parcialmente lleno, o vacío
Un cuadrante parcialmente lleno se subdivide recursivamente en
subcuadrantes.
Este proceso de división continúa hasta que todos los cuadrantes sean
homogéneos o hasta alcanzar una profundidad límite previamente
determinada.
Cuando cuatro cuadrantes hermanos son homogéneos, se eliminan y su
padre se reemplaza por un nodo totalmente lleno o vacío.
Cualquier nodo parcialmente lleno en la profundidad límite se clasifica
como lleno, con lo que tampoco en este caso existe el concepto de
ocupación parcial.
Representación de partición espacial: árboles
de cuadrantes y árboles octales
Representación con árbol de
cuadrantes parcialmente llenos
en los nodos internos y llenos
o vacíos en la hojas
Relajando el criterio para
representar un nodo como
homogéneo, la representación
será más compacta aunque
menos precisa.
Representación de partición espacial: árboles
de cuadrantes y árboles octales
El árbol de octantes es similar
al de cuadrantes, pero en tres
dimensiones.
Descomposición espacial con
celdas de distintos tamaños,
pudiéndose realizar una gestión
más eficaz de la memoria.
El número de nodos en una
representación es proporcional
a la superficie del objeto.
Representación de partición espacial: árboles
k-d (k-d trees)Se pueden ver como una generalización de los árboles de
cuadrantes. k-d hace referencia a la dimensión del espacio
en el que trabajan (k-dim.)
Dividen recursivamente el espacio en pares de
subespacios, cada uno separado por un (hiper)plano de
posición arbitraria y orientación paralela a uno de los ejes
de coordenadas
La posición de cada plano de corte se elige en función de
algún criterio específico (por ejemplo, en una escena, dejar
igual número de vértices a cada lado del plano, para
detección de interferencias)
Son métodos de división del espacio más bien que técnicas
de representación de objetos
Árboles k-d: ejemplo para k=3
Primer nivel de división:
plano rojo. Corta la celda
(cubo blanco) en dos
Segundo nivel de división:
planos verdes (no tienen igual
posición)
Tercer nivel de división: azul
Acabamos teniendo 8 nodos
hojas
Representación de partición espacial: árboles
binarios de partición del espacio (BSP)
Dividen recursivamente el espacio en pares de subespacios, cada uno
separado por un plano de orientación y posición arbitrarias (no por planos
paralelos a los ejes, como en los casos anteriores).
Cada nodo interno del árbol BSP:
Está relacionado con un plano y tiene dos nodos hijos, uno para cada lado del
plano.
Almacena también los objetos contenidos íntegramente en el plano (puntos,
aristas y polígonos en 3D)
Suponiendo que las normales apunten hacia afuera del objeto, el hijo de la
izquierda está detrás o dentro del plano, mientras que el de la derecha se
encuentra delante o fuera del plano.
Si se divide aún más el semiespacio a un lado del plano, entonces su hijo es
la raíz de un subárbol; si por el contrario el semiespacio es homogéneo y no
tenemos que seguir dividiendo, el nodo es una hoja, y representa una región
que está completamente dentro o fuera del poliedro.
Estas regiones homogéneas se denominan celdas dentro y fuera.
Representación de partición espacial: árboles BSP
El concepto de subdivisión que sirve
de base a los árboles BSP es
independiente de la dimensión.
Sencillo y elegante.
Representación poco compacta.
Son útiles como métodos de
partición o división del espacio y
para representar figuras poliédricas
Utilizados para cálculos de
visibilidad (ej: 1ª versión de Doom)
Representación de partición espacial: árboles
BSP
Representación de partición espacial: árboles
BSP
Representación de partición espacial: árboles
BSP
Representación de partición espacial: árboles
BSP
Índice
1. Introducción:
2. Técnicas de representación de objetos
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
3. Comparación entre representaciones
2.6 Geometría sólida constructiva: CSG
Combinamos primitivas simples a través de operadores
booleanos.
Operaciones Booleanas con sólidos:
Combinan sólidos como conjuntos de puntos.
Pueden generar sólidos equivalentes de diferentes maneras (no
siempre hay una representación única).
Geometría sólida constructiva: CSG
Un objeto se almacena como
un árbol binario:
Los nodos internos almacenan
operadores booleanos o
geométricos.
Las hojas almacenan
primitivas simples.
Las aristas del árbol deben
estar ordenadas, ya que el
resultado de las operaciones
booleanas depende del
orden con el que se realizan
Geometría sólida constructiva: CSG
Gran capacidad de editar
modelos a través de la
eliminación, adición,
reemplazo y modificación de
subárboles.
Almacenamiento compacto.
Permite calcular con sencillez
las propiedades físicas de los
objetos
Resuelve con facilidad las
interacciones entre objetos.
Maneja de igual forma
superficies curvas y
poliédricas
Geometría sólida constructiva: CSG
Lento en la generación de
escenas complejas (traza de
rayos: adaptado a este tipo de
representación)
Forma natural e intuitiva para
el diseño de un gran conjunto
de objetos (orientado al
usuario)
Índice
1. Introducción:
2. Técnicas de representación de objetos
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
3. Comparación entre representaciones
2.7 Modelos basados en campos
escalares
En la naturaleza existen muchos objetos con apariencia
redondeada
En muchos casos, lo importante es la forma global y no las
dimensiones exactas
Es necesario facilitar la generación y edición de este tipo de
objetos
Mucha atención en la actualidad al modelado y edición de
objetos de forma libre (free-form). Los modelos basados en
campos escalares son un posible planteamiento, usado desde
hace algunos años
Modelos basados en campos escalares
Las primitivas de
modelado basadas en
campos escalares se
autodeforman en la
proximidad de otras,
dando lugar a
transiciones suaves y
permitiendo obtener
formas complejas
utilizando un numero
pequeño de dichas
primitivas.
Modelos basados en campos escalares
Un objeto 3D se modela
como una isosuperficie de
un campo escalar que es
generado por primitivas
puntuales.
El valor del campo creado
por una primitiva Pi vendrá
dado por una función de R3
en R de dicho punto.
V (x, y, z) f (x, y, z) i =
Modelos basados en campos escalares
Combinando primitivas se suma el campo generado por
cada una de ellas, y se pueden modelar formas complejas.
Definiendo un atributo (por ejemplo, color, rugosidad, etc.)
para cada primitiva (Ci) se puede calcular su valor en un
punto con una simple ponderación :
V(x y z) V (x y z) i
i
N
, , = , ,
=

1
( )
( )
C x y z ( )
V x y z
CV x y z i i
i
N
, ,
, ,
= , ,
=

1
1
Modelos basados en campos
escalares:
Blobby model, de J. Blinn
Posiblemente el primer método basado en campos escalares ampliamente usado
(luego aparecieron otros, como las metabolas)
Parámetros:
a: afecta a la rapidez de la caída exponencial del campo
b: limita el valor que puede alcanzar el campo, en cualquier punto.
g (x,y,z) es una función de la distancia del punto a la primitiva
(originalmente, r2). Determina la forma de la primitiva si está aislada.
Si el parámetro b es negativo la primitiva produciría una erosión sobre las
adyacentes.
El campo decae muy rápidamente con la distancia.
V (x y z) b ( a g (x y z)) i i i i , , = *exp ? , ,
Modelos basados en campos escalares
La suma de campos en el
espacio genera una
superficie deformada por la
atracción de una esfera
sobre la otra.
La interacción entre las
primitivas consigue
deformaciones locales, con
transiciones mucho más
suaves.
La aplicación de texturas
plantea problemas.
Modelos basados en campos escalares
Nos da problemas, por ejemplo, en animación (es difícil
relacionar el movimiento de las fuentes del campo con el del
objeto)
Es fácil detectar colisiones (podemos evaluar la función de
potencial en el punto; si es mayor que el umbral, está dentro)
Generación de imágenes: bien mediante traza de rayos, o
pasando a otras representaciones, como las basadas en volumen
o aproximando su frontera)
Índice
1. Introducción:
2. Técnicas de representación de objetos
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
3. Comparación entre representaciones
Otros tipos de representaciones
Existen multitud de representaciones, adaptadas a determinados
problemas. Podemos citar, por ejemplo:
Métodos basados en geometría fractal: son útiles para representar
elementos naturales, como montañas, terreno, árboles y plantas, etc.
Sistemas de partículas: son muy útiles para simular, representar y animar
fluidos y objetos similares (agua, humo, materiales granulares, etc.)
Modelos basados en física para modelizar materiales deformables (por
ejemplo, modelos masa-muelle, etc.)
Además de técnicas para representar objetos, existen también técnicas
para representar información (campos vectoriales o tensoriales, etc.)
No da tiempo material a verlos todos en la asignatura…
Índice
1. Introducción:
2. Técnicas de representación de objetos
1. Modelos de alambre
2. Generación mediante primitivas parametrizables
3. Representaciones de desplazamiento
4. Representaciones por fronteras. Modelos de mallas
5. Representaciones de partición espacial
6. Geometría constructiva de sólidos
7. Modelos basados en campos escalares
8. Otros tipos de representaciones
3. Comparación entre representaciones
3. Comparación de
representaciones
Precisión:
Los métodos de partición de espacio y representación poligonales
de fronteras sólo producen aproximaciones de un gran número de
objetos. La resolución necesaria para producir gráficos de alta
calidad puede ser demasiado elevada en algunos casos (se pueden
usar técnicas multirresolución).
Por lo tanto, los sistemas que permiten utilizar gráficos de alta
calidad pueden emplear CSG con primitivas no poliédricas y
representaciones de fronteras que permitan superficies curvas.
La generación por primitivas también puede crear imágenes de alta
calidad, pero no permite combinar dos objetos sencillos utilizando
operadores booleanos.
Por último, los campos escalares pueden generar imágenes de muy
alta calidad para cierto tipo de objetos, si bien dependen de una
selección adecuada de la función de campo.
9. Comparación de
representaciones
Dominio:
El dominio de los objetos que se pueden representar con la
generación por primitivas y los desplazamientos es muy limitado.
En cambio los métodos de partición espacial pueden representar
cualquier sólido, aunque muchas veces sólo como aproximaciones.
Si se ofrecen otros tipos de caras y aristas además de los polígonos
acotados por líneas rectas, es posible utilizar la representación de
fronteras para representar una gama muy amplia de objetos.
Los campos escalares (como blobby models o metaballs) pueden
representar también cualquier tipo de sólido si bien la dificultad de
modelarlo puede ser grande, y su aplicación se restringe a los
modelos físicos ya comentados.
9. Comparación de
representaciones
Unicidad:
Los únicos métodos que garantizan la unicidad son los basados en modelos
analíticos. Los basados en árboles de octantes y la enumeración de ocupación
espacial lo pueden ser, con reparos (problema: muestreo)
La generación por primitivas no garantiza la unicidad, pero se puede asegurar si se
elige con cuidado el conjunto de primitivas.
El resto de los métodos no garantizan esta propiedad.
Validez:
Las representaciones de fronteras son las más difíciles de validar.
Un árbol BSP representa un conjunto espacial válido, aunque no necesariamente
un sólido acotado.
Sólo hay que efectuar una sencilla revisión sintáctica local para validar un árbol
CSG o un árbol de octantes, y no se requiere ninguna verificación para la
enumeración de ocupación espacial.
En campos escalares, si se eligen correctamente las funciones que generan
campos de forma que sean continuas, no hay problemas de validez.
9. Comparación de
representaciones
Cerradura:
Los objetos creados con la generación por primitivas no son fáciles de
combinar y los desplazamientos simples no son cerrados, al aplicarse
operaciones booleanas de conjuntos. Por lo tanto, ninguno de estos dos
métodos se emplea como representación interna en sistemas de modelado.
Algunas representaciones de fronteras pueden presentar problemas de
cierre con operaciones booleanas.
Almacenamiento y eficiencia: Los métodos de representación se
clasifican en función de su capacidad para producir modelos
evaluados o no evaluados.
Los modelos no evaluados contienen información que debe procesarse
para efectuar operaciones básicas, como la determinación de la forma del
objeto.
En lo que respecta a la utilización de operaciones booleanas, la CSG crea
modelos no evaluados, ya que cada vez que se realizan cálculos hay que
recorrer el árbol y evaluar las expresiones.
9. Comparación de
representaciones
Como resumen se puede decir que no existe una
representación exacta y óptima que modele de forma
adecuada objetos sólidos en tres dimensiones.
Cada una tiene ciertas ventajas e inconvenientes, y cada
una es más adecuada para un tipo específico de
aplicaciones.
Algunos sistemas comerciales emplean varias de estas
representaciones simultáneamente, ya que algunas
operaciones concretas son más eficientes en unos modelos
que en otros.
9. Comparación de representaciones:
técnicas más utilizadas
1. Facetas poligonales
Mayor complejidad para caras curvas
Algoritmos de sombreado eficientes por hardware
2. Parches bicúbicos
Menos parches para igual precisión
Costosos de visualizar
3. Geometría constructiva de sólidos
Exacta para algunos casos (formados por objetos simples)
Intuitivos; fáciles de usar
9. Comparación de representaciones:
técnicas más utilizadas
4. Subdivisión espacial
Necesaria para objetos volumétricos o espacios 3D
Útiles en traza de rayos y para acelerar determinados
cálculos
5. Representaciones implícitas
Aplicable a pocos tipos de objetos
Incómoda para sombrear y dibujar
Útil para cajas contenedoras
Usado a veces en traza de rayos (típico: esferas en escenas)
Modelos basados en campos escalares
a: afecta a la caída exponencial
del campo
b: limita el valor que puede
alcanzar el campo, en cualquier
punto..
g (x,y,z) es el cuadrado de la
distancia del punto a la
primitiva y determina la forma
de la primitiva si está aislada.
Si el parámetro b es negativo la
primitiva produciría una erosión
sobre las adyacentes.
El campo decae muy
rápidamente con la distancia.
V (x y z) b ( a g (x y z)) i i i i , , = *exp ? , ,
Modelos basados en campos escalares
El campo tiene un alcance finito
(depende de la distancia al
cuadrado).
La caída del campo es más
suave. Por lo tanto, una
primitiva tendrá más influencia
en zonas más alejadas.
El valor del campo en algunos
puntos característicos:
V(0) = 1.
V(R) = 1
V(R/2) = ½
Modelos basados en campos escalares
Admite diferentes funciones
de campo.
Distintas funciones influyen
en las prestaciones del
modelo:
Tiempo de cómputo
Calidad del objeto
Proceso de modelado.